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
Public Class Methods
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
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
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
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
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
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
# 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
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
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
# 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
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
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
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
# File lib/puppet/graph/rb_tree_map.rb 194 def to_hash 195 @root ? @root.to_hash : {} 196 end
Private Instance Methods
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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