Class: TreeMap::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/treemap/tree_map.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(parent, key) ⇒ Node

Returns a new instance of Node.



44
45
46
47
48
49
50
51
 
# 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

Instance Attribute Details

#height ⇒ Object

Returns the value of attribute height.



42
43
44
 
# File 'lib/treemap/tree_map.rb', line 42

def height
  @height
end

#key ⇒ Object

Returns the value of attribute key.



42
43
44
 
# File 'lib/treemap/tree_map.rb', line 42

def key
  @key
end

#left ⇒ Object

Returns the value of attribute left.



42
43
44
 
# File 'lib/treemap/tree_map.rb', line 42

def left
  @left
end

#parent ⇒ Object

Returns the value of attribute parent.



42
43
44
 
# File 'lib/treemap/tree_map.rb', line 42

def parent
  @parent
end

#right ⇒ Object

Returns the value of attribute right.



42
43
44
 
# File 'lib/treemap/tree_map.rb', line 42

def right
  @right
end

#value ⇒ Object

Returns the value of attribute value.



42
43
44
 
# File 'lib/treemap/tree_map.rb', line 42

def value
  @value
end

Instance Method Details

#==(other) ⇒ Object Also known as: eql? 



72
73
74
75
76
77
78
 
# 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

#copy(parent) ⇒ Object 



53
54
55
56
57
58
59
60
61
62
63
64
 
# 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

#first ⇒ Object

Returns the first node in this subtree.



123
124
125
126
127
128
129
130
131
 
# 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 ⇒ Object 



82
83
84
 
# File 'lib/treemap/tree_map.rb', line 82

def hash
  (key.nil? ? 0 : key.hash) ^ (value.nil? ? 0 : value.hash)
end

#last ⇒ Object

Returns the last node in this subtree.



134
135
136
137
138
139
140
141
142
 
# 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 ⇒ Object

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



91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
# 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 ⇒ Object

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



107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
# 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) ⇒ Object 



66
67
68
69
70
 
# File 'lib/treemap/tree_map.rb', line 66

def set_value(new_value)
    old_value = @value
    @value = new_value
    old_value
end

#to_s ⇒ Object 



86
87
88
 
# File 'lib/treemap/tree_map.rb', line 86

def to_s
  "#{@key}=#{@value}"
end