class TreeMap::Node

Attributes

height[RW]
key[RW]
left[RW]
parent[RW]
right[RW]
value[RW]

Public Class Methods

new(parent, key) click to toggle source
# File lib/treemap/tree_map.rb, line 44
def initialize(parent, key)
  @parent = parent
  @left = nil
  @right = nil
  @key = key
  @value = nil
  @height = 1
end

Public Instance Methods

==(other) click to toggle source
# File lib/treemap/tree_map.rb, line 72
def ==(other)
  if other.is_a?(Node)
    @key == other.key && @value == other.value
  else
    false
  end
end
Also aliased as: eql?
copy(parent) click to toggle source
# File lib/treemap/tree_map.rb, line 53
def copy(parent)
  result = Node.new(@parent, @key)
  if @left
    result.left = @left.copy(result)
  end
  if @right
    result.right = @right.copy(result)
  end
  result.value = @value
  result.height = @height
  result
end
eql?(other)
Alias for: ==
first() click to toggle source

Returns the first node in this subtree.

# File lib/treemap/tree_map.rb, line 123
def first
  node = self
  child = node.left
  while child
    node = child
    child = node.left
  end
  node
end
hash() click to toggle source
# File lib/treemap/tree_map.rb, line 82
def hash
  (key.nil? ? 0 : key.hash) ^ (value.nil? ? 0 : value.hash)
end
last() click to toggle source

Returns the last node in this subtree.

# File lib/treemap/tree_map.rb, line 134
def last
  node = self
  child = node.right
  while child
    node = child
    child = node.right
  end
  node
end
next_node() click to toggle source

Returns the next node in an inorder traversal, or null if this is the last node in the tree.

# File lib/treemap/tree_map.rb, line 91
def next_node
  return @right.first if @right

  node = self
  parent = node.parent
  while parent
    if parent.left == node
      return parent
    end
    node = parent
    parent = node.parent
  end
  nil
end
prev_node() click to toggle source

Returns the previous node in an inorder traversal, or null if this is the first node in the tree.

# File lib/treemap/tree_map.rb, line 107
def prev_node
  return @left.last if @left

  node = self
  parent = node.parent
  while parent
    if parent.right == node
      return parent
    end
    node = parent
    parent = node.parent
  end
  nil
end
set_value(new_value) click to toggle source
# File lib/treemap/tree_map.rb, line 66
def set_value(new_value)
    old_value = @value
    @value = new_value
    old_value
end
to_s() click to toggle source
# File lib/treemap/tree_map.rb, line 86
def to_s
  "#{@key}=#{@value}"
end