#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,="" pen="" typename=""></typename>

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 containers_reader="" edge_eval,="" ranit_type,="" typename=""></typename>

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