/* -*- C++ -*-

 *

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

 *

 * Copyright (C) 2003-2008

 * 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 paths

///\file

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

///

#ifndef LEMON_PATH_UTILS_H

#define LEMON_PATH_UTILS_H

#include <lemon/concepts/path.h>

#include <lemon/lemon_reader.h>

#include <lemon/lemon_writer.h>

namespace lemon {

  namespace _path_bits {

    template <typename Path, typename Enable = void>

    struct RevTagIndicator {

      static const bool value = false;

    };

    template <typename Graph>

    struct RevTagIndicator<

      Graph, 

      typename enable_if<typename Graph::RevTag, void>::type

    > {

      static const bool value = true;

    };

    template <typename Target, typename Source,

              typename BuildEnable = void, typename RevEnable = void>

    struct PathCopySelector {

      static void copy(Target& target, const Source& source) {

        target.clear();

        for (typename Source::EdgeIt it(source); it != INVALID; ++it) {

          target.addBack(it);

        }

      }

    };

    template <typename Target, typename Source, typename BuildEnable>

    struct PathCopySelector<

      Target, Source, BuildEnable, 

      typename enable_if<typename Source::RevPathTag, void>::type> {

      static void copy(Target& target, const Source& source) {

        target.clear();

        for (typename Source::RevEdgeIt it(source); it != INVALID; ++it) {

          target.addFront(it);

        }

      }

    };

    template <typename Target, typename Source, typename RevEnable>

    struct PathCopySelector<

      Target, Source, 

      typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {

      static void copy(Target& target, const Source& source) {

        target.clear();

        target.build(source);

      }

    };

    template <typename Target, typename Source>

    struct PathCopySelector<

      Target, Source, 

      typename enable_if<typename Target::BuildTag, void>::type,

      typename enable_if<typename Source::RevPathTag, void>::type> {

      static void copy(Target& target, const Source& source) {

        target.clear();

        target.buildRev(source);

      }

    };

  }

  /// \brief Make of copy of a path.

  ///

  ///  Make of copy of a path.

  template <typename Target, typename Source>

  void copyPath(Target& target, const Source& source) {

    checkConcept<concepts::PathDumper<typename Source::Graph>, Source>();

    _path_bits::PathCopySelector<Target, Source>::copy(target, source);

  }

  /// \brief Checks the path's consistency.

  ///

  /// Checks that each edge's target is the next's source. 

  /// 

  template <typename Graph, typename Path>

  bool checkPath(const Graph& graph, const Path& path) {

    typename Path::EdgeIt it(path);

    if (it == INVALID) return true;

    typename Graph::Node node = graph.target(it);

    ++it;

    while (it != INVALID) {

      if (graph.source(it) != node) return false;

      node = graph.target(it);

      ++it;

    }

    return true;

  }

  /// \brief Gives back the source of the path

  ///

  /// Gives back the source of the path.

  template <typename Graph, typename Path>

  typename Graph::Node pathSource(const Graph& graph, const Path& path) {

    return graph.source(path.front());

  }

  /// \brief Gives back the target of the path

  ///

  /// Gives back the target of the path.

  template <typename Graph, typename Path>

  typename Graph::Node pathTarget(const Graph& graph, const Path& path) {

    return graph.target(path.back());

  }

  /// \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));

    }

  };

}

#endif