/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2006

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

///\ingroup concept

///\file

///\brief Classes for representing paths in graphs.

///

///\todo Iterators have obsolete style

#ifndef LEMON_CONCEPT_PATH_H

#define LEMON_CONCEPT_PATH_H

#include <lemon/bits/invalid.h>

#include <lemon/concept_check.h>

namespace lemon {

  namespace concepts {

    /// \addtogroup concept

    /// @{

    //! \brief A skeleton structure for representing directed paths in a graph.

    //!

    //! A skeleton structure for representing directed paths in a graph.

    //! \param _Graph The graph type in which the path is.

    //!

    //! In a sense, the path can be treated as a graph, for it has \c NodeIt

    //! and \c EdgeIt with the same usage. These types converts to the \c Node

    //! and \c Edge of the original graph.

    template<typename _Graph>

    class Path {

    public:

      /// Type of the underlying graph.

      typedef _Graph Graph;

      /// Edge type of the underlying graph.

      typedef typename Graph::Edge Edge;

      /// Node type of the underlying graph.

      typedef typename Graph::Node Node;

      class NodeIt;

      class EdgeIt;

      /// \param _g The graph in which the path is.

      ///

      Path(const Graph &_g) {

	ignore_unused_variable_warning(_g);

      }

      /// Length of the path ie. the number of edges in the path.

      int length() const {return 0;}

      /// Returns whether the path is empty.

      bool empty() const { return true;}

      /// Resets the path to an empty path.

      void clear() {}

      /// \brief Starting point of the path.

      ///

      /// Starting point of the path.

      /// Returns INVALID if the path is empty.

      Node target() const {return INVALID;}

      /// \brief End point of the path.

      ///

      /// End point of the path.

      /// Returns INVALID if the path is empty.

      Node source() const {return INVALID;}

      /// \brief The target of an edge.

      ///

      /// Returns node iterator pointing to the target node of the

      /// given edge iterator.

      NodeIt target(const EdgeIt&) const {return INVALID;}

      /// \brief The source of an edge.

      ///

      /// Returns node iterator pointing to the source node of the

      /// given edge iterator.

      NodeIt source(const EdgeIt&) const {return INVALID;}

      /// \brief Iterator class to iterate on the nodes of the paths

      ///

      /// This class is used to iterate on the nodes of the paths

      ///

      /// Of course it converts to Graph::Node.

      class NodeIt {

      public:

	/// Default constructor

	NodeIt() {}

	/// Invalid constructor

	NodeIt(Invalid) {}

	/// Constructor with starting point

	NodeIt(const Path &) {}

	///Conversion to Graph::Node

	operator Node() const { return INVALID; }

	/// Next node

	NodeIt& operator++() {return *this;}

	/// Comparison operator

	bool operator==(const NodeIt&) const {return true;}

	/// Comparison operator

	bool operator!=(const NodeIt&) const {return true;}

 	/// Comparison operator

 	bool operator<(const NodeIt&) const {return false;}

      };

      /// \brief Iterator class to iterate on the edges of the paths

      ///

      /// This class is used to iterate on the edges of the paths

      ///

      /// Of course it converts to Graph::Edge

      class EdgeIt {

      public:

	/// Default constructor

	EdgeIt() {}

	/// Invalid constructor

	EdgeIt(Invalid) {}

	/// Constructor with starting point

	EdgeIt(const Path &) {}

	operator Edge() const { return INVALID; }

	/// Next edge

	EdgeIt& operator++() {return *this;}

	/// Comparison operator

	bool operator==(const EdgeIt&) const {return true;}

	/// Comparison operator

	bool operator!=(const EdgeIt&) const {return true;}

 	/// Comparison operator

 	bool operator<(const EdgeIt&) const {return false;}

      };

      friend class Builder;

      /// \brief Class to build paths

      ///

      /// This class is used to fill a path with edges.

      ///

      /// You can push new edges to the front and to the back of the path in

      /// arbitrary order then you should commit these changes to the graph.

      ///

      /// While the builder is active (after the first modifying

      /// operation and until the call of \ref commit()) the

      /// underlining Path is in a "transitional" state (operations on

      /// it have undefined result).

      class Builder {

      public:

        /// Constructor

        /// Constructor

	/// \param _path the path you want to fill in.

	///

	Builder(Path &_path) { ignore_unused_variable_warning(_path); }

	/// Sets the starting node of the path.

	/// Sets the starting node of the path. Edge added to the path

	/// afterwards have to be incident to this node.

	/// You \em must start building an empty path with these functions.

	/// (And you \em must \em not use it later).

	/// \sa pushFront()

	/// \sa pushBack()

	void setStartNode(const Node &) {}

	///Push a new edge to the front of the path

	///Push a new edge to the front of the path.

	///If the path is empty, you \em must call \ref setStartNode() before

	///the first use of \ref pushFront().

	void pushFront(const Edge&) {}

	///Push a new edge to the back of the path

	///Push a new edge to the back of the path.

	///If the path is empty, you \em must call \ref setStartNode() before

	///the first use of \ref pushBack().

	void pushBack(const Edge&) {}

	///Commit the changes to the path.

	///Commit the changes to the path.

        ///

	void commit() {}

	///Reserve (front) storage for the builder in advance.

	///If you know a reasonable upper bound on the number of the edges

	///to add to the front of the path,

	///using this function you may speed up the building.

	void reserveFront(size_t) {}

	///Reserve (back) storage for the builder in advance.

	///If you know a reasonable upper bound on the number of the edges

	///to add to the back of the path,

	///using this function you may speed up the building.

	void reserveBack(size_t) {}

      };

      template <typename _Path>

      struct Constraints {

	void constraints() {

          typedef typename _Path::Node Node;

          typedef typename _Path::NodeIt NodeIt;

          typedef typename Graph::Node GraphNode;

          typedef typename _Path::Edge Edge;

          typedef typename _Path::EdgeIt EdgeIt;

          typedef typename Graph::Edge GraphEdge;

          typedef typename _Path::Builder Builder;

          path = _Path(graph);

          bool b = cpath.empty();

          int l = cpath.length();

          Node gn;

          Edge ge;

          gn = cpath.source();

          gn = cpath.target();

          NodeIt nit;

          EdgeIt eit(INVALID);

          nit = path.source(eit);

          nit = path.target(eit);

          nit = NodeIt();

          nit = NodeIt(cpath);

          nit = INVALID;

          gn = nit;

          ++nit;

          b = nit == nit;

          b = nit != nit;

          b = nit < nit;

          eit = EdgeIt();

          eit = EdgeIt(cpath);

          eit = INVALID;

          ge = eit;

          ++eit;

          b = eit == eit;

          b = eit != eit;

          b = eit < eit;

          size_t st = 0;

          Builder builder(path); 

          builder.setStartNode(gn);

          builder.pushFront(ge);

          builder.pushBack(ge);

          builder.commit();

          builder.reserveFront(st);

          builder.reserveBack(st);

          ignore_unused_variable_warning(l);

          ignore_unused_variable_warning(b);

	}

        const Graph& graph;

        const _Path& cpath;

        _Path& path;

      };

    };

  ///@}

  }

} // namespace lemon

#endif // LEMON_CONCEPT_PATH_H