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

 *

 */

#ifndef LEMON_BITS_PRED_MAP_PATH_H

#define LEMON_BITS_PRED_MAP_PATH_H

namespace lemon {

  template <typename _Graph, typename _PredMap>

  class PredMapPath {

  public:

    typedef True RevPathTag;

    typedef _Graph Graph;

    typedef typename Graph::Edge Edge;

    typedef _PredMap PredMap;

    PredMapPath(const Graph& _graph, const PredMap& _predMap,

                typename Graph::Node _target)

      : graph(_graph), predMap(_predMap), target(_target) {}

    int length() const {

      int len = 0;

      typename Graph::Node node = target;

      typename Graph::Edge edge;

      while ((edge = predMap[node]) != INVALID) {

        node = graph.source(edge);

        ++len;

      }

      return len;

    }

    bool empty() const {

      return predMap[target] != INVALID;

    }

    class RevIt {

    public:

      RevIt() {}

      RevIt(Invalid) : path(0), current(INVALID) {}

      RevIt(const PredMapPath& _path) 

        : path(&_path), current(_path.target) {}

      operator const typename Graph::Edge() const {

        return path->predMap[current];

      }

      RevIt& operator++() {

        current = path->graph.source(path->predMap[current]);

        if (path->predMap[current] == INVALID) current = INVALID;

        return *this;

      }

      bool operator==(const RevIt& e) const { 

        return current == e.current; 

      }

      bool operator!=(const RevIt& e) const {

        return current != e.current; 

      }

      bool operator<(const RevIt& e) const { 

        return current < e.current; 

      }

    private:

      const PredMapPath* path;

      typename Graph::Node current;

    };

  private:

    const Graph& graph;

    const PredMap& predMap;

    typename Graph::Node target;

  };

  template <typename _Graph, typename _PredMatrixMap>

  class PredMatrixMapPath {

  public:

    typedef True RevPathTag;

    typedef _Graph Graph;

    typedef typename Graph::Edge Edge;

    typedef _PredMatrixMap PredMatrixMap;

    PredMatrixMapPath(const Graph& _graph, 

                      const PredMatrixMap& _predMatrixMap,

                      typename Graph::Node _source, 

                      typename Graph::Node _target)

      : graph(_graph), predMatrixMap(_predMatrixMap), 

        source(_source), target(_target) {}

    int length() const {

      int len = 0;

      typename Graph::Node node = target;

      typename Graph::Edge edge;

      while ((edge = predMatrixMap(source, node)) != INVALID) {

        node = graph.source(edge);

        ++len;

      }

      return len;

    }

    bool empty() const {

      return source != target;

    }

    class RevIt {

    public:

      RevIt() {}

      RevIt(Invalid) : path(0), current(INVALID) {}

      RevIt(const PredMatrixMapPath& _path) 

        : path(&_path), current(_path.target) {}

      operator const typename Graph::Edge() const {

        return path->predMatrixMap(path->source, current);

      }

      RevIt& operator++() {

        current = 

          path->graph.source(path->predMatrixMap(path->source, current));

        if (path->predMatrixMap(path->source, current) == INVALID) 

          current = INVALID;

        return *this;

      }

      bool operator==(const RevIt& e) const { 

        return current == e.current; 

      }

      bool operator!=(const RevIt& e) const {

        return current != e.current; 

      }

      bool operator<(const RevIt& e) const { 

        return current < e.current; 

      }

    private:

      const PredMatrixMapPath* path;

      typename Graph::Node current;

    };

  private:

    const Graph& graph;

    const PredMatrixMap& predMatrixMap;

    typename Graph::Node source;

    typename Graph::Node target;

  };

}

#endif