class Puppet::Graph::RbTreeMap

Algorithms and Containers project is Copyright © 2009 Kanwei Li

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the 'Software'), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

A RbTreeMap is a map that is stored in sorted order based on the order of its keys. This ordering is determined by applying the function <=> to compare the keys. No duplicate values for keys are allowed, so duplicate values are overwritten.

A major advantage of RBTreeMap over a Hash is the fact that keys are stored in order and can thus be iterated over in order. This is useful for many datasets.

The implementation is adapted from Robert Sedgewick's Left Leaning Red-Black Tree implementation, which can be found at www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java

Most methods have O(log n) complexity.

Attributes

length[R]
size[R]

Public Class Methods

new() click to toggle source

Create and initialize a new empty TreeMap.

   # File lib/puppet/graph/rb_tree_map.rb
41 def initialize
42   @root = nil
43   @size = 0
44 end

Public Instance Methods

[](key)
Alias for: get
[]=(key, value)
Alias for: push
delete(key) click to toggle source

Deletes the item and key if it's found, 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("MA") #=> "Massachusetts"
    # File lib/puppet/graph/rb_tree_map.rb
121 def delete(key)
122   result = nil
123   if @root
124     return unless has_key? key
125     @root, result = delete_recursive(@root, key)
126     @root.color = :black if @root
127     @size -= 1
128   end
129   result
130 end
delete_max() click to toggle source

Deletes the item with the largest 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
    # File lib/puppet/graph/rb_tree_map.rb
167 def delete_max
168   result = nil
169   if @root
170     @root, result = delete_max_recursive(@root)
171     @root.color = :black if @root
172     @size -= 1
173   end
174   result
175 end
delete_min() click to toggle source

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
    # File lib/puppet/graph/rb_tree_map.rb
147 def delete_min
148   result = nil
149   if @root
150     @root, result = delete_min_recursive(@root)
151     @root.color = :black if @root
152     @size -= 1
153   end
154   result
155 end
each(&blk) click to toggle source

Yields [key, value] pairs in order by key.

    # File lib/puppet/graph/rb_tree_map.rb
178 def each(&blk)
179   recursive_yield(@root, &blk)
180 end
empty?() click to toggle source

Returns true if the tree is empty, false otherwise

    # File lib/puppet/graph/rb_tree_map.rb
133 def empty?
134   @root.nil?
135 end
first() click to toggle source
    # File lib/puppet/graph/rb_tree_map.rb
182 def first
183   return nil unless @root
184   node = min_recursive(@root)
185   [node.key, node.value]
186 end
get(key) click to toggle source

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"
   # File lib/puppet/graph/rb_tree_map.rb
81 def get(key)
82   node = get_recursive(@root, key)
83   node ? node.value : nil
84   node.value if node
85 end
Also aliased as: []
has_key?(key) click to toggle source

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
   # File lib/puppet/graph/rb_tree_map.rb
69 def has_key?(key)
70   !get_recursive(@root, key).nil?
71 end
last() click to toggle source
    # File lib/puppet/graph/rb_tree_map.rb
188 def last
189   return nil unless @root
190   node = max_recursive(@root)
191   [node.key, node.value]
192 end
max_key() click to toggle source

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"
    # File lib/puppet/graph/rb_tree_map.rb
108 def max_key
109   @root.nil? ? nil : max_recursive(@root).key
110 end
min_key() click to toggle source

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"
   # File lib/puppet/graph/rb_tree_map.rb
96 def min_key
97   @root.nil? ? nil : min_recursive(@root).key
98 end
push(key, value) click to toggle source

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”

   # File lib/puppet/graph/rb_tree_map.rb
53 def push(key, value)
54   @root = insert(@root, key, value)
55   @root.color = :black
56   value
57 end
Also aliased as: []=
to_hash() click to toggle source
    # File lib/puppet/graph/rb_tree_map.rb
194 def to_hash
195   @root ? @root.to_hash : {}
196 end

Private Instance Methods

delete_max_recursive(node) click to toggle source
    # File lib/puppet/graph/rb_tree_map.rb
331 def delete_max_recursive(node)
332   if (isred(node.left))
333     node = node.rotate_right
334   end
335   return nil, node.value if node.right.nil?
336   if ( !isred(node.right) && !isred(node.right.left) )
337     node.move_red_right
338   end
339   node.right, result = delete_max_recursive(node.right)
340 
341   return node.fixup, result
342 end
delete_min_recursive(node) click to toggle source
    # File lib/puppet/graph/rb_tree_map.rb
319 def delete_min_recursive(node)
320   if node.left.nil?
321     return nil, node.value
322   end
323   if ( !isred(node.left) && !isred(node.left.left) )
324     node.move_red_left
325   end
326   node.left, result = delete_min_recursive(node.left)
327 
328   return node.fixup, result
329 end
delete_recursive(node, key) click to toggle source
    # File lib/puppet/graph/rb_tree_map.rb
294 def delete_recursive(node, key)
295   if (key <=> node.key) == -1
296     node.move_red_left if ( !isred(node.left) && !isred(node.left.left) )
297     node.left, result = delete_recursive(node.left, key)
298   else
299     node.rotate_right if isred(node.left)
300     if ( ( (key <=> node.key) == 0) && node.right.nil? )
301       return nil, node.value
302     end
303     if ( !isred(node.right) && !isred(node.right.left) )
304       node.move_red_right
305     end
306     if (key <=> node.key) == 0
307       result = node.value
308       min_child = min_recursive(node.right)
309       node.value = min_child.value
310       node.key = min_child.key
311       node.right = delete_min_recursive(node.right).first
312     else
313       node.right, result = delete_recursive(node.right, key)
314     end
315   end
316   return node.fixup, result
317 end
get_recursive(node, key) click to toggle source
    # File lib/puppet/graph/rb_tree_map.rb
344 def get_recursive(node, key)
345   return nil if node.nil?
346   case key <=> node.key
347   when  0 then return node
348   when -1 then return get_recursive(node.left, key)
349   when  1 then return get_recursive(node.right, key)
350   end
351 end
insert(node, key, value) click to toggle source
    # File lib/puppet/graph/rb_tree_map.rb
365 def insert(node, key, value)
366   unless node
367     @size += 1
368     return Node.new(key, value)
369   end
370 
371   case key <=> node.key
372   when  0 then node.value = value
373   when -1 then node.left = insert(node.left, key, value)
374   when  1 then node.right = insert(node.right, key, value)
375   end
376 
377   node.rotate_left if (node.right && node.right.red?)
378   node.rotate_right if (node.left && node.left.red? && node.left.left && node.left.left.red?)
379   node.colorflip if (node.left && node.left.red? && node.right && node.right.red?)
380   node
381 end
isred(node) click to toggle source
    # File lib/puppet/graph/rb_tree_map.rb
383 def isred(node)
384   return false if node.nil?
385 
386   node.color == :red
387 end
max_recursive(node) click to toggle source
    # File lib/puppet/graph/rb_tree_map.rb
359 def max_recursive(node)
360   return node if node.right.nil?
361 
362   max_recursive(node.right)
363 end
min_recursive(node) click to toggle source
    # File lib/puppet/graph/rb_tree_map.rb
353 def min_recursive(node)
354   return node if node.left.nil?
355 
356   min_recursive(node.left)
357 end
recursive_yield(node) { |key, value| ... } click to toggle source
    # File lib/puppet/graph/rb_tree_map.rb
287 def recursive_yield(node, &blk)
288   return unless node
289   recursive_yield(node.left, &blk)
290   yield node.key, node.value
291   recursive_yield(node.right, &blk)
292 end