class Splaytree
Constants
- VERSION
Attributes
length[R]
root[R]
size[R]
Public Class Methods
new()
click to toggle source
# File lib/splaytree.rb, line 10 def initialize @root = nil @size = 0 end
Public Instance Methods
ceiling(key)
click to toggle source
# File lib/splaytree.rb, line 37 def ceiling(key) return if empty? get(key) return @root.to_h if @root.key >= key get_one_higher_of_root end
clear()
click to toggle source
# File lib/splaytree.rb, line 172 def clear @root = nil @size = 0 end
display()
click to toggle source
# File lib/splaytree.rb, line 213 def display print_tree = -> (node, depth) do return unless node print_tree.call(node.right, depth + 1) puts node.key.to_s.rjust(5*depth, ' ') print_tree.call(node.left, depth + 1) end print_tree.call(@root, 0) end
duplicates(key)
click to toggle source
# File lib/splaytree.rb, line 77 def duplicates(key) return if empty? get(key) return if @root.key != key @root.duplicates + [@root.value] end
each() { |node| ... }
click to toggle source
# File lib/splaytree.rb, line 177 def each return if empty? stack = [] node = @root loop do if node stack.push(node) node.duplicates.each do |value| stack.push(Node.new(node.key, value, node)) end node = node.left else break if stack.empty? node = stack.pop yield(node) node = node.right end end end
each_key() { |key| ... }
click to toggle source
# File lib/splaytree.rb, line 197 def each_key each { |node| yield node.key } end
each_value() { |value| ... }
click to toggle source
# File lib/splaytree.rb, line 201 def each_value each { |node| yield node.value } end
empty?()
click to toggle source
# File lib/splaytree.rb, line 15 def empty? @root.nil? end
floor(key)
click to toggle source
# File lib/splaytree.rb, line 44 def floor(key) return if empty? get(key) return @root.to_h if @root.key <= key get_one_lower_of_root end
get(key)
click to toggle source
# File lib/splaytree.rb, line 84 def get(key) return if empty? node = @root value = nil loop do case key <=> node.key when 0 value = node.value break when -1 break if node.left.nil? node = node.left when 1 break if node.right.nil? node = node.right else raise TypeError, 'Keys should be comparable!' end end splay(node) value end
Also aliased as: []
height()
click to toggle source
# File lib/splaytree.rb, line 67 def height subtree_height = -> (node) do return 0 unless node left = 1 + subtree_height.call(node.left) right = 1 + subtree_height.call(node.right) left > right ? left : right end subtree_height.call(@root) end
higher(key)
click to toggle source
# File lib/splaytree.rb, line 23 def higher(key) return if empty? get(key) return @root.to_h if @root.key > key get_one_higher_of_root end
insert(key, value)
click to toggle source
# File lib/splaytree.rb, line 108 def insert(key, value) node = Node.new(key, value) if @root current = @root loop do case key <=> current.key when 0 node = current node.add_duplicate!(value) break when -1 unless current.left current.set_left(node) break end current = current.left when 1 unless current.right current.set_right(node) break end current = current.right else raise TypeError, 'Keys should be comparable!' end end end splay(node) @size += 1 true end
Also aliased as: []=
key?(key)
click to toggle source
# File lib/splaytree.rb, line 19 def key?(key) !!get(key) end
keys()
click to toggle source
# File lib/splaytree.rb, line 205 def keys to_enum(:each_key).to_a end
lower(key)
click to toggle source
# File lib/splaytree.rb, line 30 def lower(key) return if empty? get(key) return @root.to_h if @root.key < key get_one_lower_of_root end
max()
click to toggle source
# File lib/splaytree.rb, line 59 def max return if empty? node = @root node = node.right while node.right splay(node) node.to_h end
min()
click to toggle source
# File lib/splaytree.rb, line 51 def min return if empty? node = @root node = node.left while node.left splay(node) node.to_h end
remove(key)
click to toggle source
# File lib/splaytree.rb, line 149 def remove(key) return if empty? get(key) return if @root.key != key if @root.duplicates? deleted = @root.remove_duplicate! else deleted = @root.value if @root.left.nil? @root = @root.right @root.parent = nil else right = @root.right @root = @root.left @root.parent = nil get(key) @root.set_right(right) end end @size -= 1 deleted end
report()
click to toggle source
# File lib/splaytree.rb, line 223 def report return if empty? result = [] each do |node| item = { node: node.key, parent: node.parent && node.parent.key, left: node.left && node.left.key, right: node.right && node.right.key } result << item end result end
update(key, value)
click to toggle source
# File lib/splaytree.rb, line 141 def update(key, value) return false if empty? get(key) return false if @root.key != key @root.value = value true end
values()
click to toggle source
# File lib/splaytree.rb, line 209 def values to_enum(:each_value).to_a end
Private Instance Methods
get_one_higher_of_root()
click to toggle source
# File lib/splaytree.rb, line 240 def get_one_higher_of_root return if @root.right.nil? node = @root.right node = node.left while node.left splay(node) node.to_h end
get_one_lower_of_root()
click to toggle source
# File lib/splaytree.rb, line 248 def get_one_lower_of_root return if @root.left.nil? node = @root.left node = node.right while node.right splay(node) node.to_h end
splay(node)
click to toggle source
# File lib/splaytree.rb, line 256 def splay(node) until node.root? parent = node.parent if parent.root? node.rotate elsif node.zigzig? parent.rotate node.rotate else node.rotate node.rotate end end @root = node end