alpar@906: /* -*- C++ -*-
alpar@906:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
hegyi@819: 
hegyi@819: 
hegyi@819: ///\ingroup paths
hegyi@819: ///\file
hegyi@819: ///\brief Classes for representing paths in graphs.
alpar@1151: ///
hegyi@819: 
alpar@921: #ifndef LEMON_PATH_H
alpar@921: #define LEMON_PATH_H
hegyi@819: 
hegyi@819: #include <vector>
hegyi@819: #include <algorithm>
hegyi@819: 
deba@2335: #include <lemon/path_utils.h>
deba@2247: #include <lemon/error.h>
deba@1993: #include <lemon/bits/invalid.h>
hegyi@819: 
alpar@921: namespace lemon {
hegyi@819: 
hegyi@819:   /// \addtogroup paths
hegyi@819:   /// @{
hegyi@819: 
hegyi@819: 
deba@2335:   /// \brief A structure for representing directed paths in a graph.
deba@2335:   ///
deba@2335:   /// A structure for representing directed path in a graph.
deba@2335:   /// \param Graph The graph type in which the path is.
deba@2335:   ///
deba@2335:   /// In a sense, the path can be treated as a list of edges. The
deba@2335:   /// lemon path type stores just this list. As a consequence it
deba@2335:   /// cannot enumerate the nodes in the path and the zero length paths
deba@2335:   /// cannot store the source.
deba@2335:   ///
deba@2335:   /// This implementation is a back and front insertable and erasable
deba@2335:   /// path type. It can be indexed in O(1) time. The front and back
deba@2335:   /// insertion and erasure is amortized O(1) time. The
deba@2335:   /// impelementation is based on two opposite organized vectors.
deba@2335:   template <typename _Graph>
deba@2247:   class Path {
hegyi@819:   public:
deba@2335: 
deba@2335:     typedef _Graph Graph;
deba@2247:     typedef typename Graph::Edge Edge;
deba@2247: 
deba@2335:     /// \brief Default constructor
deba@2335:     ///
deba@2335:     /// Default constructor
deba@2335:     Path() {}
hegyi@819: 
deba@2335:     /// \brief Template copy constructor
deba@2247:     ///
deba@2335:     /// This path can be initialized with any other path type. It just
deba@2335:     /// makes a copy of the given path.
deba@2335:     template <typename CPath>
deba@2335:     Path(const CPath& cpath) {
deba@2335:       copyPath(*this, cpath);
hegyi@819:     }
hegyi@819: 
deba@2335:     /// \brief Template copy assignment
hegyi@819:     ///
deba@2335:     /// This path can be initialized with any other path type. It just
deba@2335:     /// makes a copy of the given path.
deba@2335:     template <typename CPath>
deba@2335:     Path& operator=(const CPath& cpath) {
deba@2335:       copyPath(*this, cpath);
deba@2335:       return *this;
hegyi@819:     }
hegyi@819: 
deba@2335:     /// \brief Lemon style iterator for path edges
deba@2247:     ///
deba@2335:     /// This class is used to iterate on the edges of the paths.
deba@2335:     class EdgeIt {
deba@2247:       friend class Path;
deba@2247:     public:
deba@2335:       /// \brief Default constructor
deba@2335:       EdgeIt() {}
deba@2335:       /// \brief Invalid constructor
deba@2335:       EdgeIt(Invalid) : path(0), idx(-1) {}
deba@2335:       /// \brief Initializate the constructor to the first edge of path
deba@2335:       EdgeIt(const Path &_path) 
deba@2335:         : path(&_path), idx(_path.empty() ? -1 : 0) {}
hegyi@819: 
deba@2335:     private:
hegyi@819: 
deba@2335:       EdgeIt(const Path &_path, int _idx) 
deba@2335:         : idx(_idx), path(&_path) {}
deba@2247: 
deba@2335:     public:
deba@2335: 
deba@2335:       /// \brief Conversion to Edge
deba@2335:       operator const Edge&() const {
deba@2335:         return path->nth(idx);
deba@2247:       }
deba@2247: 
deba@2335:       /// \brief Next edge
deba@2335:       EdgeIt& operator++() { 
deba@2335:         ++idx;
deba@2335:         if (idx >= path->length()) idx = -1; 
deba@2247:         return *this; 
deba@2247:       }
deba@2247: 
deba@2247:       /// \brief Comparison operator
deba@2335:       bool operator==(const EdgeIt& e) const { return idx==e.idx; }
deba@2247:       /// \brief Comparison operator
deba@2335:       bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
deba@2247:       /// \brief Comparison operator
deba@2335:       bool operator<(const EdgeIt& e) const { return idx<e.idx; }
deba@2247: 
deba@2247:     private:
deba@2247:       const Path *path;
deba@2335:       int idx;
deba@2247:     };
deba@2247: 
deba@2335:     /// \brief Length of the path.
deba@2335:     int length() const { return head.size() + tail.size(); }
deba@2335:     /// \brief Returns whether the path is empty.
deba@2335:     bool empty() const { return head.empty() && tail.empty(); }
deba@2335: 
deba@2335:     /// \brief Resets the path to an empty path.
deba@2335:     void clear() { head.clear(); tail.clear(); }
deba@2335: 
deba@2335:     /// \brief Gives back the nth edge.
deba@2335:     ///
deba@2335:     /// \pre n is in the [0..length() - 1] range
deba@2335:     const Edge& nth(int n) const {
deba@2335:       return n < (int)head.size() ? *(head.rbegin() + n) :
deba@2335:         *(tail.begin() + (n - head.size()));
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Initializes edge iterator to point to the nth edge
deba@2335:     ///
deba@2335:     /// \pre n is in the [0..length() - 1] range
deba@2335:     EdgeIt nthIt(int n) const {
deba@2335:       return EdgeIt(*this, n);
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Gives back the first edge of the path
deba@2335:     const Edge& front() const {
deba@2335:       return head.empty() ? tail.front() : head.back();
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Add a new edge before the current path
deba@2335:     void addFront(const Edge& edge) {
deba@2335:       head.push_back(edge);
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Erase the first edge of the path
deba@2335:     void eraseFront() {
deba@2335:       if (!head.empty()) {
deba@2335:         head.pop_back();
deba@2335:       } else {
deba@2335:         head.clear();
deba@2335:         int halfsize = tail.size() / 2;
deba@2335:         head.resize(halfsize);
deba@2335:         std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
deba@2335:                   head.rbegin());
deba@2335:         std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
deba@2335:         tail.resize(tail.size() - halfsize - 1);
deba@2335:       }
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Gives back the last edge of the path
deba@2335:     const Edge& back() const {
deba@2335:       return tail.empty() ? head.front() : tail.back();
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Add a new edge behind the current path
deba@2335:     void addBack(const Edge& edge) {
deba@2335:       tail.push_back(edge);
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Erase the last edge of the path
deba@2335:     void eraseBack() {
deba@2335:       if (!tail.empty()) {
deba@2335:         tail.pop_back();
deba@2335:       } else {
deba@2335:         int halfsize = head.size() / 2;
deba@2335:         tail.resize(halfsize);
deba@2335:         std::copy(head.begin() + 1, head.begin() + halfsize + 1,
deba@2335:                   tail.rbegin());
deba@2335:         std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
deba@2335:         head.resize(head.size() - halfsize - 1);
deba@2335:       }
deba@2335:     }
deba@2335: 
deba@2335: 
deba@2335: 
deba@2335:     typedef True BuildTag;
deba@2335: 
deba@2335:     template <typename CPath>
deba@2335:     void build(const CPath& path) {
deba@2335:       int len = path.length();
deba@2335:       tail.reserve(len);
deba@2335:       for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
deba@2335:         tail.push_back(it);
deba@2335:       }
deba@2335:     }
deba@2335: 
deba@2335:     template <typename CPath>
deba@2335:     void buildRev(const CPath& path) {
deba@2335:       int len = path.length();
deba@2335:       head.reserve(len);
deba@2357:       for (typename CPath::RevEdgeIt it(path); it != INVALID; ++it) {
deba@2335:         head.push_back(it);
deba@2335:       }
deba@2335:     }
deba@2335: 
deba@2335:   protected:
deba@2335:     typedef std::vector<Edge> Container;
deba@2335:     Container head, tail;
deba@2335: 
deba@2335:   };
deba@2335: 
deba@2335:   /// \brief A structure for representing directed paths in a graph.
deba@2335:   ///
deba@2335:   /// A structure for representing directed path in a graph.
deba@2335:   /// \param Graph The graph type in which the path is.
deba@2335:   ///
deba@2335:   /// In a sense, the path can be treated as a list of edges. The
deba@2335:   /// lemon path type stores just this list. As a consequence it
deba@2335:   /// cannot enumerate the nodes in the path and the zero length paths
deba@2335:   /// cannot store the source.
deba@2335:   ///
deba@2335:   /// This implementation is a just back insertable and erasable path
deba@2335:   /// type. It can be indexed in O(1) time. The back insertion and
deba@2335:   /// erasure is amortized O(1) time. This implementation is faster
deba@2335:   /// then the \c Path type because it use just one vector for the
deba@2335:   /// edges.
deba@2335:   template <typename _Graph>
deba@2335:   class SimplePath {
deba@2335:   public:
deba@2335: 
deba@2335:     typedef _Graph Graph;
deba@2335:     typedef typename Graph::Edge Edge;
deba@2335: 
deba@2335:     /// \brief Default constructor
deba@2335:     ///
deba@2335:     /// Default constructor
deba@2335:     SimplePath() {}
deba@2335: 
deba@2335:     /// \brief Template copy constructor
deba@2335:     ///
deba@2335:     /// This path can be initialized with any other path type. It just
deba@2335:     /// makes a copy of the given path.
deba@2335:     template <typename CPath>
deba@2335:     SimplePath(const CPath& cpath) {
deba@2335:       copyPath(*this, cpath);
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Template copy assignment
deba@2335:     ///
deba@2335:     /// This path can be initialized with any other path type. It just
deba@2335:     /// makes a copy of the given path.
deba@2335:     template <typename CPath>
deba@2335:     SimplePath& operator=(const CPath& cpath) {
deba@2335:       copyPath(*this, cpath);
deba@2335:       return *this;
deba@2335:     }
deba@2335: 
deba@2247:     /// \brief Iterator class to iterate on the edges of the paths
deba@2247:     ///
deba@2247:     /// This class is used to iterate on the edges of the paths
deba@2335:     ///
deba@2247:     /// Of course it converts to Graph::Edge
hegyi@819:     class EdgeIt {
deba@2335:       friend class SimplePath;
deba@2335:     public:
deba@2335:       /// Default constructor
deba@2335:       EdgeIt() {}
deba@2335:       /// Invalid constructor
deba@2335:       EdgeIt(Invalid) : path(0), idx(-1) {}
deba@2335:       /// \brief Initializate the constructor to the first edge of path
deba@2335:       EdgeIt(const SimplePath &_path) 
deba@2335:         : path(&_path), idx(_path.empty() ? -1 : 0) {}
deba@2335: 
deba@2335:     private:
deba@2335: 
deba@2335:       /// Constructor with starting point
deba@2335:       EdgeIt(const SimplePath &_path, int _idx) 
deba@2335:         : idx(_idx), path(&_path) {}
deba@2335: 
deba@2247:     public:
hegyi@819: 
deba@2335:       ///Conversion to Graph::Edge
deba@2335:       operator const Edge&() const {
deba@2335:         return path->nth(idx);
hegyi@819:       }
hegyi@819: 
deba@2335:       /// Next edge
deba@2247:       EdgeIt& operator++() { 
deba@2335:         ++idx;
deba@2335:         if (idx >= path->length()) idx = -1; 
deba@2247:         return *this; 
deba@2247:       }
deba@2247: 
hegyi@819:       /// Comparison operator
deba@2335:       bool operator==(const EdgeIt& e) const { return idx==e.idx; }
deba@2335:       /// Comparison operator
deba@2335:       bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
deba@2335:       /// Comparison operator
deba@2335:       bool operator<(const EdgeIt& e) const { return idx<e.idx; }
deba@2247: 
deba@2335:     private:
deba@2335:       const SimplePath *path;
deba@2335:       int idx;
deba@2335:     };
deba@2335: 
deba@2335:     /// \brief Length of the path.
deba@2335:     int length() const { return data.size(); }
deba@2335:     /// \brief Returns whether the path is empty.
deba@2335:     bool empty() const { return data.empty(); }
deba@2335: 
deba@2335:     /// \brief Resets the path to an empty path.
deba@2335:     void clear() { data.clear(); }
deba@2335: 
deba@2335:     /// \brief Gives back the nth edge.
deba@2335:     ///
deba@2335:     /// \pre n is in the [0..length() - 1] range
deba@2335:     const Edge& nth(int n) const {
deba@2335:       return data[n];
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief  Initializes edge iterator to point to the nth edge.
deba@2335:     EdgeIt nthIt(int n) const {
deba@2335:       return EdgeIt(*this, n);
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Gives back the last edge of the path.
deba@2335:     const Edge& back() const {
deba@2335:       return data.back();
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Add a new edge behind the current path.
deba@2335:     void addBack(const Edge& edge) {
deba@2335:       data.push_back(edge);
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Erase the last edge of the path
deba@2335:     void eraseBack() {
deba@2335:       data.pop_back();
deba@2335:     }
deba@2335: 
deba@2335:     typedef True BuildTag;
deba@2335: 
deba@2335:     template <typename CPath>
deba@2335:     void build(const CPath& path) {
deba@2335:       int len = path.length();
deba@2335:       data.resize(len);
deba@2335:       int index = 0;
deba@2335:       for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
deba@2335:         data[index] = it;;
deba@2335:         ++index;
deba@2335:       }
deba@2335:     }
deba@2335: 
deba@2335:     template <typename CPath>
deba@2335:     void buildRev(const CPath& path) {
deba@2335:       int len = path.length();
deba@2335:       data.resize(len);
deba@2335:       int index = len;
deba@2357:       for (typename CPath::RevEdgeIt it(path); it != INVALID; ++it) {
deba@2335:         --index;
deba@2335:         data[index] = it;;
deba@2335:       }
deba@2335:     }
deba@2335: 
deba@2335:   protected:
deba@2335:     typedef std::vector<Edge> Container;
deba@2335:     Container data;
deba@2335: 
deba@2335:   };
deba@2335: 
deba@2335:   /// \brief A structure for representing directed paths in a graph.
deba@2335:   ///
deba@2335:   /// A structure for representing directed path in a graph.
deba@2335:   /// \param Graph The graph type in which the path is.
deba@2335:   ///
deba@2335:   /// In a sense, the path can be treated as a list of edges. The
deba@2335:   /// lemon path type stores just this list. As a consequence it
deba@2335:   /// cannot enumerate the nodes in the path and the zero length paths
deba@2335:   /// cannot store the source.
deba@2335:   ///
deba@2335:   /// This implementation is a back and front insertable and erasable
deba@2335:   /// path type. It can be indexed in O(k) time, where k is the rank
deba@2335:   /// of the edge in the path. The length can be computed in O(n)
deba@2335:   /// time. The front and back insertion and erasure is O(1) time
deba@2335:   /// and it can be splited and spliced in O(1) time.
deba@2335:   template <typename _Graph>
deba@2335:   class ListPath {
deba@2335:   public:
deba@2335: 
deba@2335:     typedef _Graph Graph;
deba@2335:     typedef typename Graph::Edge Edge;
deba@2335: 
deba@2335:   protected:
deba@2335: 
deba@2335:     // the std::list<> is incompatible 
deba@2335:     // hard to create invalid iterator
deba@2335:     struct Node {
deba@2335:       Edge edge;
deba@2335:       Node *next, *prev;
deba@2335:     };
deba@2335: 
deba@2335:     Node *first, *last;
deba@2335: 
deba@2335:     std::allocator<Node> alloc;
deba@2335: 
deba@2335:   public:
deba@2335:  
deba@2335:     /// \brief Default constructor
deba@2335:     ///
deba@2335:     /// Default constructor
deba@2335:     ListPath() : first(0), last(0) {}
deba@2335: 
deba@2335:     /// \brief Template copy constructor
deba@2335:     ///
deba@2335:     /// This path can be initialized with any other path type. It just
deba@2335:     /// makes a copy of the given path.
deba@2335:     template <typename CPath>
deba@2335:     ListPath(const CPath& cpath) : first(0), last(0) {
deba@2335:       copyPath(*this, cpath);
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Destructor of the path
deba@2335:     ///
deba@2335:     /// Destructor of the path
deba@2335:     ~ListPath() {
deba@2335:       clear();
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Template copy assignment
deba@2335:     ///
deba@2335:     /// This path can be initialized with any other path type. It just
deba@2335:     /// makes a copy of the given path.
deba@2335:     template <typename CPath>
deba@2335:     ListPath& operator=(const CPath& cpath) {
deba@2335:       copyPath(*this, cpath);
deba@2335:       return *this;
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Iterator class to iterate on the edges of the paths
deba@2335:     ///
deba@2335:     /// This class is used to iterate on the edges of the paths
deba@2335:     ///
deba@2335:     /// Of course it converts to Graph::Edge
deba@2335:     class EdgeIt {
deba@2335:       friend class ListPath;
deba@2335:     public:
deba@2335:       /// Default constructor
deba@2335:       EdgeIt() {}
deba@2335:       /// Invalid constructor
deba@2335:       EdgeIt(Invalid) : path(0), node(0) {}
deba@2335:       /// \brief Initializate the constructor to the first edge of path
deba@2335:       EdgeIt(const ListPath &_path) 
deba@2335:         : path(&_path), node(_path.first) {}
deba@2335: 
deba@2335:     protected:
deba@2335: 
deba@2335:       EdgeIt(const ListPath &_path, Node *_node) 
deba@2335:         : path(&_path), node(_node) {}
deba@2335: 
deba@2335: 
deba@2335:     public:
deba@2335: 
deba@2335:       ///Conversion to Graph::Edge
deba@2335:       operator const Edge&() const {
deba@2335:         return node->edge;
deba@2335:       }
deba@2335: 
deba@2335:       /// Next edge
deba@2335:       EdgeIt& operator++() { 
deba@2335:         node = node->next;
deba@2335:         return *this; 
deba@2335:       }
deba@2335: 
hegyi@819:       /// Comparison operator
deba@2335:       bool operator==(const EdgeIt& e) const { return node==e.node; }
deba@2335:       /// Comparison operator
deba@2335:       bool operator!=(const EdgeIt& e) const { return node!=e.node; }
deba@2335:       /// Comparison operator
deba@2335:       bool operator<(const EdgeIt& e) const { return node<e.node; }
deba@2247: 
deba@2335:     private:
deba@2335:       const ListPath *path;
deba@2335:       Node *node;
deba@2335:     };
deba@2335: 
deba@2335:     /// \brief Gives back the nth edge.
deba@2335:     ///
deba@2335:     /// Gives back the nth edge in O(n) time.
deba@2335:     /// \pre n is in the [0..length() - 1] range
deba@2335:     const Edge& nth(int n) const {
deba@2335:       Node *node = first;
deba@2335:       for (int i = 0; i < n; ++i) {
deba@2335:         node = node->next;
deba@2335:       }
deba@2335:       return node->edge;
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Initializes edge iterator to point to the nth edge.
deba@2335:     EdgeIt nthIt(int n) const {
deba@2335:       Node *node = first;
deba@2335:       for (int i = 0; i < n; ++i) {
deba@2335:         node = node->next;
deba@2335:       }
deba@2335:       return EdgeIt(*this, node);
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Length of the path.
deba@2335:     int length() const {
deba@2335:       int len = 0;
deba@2335:       Node *node = first;
deba@2335:       while (node != 0) {
deba@2335:         node = node->next;
deba@2335:         ++len;
deba@2335:       }
deba@2335:       return len;
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Returns whether the path is empty.
deba@2335:     bool empty() const { return first == 0; }
deba@2335: 
deba@2335:     /// \brief Resets the path to an empty path.
deba@2335:     void clear() {
deba@2335:       while (first != 0) {
deba@2335:         last = first->next;
deba@2335:         alloc.destroy(first);
deba@2335:         alloc.deallocate(first, 1);
deba@2335:         first = last;
deba@2335:       }
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Gives back the first edge of the path
deba@2335:     const Edge& front() const {
deba@2335:       return first->edge;
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Add a new edge before the current path
deba@2335:     void addFront(const Edge& edge) {
deba@2335:       Node *node = alloc.allocate(1);
deba@2335:       alloc.construct(node, Node());
deba@2335:       node->prev = 0;
deba@2335:       node->next = first;
deba@2335:       node->edge = edge;
deba@2335:       if (first) {
deba@2335:         first->prev = node;
deba@2335:         first = node;
deba@2335:       } else {
deba@2335:         first = last = node;
deba@2335:       }
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Erase the first edge of the path
deba@2335:     void eraseFront() {
deba@2335:       Node *node = first;
deba@2335:       first = first->next;
deba@2335:       if (first) {
deba@2335:         first->prev = 0;
deba@2335:       } else {
deba@2335:         last = 0;
deba@2335:       }
deba@2335:       alloc.destroy(node);
deba@2335:       alloc.deallocate(node, 1);
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Gives back the last edge of the path.
deba@2335:     const Edge& back() const {
deba@2335:       return last->edge;
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Add a new edge behind the current path.
deba@2335:     void addBack(const Edge& edge) {
deba@2335:       Node *node = alloc.allocate(1);
deba@2335:       alloc.construct(node, Node());
deba@2335:       node->next = 0;
deba@2335:       node->prev = last;
deba@2335:       node->edge = edge;
deba@2335:       if (last) {
deba@2335:         last->next = node;
deba@2335:         last = node;
deba@2335:       } else {
deba@2335:         last = first = node;
deba@2335:       }
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Erase the last edge of the path
deba@2335:     void eraseBack() {
deba@2335:       Node *node = last;
deba@2335:       last = last->prev;
deba@2335:       if (last) {
deba@2335:         last->next = 0;
deba@2335:       } else {
deba@2335:         first = 0;
deba@2335:       }
deba@2335:       alloc.destroy(node);
deba@2335:       alloc.deallocate(node, 1);
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Splicing the given path to the current path.
deba@2335:     ///
deba@2335:     /// It splices the \c tpath to the back of the current path and \c
deba@2335:     /// tpath becomes empty. The time complexity of this function is
deba@2335:     /// O(1).
deba@2335:     void spliceBack(ListPath& tpath) {
deba@2335:       if (first) {
deba@2335:         if (tpath.first) {
deba@2335:           last->next = tpath.first;
deba@2335:           tpath.first->prev = last;
deba@2335:           last = tpath.last;
deba@2335:         }
deba@2335:       } else {
deba@2335:         first = tpath.first;
deba@2335:         last = tpath.last;
deba@2335:       }
deba@2335:       tpath.first = tpath.last = 0;
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Splicing the given path to the current path.
deba@2335:     ///
deba@2335:     /// It splices the \c tpath before the current path and \c tpath
deba@2335:     /// becomes empty. The time complexity of this function
deba@2335:     /// is O(1).
deba@2335:     void spliceFront(ListPath& tpath) {
deba@2335:       if (first) {
deba@2335:         if (tpath.first) {
deba@2335:           first->prev = tpath.last;
deba@2335:           tpath.last->next = first;
deba@2335:           first = tpath.first;
deba@2335:         }
deba@2335:       } else {
deba@2335:         first = tpath.first;
deba@2335:         last = tpath.last;
deba@2335:       }
deba@2335:       tpath.first = tpath.last = 0;
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Splicing the given path into the current path.
deba@2335:     ///
deba@2335:     /// It splices the \c tpath into the current path before the
deba@2335:     /// position of \c it iterator and \c tpath becomes empty. The
deba@2335:     /// time complexity of this function is O(1). If the \c it is \c
deba@2335:     /// INVALID then it will splice behind the current path.
deba@2335:     void splice(EdgeIt it, ListPath& tpath) {
deba@2335:       if (it.node) {
deba@2335:         if (tpath.first) {
deba@2335:           tpath.first->prev = it.node->prev;
deba@2335:           if (it.node->prev) {
deba@2335:             it.node->prev->next = tpath.first;
deba@2335:           } else {
deba@2335:             first = tpath.first;
deba@2335:           }
deba@2335:           it.node->prev = tpath.last;
deba@2335:           tpath.last->next = it.node;
deba@2335:         }
deba@2335:       } else {
deba@2335:         if (first) {
deba@2335:           if (tpath.first) {
deba@2335:             last->next = tpath.first;
deba@2335:             tpath.first->prev = last;
deba@2335:             last = tpath.last;
deba@2335:           }
deba@2335:         } else {
deba@2335:           first = tpath.first;
deba@2335:           last = tpath.last;
deba@2335:         }
deba@2335:       }
deba@2335:       tpath.first = tpath.last = 0;
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Spliting the current path.
deba@2335:     ///
deba@2335:     /// It splits the current path into two parts. The part before \c
deba@2335:     /// it iterator will remain in the current path and the part from
deba@2335:     /// the it will put into the \c tpath. If the \c tpath had edges
deba@2335:     /// before the operation they will be removed first.  The time
deba@2335:     /// complexity of this function is O(1) plus the clearing of \c
deba@2335:     /// tpath. If the \c it is \c INVALID then it just clears \c
deba@2335:     /// tpath.
deba@2335:     void split(EdgeIt it, ListPath& tpath) {
deba@2335:       tpath.clear();
deba@2335:       if (it.node) {
deba@2335:         tpath.first = it.node;
deba@2335:         tpath.last = last;
deba@2335:         if (it.node->prev) {
deba@2335:           last = it.node->prev;
deba@2335:           last->next = 0;
deba@2335:         } else {
deba@2335:           first = last = 0;
deba@2335:         }
deba@2335:         it.node->prev = 0;
deba@2335:       }
deba@2335:     }
deba@2335: 
deba@2335: 
deba@2335:     typedef True BuildTag;
deba@2335: 
deba@2335:     template <typename CPath>
deba@2335:     void build(const CPath& path) {
deba@2335:       for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
deba@2335:         addBack(it);
deba@2335:       }
deba@2335:     }
deba@2335: 
deba@2335:     template <typename CPath>
deba@2335:     void buildRev(const CPath& path) {
deba@2357:       for (typename CPath::RevEdgeIt it(path); it != INVALID; ++it) {
deba@2335:         addFront(it);
deba@2335:       }
deba@2335:     }
deba@2335: 
deba@2335:   };
deba@2335: 
deba@2335:   /// \brief A structure for representing directed paths in a graph.
deba@2335:   ///
deba@2335:   /// A structure for representing directed path in a graph.
deba@2335:   /// \param Graph The graph type in which the path is.
deba@2335:   ///
deba@2335:   /// In a sense, the path can be treated as a list of edges. The
deba@2335:   /// lemon path type stores just this list. As a consequence it
deba@2335:   /// cannot enumerate the nodes in the path and the zero length paths
deba@2335:   /// cannot store the source.
deba@2335:   ///
deba@2335:   /// This implementation is completly static, so it cannot be
deba@2335:   /// modified exclude the assign an other path. It is intented to be
athos@2336:   /// used when you want to store a large number of paths because it is
deba@2335:   /// the most memory efficient path type in the lemon.
deba@2335:   template <typename _Graph>
deba@2335:   class StaticPath {
deba@2335:   public:
deba@2335: 
deba@2335:     typedef _Graph Graph;
deba@2335:     typedef typename Graph::Edge Edge;
deba@2335: 
deba@2335:     /// \brief Default constructor
deba@2335:     ///
deba@2335:     /// Default constructor
deba@2335:     StaticPath() : len(0), edges(0) {}
deba@2335:     
deba@2335:     /// \brief Template copy constructor
deba@2335:     ///
deba@2335:     /// This path can be initialized with any other path type. It just
deba@2335:     /// makes a copy of the given path.
deba@2335:     template <typename CPath>
deba@2335:     StaticPath(const CPath& cpath) : edges(0) {
deba@2335:       copyPath(*this, cpath);
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Destructor of the path
deba@2335:     ///
deba@2335:     /// Destructor of the path
deba@2335:     ~StaticPath() {
deba@2335:       if (edges) delete[] edges;
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Template copy assignment
deba@2335:     ///
deba@2335:     /// This path can be initialized with any other path type. It just
deba@2335:     /// makes a copy of the given path.
deba@2335:     template <typename CPath>
deba@2335:     StaticPath& operator=(const CPath& cpath) {
deba@2335:       copyPath(*this, cpath);
deba@2335:       return *this;
deba@2335:     }
deba@2335: 
deba@2335:     /// \brief Iterator class to iterate on the edges of the paths
deba@2335:     ///
deba@2335:     /// This class is used to iterate on the edges of the paths
deba@2335:     ///
deba@2335:     /// Of course it converts to Graph::Edge
deba@2335:     class EdgeIt {
deba@2335:       friend class StaticPath;
deba@2335:     public:
deba@2335:       /// Default constructor
deba@2335:       EdgeIt() {}
deba@2335:       /// Invalid constructor
deba@2335:       EdgeIt(Invalid) : path(0), idx(-1) {}
deba@2335:       /// Initializate the constructor to the first edge of path
deba@2335:       EdgeIt(const StaticPath &_path) 
deba@2335:         : path(&_path), idx(_path.empty() ? -1 : 0) {}
hegyi@819: 
hegyi@819:     private:
deba@2247: 
deba@2335:       /// Constructor with starting point
deba@2335:       EdgeIt(const StaticPath &_path, int _idx) 
deba@2335:         : idx(_idx), path(&_path) {}
deba@2335: 
deba@2335:     public:
deba@2335: 
deba@2335:       ///Conversion to Graph::Edge
deba@2335:       operator const Edge&() const {
deba@2335:         return path->nth(idx);
deba@2335:       }
deba@2335: 
deba@2335:       /// Next edge
deba@2335:       EdgeIt& operator++() { 
deba@2335:         ++idx;
deba@2335:         if (idx >= path->length()) idx = -1; 
deba@2335:         return *this; 
deba@2335:       }
deba@2335: 
deba@2335:       /// Comparison operator
deba@2335:       bool operator==(const EdgeIt& e) const { return idx==e.idx; }
deba@2335:       /// Comparison operator
deba@2335:       bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
deba@2335:       /// Comparison operator
deba@2335:       bool operator<(const EdgeIt& e) const { return idx<e.idx; }
deba@2335: 
deba@2335:     private:
deba@2335:       const StaticPath *path;
deba@2335:       int idx;
hegyi@819:     };
hegyi@819: 
deba@2335:     /// \brief Gives back the nth edge.
deba@2335:     ///
deba@2335:     /// \pre n is in the [0..length() - 1] range
deba@2335:     const Edge& nth(int n) const {
deba@2335:       return edges[n];
deba@2335:     }
hegyi@819: 
deba@2335:     /// \brief Initializes edge iterator to point to the nth edge.
deba@2335:     EdgeIt nthIt(int n) const {
deba@2335:       return EdgeIt(*this, n);
deba@2335:     }
hegyi@819: 
deba@2335:     /// \brief Gives back the length of the path.
deba@2335:     int length() const { return len; }
hegyi@819: 
deba@2335:     /// \brief Returns true when the path is empty.
deba@2335:     int empty() const { return len == 0; }
hegyi@819: 
deba@2335:     /// \break Erase all edge in the graph.
deba@2335:     void clear() {
deba@2335:       len = 0;
deba@2335:       if (edges) delete[] edges;
deba@2335:       edges = 0;
deba@2335:     }
hegyi@819: 
deba@2335:     /// \brief Gives back the first edge of the path.
deba@2335:     const Edge& front() const {
deba@2335:       return edges[0];
deba@2335:     }
hegyi@819: 
deba@2335:     /// \brief Gives back the last edge of the path.
deba@2335:     const Edge& back() const {
deba@2335:       return edges[len - 1];
deba@2335:     }
deba@2335: 
deba@2335: 
deba@2335:     typedef True BuildTag;
deba@2335: 
deba@2335:     template <typename CPath>
deba@2335:     void build(const CPath& path) {
deba@2335:       len = path.length();
deba@2335:       edges = new Edge[len];
deba@2335:       int index = 0;
deba@2335:       for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
deba@2335:         edges[index] = it;
deba@2335:         ++index;
deba@2247:       }
deba@2335:     }
hegyi@819: 
deba@2335:     template <typename CPath>
deba@2335:     void buildRev(const CPath& path) {
deba@2335:       len = path.length();
deba@2335:       edges = new Edge[len];
deba@2335:       int index = len;
deba@2357:       for (typename CPath::RevEdgeIt it(path); it != INVALID; ++it) {
deba@2335:         --index;
deba@2335:         edges[index] = it;
deba@2247:       }
deba@2335:     }
hegyi@837: 
deba@2335:   private:
deba@2335:     int len;
deba@2335:     Edge* edges;
hegyi@819:   };
hegyi@819: 
hegyi@819:   ///@}
hegyi@819: 
alpar@921: } // namespace lemon
hegyi@819: 
alpar@921: #endif // LEMON_PATH_H