Module: Copland::Orderer
- Defined in:
- lib/copland/ordering.rb
Overview
This is module that implements ordering algorithms. Currently only one such algorithm is implemented, and it is used for ordering interceptors and AutoLoad-ed services.
Class Method Summary collapse
-
.order(elements) ⇒ Object
Orders the given list of elements.
Class Method Details
.order(elements) ⇒ Object
Orders the given list of elements. Each element MUST support the following interface:
# point
: return a service-point or configuration-point with
which the element is associated. This is used for error reporting,
when the ordering fails.
# +before?(e): return true iff the element must occur before the
element 'e' in the list. 'e' must be an element instance.
# +after?(e): return true iff the element must occur after the
element 'e' in the list. 'e' must be an element instance.
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
# File 'lib/copland/ordering.rb', line 55 def order( elements ) list = [] return list if elements.empty? elements = elements.dup # 1: shift first element of 'elements' onto 'list' list.push elements.shift while !elements.empty? # 2: for each element 'i' of 'elements', compare it with each # element 'j' of 'list'. If position of i is constrained relative # to j, shift i onto list relative to j. If conflicting constraints # are discovered for i relative to multiple elements of list, raise # an exception. If i is unconstrained relative to any j, leave it # (for now) in 'elements'. index = 0 insertions_made = 0 while index < elements.length i = elements[ index ] must_be_at = -1 list.each_index do |position| j = list[ position ] if must_be_at < 0 && i.before?( j ) must_be_at = position end if must_be_at >= 0 && i.after?( j ) raise OrderingException, "#{i.point.full_name} < #{list[must_be_at].point.full_name} && " + "#{i.point.full_name} > #{j.point.full_name}" end end if must_be_at >= 0 elements.delete_at index list.insert must_be_at, i insertions_made += 1 else index += 1 end end # 3: if no new elements were shifted onto 'list', start over at step 1. # otherwise repeat from step 2. Continue until 'elements' list is # empty. if !elements.empty? && insertions_made < 1 # this is safe because, at this point, we know that the elements in 'list' # and the remaining elements in 'elements' are independent of each other; # thus, we can just push any value from 'elements' onto the end 'list', # without violating any constraints. list.push elements.shift end end return list end |