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