class Splaytree::Node

Attributes

duplicates[RW]
key[R]
left[RW]
parent[RW]
right[RW]
value[RW]

Public Class Methods

new(key, value = nil, parent = nil, left = nil, right = nil) click to toggle source
# File lib/splaytree/node.rb, line 8
def initialize(key, value = nil, parent = nil, left = nil, right = nil)
  @key = key
  @value = value
  @parent = parent
  @left = left
  @right = right
  @duplicates = []
end

Public Instance Methods

<=>(other) click to toggle source
# File lib/splaytree/node.rb, line 97
def <=>(other)
  return unless other
  key <=> other.key
end
add_duplicate!(value) click to toggle source
# File lib/splaytree/node.rb, line 17
def add_duplicate!(value)
  @duplicates.push(@value)
  @value = value
end
duplicates?() click to toggle source
# File lib/splaytree/node.rb, line 29
def duplicates?
  !@duplicates.empty?
end
gparent() click to toggle source
# File lib/splaytree/node.rb, line 41
def gparent
  parent && parent.parent
end
parent_root?() click to toggle source
# File lib/splaytree/node.rb, line 37
def parent_root?
  parent && parent.root?
end
remove_duplicate!() click to toggle source
# File lib/splaytree/node.rb, line 22
def remove_duplicate!
  return if @duplicates.empty?
  deleted = @value
  @value = @duplicates.pop
  deleted
end
root?() click to toggle source
# File lib/splaytree/node.rb, line 33
def root?
  parent.nil?
end
rotate() click to toggle source
# File lib/splaytree/node.rb, line 57
def rotate
  parent = self.parent
  gparent = self.gparent
  if gparent
    if parent.object_id == gparent.left.object_id
      gparent.set_left(self)
    else
      gparent.set_right(self)
    end
  else
    self.parent = nil
  end

  if object_id == parent.left.object_id
    parent.set_left(right)
    set_right(parent)
  else
    parent.set_right(left)
    set_left(parent)
  end
end
set_left(node) click to toggle source
# File lib/splaytree/node.rb, line 45
def set_left(node)
  @left = node
  return unless node
  node.parent = self
end
set_right(node) click to toggle source
# File lib/splaytree/node.rb, line 51
def set_right(node)
  @right = node
  return unless node
  node.parent = self
end
to_a() click to toggle source
# File lib/splaytree/node.rb, line 93
def to_a
  [key, value]
end
to_h() click to toggle source
# File lib/splaytree/node.rb, line 88
def to_h
  { key => value }
end
Also aliased as: to_hash
to_hash()
Alias for: to_h
to_s() click to toggle source
# File lib/splaytree/node.rb, line 84
def to_s
  key.to_s
end
zigzig?() click to toggle source
# File lib/splaytree/node.rb, line 79
def zigzig?
  (object_id == parent.left.object_id && parent.object_id == gparent.left.object_id) ||
    (object_id == parent.right.object_id && parent.object_id == gparent.right.object_id)
end