Class: Immutable::SortedSet::PlainAVLNode

Inherits:
AVLNode
  • Object
show all
Defined in:
lib/immutable/sorted_set.rb

Overview

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

in their natural order

Defined Under Namespace

Classes: Empty

Constant Summary collapse

EmptyNode = 
PlainAVLNode::Empty.new

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from AVLNode

#at, #balance, #between, #bulk_delete, #bulk_insert, #delete, #drop, #each, #each_between, #each_greater, #each_less, #empty?, #finish_removal, #include?, #insert, #keep_only, #max, #min, #partition, #prefix, #rebalance, #rebalance_left, #rebalance_right, #reverse_each, #slice, #suffix, #take

Constructor Details

#initialize(item, left, right) ⇒ PlainAVLNode

Returns a new instance of PlainAVLNode.



1448
1449
1450
1451
1452
 
# File 'lib/immutable/sorted_set.rb', line 1448

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

Instance Attribute Details

#height ⇒ Object (readonly)

Returns the value of attribute height.



1453
1454
1455
 
# File 'lib/immutable/sorted_set.rb', line 1453

def height
  @height
end

#item ⇒ Object (readonly)

Returns the value of attribute item.



1453
1454
1455
 
# File 'lib/immutable/sorted_set.rb', line 1453

def item
  @item
end

#left ⇒ Object (readonly)

Returns the value of attribute left.



1453
1454
1455
 
# File 'lib/immutable/sorted_set.rb', line 1453

def left
  @left
end

#right ⇒ Object (readonly)

Returns the value of attribute right.



1453
1454
1455
 
# File 'lib/immutable/sorted_set.rb', line 1453

def right
  @right
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



1453
1454
1455
 
# File 'lib/immutable/sorted_set.rb', line 1453

def size
  @size
end

Class Method Details

.from_items(items, from = 0, to = items.size-1) ⇒ Object 



1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
 
# File 'lib/immutable/sorted_set.rb', line 1433

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

Instance Method Details

#clear ⇒ Object 



1467
1468
1469
 
# File 'lib/immutable/sorted_set.rb', line 1467

def clear
  PlainAVLNode::EmptyNode
end

#derive(item, left, right) ⇒ Object 



1471
1472
1473
 
# File 'lib/immutable/sorted_set.rb', line 1471

def derive(item, left, right)
  PlainAVLNode.new(item, left, right)
end

#direction(item) ⇒ Object 



1475
1476
1477
 
# File 'lib/immutable/sorted_set.rb', line 1475

def direction(item)
  item <=> @item
end

#from_items(items) ⇒ Object

Used to implement #map Takes advantage of the fact that Enumerable#map allocates a new Array



1457
1458
1459
1460
1461
 
# File 'lib/immutable/sorted_set.rb', line 1457

def from_items(items)
  items.uniq!
  items.sort!
  PlainAVLNode.from_items(items)
end

#natural_order? ⇒ Boolean

Returns:

  • (Boolean) 


1463
1464
1465
 
# File 'lib/immutable/sorted_set.rb', line 1463

def natural_order?
  true
end