Class: Algorithms::Containers::RubySplayTreeMap

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

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RubySplayTreeMap

Create and initialize a new empty SplayTreeMap.



24
25
26
27
 
# File 'lib/containers/splay_tree_map.rb', line 24

def initialize
  @size = 0
  clear
end

Instance Method Details

#clear ⇒ Object

Remove all elements from the SplayTreeMap

Complexity: O(1)



79
80
81
82
83
 
# File 'lib/containers/splay_tree_map.rb', line 79

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 = Algorithms::Containers::SplayTreeMap.new
map["MA"] = "Massachusetts"
map["GA"] = "Georgia"
map.delete("GA") #=> "Georgia"
map.delete("DE") #=> nil



172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/containers/splay_tree_map.rb', line 172

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

#each ⇒ Object

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



191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
 
# File 'lib/containers/splay_tree_map.rb', line 191

def each
  return nil unless @root
  stack = 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 = Algorithms::Containers::SplayTreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.get("GA") #=> "Georgia"



118
119
120
121
122
123
 
# File 'lib/containers/splay_tree_map.rb', line 118

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 = Algorithms::Containers::SplayTreeMap.new
map["MA"] = "Massachusetts"
map["GA"] = "Georgia"
map.has_key?("GA") #=> true
map.has_key?("DE") #=> false

Returns:

  • (Boolean) 


106
107
108
 
# File 'lib/containers/splay_tree_map.rb', line 106

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

#height ⇒ Object

Return the height of the tree structure in the SplayTreeMap.

Complexity: O(log n)

map = Algorithms::Containers::SplayTreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.height #=> 2



93
94
95
 
# File 'lib/containers/splay_tree_map.rb', line 93

def height
  height_recursive(@root)
end

#max ⇒ Object

Return the largest [key, value] pair in the SplayTreeMap, or nil if the tree is empty.

Complexity: amortized O(log n)

map = Algorithms::Containers::SplayTreeMap.new
map["MA"] = "Massachusetts"
map["GA"] = "Georgia"
map.max #=> ["MA", "Massachusetts"]



152
153
154
155
156
157
158
159
160
 
# File 'lib/containers/splay_tree_map.rb', line 152

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

#min ⇒ Object

Return the smallest [key, value] pair in the SplayTreeMap, or nil if the tree is empty.

Complexity: amortized O(log n)

map = Algorithms::Containers::SplayTreeMap.new
map["MA"] = "Massachusetts"
map["GA"] = "Georgia"
map.min #=> ["GA", "Georgia"]



134
135
136
137
138
139
140
141
142
 
# File 'lib/containers/splay_tree_map.rb', line 134

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 = Algorithms::Containers::SplayTreeMap.new
map.push("MA", "Massachusetts") #=> "Massachusetts"
map.get("MA") #=> "Massachusetts"



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/containers/splay_tree_map.rb', line 36

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

#size ⇒ Object

Return the number of items in the SplayTreeMap.

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



71
72
73
 
# File 'lib/containers/splay_tree_map.rb', line 71

def size
  @size
end