class PartiallyOrderedList

Convenience class that finds an order for a set of elements that satisfies an arbitrary sorting function that can be undefined for some pairs. TODO: Optimize and gemify (or find existing gem that does this)

Constants

CircularOrderingError

Attributes

elements[RW]
ordering[RW]

Public Class Methods

new(&block) click to toggle source
# File lib/farscape/helpers/partially_ordered_list.rb, line 25
def initialize(&block)
  raise ArgumentError, "#{self.class}.new requires a block" unless block_given?
  @elements = []
  @ordering = block
end

Public Instance Methods

add(item) click to toggle source
# File lib/farscape/helpers/partially_ordered_list.rb, line 31
def add(item)
  @cached_ary = nil
  new_el = Element.new(item, [])
  elements.each do |old_el|
    case ordering.call(old_el.item, new_el.item)
    when -1
      new_el.preceders << old_el
    when 1
      old_el.preceders << new_el
    end
  end
  elements << new_el
end
delete(item) click to toggle source
# File lib/farscape/helpers/partially_ordered_list.rb, line 45
def delete(item)
  if element = elements.find { |elt| elt.item == item }
    elements.delete(element)
    @cached_ary.delete(element) if @cached_ary
    elements.each { |elt| elt.preceders.delete(element) }
    item
  end
end
each() { |item| ... } click to toggle source
# File lib/farscape/helpers/partially_ordered_list.rb, line 54
def each(&block)
  return to_enum unless block_given?
  if @cached_ary && @cached_ary.size == elements.size
    @cached_ary.each{ |elt| yield elt.item }
  else
    @cached_ary = []
    unadded = elements.map{ |elt| elt=elt.dup; elt.preceders = elt.preceders.dup; elt }
    while unadded.any?
      i = unadded.find_index { |candidate| candidate.preceders.none? }
      if i
        to_add = unadded.delete_at(i)
        yield(to_add.item)
        unadded.each { |elt| elt.preceders.delete(to_add) }
        @cached_ary << to_add
      else
        raise CircularOrderingError.new("Could not resolve ordering for #{unadded.map(&:item)}")
      end
    end
  end
end