Class: SplayTree

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/splay_tree.rb,
lib/splay_tree/node.rb,
lib/splay_tree/version.rb

Defined Under Namespace

Classes: Node

Constant Summary collapse

UndefinedValue = 
Module.new
VERSION = 
"0.4.0"

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(default = UndefinedValue, &block) ⇒ SplayTree

Create a SplayTree

Parameters:

  • default (Object) (defaults to: UndefinedValue) —

    the default value for missing key



27
28
29
30
31
32
33
34
35
36
 
# File 'lib/splay_tree.rb', line 27

def initialize(default = UndefinedValue, &block)
  if !UndefinedValue.equal?(default) && block
    raise ArgumentError,
          "You need to pass either argument or a block as a default value"
  end
  @root    = Node::EMPTY
  @subtree = Node.new(nil, nil)
  @default = default
  @default_proc = block
end

Instance Attribute Details

#default ⇒ Object

The default value for non existent key



14
15
16
 
# File 'lib/splay_tree.rb', line 14

def default
  @default
end

#default_proc ⇒ Object

The default block for non existent key



19
20
21
 
# File 'lib/splay_tree.rb', line 19

def default_proc
  @default_proc
end

Instance Method Details

#[](key) ⇒ Object Also known as: fetch

Find object by the key

Parameters:

  • key (Object) —

    the search key



164
165
166
167
168
169
170
 
# File 'lib/splay_tree.rb', line 164

def [](key)
  splay(key) unless @root.empty?

  return default_value if @root.key != key

  @root.value
end

#[]=(key, value) ⇒ Boolean Also known as: insert

Insert a node into a tree with the given key and value provided that the tree does not already contain the key. The node becomes the root of the tree.

Parameters:

  • key (Object) —

    the key under which the node is inserted

  • value (Object) —

    the value of the node inserted into the tree

Returns:

  • (Boolean) —

    false if key already exists, true otherwise



146
147
148
149
150
151
152
153
154
155
 
# File 'lib/splay_tree.rb', line 146

def []=(key, value)
  if @root.empty?
    @root = Node.new(key, value)
    return true
  end

  @root = @root.insert(key, value)

  splay(key)
end

#delete(key) ⇒ Object

Delete a node specified by the key from the tree given the tree contains a node with this key. The deleted node value is returned. If the node is not found a nil is returned.

Parameters:

  • key (Object)

Returns:

  • (Object) —

    the node’s value under the key



196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
 
# File 'lib/splay_tree.rb', line 196

def delete(key)
  return if empty?

  splay(key)
  return if @root.key != key

  deleted = @root
  right = @root.right
  @root = @root.left
  if @root.empty?
    @root = right
  else
    splay(key) # ensure empty right child
    @root.right = right
  end
  deleted.value
end

#dump ⇒ String

Dump the tree structure in bracket format (root left right)

Returns:

  • (String) 


230
231
232
 
# File 'lib/splay_tree.rb', line 230

def dump
  @root.dump || ""
end

#each {|key, value| ... } ⇒ self

Iterate over each key & value pair in the tree

Examples:

tree = SplayTree.new
tree.each { |key, val| ... }

Yields:

  • (key, value)

Yield Parameters:

  • key (Object)
  • value (Object)

Returns:

  • (self) 


63
64
65
66
67
68
69
70
 
# File 'lib/splay_tree.rb', line 63

def each(&block)
  if block_given?
    @root.each(&block)
    self
  else
    @root.to_enum
  end
end

#each_key {|key| ... } ⇒ self

Iterate over each key in the tree

Examples:

tree = SplayTree.new
tree.each_key { |key| ... }

Yields:

  • (key)

Yield Parameters:

  • key (Object)

Returns:

  • (self) 


85
86
87
88
89
90
91
92
 
# File 'lib/splay_tree.rb', line 85

def each_key(&block)
  if block_given?
    @root.each_key(&block)
    self
  else
    @root.to_enum(:each_key)
  end
end

#each_value {|value| ... } ⇒ self

Iterate over each value in the tree

Examples:

tree = SplayTree.new
tree.each_value { |val| ... }

Yields:

  • (value)

Yield Parameters:

  • value (Object)

Returns:

  • (self) 


107
108
109
110
111
112
113
114
 
# File 'lib/splay_tree.rb', line 107

def each_value(&block)
  if block_given?
    @root.each_value(&block)
    self
  else
    @root.to_enum(:each_value)
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


39
40
41
 
# File 'lib/splay_tree.rb', line 39

def empty?
  @root == Node::EMPTY
end

#key?(key) ⇒ Boolean

Check if tree contains a node with a matching key.

Returns:

  • (Boolean) 


178
179
180
181
182
183
 
# File 'lib/splay_tree.rb', line 178

def key?(key)
  return false if @root.empty?

  splay(key)
  @root.key == key
end

#keys ⇒ Array[Object]

Return a new array of all the keys in the tree

Returns:

  • (Array[Object]) 


121
122
123
 
# File 'lib/splay_tree.rb', line 121

def keys
  each_key.to_a
end

#size ⇒ Object Also known as: length 



44
45
46
 
# File 'lib/splay_tree.rb', line 44

def size
  @root.size
end

#split(key) ⇒ Object

Construct and return two trees t1 and t2, where t1 contains items in t less than or equal to key, and t2 contains all items in t greater than key.

Parameters:

  • key (Object) 


221
222
 
# File 'lib/splay_tree.rb', line 221

def split(key)
end

#to_hash ⇒ Hash

Export tree as hash

Returns:

  • (Hash) 


239
240
241
 
# File 'lib/splay_tree.rb', line 239

def to_hash
  each_with_object({}) { |(k, v), acc| acc[k] = v }
end

#values ⇒ Array[Object]

Return a new array of all the values in the tree

Returns:

  • (Array[Object]) 


130
131
132
 
# File 'lib/splay_tree.rb', line 130

def values
  each_value.to_a
end