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