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

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