Class: Immutable::SortedSet::PlainAVLNode
- 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
Instance Attribute Summary collapse
-
#height ⇒ Object
readonly
Returns the value of attribute height.
-
#item ⇒ Object
readonly
Returns the value of attribute item.
-
#left ⇒ Object
readonly
Returns the value of attribute left.
-
#right ⇒ Object
readonly
Returns the value of attribute right.
-
#size ⇒ Object
readonly
Returns the value of attribute size.
Class Method Summary collapse
Instance Method Summary collapse
- #clear ⇒ Object
- #derive(item, left, right) ⇒ Object
- #direction(item) ⇒ Object
-
#from_items(items) ⇒ Object
Used to implement #map Takes advantage of the fact that Enumerable#map allocates a new Array.
-
#initialize(item, left, right) ⇒ PlainAVLNode
constructor
A new instance of PlainAVLNode.
- #natural_order? ⇒ Boolean
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
1463 1464 1465 |
# File 'lib/immutable/sorted_set.rb', line 1463 def natural_order? true end |