Class: Puppet::Graph::RbTreeMap

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

Overview

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.

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RbTreeMap

Create and initialize a new empty TreeMap.



43
44
45
46
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 43

def initialize
  @root = nil
  @size = 0
end

Instance Attribute Details

#size ⇒ Object (readonly) Also known as: length

Returns the value of attribute size.



38
39
40
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 38

def size
  @size
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.

Complexity: O(log n)

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



123
124
125
126
127
128
129
130
131
132
133
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 123

def delete(key)
  result = nil
  if @root
    return unless has_key? key

    @root, result = delete_recursive(@root, key)
    @root.color = :black if @root
    @size -= 1
  end
  result
end

#delete_max ⇒ Object

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



170
171
172
173
174
175
176
177
178
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 170

def delete_max
  result = nil
  if @root
    @root, result = delete_max_recursive(@root)
    @root.color = :black if @root
    @size -= 1
  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



150
151
152
153
154
155
156
157
158
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 150

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

#each(&blk) ⇒ Object

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



181
182
183
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 181

def each(&blk)
  recursive_yield(@root, &blk)
end

#empty? ⇒ Boolean

Returns true if the tree is empty, false otherwise

Returns:

  • (Boolean) 


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

def empty?
  @root.nil?
end

#first ⇒ Object 



185
186
187
188
189
190
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 185

def first
  return nil unless @root

  node = min_recursive(@root)
  [node.key, node.value]
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"



83
84
85
86
87
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 83

def get(key)
  node = get_recursive(@root, key)
  node ? node.value : nil
  node.value if node
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) 


71
72
73
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 71

def has_key?(key)
  !get_recursive(@root, key).nil?
end

#last ⇒ Object 



192
193
194
195
196
197
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 192

def last
  return nil unless @root

  node = max_recursive(@root)
  [node.key, node.value]
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"



110
111
112
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 110

def max_key
  @root.nil? ? nil : max_recursive(@root).key
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"



98
99
100
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 98

def min_key
  @root.nil? ? nil : min_recursive(@root).key
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”



55
56
57
58
59
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 55

def push(key, value)
  @root = insert(@root, key, value)
  @root.color = :black
  value
end

#to_hash ⇒ Object 



199
200
201
 
# File 'lib/puppet/graph/rb_tree_map.rb', line 199

def to_hash
  @root ? @root.to_hash : {}
end