class Puppet::Graph::RbTreeMap

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
42 def initialize
43   @root = nil
44   @size = 0
45 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
122 def delete(key)
123   result = nil
124   if @root
125     return unless has_key? key
126     @root, result = delete_recursive(@root, key)
127     @root.color = :black if @root
128     @size -= 1
129   end
130   result
131 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
168 def delete_max
169   result = nil
170   if @root
171     @root, result = delete_max_recursive(@root)
172     @root.color = :black if @root
173     @size -= 1
174   end
175   result
176 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
148 def delete_min
149   result = nil
150   if @root
151     @root, result = delete_min_recursive(@root)
152     @root.color = :black if @root
153     @size -= 1
154   end
155   result
156 end

each(&blk) click to toggle source

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

    # File lib/puppet/graph/rb_tree_map.rb
179 def each(&blk)
180   recursive_yield(@root, &blk)
181 end

empty?() click to toggle source

Returns true if the tree is empty, false otherwise

    # File lib/puppet/graph/rb_tree_map.rb
134 def empty?
135   @root.nil?
136 end

first() click to toggle source

    # File lib/puppet/graph/rb_tree_map.rb
183 def first
184   return nil unless @root
185   node = min_recursive(@root)
186   [node.key, node.value]
187 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
82 def get(key)
83   node = get_recursive(@root, key)
84   node ? node.value : nil
85   node.value if node
86 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
70 def has_key?(key)
71   !get_recursive(@root, key).nil?
72 end

last() click to toggle source

    # File lib/puppet/graph/rb_tree_map.rb
189 def last
190   return nil unless @root
191   node = max_recursive(@root)
192   [node.key, node.value]
193 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
109 def max_key
110   @root.nil? ? nil : max_recursive(@root).key
111 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
97 def min_key
98   @root.nil? ? nil : min_recursive(@root).key
99 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
54 def push(key, value)
55   @root = insert(@root, key, value)
56   @root.color = :black
57   value
58 end

Also aliased as: []=

to_hash() click to toggle source

    # File lib/puppet/graph/rb_tree_map.rb
195 def to_hash
196   @root ? @root.to_hash : {}
197 end

Private Instance Methods

delete_max_recursive(node) click to toggle source

    # File lib/puppet/graph/rb_tree_map.rb
332 def delete_max_recursive(node)
333   if (isred(node.left))
334     node = node.rotate_right
335   end
336   return nil, node.value if node.right.nil?
337   if ( !isred(node.right) && !isred(node.right.left) )
338     node.move_red_right
339   end
340   node.right, result = delete_max_recursive(node.right)
341 
342   return node.fixup, result
343 end

delete_min_recursive(node) click to toggle source

    # File lib/puppet/graph/rb_tree_map.rb
320 def delete_min_recursive(node)
321   if node.left.nil?
322     return nil, node.value
323   end
324   if ( !isred(node.left) && !isred(node.left.left) )
325     node.move_red_left
326   end
327   node.left, result = delete_min_recursive(node.left)
328 
329   return node.fixup, result
330 end

delete_recursive(node, key) click to toggle source

    # File lib/puppet/graph/rb_tree_map.rb
295 def delete_recursive(node, key)
296   if (key <=> node.key) == -1
297     node.move_red_left if ( !isred(node.left) && !isred(node.left.left) )
298     node.left, result = delete_recursive(node.left, key)
299   else
300     node.rotate_right if isred(node.left)
301     if ( ( (key <=> node.key) == 0) && node.right.nil? )
302       return nil, node.value
303     end
304     if ( !isred(node.right) && !isred(node.right.left) )
305       node.move_red_right
306     end
307     if (key <=> node.key) == 0
308       result = node.value
309       min_child = min_recursive(node.right)
310       node.value = min_child.value
311       node.key = min_child.key
312       node.right = delete_min_recursive(node.right).first
313     else
314       node.right, result = delete_recursive(node.right, key)
315     end
316   end
317   return node.fixup, result
318 end

get_recursive(node, key) click to toggle source

    # File lib/puppet/graph/rb_tree_map.rb
345 def get_recursive(node, key)
346   return nil if node.nil?
347   case key <=> node.key
348   when  0 then return node
349   when -1 then return get_recursive(node.left, key)
350   when  1 then return get_recursive(node.right, key)
351   end
352 end

insert(node, key, value) click to toggle source

    # File lib/puppet/graph/rb_tree_map.rb
366 def insert(node, key, value)
367   unless node
368     @size += 1
369     return Node.new(key, value)
370   end
371 
372   case key <=> node.key
373   when  0 then node.value = value
374   when -1 then node.left = insert(node.left, key, value)
375   when  1 then node.right = insert(node.right, key, value)
376   end
377 
378   node.rotate_left if (node.right && node.right.red?)
379   node.rotate_right if (node.left && node.left.red? && node.left.left && node.left.left.red?)
380   node.colorflip if (node.left && node.left.red? && node.right && node.right.red?)
381   node
382 end

isred(node) click to toggle source

    # File lib/puppet/graph/rb_tree_map.rb
384 def isred(node)
385   return false if node.nil?
386 
387   node.color == :red
388 end

max_recursive(node) click to toggle source

    # File lib/puppet/graph/rb_tree_map.rb
360 def max_recursive(node)
361   return node if node.right.nil?
362 
363   max_recursive(node.right)
364 end

min_recursive(node) click to toggle source

    # File lib/puppet/graph/rb_tree_map.rb
354 def min_recursive(node)
355   return node if node.left.nil?
356 
357   min_recursive(node.left)
358 end

recursive_yield(node) { |key, value| ... } click to toggle source

    # File lib/puppet/graph/rb_tree_map.rb
288 def recursive_yield(node, &blk)
289   return unless node
290   recursive_yield(node.left, &blk)
291   yield node.key, node.value
292   recursive_yield(node.right, &blk)
293 end