#--
# =============================================================================
# Copyright (c) 2004, Jamis Buck (jgb3@email.byu.edu)
# All rights reserved.
# 
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
# 
#     * Redistributions of source code must retain the above copyright notice,
#       this list of conditions and the following disclaimer.
# 
#     * Redistributions in binary form must reproduce the above copyright
#       notice, this list of conditions and the following disclaimer in the
#       documentation and/or other materials provided with the distribution.
# 
#     * The names of its contributors may not be used to endorse or promote
#       products derived from this software without specific prior written
#       permission.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
# POSSIBILITY OF SUCH DAMAGE.
# =============================================================================
#++

require 'copland/errors'

module Copland

  # 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.
  module Orderer

    # 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.
    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
    module_function :order

  end

end