Class: Hamster::SortedSet::PlainAVLNode

Inherits:
AVLNode
  • Object
show all
Defined in:
lib/hamster/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.



1409
1410
1411
1412
1413
 
# File 'lib/hamster/sorted_set.rb', line 1409

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.



1414
1415
1416
 
# File 'lib/hamster/sorted_set.rb', line 1414

def height
  @height
end

#item ⇒ Object (readonly)

Returns the value of attribute item.



1414
1415
1416
 
# File 'lib/hamster/sorted_set.rb', line 1414

def item
  @item
end

#left ⇒ Object (readonly)

Returns the value of attribute left.



1414
1415
1416
 
# File 'lib/hamster/sorted_set.rb', line 1414

def left
  @left
end

#right ⇒ Object (readonly)

Returns the value of attribute right.



1414
1415
1416
 
# File 'lib/hamster/sorted_set.rb', line 1414

def right
  @right
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



1414
1415
1416
 
# File 'lib/hamster/sorted_set.rb', line 1414

def size
  @size
end

Class Method Details

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

items must be sorted



1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
 
# File 'lib/hamster/sorted_set.rb', line 1395

def self.from_items(items, from = 0, to = items.size-1) # items must be sorted
  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 



1424
1425
1426
 
# File 'lib/hamster/sorted_set.rb', line 1424

def clear
  PlainAVLNode::EmptyNode
end

#derive(item, left, right) ⇒ Object 



1428
1429
1430
 
# File 'lib/hamster/sorted_set.rb', line 1428

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

#direction(item) ⇒ Object 



1432
1433
1434
 
# File 'lib/hamster/sorted_set.rb', line 1432

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

#from_items(items) ⇒ Object 



1416
1417
1418
 
# File 'lib/hamster/sorted_set.rb', line 1416

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

#natural_order? ⇒ Boolean

Returns:

  • (Boolean) 


1420
1421
1422
 
# File 'lib/hamster/sorted_set.rb', line 1420

def natural_order?
  true
end