class Immutable::SortedSet::PlainAVLNode

@private AVL node which does not use a comparator function; it keeps items sorted

in their natural order

Constants

EmptyNode

Attributes

height[R]
item[R]
left[R]
right[R]
size[R]

Public Class Methods

from_items(items, from = 0, to = items.size-1) click to toggle source
# File lib/immutable/sorted_set.rb, line 1431
def self.from_items(items, from = 0, to = items.size-1)
  # items must be sorted, with no duplicates
  size = to - from + 1
  if size >= 3
    middle = (to + from) / 2
    PlainAVLNode.new(items[middle], PlainAVLNode.from_items(items, from, middle-1), PlainAVLNode.from_items(items, middle+1, to))
  elsif size == 2
    PlainAVLNode.new(items[from], PlainAVLNode::EmptyNode, PlainAVLNode.new(items[from+1], PlainAVLNode::EmptyNode, PlainAVLNode::EmptyNode))
  elsif size == 1
    PlainAVLNode.new(items[from], PlainAVLNode::EmptyNode, PlainAVLNode::EmptyNode)
  elsif size == 0
    PlainAVLNode::EmptyNode
  end
end
new(item, left, right) click to toggle source
# File lib/immutable/sorted_set.rb, line 1446
def initialize(item, left, right)
  @item,  @left, @right = item, left, right
  @height = ((right.height > left.height) ? right.height : left.height) + 1
  @size   = right.size + left.size + 1
end

Public Instance Methods

clear() click to toggle source
# File lib/immutable/sorted_set.rb, line 1465
def clear
  PlainAVLNode::EmptyNode
end
derive(item, left, right) click to toggle source
# File lib/immutable/sorted_set.rb, line 1469
def derive(item, left, right)
  PlainAVLNode.new(item, left, right)
end
direction(item) click to toggle source
# File lib/immutable/sorted_set.rb, line 1473
def direction(item)
  item <=> @item
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 1455
def from_items(items)
  items.uniq!
  items.sort!
  PlainAVLNode.from_items(items)
end
natural_order?() click to toggle source
# File lib/immutable/sorted_set.rb, line 1461
def natural_order?
  true
end