class Geom2D::Utils::SortedLinkedList

A doubly linked list that keeps its items sorted.

Public Class Methods

new(comparator = nil, &block) click to toggle source

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

clear() click to toggle source

Clears the list.

# File lib/geom2d/utils/sorted_linked_list.rb, line 131
def clear
  @anchor = Node.create_anchor
end
delete(value) click to toggle source

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
each() { |value| ... } click to toggle source

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
empty?() click to toggle source

Returns true if the list is empty?

# File lib/geom2d/utils/sorted_linked_list.rb, line 80
def empty?
  @anchor.next_node == @anchor
end
find_node(value) click to toggle source

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
insert(value) click to toggle source

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
last() click to toggle source

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
pop() click to toggle source

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
push(value) click to toggle source

Inserts the value and returns self.

# File lib/geom2d/utils/sorted_linked_list.rb, line 111
def push(value)
  insert(value)
  self
end