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.


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)


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

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.


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"

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)

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

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"]

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"]

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"

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

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

def size
  @size
end