# File lib/treap.rb, line 9
  def initialize(order=:ascending)
    @priority  = -1
    @order     = order
    @cmp       = order == :ascending ? 1 : -1
    @parent    = nil
    @right     = nil
    @left      = nil
    @key       = nil
    @value     = nil
  end

# File lib/treap.rb, line 204
  def [](key)
    node = get_node(key)
    node ? node.value : nil
  end

# File lib/treap.rb, line 200
  def []=(key,val)
    insert(key,val)
  end

# File lib/treap.rb, line 296
  def as_string(mult=1)
    indent = " " * mult
    return "#{indent}+\n" if empty?
    @right.as_string(mult + 2) +
      "#{indent}+-#{@key}\n"   +
      @left.as_string(mult + 2)
  end

# File lib/treap.rb, line 65
  def clear
    @left = @right = @key = @value = nil
    @priority = -1
  end

# File lib/treap.rb, line 256
  def copy_node(node)
    instance_variables.each do |v|
      next if v == "@parent"
      instance_variable_set(v,node.instance_variable_get(v))
    end  
  end

# File lib/treap.rb, line 210
  def delete(key)
    return nil unless node = get_node(key)
    node.delete_node
  end

# File lib/treap.rb, line 50
  def delete_node
    if leaf?
      node = self.dup
      @left = @right = @key = @value = nil
      @priority = -1
      node
    elsif @left.priority > @right.priority
      rotate_right
      @right.delete_node
    else
      rotate_left
      @left.delete_node
    end
  end

# File lib/treap.rb, line 161
  def each
    node = min_node
    while node
      yield node
      node = node.succ
    end
  end

# File lib/treap.rb, line 223
  def each_key
    each {|n| yield n.key}
  end

# File lib/treap.rb, line 231
  def each_pair
    each {|n| yield n.key, n.value}
  end

# File lib/treap.rb, line 170
  def each_rev
    node = max_node
    while node
      yield node
      node = node.pred
    end
  end

# File lib/treap.rb, line 227
  def each_value
    each {|n| yield n.value}
  end

# File lib/treap.rb, line 285
  def empty?
    @priority < 0
  end

# File lib/treap.rb, line 70
  def get_node(key)
    return self if @key == key
    return nil if empty?
    go_left?(key) ? @left.get_node(key) : @right.get_node(key)
  end

# File lib/treap.rb, line 250
  def go_left?(key)  ((@key <=> key) * @cmp) > 0 end

# File lib/treap.rb, line 251
  def go_right?(key) ((@key <=> key) * @cmp) < 0 end

# File lib/treap.rb, line 305
  def height(h=0)
    return 0 if empty?
    lh = @left.height(h+1)
    rh = @right.height(h+1)
    h = lh if lh > h
    h = rh if rh > h
    h
  end

# File lib/treap.rb, line 22
  def insert(key, data=nil, parent=nil, priority = nil)
    priority ||= rand
    if self.empty?
      @parent   = parent
      @priority = priority
      @key      = key
      @value    = data
      @left     = Treap.new(@order)
      @right    = Treap.new(@order)
      return self
    end  
    if    go_right?(key)
      @right.insert(key, data, self, priority)
      rotate_left if @right.priority > @priority
    elsif go_left?(key)
      @left.insert(key, data, self, priority)
      rotate_right if @left.priority > @priority
    else
      @value = data
    end
    self
  end

# File lib/treap.rb, line 187
  def join_tree(t2)
    if ((max_key <=> t2.min_key) * @cmp) >= 0
      warn "Tree1 must be less than Tree2"
      return
    end
    cat = Treap.new(@order)
    cat.left, cat.right = self, t2
    cat.delete_node
    return cat
  end

# File lib/treap.rb, line 215
  def keys
    nodes.map{|n| n.key}
  end

# File lib/treap.rb, line 289
  def leaf?
    @left.empty? && @right.empty?
  end

# File lib/treap.rb, line 253
  def left_or_me?(key)  ((@key <=> key) * @cmp) >= 0 end

# File lib/treap.rb, line 102
  def max_in_range(hi)
    case
      when @key == hi
        return self
      when go_left?(hi)
        return pred || self if @left.empty?
        return @left.max_in_range(hi)
      when go_right?(hi)
        return self if @right.empty?
        return @right.max_in_range(hi)
    end
  end

# File lib/treap.rb, line 244
  def max_key() max_node.key end

# File lib/treap.rb, line 124
  def max_node
    return nil if empty?
    node = self
    while !node.right.empty?
      node = node.right
    end
    node
  end

# File lib/treap.rb, line 245
  def max_val() max_node.value end

# File lib/treap.rb, line 89
  def min_in_range(lo)
    case
      when @key == lo
        return self
      when go_left?(lo)
        return self if @left.empty?
        return @left.min_in_range(lo)
      when go_right?(lo)
        return succ || self if @right.empty?
        return @right.min_in_range(lo)
    end
  end

# File lib/treap.rb, line 242
  def min_key() min_node.key end

# File lib/treap.rb, line 115
  def min_node
    return nil if empty?
    node = self
    while !node.left.empty?
      node = node.left
    end
    node
  end

# File lib/treap.rb, line 243
  def min_val() min_node.value end

# File lib/treap.rb, line 45
  def nodes
    return [] if empty?
    [@left.nodes, self, @right.nodes].flatten
  end

# File lib/treap.rb, line 147
  def pred
    if @left.empty?
      node = self
      y = @parent
      while y and node == y.left
        node = y
        y = node.parent
      end
      y
    else
      @left.max_node
    end
  end

# File lib/treap.rb, line 235
  def range_keys(lo=nil,hi=nil)
    range_nodes(lo,hi).map{|n|n.key}
  end

# File lib/treap.rb, line 76
  def range_nodes(lo=nil, hi=nil)
    lo_node = lo ? min_in_range(lo) : min_node
    hi_node = hi ? max_in_range(hi) : max_node
    ret = []
    return ret if lo_node.go_left?(hi_node.key)
    while lo_node != hi_node
      ret.push lo_node
      lo_node = lo_node.succ
    end
    ret << lo_node
  end

# File lib/treap.rb, line 238
  def range_values(lo=nil,hi=nil)
    range_nodes(lo,hi).map{|n|n.value}
  end

# File lib/treap.rb, line 254
  def right_or_me?(key) ((@key <=> key) * @cmp) <= 0 end

# File lib/treap.rb, line 263
  def rotate_left
    t = self.dup
    self.copy_node(@right)
    self.right.parent = self
    t.parent = self
    t.right = self.left
    t.right.parent = t
    t.left.parent  = t
    self.left = t
  end

# File lib/treap.rb, line 274
  def rotate_right
    t = self.dup
    self.copy_node(@left)
    self.left.parent = self
    t.parent = self
    t.left = self.right
    t.right.parent = t
    t.left.parent  = t
    self.right = t
  end

# File lib/treap.rb, line 179
  def split_tree(key)
    delete(key)
    insert(key,nil,nil,100)
    t1, t2 = self.left, self.right
    self.delete(key)
    [t1, t2]
  end

# File lib/treap.rb, line 133
  def succ
    if @right.empty?
      node = self
      y = @parent
      while y and node == y.right
        node = y
        y = y.parent
      end
      y
    else
      @right.min_node
    end
  end

# File lib/treap.rb, line 219
  def values
    nodes.map{|n| n.value}
  end