#include <lemon/lemon_reader.h>

 #include <lemon/lemon_writer.h>

   /// \brief Class which helps to iterate the nodes of a path

   ///

   /// In a sense, the path can be treated as a list of edges. The

   /// lemon path type stores just this list. As a consequence it

   /// cannot enumerate the nodes in the path and the zero length paths

   /// cannot store the node.

   ///

   /// This class implements the node iterator of a path structure. To

   /// provide this feature, the underlying graph should be given to

   /// the constructor of the iterator.

   template <typename Path>

   class PathNodeIt {

   private:

     const typename Path::Graph *_graph;

     typename Path::EdgeIt _it;

     typename Path::Graph::Node _nd;

   public:

     typedef typename Path::Graph Graph;

     typedef typename Graph::Node Node;

     /// Default constructor

     PathNodeIt() {}

     /// Invalid constructor

     PathNodeIt(Invalid) 

       : _graph(0), _it(INVALID), _nd(INVALID) {}

     /// Constructor

     PathNodeIt(const Graph& graph, const Path& path) 

       : _graph(&graph), _it(path) {

       _nd = (_it != INVALID ? _graph->source(_it) : INVALID);

     }

     /// Constructor

     PathNodeIt(const Graph& graph, const Path& path, const Node& src) 

       : _graph(&graph), _it(path), _nd(src) {}

     ///Conversion to Graph::Node

     operator Node() const {

       return _nd;

     }

     /// Next node

     PathNodeIt& operator++() {

       if (_it == INVALID) _nd = INVALID;

       else {

 	_nd = _graph->target(_it);

 	++_it;

       }

       return *this;

     }

     /// Comparison operator

     bool operator==(const PathNodeIt& n) const { 

       return _it == n._it && _nd == n._nd; 

     }

     /// Comparison operator

     bool operator!=(const PathNodeIt& n) const { 

       return _it != n._it || _nd != n._nd; 

     }

     /// Comparison operator

     bool operator<(const PathNodeIt& n) const { 

       return (_it < n._it && _nd != INVALID);

     }

   };

   /// \brief Item writer for paths

   ///

   /// This class can write paths into files. You can store paths in

   /// distinict mapset or in attributes section.

   ///

   ///\code

   /// GraphWriter<SmartGraph> gw(std::cout, g);

   /// NodeMapWriter<SmartGraph> nmw(gw, g, gw);

   ///

   /// SmartGraph::NodeMap<Path<SmartGraph> > pnm(g);

   /// for (SmartGraph::NodeIt n(g); n != INVALID; ++n) {

   ///   pnm[n] = bfs.path(n);

   /// }

   /// nmw.writeNodeMap("pnm", pnm, PathWriter<Path<SmartGraph> >(gw));

   ///

   /// gw.run();

   ///\endcode

   ///

   /// \warning Do not use this class to write node or edge map values

   /// into usual nodesets or edgesets. You will not be able to read

   /// back your paths. Rather use NodeMapWriter, EdgeSetWriter or

   /// UEdgeSetWriter to dump paths from maps to lemon file.

   template <typename Path>

   class PathWriter {

   private:

     typedef typename Path::Edge Edge;

     std::auto_ptr<_writer_bits::LabelWriterBase<Edge> > edgeLabelWriter;

   public:

     typedef Path Value;

     PathWriter(const PathWriter& pw) {

       edgeLabelWriter.reset(pw.edgeLabelWriter->clone());

     }

     /// \brief Constructor

     ///

     /// The paramter shold be an edge label writer which could

     /// be a GraphWriter or an EdgeSetWriter. 

     template <typename EdgeLabelWriter>

     explicit PathWriter(const EdgeLabelWriter& _edgeLabelWriter) {

       edgeLabelWriter.reset(new _writer_bits::

 	LabelWriter<Edge, EdgeLabelWriter>(_edgeLabelWriter));

     }

     /// \brief Writer function

     ///

     /// Writes the path to the current stream. The representation

     /// is the edge labels beetween parentheses.

     void write(std::ostream& os, const Value& value) const {

       if (!edgeLabelWriter->isLabelWriter()) {

 	throw DataFormatError("Cannot find edgeset or label map");

       }

       os << '(' << ' ';

       for (typename Path::EdgeIt e(value); e != INVALID; ++e) {

 	edgeLabelWriter->write(os, e);

 	os << ' ';

       }

       os << ')';

     }

   };

   namespace _path_bits {

     template <typename _Graph>

     class PathProxy {

     public:

       typedef False RevPathTag;

       typedef _Graph Graph;

       typedef typename Graph::Edge Edge;

       PathProxy(const std::vector<Edge>& edges)

 	: _edges(edges) {}

       int length() const {

 	return _edges.size();

       }

       bool empty() const {

 	return _edges.size() == 0;

       }

       class EdgeIt {

       public:

 	EdgeIt() {}

 	EdgeIt(const PathProxy& path) 

 	  : _path(&path), _index(0) {}

 	operator const Edge() const {

 	  return _path->_edges[_index];

 	}

 	EdgeIt& operator++() {

 	  ++_index;

 	  return *this;

 	}

 	bool operator==(Invalid) const { 

 	  return int(_path->_edges.size()) == _index; 

 	}

 	bool operator!=(Invalid) const { 

 	  return int(_path->_edges.size()) != _index; 

 	}

       private:

 	const PathProxy* _path;

 	int _index;

       };

     private:

       const std::vector<Edge>& _edges;

     };

   }

   /// \brief Item reader for paths 

   ///

   /// This class can read paths from files. You can store paths in

   /// distinict mapset or in attributes section.

   ///

   ///\code

   /// GraphReader<SmartGraph> gr(std::cout, g);

   /// NodeMapReader<SmartGraph> nmr(gr, g, gr);

   ///

   /// SmartGraph::NodeMap<Path<SmartGraph> > pnm(g);

   /// nmr.readNodeMap("pnm", pnm, PathReader<Path<SmartGraph> >(gr));

   ///

   /// gr.run();

   ///\endcode

   ///

   /// \warning Do not use this class to read node or edge map values

   /// from nodesets or edgesets. The edges are not surely constructed

   /// when the edge list should be read. Rather use NodeMapReader,

   /// EdgeSetReader or UEdgeSetReader to read distinict map sets from file.

   template <typename Path>

   class PathReader {

   private:

     typedef typename Path::Edge Edge;

     std::auto_ptr<_reader_bits::LabelReaderBase<Edge> > edgeLabelReader;

   public:

     typedef Path Value;

     PathReader(const PathReader& pw) {

       edgeLabelReader.reset(pw.edgeLabelReader->clone());

     }

     /// \brief Constructor

     ///

     /// The paramter shold be an edge label reader which could

     /// be a GraphReader or an EdgeSetReader. 

     template <typename EdgeLabelReader>

     explicit PathReader(const EdgeLabelReader& _edgeLabelReader) {

       edgeLabelReader.reset(new _reader_bits::

 	LabelReader<Edge, EdgeLabelReader>(_edgeLabelReader));

     }

     /// \brief Reader function

     ///

     /// Reads the path from the current stream. The representation

     /// is the edge labels beetween parentheses.

     void read(std::istream& is, Value& value) const {

       if (!edgeLabelReader->isLabelReader()) {

 	throw DataFormatError("Cannot find edgeset or label map");

       }

       char c;

       if (!(is >> c) || c != '(') 

 	throw DataFormatError("PathReader format error");

       std::vector<typename Path::Edge> v;

       while (is >> c && c != ')') {

 	is.putback(c);

 	Edge edge = edgeLabelReader->read(is);

 	v.push_back(edge);

       }

       if (!is) throw DataFormatError("PathReader format error");

       copyPath(value, _path_bits::PathProxy<typename Path::Edge>(v));

     }

   };