Class: Containers::RubySplayTreeMap
- Inherits:
-
Object
- Object
- Containers::RubySplayTreeMap
- Includes:
- Enumerable
- Defined in:
- lib/containers/splay_tree_map.rb
Overview
SOFTWARE.
Defined Under Namespace
Classes: Node
Instance Method Summary collapse
-
#clear ⇒ Object
Remove all elements from the SplayTreeMap.
-
#delete(key) ⇒ Object
Deletes the item and key if it’s found, and returns the item.
-
#each ⇒ Object
Iterates over the SplayTreeMap in ascending order.
-
#get(key) ⇒ Object
(also: #[])
Return the item associated with the key, or nil if none found.
-
#has_key?(key) ⇒ Boolean
Return true if key is found in the SplayTreeMap, false otherwise.
-
#height ⇒ Object
Return the height of the tree structure in the SplayTreeMap.
-
#initialize ⇒ RubySplayTreeMap
constructor
Create and initialize a new empty SplayTreeMap.
-
#max ⇒ Object
Return the largest [key, value] pair in the SplayTreeMap, or nil if the tree is empty.
-
#min ⇒ Object
Return the smallest [key, value] pair in the SplayTreeMap, or nil if the tree is empty.
-
#push(key, value) ⇒ Object
(also: #[]=)
Insert an item with an associated key into the SplayTreeMap, and returns the item inserted.
-
#size ⇒ Object
Return the number of items in the SplayTreeMap.
Constructor Details
permalink #initialize ⇒ RubySplayTreeMap
Create and initialize a new empty SplayTreeMap.
43 44 45 46 |
# File 'lib/containers/splay_tree_map.rb', line 43 def initialize @size = 0 clear end |
Instance Method Details
permalink #clear ⇒ Object
Remove all elements from the SplayTreeMap
Complexity: O(1)
98 99 100 101 102 |
# File 'lib/containers/splay_tree_map.rb', line 98 def clear @root = nil @size = 0 @header = Node.new(nil, nil, nil, nil) end |
permalink #delete(key) ⇒ Object
Deletes the item and key if it’s found, and returns the item. Returns nil if key is not present.
Complexity: amortized O(log n)
map = Containers::SplayTreeMap.new
map["MA"] = "Massachusetts"
map["GA"] = "Georgia"
map.delete("GA") #=> "Georgia"
map.delete("DE") #=> nil
191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 |
# File 'lib/containers/splay_tree_map.rb', line 191 def delete(key) return nil if @root.nil? deleted = nil splay(key) if (key <=> @root.key) == 0 # The key exists deleted = @root.value if @root.left.nil? @root = @root.right else x = @root.right @root = @root.left splay(key) @root.right = x end end deleted end |
permalink #each ⇒ Object
Iterates over the SplayTreeMap in ascending order. Uses an iterative, not recursive, approach.
210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 |
# File 'lib/containers/splay_tree_map.rb', line 210 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 |
permalink #get(key) ⇒ Object Also known as: []
Return the item associated with the key, or nil if none found.
Complexity: amortized O(log n)
map = Containers::SplayTreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.get("GA") #=> "Georgia"
137 138 139 140 141 142 |
# File 'lib/containers/splay_tree_map.rb', line 137 def get(key) return nil if @root.nil? splay(key) (@root.key <=> key) == 0 ? @root.value : nil end |
permalink #has_key?(key) ⇒ Boolean
Return true if key is found in the SplayTreeMap, false otherwise.
Complexity: amortized O(log n)
map = Containers::SplayTreeMap.new
map["MA"] = "Massachusetts"
map["GA"] = "Georgia"
map.has_key?("GA") #=> true
map.has_key?("DE") #=> false
125 126 127 |
# File 'lib/containers/splay_tree_map.rb', line 125 def has_key?(key) !get(key).nil? end |
permalink #height ⇒ Object
Return the height of the tree structure in the SplayTreeMap.
Complexity: O(log n)
map = Containers::SplayTreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.height #=> 2
112 113 114 |
# File 'lib/containers/splay_tree_map.rb', line 112 def height height_recursive(@root) end |
permalink #max ⇒ Object
Return the largest [key, value] pair in the SplayTreeMap, or nil if the tree is empty.
Complexity: amortized O(log n)
map = Containers::SplayTreeMap.new
map["MA"] = "Massachusetts"
map["GA"] = "Georgia"
map.max #=> ["MA", "Massachusetts"]
171 172 173 174 175 176 177 178 179 |
# File 'lib/containers/splay_tree_map.rb', line 171 def max return nil if @root.nil? n = @root while n.right n = n.right end splay(n.key) return [n.key, n.value] end |
permalink #min ⇒ Object
Return the smallest [key, value] pair in the SplayTreeMap, or nil if the tree is empty.
Complexity: amortized O(log n)
map = Containers::SplayTreeMap.new
map["MA"] = "Massachusetts"
map["GA"] = "Georgia"
map.min #=> ["GA", "Georgia"]
153 154 155 156 157 158 159 160 161 |
# File 'lib/containers/splay_tree_map.rb', line 153 def min return nil if @root.nil? n = @root while n.left n = n.left end splay(n.key) return [n.key, n.value] end |
permalink #push(key, value) ⇒ Object Also known as: []=
Insert an item with an associated key into the SplayTreeMap, and returns the item inserted
Complexity: amortized O(log n)
map = Containers::SplayTreeMap.new
map.push("MA", "Massachusetts") #=> "Massachusetts"
map.get("MA") #=> "Massachusetts"
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
# File 'lib/containers/splay_tree_map.rb', line 55 def push(key, value) if @root.nil? @root = Node.new(key, value, nil, nil) @size = 1 return value end splay(key) cmp = (key <=> @root.key) if cmp == 0 @root.value = value return value end node = Node.new(key, value, nil, nil) if cmp < 1 node.left = @root.left node.right = @root @root.left = nil else node.right = @root.right node.left = @root @root.right = nil end @root = node @size += 1 value end |
permalink #size ⇒ Object
Return the number of items in the SplayTreeMap.
map = Containers::SplayTreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.size #=> 2
90 91 92 |
# File 'lib/containers/splay_tree_map.rb', line 90 def size @size end |