alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@96:  *
alpar@209:  * This file is a part of LEMON, a generic C++ optimization library.
alpar@96:  *
alpar@440:  * Copyright (C) 2003-2009
alpar@96:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@96:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@96:  *
alpar@96:  * Permission to use, modify and distribute this software is granted
alpar@96:  * provided that this copyright notice appears in all copies. For
alpar@96:  * precise terms see the accompanying LICENSE file.
alpar@96:  *
alpar@96:  * This software is provided "AS IS" with no warranty of any kind,
alpar@96:  * express or implied, and with no claim as to its suitability for any
alpar@96:  * purpose.
alpar@96:  *
alpar@96:  */
alpar@96: 
alpar@96: ///\ingroup paths
alpar@96: ///\file
alpar@96: ///\brief Classes for representing paths in digraphs.
alpar@96: ///
alpar@96: 
alpar@96: #ifndef LEMON_PATH_H
alpar@96: #define LEMON_PATH_H
alpar@96: 
alpar@96: #include <vector>
alpar@96: #include <algorithm>
alpar@96: 
alpar@96: #include <lemon/error.h>
deba@220: #include <lemon/core.h>
alpar@100: #include <lemon/concepts/path.h>
alpar@96: 
alpar@96: namespace lemon {
alpar@96: 
alpar@96:   /// \addtogroup paths
alpar@96:   /// @{
alpar@96: 
alpar@96: 
alpar@96:   /// \brief A structure for representing directed paths in a digraph.
alpar@96:   ///
alpar@96:   /// A structure for representing directed path in a digraph.
kpeter@559:   /// \tparam GR The digraph type in which the path is.
alpar@96:   ///
alpar@96:   /// In a sense, the path can be treated as a list of arcs. The
alpar@97:   /// lemon path type stores just this list. As a consequence, it
alpar@97:   /// cannot enumerate the nodes of the path and the source node of
alpar@97:   /// a zero length path is undefined.
alpar@96:   ///
alpar@96:   /// This implementation is a back and front insertable and erasable
alpar@96:   /// path type. It can be indexed in O(1) time. The front and back
alpar@97:   /// insertion and erase is done in O(1) (amortized) time. The
alpar@97:   /// implementation uses two vectors for storing the front and back
alpar@97:   /// insertions.
kpeter@559:   template <typename GR>
alpar@96:   class Path {
alpar@96:   public:
alpar@96: 
kpeter@559:     typedef GR Digraph;
alpar@96:     typedef typename Digraph::Arc Arc;
alpar@96: 
alpar@96:     /// \brief Default constructor
alpar@96:     ///
alpar@96:     /// Default constructor
alpar@96:     Path() {}
alpar@96: 
alpar@96:     /// \brief Template copy constructor
alpar@96:     ///
alpar@97:     /// This constuctor initializes the path from any other path type.
alpar@97:     /// It simply makes a copy of the given path.
alpar@96:     template <typename CPath>
alpar@96:     Path(const CPath& cpath) {
alpar@96:       copyPath(*this, cpath);
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Template copy assignment
alpar@96:     ///
alpar@97:     /// This operator makes a copy of a path of any other type.
alpar@96:     template <typename CPath>
alpar@96:     Path& operator=(const CPath& cpath) {
alpar@96:       copyPath(*this, cpath);
alpar@96:       return *this;
alpar@96:     }
alpar@96: 
ladanyi@236:     /// \brief LEMON style iterator for path arcs
alpar@96:     ///
alpar@96:     /// This class is used to iterate on the arcs of the paths.
alpar@96:     class ArcIt {
alpar@96:       friend class Path;
alpar@96:     public:
alpar@96:       /// \brief Default constructor
alpar@96:       ArcIt() {}
alpar@96:       /// \brief Invalid constructor
alpar@96:       ArcIt(Invalid) : path(0), idx(-1) {}
alpar@97:       /// \brief Initializate the iterator to the first arc of path
alpar@209:       ArcIt(const Path &_path)
alpar@96:         : path(&_path), idx(_path.empty() ? -1 : 0) {}
alpar@96: 
alpar@96:     private:
alpar@96: 
alpar@209:       ArcIt(const Path &_path, int _idx)
alpar@96:         : path(&_path), idx(_idx) {}
alpar@96: 
alpar@96:     public:
alpar@96: 
alpar@96:       /// \brief Conversion to Arc
alpar@96:       operator const Arc&() const {
alpar@96:         return path->nth(idx);
alpar@96:       }
alpar@96: 
alpar@96:       /// \brief Next arc
alpar@209:       ArcIt& operator++() {
alpar@96:         ++idx;
alpar@209:         if (idx >= path->length()) idx = -1;
alpar@209:         return *this;
alpar@96:       }
alpar@96: 
alpar@96:       /// \brief Comparison operator
alpar@96:       bool operator==(const ArcIt& e) const { return idx==e.idx; }
alpar@96:       /// \brief Comparison operator
alpar@96:       bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
alpar@96:       /// \brief Comparison operator
alpar@96:       bool operator<(const ArcIt& e) const { return idx<e.idx; }
alpar@96: 
alpar@96:     private:
alpar@96:       const Path *path;
alpar@96:       int idx;
alpar@96:     };
alpar@96: 
alpar@96:     /// \brief Length of the path.
alpar@96:     int length() const { return head.size() + tail.size(); }
alpar@97:     /// \brief Return whether the path is empty.
alpar@96:     bool empty() const { return head.empty() && tail.empty(); }
alpar@96: 
alpar@97:     /// \brief Reset the path to an empty one.
alpar@96:     void clear() { head.clear(); tail.clear(); }
alpar@96: 
alpar@97:     /// \brief The nth arc.
alpar@96:     ///
kpeter@559:     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
alpar@96:     const Arc& nth(int n) const {
alpar@96:       return n < int(head.size()) ? *(head.rbegin() + n) :
alpar@96:         *(tail.begin() + (n - head.size()));
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief Initialize arc iterator to point to the nth arc
alpar@96:     ///
kpeter@559:     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
alpar@96:     ArcIt nthIt(int n) const {
alpar@96:       return ArcIt(*this, n);
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief The first arc of the path
alpar@96:     const Arc& front() const {
alpar@96:       return head.empty() ? tail.front() : head.back();
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Add a new arc before the current path
alpar@96:     void addFront(const Arc& arc) {
alpar@96:       head.push_back(arc);
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Erase the first arc of the path
alpar@96:     void eraseFront() {
alpar@96:       if (!head.empty()) {
alpar@96:         head.pop_back();
alpar@96:       } else {
alpar@96:         head.clear();
alpar@96:         int halfsize = tail.size() / 2;
alpar@96:         head.resize(halfsize);
alpar@96:         std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
alpar@96:                   head.rbegin());
alpar@96:         std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
alpar@96:         tail.resize(tail.size() - halfsize - 1);
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief The last arc of the path
alpar@96:     const Arc& back() const {
alpar@96:       return tail.empty() ? head.front() : tail.back();
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Add a new arc behind the current path
alpar@96:     void addBack(const Arc& arc) {
alpar@96:       tail.push_back(arc);
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Erase the last arc of the path
alpar@96:     void eraseBack() {
alpar@96:       if (!tail.empty()) {
alpar@96:         tail.pop_back();
alpar@96:       } else {
alpar@96:         int halfsize = head.size() / 2;
alpar@96:         tail.resize(halfsize);
alpar@96:         std::copy(head.begin() + 1, head.begin() + halfsize + 1,
alpar@96:                   tail.rbegin());
alpar@96:         std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
alpar@96:         head.resize(head.size() - halfsize - 1);
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@96:     typedef True BuildTag;
alpar@96: 
alpar@96:     template <typename CPath>
alpar@96:     void build(const CPath& path) {
alpar@96:       int len = path.length();
alpar@96:       tail.reserve(len);
alpar@96:       for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
alpar@96:         tail.push_back(it);
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@96:     template <typename CPath>
alpar@96:     void buildRev(const CPath& path) {
alpar@96:       int len = path.length();
alpar@96:       head.reserve(len);
alpar@96:       for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
alpar@96:         head.push_back(it);
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@96:   protected:
alpar@96:     typedef std::vector<Arc> Container;
alpar@96:     Container head, tail;
alpar@96: 
alpar@96:   };
alpar@96: 
alpar@96:   /// \brief A structure for representing directed paths in a digraph.
alpar@96:   ///
alpar@96:   /// A structure for representing directed path in a digraph.
kpeter@559:   /// \tparam GR The digraph type in which the path is.
alpar@96:   ///
alpar@96:   /// In a sense, the path can be treated as a list of arcs. The
alpar@96:   /// lemon path type stores just this list. As a consequence it
alpar@96:   /// cannot enumerate the nodes in the path and the zero length paths
alpar@96:   /// cannot store the source.
alpar@96:   ///
alpar@96:   /// This implementation is a just back insertable and erasable path
alpar@96:   /// type. It can be indexed in O(1) time. The back insertion and
alpar@96:   /// erasure is amortized O(1) time. This implementation is faster
alpar@96:   /// then the \c Path type because it use just one vector for the
alpar@96:   /// arcs.
kpeter@559:   template <typename GR>
alpar@96:   class SimplePath {
alpar@96:   public:
alpar@96: 
kpeter@559:     typedef GR Digraph;
alpar@96:     typedef typename Digraph::Arc Arc;
alpar@96: 
alpar@96:     /// \brief Default constructor
alpar@96:     ///
alpar@96:     /// Default constructor
alpar@96:     SimplePath() {}
alpar@96: 
alpar@96:     /// \brief Template copy constructor
alpar@96:     ///
alpar@96:     /// This path can be initialized with any other path type. It just
alpar@96:     /// makes a copy of the given path.
alpar@96:     template <typename CPath>
alpar@96:     SimplePath(const CPath& cpath) {
alpar@96:       copyPath(*this, cpath);
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Template copy assignment
alpar@96:     ///
alpar@96:     /// This path can be initialized with any other path type. It just
alpar@96:     /// makes a copy of the given path.
alpar@96:     template <typename CPath>
alpar@96:     SimplePath& operator=(const CPath& cpath) {
alpar@96:       copyPath(*this, cpath);
alpar@96:       return *this;
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Iterator class to iterate on the arcs of the paths
alpar@96:     ///
alpar@96:     /// This class is used to iterate on the arcs of the paths
alpar@96:     ///
alpar@96:     /// Of course it converts to Digraph::Arc
alpar@96:     class ArcIt {
alpar@96:       friend class SimplePath;
alpar@96:     public:
alpar@96:       /// Default constructor
alpar@96:       ArcIt() {}
alpar@96:       /// Invalid constructor
alpar@96:       ArcIt(Invalid) : path(0), idx(-1) {}
alpar@96:       /// \brief Initializate the constructor to the first arc of path
alpar@209:       ArcIt(const SimplePath &_path)
alpar@96:         : path(&_path), idx(_path.empty() ? -1 : 0) {}
alpar@96: 
alpar@96:     private:
alpar@96: 
alpar@96:       /// Constructor with starting point
alpar@209:       ArcIt(const SimplePath &_path, int _idx)
alpar@96:         : idx(_idx), path(&_path) {}
alpar@96: 
alpar@96:     public:
alpar@96: 
alpar@96:       ///Conversion to Digraph::Arc
alpar@96:       operator const Arc&() const {
alpar@96:         return path->nth(idx);
alpar@96:       }
alpar@96: 
alpar@96:       /// Next arc
alpar@209:       ArcIt& operator++() {
alpar@96:         ++idx;
alpar@209:         if (idx >= path->length()) idx = -1;
alpar@209:         return *this;
alpar@96:       }
alpar@96: 
alpar@96:       /// Comparison operator
alpar@96:       bool operator==(const ArcIt& e) const { return idx==e.idx; }
alpar@96:       /// Comparison operator
alpar@96:       bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
alpar@96:       /// Comparison operator
alpar@96:       bool operator<(const ArcIt& e) const { return idx<e.idx; }
alpar@96: 
alpar@96:     private:
alpar@96:       const SimplePath *path;
alpar@96:       int idx;
alpar@96:     };
alpar@96: 
alpar@96:     /// \brief Length of the path.
alpar@96:     int length() const { return data.size(); }
alpar@97:     /// \brief Return true if the path is empty.
alpar@96:     bool empty() const { return data.empty(); }
alpar@96: 
alpar@97:     /// \brief Reset the path to an empty one.
alpar@96:     void clear() { data.clear(); }
alpar@96: 
alpar@97:     /// \brief The nth arc.
alpar@96:     ///
kpeter@559:     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
alpar@96:     const Arc& nth(int n) const {
alpar@96:       return data[n];
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief  Initializes arc iterator to point to the nth arc.
alpar@96:     ArcIt nthIt(int n) const {
alpar@96:       return ArcIt(*this, n);
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief The first arc of the path.
alpar@96:     const Arc& front() const {
alpar@96:       return data.front();
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief The last arc of the path.
alpar@96:     const Arc& back() const {
alpar@96:       return data.back();
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Add a new arc behind the current path.
alpar@96:     void addBack(const Arc& arc) {
alpar@96:       data.push_back(arc);
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Erase the last arc of the path
alpar@96:     void eraseBack() {
alpar@96:       data.pop_back();
alpar@96:     }
alpar@96: 
alpar@96:     typedef True BuildTag;
alpar@96: 
alpar@96:     template <typename CPath>
alpar@96:     void build(const CPath& path) {
alpar@96:       int len = path.length();
alpar@96:       data.resize(len);
alpar@96:       int index = 0;
alpar@96:       for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
alpar@96:         data[index] = it;;
alpar@96:         ++index;
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@96:     template <typename CPath>
alpar@96:     void buildRev(const CPath& path) {
alpar@96:       int len = path.length();
alpar@96:       data.resize(len);
alpar@96:       int index = len;
alpar@96:       for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
alpar@96:         --index;
alpar@96:         data[index] = it;;
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@96:   protected:
alpar@96:     typedef std::vector<Arc> Container;
alpar@96:     Container data;
alpar@96: 
alpar@96:   };
alpar@96: 
alpar@96:   /// \brief A structure for representing directed paths in a digraph.
alpar@96:   ///
alpar@96:   /// A structure for representing directed path in a digraph.
kpeter@559:   /// \tparam GR The digraph type in which the path is.
alpar@96:   ///
alpar@96:   /// In a sense, the path can be treated as a list of arcs. The
alpar@96:   /// lemon path type stores just this list. As a consequence it
alpar@96:   /// cannot enumerate the nodes in the path and the zero length paths
alpar@96:   /// cannot store the source.
alpar@96:   ///
alpar@96:   /// This implementation is a back and front insertable and erasable
alpar@96:   /// path type. It can be indexed in O(k) time, where k is the rank
alpar@96:   /// of the arc in the path. The length can be computed in O(n)
alpar@96:   /// time. The front and back insertion and erasure is O(1) time
alpar@96:   /// and it can be splited and spliced in O(1) time.
kpeter@559:   template <typename GR>
alpar@96:   class ListPath {
alpar@96:   public:
alpar@96: 
kpeter@559:     typedef GR Digraph;
alpar@96:     typedef typename Digraph::Arc Arc;
alpar@96: 
alpar@96:   protected:
alpar@96: 
alpar@209:     // the std::list<> is incompatible
alpar@96:     // hard to create invalid iterator
alpar@96:     struct Node {
alpar@96:       Arc arc;
alpar@96:       Node *next, *prev;
alpar@96:     };
alpar@96: 
alpar@96:     Node *first, *last;
alpar@96: 
alpar@96:     std::allocator<Node> alloc;
alpar@96: 
alpar@96:   public:
alpar@209: 
alpar@96:     /// \brief Default constructor
alpar@96:     ///
alpar@96:     /// Default constructor
alpar@96:     ListPath() : first(0), last(0) {}
alpar@96: 
alpar@96:     /// \brief Template copy constructor
alpar@96:     ///
alpar@96:     /// This path can be initialized with any other path type. It just
alpar@96:     /// makes a copy of the given path.
alpar@96:     template <typename CPath>
alpar@96:     ListPath(const CPath& cpath) : first(0), last(0) {
alpar@96:       copyPath(*this, cpath);
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Destructor of the path
alpar@96:     ///
alpar@96:     /// Destructor of the path
alpar@96:     ~ListPath() {
alpar@96:       clear();
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Template copy assignment
alpar@96:     ///
alpar@96:     /// This path can be initialized with any other path type. It just
alpar@96:     /// makes a copy of the given path.
alpar@96:     template <typename CPath>
alpar@96:     ListPath& operator=(const CPath& cpath) {
alpar@96:       copyPath(*this, cpath);
alpar@96:       return *this;
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Iterator class to iterate on the arcs of the paths
alpar@96:     ///
alpar@96:     /// This class is used to iterate on the arcs of the paths
alpar@96:     ///
alpar@96:     /// Of course it converts to Digraph::Arc
alpar@96:     class ArcIt {
alpar@96:       friend class ListPath;
alpar@96:     public:
alpar@96:       /// Default constructor
alpar@96:       ArcIt() {}
alpar@96:       /// Invalid constructor
alpar@96:       ArcIt(Invalid) : path(0), node(0) {}
alpar@96:       /// \brief Initializate the constructor to the first arc of path
alpar@209:       ArcIt(const ListPath &_path)
alpar@96:         : path(&_path), node(_path.first) {}
alpar@96: 
alpar@96:     protected:
alpar@96: 
alpar@209:       ArcIt(const ListPath &_path, Node *_node)
alpar@96:         : path(&_path), node(_node) {}
alpar@96: 
alpar@96: 
alpar@96:     public:
alpar@96: 
alpar@96:       ///Conversion to Digraph::Arc
alpar@96:       operator const Arc&() const {
alpar@96:         return node->arc;
alpar@96:       }
alpar@96: 
alpar@96:       /// Next arc
alpar@209:       ArcIt& operator++() {
alpar@96:         node = node->next;
alpar@209:         return *this;
alpar@96:       }
alpar@96: 
alpar@96:       /// Comparison operator
alpar@96:       bool operator==(const ArcIt& e) const { return node==e.node; }
alpar@96:       /// Comparison operator
alpar@96:       bool operator!=(const ArcIt& e) const { return node!=e.node; }
alpar@96:       /// Comparison operator
alpar@96:       bool operator<(const ArcIt& e) const { return node<e.node; }
alpar@96: 
alpar@96:     private:
alpar@96:       const ListPath *path;
alpar@96:       Node *node;
alpar@96:     };
alpar@96: 
alpar@97:     /// \brief The nth arc.
alpar@96:     ///
alpar@97:     /// This function looks for the nth arc in O(n) time.
kpeter@559:     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
alpar@96:     const Arc& nth(int n) const {
alpar@96:       Node *node = first;
alpar@96:       for (int i = 0; i < n; ++i) {
alpar@96:         node = node->next;
alpar@96:       }
alpar@96:       return node->arc;
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Initializes arc iterator to point to the nth arc.
alpar@96:     ArcIt nthIt(int n) const {
alpar@96:       Node *node = first;
alpar@96:       for (int i = 0; i < n; ++i) {
alpar@96:         node = node->next;
alpar@96:       }
alpar@96:       return ArcIt(*this, node);
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Length of the path.
alpar@96:     int length() const {
alpar@96:       int len = 0;
alpar@96:       Node *node = first;
alpar@96:       while (node != 0) {
alpar@96:         node = node->next;
alpar@96:         ++len;
alpar@96:       }
alpar@96:       return len;
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief Return true if the path is empty.
alpar@96:     bool empty() const { return first == 0; }
alpar@96: 
alpar@97:     /// \brief Reset the path to an empty one.
alpar@96:     void clear() {
alpar@96:       while (first != 0) {
alpar@96:         last = first->next;
alpar@96:         alloc.destroy(first);
alpar@96:         alloc.deallocate(first, 1);
alpar@96:         first = last;
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief The first arc of the path
alpar@96:     const Arc& front() const {
alpar@96:       return first->arc;
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Add a new arc before the current path
alpar@96:     void addFront(const Arc& arc) {
alpar@96:       Node *node = alloc.allocate(1);
alpar@96:       alloc.construct(node, Node());
alpar@96:       node->prev = 0;
alpar@96:       node->next = first;
alpar@96:       node->arc = arc;
alpar@96:       if (first) {
alpar@96:         first->prev = node;
alpar@96:         first = node;
alpar@96:       } else {
alpar@96:         first = last = node;
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Erase the first arc of the path
alpar@96:     void eraseFront() {
alpar@96:       Node *node = first;
alpar@96:       first = first->next;
alpar@96:       if (first) {
alpar@96:         first->prev = 0;
alpar@96:       } else {
alpar@96:         last = 0;
alpar@96:       }
alpar@96:       alloc.destroy(node);
alpar@96:       alloc.deallocate(node, 1);
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief The last arc of the path.
alpar@96:     const Arc& back() const {
alpar@96:       return last->arc;
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Add a new arc behind the current path.
alpar@96:     void addBack(const Arc& arc) {
alpar@96:       Node *node = alloc.allocate(1);
alpar@96:       alloc.construct(node, Node());
alpar@96:       node->next = 0;
alpar@96:       node->prev = last;
alpar@96:       node->arc = arc;
alpar@96:       if (last) {
alpar@96:         last->next = node;
alpar@96:         last = node;
alpar@96:       } else {
alpar@96:         last = first = node;
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Erase the last arc of the path
alpar@96:     void eraseBack() {
alpar@96:       Node *node = last;
alpar@96:       last = last->prev;
alpar@96:       if (last) {
alpar@96:         last->next = 0;
alpar@96:       } else {
alpar@96:         first = 0;
alpar@96:       }
alpar@96:       alloc.destroy(node);
alpar@96:       alloc.deallocate(node, 1);
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief Splice a path to the back of the current path.
alpar@96:     ///
alpar@97:     /// It splices \c tpath to the back of the current path and \c
alpar@96:     /// tpath becomes empty. The time complexity of this function is
alpar@96:     /// O(1).
alpar@96:     void spliceBack(ListPath& tpath) {
alpar@96:       if (first) {
alpar@96:         if (tpath.first) {
alpar@96:           last->next = tpath.first;
alpar@96:           tpath.first->prev = last;
alpar@96:           last = tpath.last;
alpar@96:         }
alpar@96:       } else {
alpar@96:         first = tpath.first;
alpar@96:         last = tpath.last;
alpar@96:       }
alpar@96:       tpath.first = tpath.last = 0;
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief Splice a path to the front of the current path.
alpar@96:     ///
alpar@97:     /// It splices \c tpath before the current path and \c tpath
alpar@96:     /// becomes empty. The time complexity of this function
alpar@96:     /// is O(1).
alpar@96:     void spliceFront(ListPath& tpath) {
alpar@96:       if (first) {
alpar@96:         if (tpath.first) {
alpar@96:           first->prev = tpath.last;
alpar@96:           tpath.last->next = first;
alpar@96:           first = tpath.first;
alpar@96:         }
alpar@96:       } else {
alpar@96:         first = tpath.first;
alpar@96:         last = tpath.last;
alpar@96:       }
alpar@96:       tpath.first = tpath.last = 0;
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief Splice a path into the current path.
alpar@96:     ///
alpar@96:     /// It splices the \c tpath into the current path before the
alpar@96:     /// position of \c it iterator and \c tpath becomes empty. The
alpar@97:     /// time complexity of this function is O(1). If the \c it is
alpar@97:     /// \c INVALID then it will splice behind the current path.
alpar@96:     void splice(ArcIt it, ListPath& tpath) {
alpar@96:       if (it.node) {
alpar@96:         if (tpath.first) {
alpar@96:           tpath.first->prev = it.node->prev;
alpar@96:           if (it.node->prev) {
alpar@96:             it.node->prev->next = tpath.first;
alpar@96:           } else {
alpar@96:             first = tpath.first;
alpar@96:           }
alpar@96:           it.node->prev = tpath.last;
alpar@96:           tpath.last->next = it.node;
alpar@96:         }
alpar@96:       } else {
alpar@96:         if (first) {
alpar@96:           if (tpath.first) {
alpar@96:             last->next = tpath.first;
alpar@96:             tpath.first->prev = last;
alpar@96:             last = tpath.last;
alpar@96:           }
alpar@96:         } else {
alpar@96:           first = tpath.first;
alpar@96:           last = tpath.last;
alpar@96:         }
alpar@96:       }
alpar@96:       tpath.first = tpath.last = 0;
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief Split the current path.
alpar@96:     ///
alpar@97:     /// It splits the current path into two parts. The part before
alpar@97:     /// the iterator \c it will remain in the current path and the part
alpar@97:     /// starting with
alpar@97:     /// \c it will put into \c tpath. If \c tpath have arcs
alpar@97:     /// before the operation they are removed first.  The time
alpar@97:     /// complexity of this function is O(1) plus the the time of emtying
alpar@97:     /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
alpar@96:     void split(ArcIt it, ListPath& tpath) {
alpar@96:       tpath.clear();
alpar@96:       if (it.node) {
alpar@96:         tpath.first = it.node;
alpar@96:         tpath.last = last;
alpar@96:         if (it.node->prev) {
alpar@96:           last = it.node->prev;
alpar@96:           last->next = 0;
alpar@96:         } else {
alpar@96:           first = last = 0;
alpar@96:         }
alpar@96:         it.node->prev = 0;
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@96: 
alpar@96:     typedef True BuildTag;
alpar@96: 
alpar@96:     template <typename CPath>
alpar@96:     void build(const CPath& path) {
alpar@96:       for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
alpar@96:         addBack(it);
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@96:     template <typename CPath>
alpar@96:     void buildRev(const CPath& path) {
alpar@96:       for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
alpar@96:         addFront(it);
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@96:   };
alpar@96: 
alpar@96:   /// \brief A structure for representing directed paths in a digraph.
alpar@96:   ///
alpar@96:   /// A structure for representing directed path in a digraph.
kpeter@559:   /// \tparam GR The digraph type in which the path is.
alpar@96:   ///
alpar@96:   /// In a sense, the path can be treated as a list of arcs. The
alpar@96:   /// lemon path type stores just this list. As a consequence it
alpar@97:   /// cannot enumerate the nodes in the path and the source node of
alpar@97:   /// a zero length path is undefined.
alpar@96:   ///
alpar@97:   /// This implementation is completly static, i.e. it can be copy constucted
alpar@97:   /// or copy assigned from another path, but otherwise it cannot be
alpar@97:   /// modified.
alpar@97:   ///
alpar@97:   /// Being the the most memory efficient path type in LEMON,
alpar@97:   /// it is intented to be
alpar@97:   /// used when you want to store a large number of paths.
kpeter@559:   template <typename GR>
alpar@96:   class StaticPath {
alpar@96:   public:
alpar@96: 
kpeter@559:     typedef GR Digraph;
alpar@96:     typedef typename Digraph::Arc Arc;
alpar@96: 
alpar@96:     /// \brief Default constructor
alpar@96:     ///
alpar@96:     /// Default constructor
alpar@96:     StaticPath() : len(0), arcs(0) {}
alpar@209: 
alpar@96:     /// \brief Template copy constructor
alpar@96:     ///
alpar@97:     /// This path can be initialized from any other path type.
alpar@96:     template <typename CPath>
alpar@96:     StaticPath(const CPath& cpath) : arcs(0) {
alpar@96:       copyPath(*this, cpath);
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Destructor of the path
alpar@96:     ///
alpar@96:     /// Destructor of the path
alpar@96:     ~StaticPath() {
alpar@96:       if (arcs) delete[] arcs;
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Template copy assignment
alpar@96:     ///
alpar@97:     /// This path can be made equal to any other path type. It simply
alpar@96:     /// makes a copy of the given path.
alpar@96:     template <typename CPath>
alpar@96:     StaticPath& operator=(const CPath& cpath) {
alpar@96:       copyPath(*this, cpath);
alpar@96:       return *this;
alpar@96:     }
alpar@96: 
alpar@96:     /// \brief Iterator class to iterate on the arcs of the paths
alpar@96:     ///
alpar@96:     /// This class is used to iterate on the arcs of the paths
alpar@96:     ///
alpar@96:     /// Of course it converts to Digraph::Arc
alpar@96:     class ArcIt {
alpar@96:       friend class StaticPath;
alpar@96:     public:
alpar@96:       /// Default constructor
alpar@96:       ArcIt() {}
alpar@96:       /// Invalid constructor
alpar@96:       ArcIt(Invalid) : path(0), idx(-1) {}
alpar@96:       /// Initializate the constructor to the first arc of path
alpar@209:       ArcIt(const StaticPath &_path)
alpar@96:         : path(&_path), idx(_path.empty() ? -1 : 0) {}
alpar@96: 
alpar@96:     private:
alpar@96: 
alpar@96:       /// Constructor with starting point
alpar@209:       ArcIt(const StaticPath &_path, int _idx)
alpar@96:         : idx(_idx), path(&_path) {}
alpar@96: 
alpar@96:     public:
alpar@96: 
alpar@96:       ///Conversion to Digraph::Arc
alpar@96:       operator const Arc&() const {
alpar@96:         return path->nth(idx);
alpar@96:       }
alpar@96: 
alpar@96:       /// Next arc
alpar@209:       ArcIt& operator++() {
alpar@96:         ++idx;
alpar@209:         if (idx >= path->length()) idx = -1;
alpar@209:         return *this;
alpar@96:       }
alpar@96: 
alpar@96:       /// Comparison operator
alpar@96:       bool operator==(const ArcIt& e) const { return idx==e.idx; }
alpar@96:       /// Comparison operator
alpar@96:       bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
alpar@96:       /// Comparison operator
alpar@96:       bool operator<(const ArcIt& e) const { return idx<e.idx; }
alpar@96: 
alpar@96:     private:
alpar@96:       const StaticPath *path;
alpar@96:       int idx;
alpar@96:     };
alpar@96: 
alpar@97:     /// \brief The nth arc.
alpar@96:     ///
kpeter@559:     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
alpar@96:     const Arc& nth(int n) const {
alpar@96:       return arcs[n];
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief The arc iterator pointing to the nth arc.
alpar@96:     ArcIt nthIt(int n) const {
alpar@96:       return ArcIt(*this, n);
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief The length of the path.
alpar@96:     int length() const { return len; }
alpar@96: 
alpar@97:     /// \brief Return true when the path is empty.
alpar@96:     int empty() const { return len == 0; }
alpar@96: 
kpeter@313:     /// \brief Erase all arcs in the digraph.
alpar@96:     void clear() {
alpar@96:       len = 0;
alpar@96:       if (arcs) delete[] arcs;
alpar@96:       arcs = 0;
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief The first arc of the path.
alpar@96:     const Arc& front() const {
alpar@96:       return arcs[0];
alpar@96:     }
alpar@96: 
alpar@97:     /// \brief The last arc of the path.
alpar@96:     const Arc& back() const {
alpar@96:       return arcs[len - 1];
alpar@96:     }
alpar@96: 
alpar@96: 
alpar@96:     typedef True BuildTag;
alpar@96: 
alpar@96:     template <typename CPath>
alpar@96:     void build(const CPath& path) {
alpar@96:       len = path.length();
alpar@96:       arcs = new Arc[len];
alpar@96:       int index = 0;
alpar@96:       for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
alpar@96:         arcs[index] = it;
alpar@96:         ++index;
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@96:     template <typename CPath>
alpar@96:     void buildRev(const CPath& path) {
alpar@96:       len = path.length();
alpar@96:       arcs = new Arc[len];
alpar@96:       int index = len;
alpar@96:       for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
alpar@96:         --index;
alpar@96:         arcs[index] = it;
alpar@96:       }
alpar@96:     }
alpar@96: 
alpar@96:   private:
alpar@96:     int len;
alpar@96:     Arc* arcs;
alpar@96:   };
alpar@96: 
alpar@98:   ///////////////////////////////////////////////////////////////////////
alpar@98:   // Additional utilities
alpar@98:   ///////////////////////////////////////////////////////////////////////
alpar@98: 
alpar@98:   namespace _path_bits {
alpar@98: 
alpar@98:     template <typename Path, typename Enable = void>
deba@144:     struct RevPathTagIndicator {
alpar@98:       static const bool value = false;
alpar@98:     };
alpar@98: 
deba@144:     template <typename Path>
deba@144:     struct RevPathTagIndicator<
alpar@209:       Path,
deba@144:       typename enable_if<typename Path::RevPathTag, void>::type
deba@144:       > {
deba@144:       static const bool value = true;
deba@144:     };
deba@144: 
deba@144:     template <typename Path, typename Enable = void>
deba@144:     struct BuildTagIndicator {
deba@144:       static const bool value = false;
deba@144:     };
deba@144: 
deba@144:     template <typename Path>
deba@144:     struct BuildTagIndicator<
alpar@209:       Path,
deba@144:       typename enable_if<typename Path::BuildTag, void>::type
alpar@98:     > {
alpar@98:       static const bool value = true;
alpar@98:     };
alpar@98: 
alpar@98:     template <typename Target, typename Source,
kpeter@487:               bool buildEnable = BuildTagIndicator<Target>::value>
kpeter@487:     struct PathCopySelectorForward {
alpar@98:       static void copy(Target& target, const Source& source) {
alpar@98:         target.clear();
alpar@98:         for (typename Source::ArcIt it(source); it != INVALID; ++it) {
alpar@98:           target.addBack(it);
alpar@98:         }
alpar@98:       }
alpar@98:     };
alpar@98: 
deba@144:     template <typename Target, typename Source>
kpeter@487:     struct PathCopySelectorForward<Target, Source, true> {
kpeter@487:       static void copy(Target& target, const Source& source) {
kpeter@487:         target.clear();
kpeter@487:         target.build(source);
kpeter@487:       }
kpeter@487:     };
kpeter@487: 
kpeter@487:     template <typename Target, typename Source,
kpeter@487:               bool buildEnable = BuildTagIndicator<Target>::value>
kpeter@487:     struct PathCopySelectorBackward {
alpar@98:       static void copy(Target& target, const Source& source) {
alpar@98:         target.clear();
alpar@98:         for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
alpar@98:           target.addFront(it);
alpar@98:         }
alpar@98:       }
alpar@98:     };
alpar@98: 
deba@144:     template <typename Target, typename Source>
kpeter@487:     struct PathCopySelectorBackward<Target, Source, true> {
alpar@98:       static void copy(Target& target, const Source& source) {
alpar@98:         target.clear();
alpar@98:         target.buildRev(source);
alpar@98:       }
alpar@98:     };
alpar@98: 
kpeter@487:     
kpeter@487:     template <typename Target, typename Source,
kpeter@487:               bool revEnable = RevPathTagIndicator<Source>::value>
kpeter@487:     struct PathCopySelector {
kpeter@487:       static void copy(Target& target, const Source& source) {
kpeter@487:         PathCopySelectorForward<Target, Source>::copy(target, source);
kpeter@487:       }      
kpeter@487:     };
kpeter@487: 
kpeter@487:     template <typename Target, typename Source>
kpeter@487:     struct PathCopySelector<Target, Source, true> {
kpeter@487:       static void copy(Target& target, const Source& source) {
kpeter@487:         PathCopySelectorBackward<Target, Source>::copy(target, source);
kpeter@487:       }      
kpeter@487:     };
kpeter@487: 
alpar@98:   }
alpar@98: 
alpar@98: 
alpar@98:   /// \brief Make a copy of a path.
alpar@98:   ///
alpar@98:   ///  This function makes a copy of a path.
alpar@98:   template <typename Target, typename Source>
alpar@98:   void copyPath(Target& target, const Source& source) {
alpar@98:     checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
alpar@98:     _path_bits::PathCopySelector<Target, Source>::copy(target, source);
alpar@98:   }
alpar@98: 
alpar@98:   /// \brief Check the consistency of a path.
alpar@98:   ///
alpar@98:   /// This function checks that the target of each arc is the same
alpar@209:   /// as the source of the next one.
alpar@209:   ///
alpar@98:   template <typename Digraph, typename Path>
alpar@98:   bool checkPath(const Digraph& digraph, const Path& path) {
alpar@98:     typename Path::ArcIt it(path);
alpar@98:     if (it == INVALID) return true;
alpar@98:     typename Digraph::Node node = digraph.target(it);
alpar@98:     ++it;
alpar@98:     while (it != INVALID) {
alpar@98:       if (digraph.source(it) != node) return false;
alpar@98:       node = digraph.target(it);
alpar@98:       ++it;
alpar@98:     }
alpar@98:     return true;
alpar@98:   }
alpar@98: 
alpar@98:   /// \brief The source of a path
alpar@98:   ///
kpeter@503:   /// This function returns the source node of the given path.
kpeter@503:   /// If the path is empty, then it returns \c INVALID.
alpar@98:   template <typename Digraph, typename Path>
alpar@98:   typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
kpeter@503:     return path.empty() ? INVALID : digraph.source(path.front());
alpar@98:   }
alpar@98: 
alpar@98:   /// \brief The target of a path
alpar@98:   ///
kpeter@503:   /// This function returns the target node of the given path.
kpeter@503:   /// If the path is empty, then it returns \c INVALID.
alpar@98:   template <typename Digraph, typename Path>
alpar@98:   typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
kpeter@503:     return path.empty() ? INVALID : digraph.target(path.back());
alpar@98:   }
alpar@98: 
alpar@98:   /// \brief Class which helps to iterate through the nodes of a path
alpar@98:   ///
alpar@98:   /// In a sense, the path can be treated as a list of arcs. The
alpar@98:   /// lemon path type stores only this list. As a consequence, it
alpar@98:   /// cannot enumerate the nodes in the path and the zero length paths
alpar@98:   /// cannot have a source node.
alpar@98:   ///
alpar@98:   /// This class implements the node iterator of a path structure. To
alpar@98:   /// provide this feature, the underlying digraph should be passed to
alpar@98:   /// the constructor of the iterator.
alpar@98:   template <typename Path>
alpar@98:   class PathNodeIt {
alpar@98:   private:
alpar@98:     const typename Path::Digraph *_digraph;
alpar@98:     typename Path::ArcIt _it;
alpar@98:     typename Path::Digraph::Node _nd;
alpar@98: 
alpar@98:   public:
alpar@98: 
alpar@98:     typedef typename Path::Digraph Digraph;
alpar@98:     typedef typename Digraph::Node Node;
alpar@209: 
alpar@98:     /// Default constructor
alpar@98:     PathNodeIt() {}
alpar@98:     /// Invalid constructor
alpar@209:     PathNodeIt(Invalid)
alpar@98:       : _digraph(0), _it(INVALID), _nd(INVALID) {}
alpar@98:     /// Constructor
alpar@209:     PathNodeIt(const Digraph& digraph, const Path& path)
alpar@98:       : _digraph(&digraph), _it(path) {
alpar@98:       _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
alpar@98:     }
alpar@98:     /// Constructor
alpar@209:     PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
alpar@98:       : _digraph(&digraph), _it(path), _nd(src) {}
alpar@98: 
alpar@98:     ///Conversion to Digraph::Node
alpar@98:     operator Node() const {
alpar@98:       return _nd;
alpar@98:     }
alpar@98: 
alpar@98:     /// Next node
alpar@98:     PathNodeIt& operator++() {
alpar@98:       if (_it == INVALID) _nd = INVALID;
alpar@98:       else {
alpar@209:         _nd = _digraph->target(_it);
alpar@209:         ++_it;
alpar@98:       }
alpar@98:       return *this;
alpar@98:     }
alpar@98: 
alpar@98:     /// Comparison operator
alpar@209:     bool operator==(const PathNodeIt& n) const {
alpar@209:       return _it == n._it && _nd == n._nd;
alpar@98:     }
alpar@98:     /// Comparison operator
alpar@209:     bool operator!=(const PathNodeIt& n) const {
alpar@209:       return _it != n._it || _nd != n._nd;
alpar@98:     }
alpar@98:     /// Comparison operator
alpar@209:     bool operator<(const PathNodeIt& n) const {
alpar@98:       return (_it < n._it && _nd != INVALID);
alpar@98:     }
alpar@209: 
alpar@98:   };
alpar@209: 
alpar@96:   ///@}
alpar@96: 
alpar@96: } // namespace lemon
alpar@96: 
alpar@96: #endif // LEMON_PATH_H