class Geom2D::Utils::SortedLinkedList
A doubly linked list that keeps its items sorted.
Public Class Methods
Creates a new SortedLinkedList
using the comparator
or the given block as compare function.
The comparator has to respond to +call(a, b)+ where a
is the value to be inserted and b
is the value to which it is compared. The return value should be true
if the value a
should be inserted before b
, i.e. at the position of b
.
# File lib/geom2d/utils/sorted_linked_list.rb, line 74 def initialize(comparator = nil, &block) @anchor = Node.create_anchor @comparator = comparator || block end
Public Instance Methods
Clears the list.
# File lib/geom2d/utils/sorted_linked_list.rb, line 131 def clear @anchor = Node.create_anchor end
Deletes the node with the given value from the list and returns its value.
# File lib/geom2d/utils/sorted_linked_list.rb, line 142 def delete(value) if node = find_node(value) node.delete end end
Yields each value in sorted order.
If no block is given, an enumerator is returned.
# File lib/geom2d/utils/sorted_linked_list.rb, line 92 def each #:yield: value return to_enum(__method__) unless block_given? current = @anchor.next_node while current != @anchor yield(current.value) current = current.next_node end end
Returns true
if the list is empty?
# File lib/geom2d/utils/sorted_linked_list.rb, line 80 def empty? @anchor.next_node == @anchor end
Returns the node with the given value, or nil
if no such value is found.
# File lib/geom2d/utils/sorted_linked_list.rb, line 102 def find_node(value) current = @anchor.next_node while current != @anchor return current if current.value == value current = current.next_node end end
Inserts a new node with the given value into the list (at a position decided by the compare function) and returns it.
# File lib/geom2d/utils/sorted_linked_list.rb, line 118 def insert(value) node = Node.new(value) current = @anchor.next_node while current != @anchor if @comparator.call(node.value, current.value) return node.insert_before(current) end current = current.next_node end node.insert_before(@anchor) end
Returns the last value in the list.
# File lib/geom2d/utils/sorted_linked_list.rb, line 85 def last empty? ? nil : @anchor.prev_node.value end
Removes the top node from the list and returns its value.
# File lib/geom2d/utils/sorted_linked_list.rb, line 136 def pop return nil if empty? @anchor.prev_node.delete end
Inserts the value and returns self.
# File lib/geom2d/utils/sorted_linked_list.rb, line 111 def push(value) insert(value) self end