Class: Containers::RubyRBTreeMap

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/containers/rb_tree_map.rb

Overview

SOFTWARE.

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RubyRBTreeMap

Create and initialize a new empty TreeMap.



48
49
50
51
 
# File 'lib/containers/rb_tree_map.rb', line 48

def initialize
  @root = nil
  @height_black = 0
end

Instance Attribute Details

#height_black ⇒ Object

Returns the value of attribute height_black.



45
46
47
 
# File 'lib/containers/rb_tree_map.rb', line 45

def height_black
  @height_black
end

Instance Method Details

#delete(key) ⇒ Object

Deletes the item and key if it’s found, and returns the item. Returns nil if key is not present.

!!! Warning !!! There is a currently a bug in the delete method that occurs rarely but often enough, especially in large datasets. It is currently under investigation.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.min_key #=> "GA"



152
153
154
155
156
157
158
159
 
# File 'lib/containers/rb_tree_map.rb', line 152

def delete(key)
  result = nil
  if @root
    @root, result = delete_recursive(@root, key)
    @root.color = :black if @root
  end
  result
end

#delete_max ⇒ Object

Deletes the item with the smallest key and returns the item. Returns nil if key is not present.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.delete_max #=> "Georgia"
map.size #=> 1



195
196
197
198
199
200
201
202
 
# File 'lib/containers/rb_tree_map.rb', line 195

def delete_max
  result = nil
  if @root
    @root, result = delete_max_recursive(@root)
    @root.color = :black if @root
  end
  result
end

#delete_min ⇒ Object

Deletes the item with the smallest key and returns the item. Returns nil if key is not present.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.delete_min #=> "Massachusetts"
map.size #=> 1



176
177
178
179
180
181
182
183
 
# File 'lib/containers/rb_tree_map.rb', line 176

def delete_min
  result = nil
  if @root
    @root, result = delete_min_recursive(@root)
    @root.color = :black if @root
  end
  result
end

#each ⇒ Object

Iterates over the TreeMap from smallest to largest element. Iterative approach.



205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
 
# File 'lib/containers/rb_tree_map.rb', line 205

def each
  return nil unless @root
  stack = Containers::Stack.new
  cursor = @root
  loop do
    if cursor
      stack.push(cursor)
      cursor = cursor.left
    else
      unless stack.empty?
        cursor = stack.pop
        yield(cursor.key, cursor.value)
        cursor = cursor.right
      else
        break
      end
    end
  end
end

#empty? ⇒ Boolean

Returns true if the tree is empty, false otherwise

Returns:

  • (Boolean) 


162
163
164
 
# File 'lib/containers/rb_tree_map.rb', line 162

def empty?
  @root.nil?
end

#get(key) ⇒ Object Also known as: []

Return the item associated with the key, or nil if none found.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.get("GA") #=> "Georgia"



111
112
113
 
# File 'lib/containers/rb_tree_map.rb', line 111

def get(key)
  get_recursive(@root, key)
end

#has_key?(key) ⇒ Boolean

Return true if key is found in the TreeMap, false otherwise

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.has_key?("GA") #=> true
map.has_key?("DE") #=> false

Returns:

  • (Boolean) 


99
100
101
 
# File 'lib/containers/rb_tree_map.rb', line 99

def has_key?(key)
  !get(key).nil?
end

#height ⇒ Object

Return the height of the tree structure in the TreeMap.

Complexity: O(1)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.height #=> 2



86
87
88
 
# File 'lib/containers/rb_tree_map.rb', line 86

def height
  @root and @root.height or 0
end

#max_key ⇒ Object

Return the largest key in the map.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.max_key #=> "MA"



136
137
138
 
# File 'lib/containers/rb_tree_map.rb', line 136

def max_key
  @root.nil? ? nil : max_recursive(@root)
end

#min_key ⇒ Object

Return the smallest key in the map.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.min_key #=> "GA"



124
125
126
 
# File 'lib/containers/rb_tree_map.rb', line 124

def min_key
  @root.nil? ? nil : min_recursive(@root)
end

#push(key, value) ⇒ Object Also known as: []=

Insert an item with an associated key into the TreeMap, and returns the item inserted

Complexity: O(log n)

map = Containers::TreeMap.new map.push(“MA”, “Massachusetts”) #=> “Massachusetts” map.get(“MA”) #=> “Massachusetts”



60
61
62
63
64
65
 
# File 'lib/containers/rb_tree_map.rb', line 60

def push(key, value)
  @root = insert(@root, key, value)
  @height_black += 1 if isred(@root)
  @root.color = :black
  value
end

#size ⇒ Object

Return the number of items in the TreeMap.

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.size #=> 2



74
75
76
 
# File 'lib/containers/rb_tree_map.rb', line 74

def size
  @root and @root.size or 0
end