class Immutable::SortedSet::AVLNode
@private
Attributes
height[R]
item[R]
left[R]
right[R]
size[R]
Public Class Methods
from_items(items, comparator, from = 0, to = items.size-1)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1017 def self.from_items(items, comparator, from = 0, to = items.size-1) # items must be sorted, without duplicates (as determined by comparator) size = to - from + 1 if size >= 3 middle = (to + from) / 2 AVLNode.new(items[middle], comparator, AVLNode.from_items(items, comparator, from, middle-1), AVLNode.from_items(items, comparator, middle+1, to)) elsif size == 2 empty = AVLNode::Empty.new(comparator) AVLNode.new(items[from], comparator, empty, AVLNode.new(items[from+1], comparator, empty, empty)) elsif size == 1 empty = AVLNode::Empty.new(comparator) AVLNode.new(items[from], comparator, empty, empty) elsif size == 0 AVLNode::Empty.new(comparator) end end
new(item, comparator, left, right)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1034 def initialize(item, comparator, left, right) @item, @comparator, @left, @right = item, comparator, left, right @height = ((right.height > left.height) ? right.height : left.height) + 1 @size = right.size + left.size + 1 end
Public Instance Methods
at(index)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1295 def at(index) if index < @left.size @left.at(index) elsif index > @left.size @right.at(index - @left.size - 1) else @item end end
balance()
click to toggle source
# File lib/immutable/sorted_set.rb, line 1313 def balance @left.height - @right.height end
between(from, to)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1200 def between(from, to) if direction(from) > 0 # all on the right @right.between(from, to) elsif direction(to) < 0 # all on the left @left.between(from, to) else left = @left.suffix(from, true) right = @right.prefix(to, true) rebalance(left, right) end end
bulk_delete(items)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1118 def bulk_delete(items) return self if items.empty? if items.size == 1 catch :not_present do return delete(items.first) end return self end left, right, keep_item = [], [], true items.each do |item| dir = direction(item) if dir > 0 right << item elsif dir < 0 left << item else keep_item = false end end left = @left.bulk_delete(left) right = @right.bulk_delete(right) finish_removal(keep_item, left, right) end
bulk_insert(items)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1076 def bulk_insert(items) return self if items.empty? if items.size == 1 catch :present do return insert(items.first) end return self end left, right = partition(items) if right.size > left.size rebalance_right(@left.bulk_insert(left), @right.bulk_insert(right)) else rebalance_left(@left.bulk_insert(left), @right.bulk_insert(right)) end end
clear()
click to toggle source
# File lib/immutable/sorted_set.rb, line 1057 def clear AVLNode::Empty.new(@comparator) end
delete(item)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1093 def delete(item) dir = direction(item) if dir == 0 if @right.empty? return @left # replace this node with its only child elsif @left.empty? return @right # likewise end if balance > 0 # tree is leaning to the left. replace with highest node on that side replace_with = @left.max derive(replace_with, @left.delete(replace_with), @right) else # tree is leaning to the right. replace with lowest node on that side replace_with = @right.min derive(replace_with, @left, @right.delete(replace_with)) end elsif dir > 0 rebalance_left(@left, @right.delete(item)) else rebalance_right(@left.delete(item), @right) end end
derive(item, left, right)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1061 def derive(item, left, right) AVLNode.new(item, @comparator, left, right) end
direction(item)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1384 def direction(item) @comparator.call(item, @item) end
drop(n)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1258 def drop(n) if n >= @size clear elsif n <= 0 self elsif @left.size >= n rebalance_right(@left.drop(n), @right) elsif @left.size + 1 == n @right else @right.drop(n - @left.size - 1) end end
each() { |item| ... }
click to toggle source
# File lib/immutable/sorted_set.rb, line 1246 def each(&block) @left.each(&block) yield @item @right.each(&block) end
each_between(from, to) { |item| ... }
click to toggle source
# File lib/immutable/sorted_set.rb, line 1234 def each_between(from, to, &block) if direction(from) > 0 # all on the right @right.each_between(from, to, &block) elsif direction(to) < 0 # all on the left @left.each_between(from, to, &block) else @left.each_greater(from, true, &block) yield @item @right.each_less(to, true, &block) end end
each_greater(item, inclusive) { |item| ... }
click to toggle source
# File lib/immutable/sorted_set.rb, line 1223 def each_greater(item, inclusive, &block) dir = direction(item) if dir < 0 || (inclusive && dir == 0) @left.each_greater(item, inclusive, &block) yield @item @right.each(&block) else @right.each_greater(item, inclusive, &block) end end
each_less(item, inclusive) { |item| ... }
click to toggle source
# File lib/immutable/sorted_set.rb, line 1212 def each_less(item, inclusive, &block) dir = direction(item) if dir > 0 || (inclusive && dir == 0) @left.each(&block) yield @item @right.each_less(item, inclusive, &block) else @left.each_less(item, inclusive, &block) end end
empty?()
click to toggle source
# File lib/immutable/sorted_set.rb, line 1053 def empty? false end
finish_removal(keep_item, left, right)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1164 def finish_removal(keep_item, left, right) # deletion of items may have occurred on left and right sides # now we may also need to delete the current item if keep_item rebalance(left, right) # no need to delete the current item elsif left.empty? right elsif right.empty? left elsif left.height > right.height replace_with = left.max derive(replace_with, left.delete(replace_with), right) else replace_with = right.min derive(replace_with, left, right.delete(replace_with)) end end
from_items(items)
click to toggle source
Used to implement map Takes advantage of the fact that Enumerable#map allocates a new Array
# File lib/immutable/sorted_set.rb, line 1043 def from_items(items) items.sort!(&@comparator) SortedSet.uniq_by_comparator!(items, @comparator) AVLNode.from_items(items, @comparator) end
include?(item)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1284 def include?(item) dir = direction(item) if dir == 0 true elsif dir > 0 @right.include?(item) else @left.include?(item) end end
insert(item)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1065 def insert(item) dir = direction(item) if dir == 0 throw :present elsif dir > 0 rebalance_right(@left, @right.insert(item)) else rebalance_left(@left.insert(item), @right) end end
keep_only(items)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1144 def keep_only(items) return clear if items.empty? left, right, keep_item = [], [], false items.each do |item| dir = direction(item) if dir > 0 right << item elsif dir < 0 left << item else keep_item = true end end left = @left.keep_only(left) right = @right.keep_only(right) finish_removal(keep_item, left, right) end
max()
click to toggle source
# File lib/immutable/sorted_set.rb, line 1305 def max @right.empty? ? @item : @right.max end
min()
click to toggle source
# File lib/immutable/sorted_set.rb, line 1309 def min @left.empty? ? @item : @left.min end
natural_order?()
click to toggle source
# File lib/immutable/sorted_set.rb, line 1049 def natural_order? false end
partition(items)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1331 def partition(items) left, right = [], [] items.each do |item| dir = direction(item) if dir > 0 right << item elsif dir < 0 left << item end end [left, right] end
prefix(item, inclusive)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1182 def prefix(item, inclusive) dir = direction(item) if dir > 0 || (inclusive && dir == 0) rebalance_left(@left, @right.prefix(item, inclusive)) else @left.prefix(item, inclusive) end end
rebalance(left, right)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1344 def rebalance(left, right) if left.height > right.height rebalance_left(left, right) else rebalance_right(left, right) end end
rebalance_left(left, right)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1352 def rebalance_left(left, right) # the tree might be unbalanced to the left (paths on the left too long) balance = left.height - right.height if balance >= 2 if left.balance > 0 # single right rotation derive(left.item, left.left, derive(@item, left.right, right)) else # left rotation, then right derive(left.right.item, derive(left.item, left.left, left.right.left), derive(@item, left.right.right, right)) end else derive(@item, left, right) end end
rebalance_right(left, right)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1368 def rebalance_right(left, right) # the tree might be unbalanced to the right (paths on the right too long) balance = left.height - right.height if balance <= -2 if right.balance > 0 # right rotation, then left derive(right.left.item, derive(@item, left, right.left.left), derive(right.item, right.left.right, right.right)) else # single left rotation derive(right.item, derive(@item, left, right.left), right.right) end else derive(@item, left, right) end end
reverse_each() { |item| ... }
click to toggle source
# File lib/immutable/sorted_set.rb, line 1252 def reverse_each(&block) @right.reverse_each(&block) yield @item @left.reverse_each(&block) end
slice(from, length)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1317 def slice(from, length) if length <= 0 clear elsif from + length <= @left.size @left.slice(from, length) elsif from > @left.size @right.slice(from - @left.size - 1, length) else left = @left.slice(from, @left.size - from) right = @right.slice(0, from + length - @left.size - 1) rebalance(left, right) end end
suffix(item, inclusive)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1191 def suffix(item, inclusive) dir = direction(item) if dir < 0 || (inclusive && dir == 0) rebalance_right(@left.suffix(item, inclusive), @right) else @right.suffix(item, inclusive) end end
take(n)
click to toggle source
# File lib/immutable/sorted_set.rb, line 1272 def take(n) if n >= @size self elsif n <= 0 clear elsif @left.size >= n @left.take(n) else rebalance_left(@left, @right.take(n - @left.size - 1)) end end