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.
1450 1451 1452 1453 1454 |
# File 'lib/immutable/sorted_set.rb', line 1450 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.
1455 1456 1457 |
# File 'lib/immutable/sorted_set.rb', line 1455 def height @height end |
#item ⇒ Object (readonly)
Returns the value of attribute item.
1455 1456 1457 |
# File 'lib/immutable/sorted_set.rb', line 1455 def item @item end |
#left ⇒ Object (readonly)
Returns the value of attribute left.
1455 1456 1457 |
# File 'lib/immutable/sorted_set.rb', line 1455 def left @left end |
#right ⇒ Object (readonly)
Returns the value of attribute right.
1455 1456 1457 |
# File 'lib/immutable/sorted_set.rb', line 1455 def right @right end |
#size ⇒ Object (readonly)
Returns the value of attribute size.
1455 1456 1457 |
# File 'lib/immutable/sorted_set.rb', line 1455 def size @size end |
Class Method Details
.from_items(items, from = 0, to = items.size-1) ⇒ Object
1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 |
# File 'lib/immutable/sorted_set.rb', line 1435 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
1469 1470 1471 |
# File 'lib/immutable/sorted_set.rb', line 1469 def clear PlainAVLNode::EmptyNode end |
#derive(item, left, right) ⇒ Object
1473 1474 1475 |
# File 'lib/immutable/sorted_set.rb', line 1473 def derive(item, left, right) PlainAVLNode.new(item, left, right) end |
#direction(item) ⇒ Object
1477 1478 1479 |
# File 'lib/immutable/sorted_set.rb', line 1477 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
1459 1460 1461 1462 1463 |
# File 'lib/immutable/sorted_set.rb', line 1459 def from_items(items) items.uniq! items.sort! PlainAVLNode.from_items(items) end |
#natural_order? ⇒ Boolean
1465 1466 1467 |
# File 'lib/immutable/sorted_set.rb', line 1465 def natural_order? true end |