alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@100:  *
alpar@209:  * This file is a part of LEMON, a generic C++ optimization library.
alpar@100:  *
alpar@440:  * Copyright (C) 2003-2009
alpar@100:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@100:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@100:  *
alpar@100:  * Permission to use, modify and distribute this software is granted
alpar@100:  * provided that this copyright notice appears in all copies. For
alpar@100:  * precise terms see the accompanying LICENSE file.
alpar@100:  *
alpar@100:  * This software is provided "AS IS" with no warranty of any kind,
alpar@100:  * express or implied, and with no claim as to its suitability for any
alpar@100:  * purpose.
alpar@100:  *
alpar@100:  */
alpar@100: 
alpar@100: #ifndef LEMON_BITS_PRED_MAP_PATH_H
alpar@100: #define LEMON_BITS_PRED_MAP_PATH_H
alpar@100: 
deba@519: #include <lemon/core.h>
deba@519: #include <lemon/concept_check.h>
deba@519: 
alpar@100: namespace lemon {
alpar@100: 
alpar@100:   template <typename _Digraph, typename _PredMap>
alpar@100:   class PredMapPath {
alpar@100:   public:
alpar@100:     typedef True RevPathTag;
alpar@100: 
alpar@100:     typedef _Digraph Digraph;
alpar@100:     typedef typename Digraph::Arc Arc;
alpar@100:     typedef _PredMap PredMap;
alpar@100: 
alpar@100:     PredMapPath(const Digraph& _digraph, const PredMap& _predMap,
alpar@100:                 typename Digraph::Node _target)
alpar@100:       : digraph(_digraph), predMap(_predMap), target(_target) {}
alpar@100: 
alpar@100:     int length() const {
alpar@100:       int len = 0;
alpar@100:       typename Digraph::Node node = target;
alpar@100:       typename Digraph::Arc arc;
alpar@100:       while ((arc = predMap[node]) != INVALID) {
alpar@100:         node = digraph.source(arc);
alpar@100:         ++len;
alpar@100:       }
alpar@100:       return len;
alpar@100:     }
alpar@100: 
alpar@100:     bool empty() const {
alpar@100:       return predMap[target] != INVALID;
alpar@100:     }
alpar@100: 
alpar@100:     class RevArcIt {
alpar@100:     public:
alpar@100:       RevArcIt() {}
alpar@100:       RevArcIt(Invalid) : path(0), current(INVALID) {}
alpar@209:       RevArcIt(const PredMapPath& _path)
alpar@100:         : path(&_path), current(_path.target) {
alpar@100:         if (path->predMap[current] == INVALID) current = INVALID;
alpar@100:       }
alpar@100: 
alpar@100:       operator const typename Digraph::Arc() const {
alpar@100:         return path->predMap[current];
alpar@100:       }
alpar@100: 
alpar@100:       RevArcIt& operator++() {
alpar@100:         current = path->digraph.source(path->predMap[current]);
alpar@100:         if (path->predMap[current] == INVALID) current = INVALID;
alpar@100:         return *this;
alpar@100:       }
alpar@100: 
alpar@209:       bool operator==(const RevArcIt& e) const {
alpar@209:         return current == e.current;
alpar@100:       }
alpar@100: 
alpar@100:       bool operator!=(const RevArcIt& e) const {
alpar@209:         return current != e.current;
alpar@100:       }
alpar@100: 
alpar@209:       bool operator<(const RevArcIt& e) const {
alpar@209:         return current < e.current;
alpar@100:       }
alpar@209: 
alpar@100:     private:
alpar@100:       const PredMapPath* path;
alpar@100:       typename Digraph::Node current;
alpar@100:     };
alpar@100: 
alpar@100:   private:
alpar@100:     const Digraph& digraph;
alpar@100:     const PredMap& predMap;
alpar@100:     typename Digraph::Node target;
alpar@100:   };
alpar@100: 
alpar@100: 
alpar@100:   template <typename _Digraph, typename _PredMatrixMap>
alpar@100:   class PredMatrixMapPath {
alpar@100:   public:
alpar@100:     typedef True RevPathTag;
alpar@100: 
alpar@100:     typedef _Digraph Digraph;
alpar@100:     typedef typename Digraph::Arc Arc;
alpar@100:     typedef _PredMatrixMap PredMatrixMap;
alpar@100: 
alpar@209:     PredMatrixMapPath(const Digraph& _digraph,
alpar@100:                       const PredMatrixMap& _predMatrixMap,
alpar@209:                       typename Digraph::Node _source,
alpar@100:                       typename Digraph::Node _target)
alpar@209:       : digraph(_digraph), predMatrixMap(_predMatrixMap),
alpar@100:         source(_source), target(_target) {}
alpar@100: 
alpar@100:     int length() const {
alpar@100:       int len = 0;
alpar@100:       typename Digraph::Node node = target;
alpar@100:       typename Digraph::Arc arc;
alpar@100:       while ((arc = predMatrixMap(source, node)) != INVALID) {
alpar@100:         node = digraph.source(arc);
alpar@100:         ++len;
alpar@100:       }
alpar@100:       return len;
alpar@100:     }
alpar@100: 
alpar@100:     bool empty() const {
alpar@100:       return source != target;
alpar@100:     }
alpar@100: 
alpar@100:     class RevArcIt {
alpar@100:     public:
alpar@100:       RevArcIt() {}
alpar@100:       RevArcIt(Invalid) : path(0), current(INVALID) {}
alpar@209:       RevArcIt(const PredMatrixMapPath& _path)
alpar@100:         : path(&_path), current(_path.target) {
alpar@209:         if (path->predMatrixMap(path->source, current) == INVALID)
alpar@100:           current = INVALID;
alpar@100:       }
alpar@100: 
alpar@100:       operator const typename Digraph::Arc() const {
alpar@100:         return path->predMatrixMap(path->source, current);
alpar@100:       }
alpar@100: 
alpar@100:       RevArcIt& operator++() {
alpar@209:         current =
alpar@100:           path->digraph.source(path->predMatrixMap(path->source, current));
alpar@209:         if (path->predMatrixMap(path->source, current) == INVALID)
alpar@100:           current = INVALID;
alpar@100:         return *this;
alpar@100:       }
alpar@100: 
alpar@209:       bool operator==(const RevArcIt& e) const {
alpar@209:         return current == e.current;
alpar@100:       }
alpar@100: 
alpar@100:       bool operator!=(const RevArcIt& e) const {
alpar@209:         return current != e.current;
alpar@100:       }
alpar@100: 
alpar@209:       bool operator<(const RevArcIt& e) const {
alpar@209:         return current < e.current;
alpar@100:       }
alpar@209: 
alpar@100:     private:
alpar@100:       const PredMatrixMapPath* path;
alpar@100:       typename Digraph::Node current;
alpar@100:     };
alpar@100: 
alpar@100:   private:
alpar@100:     const Digraph& digraph;
alpar@100:     const PredMatrixMap& predMatrixMap;
alpar@100:     typename Digraph::Node source;
alpar@100:     typename Digraph::Node target;
alpar@100:   };
alpar@100: 
alpar@100: }
alpar@100: 
alpar@100: #endif