Class: Containers::RubySplayTreeMap

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/containers/splay_tree_map.rb

Overview

SOFTWARE.

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initializeRubySplayTreeMap

Create and initialize a new empty SplayTreeMap.

[View source]

43
44
45
46
# File 'lib/containers/splay_tree_map.rb', line 43

def initialize
  @size = 0
  clear
end

Instance Method Details

#clearObject

Remove all elements from the SplayTreeMap

Complexity: O(1)

[View source]

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

#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
[View source]

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

#eachObject

Iterates over the SplayTreeMap in ascending order. Uses an iterative, not recursive, approach.

[View source]

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

#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"
[View source]

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

#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

Returns:

  • (Boolean)
[View source]

125
126
127
# File 'lib/containers/splay_tree_map.rb', line 125

def has_key?(key)
  !get(key).nil?
end

#heightObject

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
[View source]

112
113
114
# File 'lib/containers/splay_tree_map.rb', line 112

def height
  height_recursive(@root)
end

#maxObject

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"]
[View source]

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

#minObject

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"]
[View source]

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

#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"
[View source]

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

#sizeObject

Return the number of items in the SplayTreeMap.

map = Containers::SplayTreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.size #=> 2
[View source]

90
91
92
# File 'lib/containers/splay_tree_map.rb', line 90

def size
  @size
end