class SplayTree

Constants

UndefinedValue
VERSION

Attributes

default[RW]

The default value for non existent key

@api public

default_proc[RW]

The default block for non existent key

@api public

Public Class Methods

new(default = UndefinedValue, &block) click to toggle source

Create a SplayTree

@param [Object] default

the default value for missing key

@api public

# 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

Public Instance Methods

[](key) click to toggle source

Find object by the key

@param [Object] key

the search key

@api public

# File lib/splay_tree.rb, line 164
def [](key)
  splay(key) unless @root.empty?

  return default_value if @root.key != key

  @root.value
end
Also aliased as: fetch
[]=(key, value) click to toggle source

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.

@param [Object] key

the key under which the node is inserted

@param [Object] value

the value of the node inserted into the tree

@return [Boolean]

false if key already exists, true otherwise

@api public

# 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
Also aliased as: insert
delete(key) click to toggle source

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.

@param [Object] key

@return [Object]

the node's value under the key

@api public

# 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() click to toggle source

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

@return [String]

@api public

# File lib/splay_tree.rb, line 230
def dump
  @root.dump || ""
end
each(&block) click to toggle source

Iterate over each key & value pair in the tree

@example

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

@yield [key, value]

@yieldparam [Object] key @yieldparam [Object] value

@return [self]

@api public

# 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(&block) click to toggle source

Iterate over each key in the tree

@example

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

@yield [key]

@yieldparam [Object] key

@return [self]

@api public

# 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(&block) click to toggle source

Iterate over each value in the tree

@example

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

@yield [value]

@yieldparam [Object] value

@return [self]

@api public

# 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?() click to toggle source

@api public

# File lib/splay_tree.rb, line 39
def empty?
  @root == Node::EMPTY
end
fetch(key)
Alias for: []
insert(key, value)
Alias for: []=
key?(key) click to toggle source

Check if tree contains a node with a matching key.

@return [Boolean]

@api public

# File lib/splay_tree.rb, line 178
def key?(key)
  return false if @root.empty?

  splay(key)
  @root.key == key
end
keys() click to toggle source

Return a new array of all the keys in the tree

@return [Array]

@api public

# File lib/splay_tree.rb, line 121
def keys
  each_key.to_a
end
length()
Alias for: size
size() click to toggle source

@api public

# File lib/splay_tree.rb, line 44
def size
  @root.size
end
Also aliased as: length
split(key) click to toggle source

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.

@param [Object] key

@api public

# File lib/splay_tree.rb, line 221
def split(key)
end
to_hash() click to toggle source

Export tree as hash

@return [Hash]

@api public

# File lib/splay_tree.rb, line 239
def to_hash
  each_with_object({}) { |(k, v), acc| acc[k] = v }
end
values() click to toggle source

Return a new array of all the values in the tree

@return [Array]

@api public

# File lib/splay_tree.rb, line 130
def values
  each_value.to_a
end

Private Instance Methods

default_value() click to toggle source

@api private

# File lib/splay_tree.rb, line 246
def default_value
  if @default != UndefinedValue
    @default
  elsif @default_proc
    @default_proc.call
  end
end
splay(key) click to toggle source

Top-down splaying by breaking down the tree.

@param [Object] key

the key at which to splay

@api private

# File lib/splay_tree.rb, line 260
def splay(key)
  current = @root
  dummy = left = right = @subtree
  @subtree.left = @subtree.right = Node::EMPTY
  loop do
    break if key == current.key

    if key < current.key
      break if current.left.empty?

      if key < current.left.key
        current = current.rotate_right
        break if current.left.empty?
      end
      right.left = current
      right = current
      current = current.left
    elsif key > current.key
      break if current.right.empty?

      if key > current.right.key
        current = current.rotate_left
        break if current.right.empty?
      end
      left.right = current
      left = current
      current = current.right
    end
  end
  left.right    = current.left
  right.left    = current.right
  current.left  = dummy.right
  current.right = dummy.left
  @root = current
end