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

class SplayTree
  attr_accessor :root

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

  def [](key)
    find(key)
  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 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 isEmpty
    @root.nil?
  end

  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