class SplayNode
  attr_accessor :key, :val, :left, :right
  def initialize(key, val)
    @key = key
    @val = val
  end

  def to_s(depth=0, values=[])
    values << "#{Array.new(depth, ' ')}#{key}, #{val}"
    values << ":" if left or right
    values << "\n"
    left.to_s(depth+1, values) if left
    right.to_s(depth+1, values) if right
    values.join
  end
end

class SplayTree
  attr_accessor :root

  def header
    @header ||= SplayNode.new(nil, nil)
  end

  def to_s
    @root.to_s
  end

  def [](key)
    if key.is_a? Range
      range(key)
    else
      find(key)
    end
  end

  def []=(key, val)
    insert(key, val)
  end

  def insert(key, val)
    unless @root
      @root = SplayNode.new(key, val)
      return
    end
    
    splay(key)
    
    if @root.key == key
      @root.val = val
      return
    end

    n = SplayNode.new(key, val)
    if key < @root.key
	    n.left = @root.left
	    n.right = @root
	    @root.left = nil
    else
      n.right = @root.right
      n.left = @root
      @root.right = nil
    end
    @root = n
  end
      
  def remove(key)
    splay(key)

    if key != @root.key
      raise "#{key} not found in tree"
    end

    unless @root.left 
      @root = @root.right
    else 
	    x = @root.right
	    @root = @root.left
	    splay(key)
	    @root.right = x
    end
  end

  def min_key
    key, _ = findMin
    key
  end

  def min_val
    _, val = findMin
    val
  end

  def max_key
    key, _ = findMax
    key
  end

  def max_val
    _, val = findMax
    val
  end

  def findMin
    return unless @root
    x = @root
    x = x.left while(x.left) 
    splay(x.key)
    return [x.key, x.val]
  end

  def findMax
    return unless @root
    x = @root
    x = x.right while(x.right) 
    splay(x.key)
    return [x.key, x.val]
  end

  def find(key)
    return unless @root
    splay(key)
    return unless @root.key == key
    return @root.val
  end

  def range(r)
    values = []
    splay(r.first)
    candidates = [@root]
    while n = candidates.pop
      if r.include? n.key
        values << [n.key, n.val]
        # look left and right
        candidates << n.left if n.left
        candidates << n.right if n.right
      elsif n.key < r.first
        # look only left
        candidates << n.right if n.right
      else
        # look only right
        candidates << n.left if n.left
      end
    end
    values.sort_by {|k, v| k}
  end

  def isEmpty
    @root.nil?
  end


  protected
  def splay(key)
    l = r = header
    t = @root
    header.left = header.right = nil
    while true
      if key < t.key
        break unless t.left
        if key < t.left.key
          y = t.left
          t.left = y.right
          y.right = t
          t = y
          break unless t.left
        end
        r.left = t
        r = t
        t = t.left
      elsif key > t.key
        break unless t.right
        if key > t.right.key
          y = t.right
          t.right = y.left
          y.left = t
          t = y
          break unless t.right
        end
        l.right = t
        l = t
        t = t.right
      else
        break
	    end
    end
    l.right = t.left
    r.left = t.right
    t.left = header.right
    t.right = header.left
    @root = t
  end

end