#ifndef TCG_SEQUENCE_OPS_H
#define TCG_SEQUENCE_OPS_H

/*!
  \file     sequence_ops.h

  \brief    This file contains algorithms returning sub-sequences of
            some input iterator range.
*/

namespace tcg {
namespace sequence_ops {

//**************************************************************************************
//    Sequence Operations
//**************************************************************************************

/*!
  \brief    Base interface for an evaluator object supported by function
            \p tcg::minimalPath().
*/
template <typename It, typename Pen>
struct EdgeEvaluator {
  typedef It iterator_type;
  typedef Pen penalty_type;

public:
  EdgeEvaluator() {}
  virtual ~EdgeEvaluator() {}

  /*!
\brief    Computes the largest allowed position reachable in a single
        step from given position \a a.
*/
  virtual iterator_type furthestFrom(const iterator_type &a) = 0;

  /*!
\brief    Computes the penalty for the specified input step.
\remark   Supplied input step is ensured to be allowed, as guaranteed
        by function furthestFrom().
*/
  virtual penalty_type penalty(const iterator_type &a,
                               const iterator_type &b) = 0;
};

//------------------------------------------------------------------------------

/*!
  \brief    Builds the sequence's minimal subpath from the specified evaluator.

  \details  This function traverses the input sequence (end excluded) searching
  for the
            minimal allowed path with respect to the number of vertices
  (primarily)
            and the penalty associated to each path edge; returns true whether
  such a
            path could be found, false if \b no path from begin to --end could
  be
            established.

            The minimal path function applies a simplified Bellman optimality
  algorithm
            on a sequence, where graph edges are specified through an edge
  evaluator
            functor, rather than being built in a graph class.

            It works this way:

              \li The minimal number of edges required to traverse the sequence
  can be
                  found by traversing the sequence with the maximum step
  allowed.

              \li Each node have the minimal number of edges required to reach
  the
                  sequence end, the minimal penalty to it, and obviously the
  next node
                  which allow this optimal configuration.

              \li The optimal "edge number-penalty" value from one point sums
  with the
                  one of the next point in the optimal configuration; thus, it
  can be
                  found retroactively starting from the end.

              \li The path retrieved with the maximum step allowed defines the
                  remaining steps to achieve the optimal number of edges,
  starting from
                  the end.

  \remark     This function is currently working only for random access
  iterators.

  \sa         The EdgeEvaluator class for the supported evaluator interface.
*/

template <typename ranit_type, typename edge_eval, typename containers_reader>
bool minimalPath(ranit_type begin, ranit_type end, edge_eval &evaluator,
                 containers_reader &output);
}
}  // namespace tcg::sequence_ops

#endif  // TCG_SEQUENCE_OPS_H

#ifdef INCLUDE_HPP
#include "hpp/sequence_ops.hpp"
#endif