Class: PartiallyOrderedList

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/farscape/helpers/partially_ordered_list.rb

Overview

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)

Defined Under Namespace

Classes: Element

Constant Summary collapse

CircularOrderingError = 
Class.new(StandardError)

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(&block) ⇒ PartiallyOrderedList

Returns a new instance of PartiallyOrderedList.

Raises:

  • (ArgumentError) 


25
26
27
28
29
 
# 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

Instance Attribute Details

#elements ⇒ Object

Returns the value of attribute elements.



23
24
25
 
# File 'lib/farscape/helpers/partially_ordered_list.rb', line 23

def elements
  @elements
end

#ordering ⇒ Object

Returns the value of attribute ordering.



23
24
25
 
# File 'lib/farscape/helpers/partially_ordered_list.rb', line 23

def ordering
  @ordering
end

Instance Method Details

#add(item) ⇒ Object 



31
32
33
34
35
36
37
38
39
40
41
42
43
 
# 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) ⇒ Object 



45
46
47
48
49
50
51
52
 
# 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(&block) ⇒ Object 



54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# 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