diff -r c1e936e6a46b -r 27aa03cd3121 lemon/path.h
--- a/lemon/path.h	Fri Jan 05 10:59:18 2007 +0000
+++ b/lemon/path.h	Mon Jan 08 10:39:59 2007 +0000
@@ -28,6 +28,7 @@
 #include <vector>
 #include <algorithm>
 
+#include <lemon/path_utils.h>
 #include <lemon/error.h>
 #include <lemon/bits/invalid.h>
 
@@ -37,392 +38,858 @@
   /// @{
 
 
-  //! \brief A structure for representing directed paths in a graph.
-  //!
-  //! A structure for representing directed path in a graph.
-  //! \param Graph The graph type in which the path is.
-  //!
-  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
-  //! and \c EdgeIt with the same usage. These types converts to the \c Node
-  //! and \c Edge of the original graph.
-  //!
-  //! \todo Thoroughfully check all the range and consistency tests.
-  template<typename Graph>
+  /// \brief A structure for representing directed paths in a graph.
+  ///
+  /// A structure for representing directed path in a graph.
+  /// \param Graph The graph type in which the path is.
+  ///
+  /// 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 source.
+  ///
+  /// This implementation is a back and front insertable and erasable
+  /// path type. It can be indexed in O(1) time. The front and back
+  /// insertion and erasure is amortized O(1) time. The
+  /// impelementation is based on two opposite organized vectors.
+  template <typename _Graph>
   class Path {
   public:
-    /// Edge type of the underlying graph.
+
+    typedef _Graph Graph;
     typedef typename Graph::Edge Edge;
-    /// Node type of the underlying graph.
-    typedef typename Graph::Node Node;
 
-    class NodeIt;
-    class EdgeIt;
+    /// \brief Default constructor
+    ///
+    /// Default constructor
+    Path() {}
 
-    struct PathError : public LogicError {
-      virtual const char* what() const throw() {
-        return "lemon::PathError";
-      }      
-    };
-
-  public:
-
-    /// \brief Constructor
+    /// \brief Template copy constructor
     ///
-    /// Constructor 
-    /// \param _G The graph in which the path is.
-    Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}
-    
-    /// \brief Subpath constructor.
-    ///
-    /// Subpath defined by two nodes.
-    /// \warning It is an error if the two edges are not in order!
-    Path(const Path &other, const NodeIt &a, const NodeIt &b) {
-      graph = other.graph; 
-      start = a;
-      edges.insert(edges.end(), 
-                   other.edges.begin() + a.id, other.edges.begin() + b.id);
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    Path(const CPath& cpath) {
+      copyPath(*this, cpath);
     }
 
-    /// \brief Subpath constructor.
+    /// \brief Template copy assignment
     ///
-    /// Subpath defined by two edges. Contains edges in [a,b)
-    /// \warning It is an error if the two edges are not in order!
-    Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {
-      graph = other.graph;
-      start = graph->source(a);
-      edges.insert(edges.end(), 
-                   other.edges.begin() + a.id, other.edges.begin() + b.id);
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    Path& operator=(const CPath& cpath) {
+      copyPath(*this, cpath);
+      return *this;
     }
 
-    /// \brief Length of the path.
+    /// \brief Lemon style iterator for path edges
     ///
-    /// The number of the edges in the path. It can be zero if the
-    /// path has only one node or it is empty.
-    int length() const { return edges.size(); }
-
-    /// \brief Returns whether the path is empty.
-    ///
-    /// Returns true when the path does not contain neither edge nor
-    /// node.
-    bool empty() const { return start == INVALID; }
-
-    /// \brief Resets the path to an empty path.
-    ///
-    /// Resets the path to an empty path.
-    void clear() { edges.clear(); start = INVALID; }
-
-    /// \brief Starting point of the path.
-    ///
-    /// Starting point of the path.
-    /// Returns INVALID if the path is empty.
-    Node source() const {
-      return start;
-    }
-    /// \brief End point of the path.
-    ///
-    /// End point of the path.
-    /// Returns INVALID if the path is empty.
-    Node target() const {
-      return length() == 0 ? start : graph->target(edges[length()-1]);
-    }
-
-    /// \brief Gives back a node iterator to point to the node of a
-    /// given index.
-    ///
-    /// Gives back a node iterator to point to the node of a given
-    /// index.
-    /// \pre n should less or equal to \c length()
-    NodeIt nthNode(int n) const {
-      return NodeIt(*this, n);
-    }
-
-    /// \brief Gives back an edge iterator to point to the edge of a
-    /// given index.
-    ///
-    /// Gives back an edge iterator to point to the node of a given
-    /// index.  
-    /// \pre n should less than \c length()
-    EdgeIt nthEdge(int n) const {
-      return EdgeIt(*this, n);
-    }
-
-    /// \brief Returns node iterator pointing to the source node of the
-    /// given edge iterator.
-    ///
-    /// Returns node iterator pointing to the source node of the given
-    /// edge iterator.
-    NodeIt source(const EdgeIt& e) const {
-      return NodeIt(*this, e.id);
-    }
-
-    /// \brief Returns node iterator pointing to the target node of the
-    /// given edge iterator.
-    ///
-    /// Returns node iterator pointing to the target node of the given
-    /// edge iterator.
-    NodeIt target(const EdgeIt& e) const {
-      return NodeIt(*this, e.id + 1);
-    }
-
-
-    /// \brief Iterator class to iterate on the nodes of the paths
-    ///
-    /// This class is used to iterate on the nodes of the paths
-    ///
-    /// Of course it converts to Graph::Node
-    class NodeIt {
+    /// This class is used to iterate on the edges of the paths.
+    class EdgeIt {
       friend class Path;
     public:
+      /// \brief Default constructor
+      EdgeIt() {}
+      /// \brief Invalid constructor
+      EdgeIt(Invalid) : path(0), idx(-1) {}
+      /// \brief Initializate the constructor to the first edge of path
+      EdgeIt(const Path &_path) 
+        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 
-      /// \brief Default constructor
-      ///
-      /// Default constructor
-      NodeIt() {}
+    private:
 
-      /// \brief Invalid constructor
-      ///
-      /// Invalid constructor
-      NodeIt(Invalid) : id(-1), path(0) {}
+      EdgeIt(const Path &_path, int _idx) 
+        : idx(_idx), path(&_path) {}
 
-      /// \brief Constructor with starting point
-      /// 
-      /// Constructor with starting point
-      NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 
-        if (id > path->length()) id = -1; 
+    public:
+
+      /// \brief Conversion to Edge
+      operator const Edge&() const {
+        return path->nth(idx);
       }
 
-      /// \brief Conversion to Graph::Node
-      ///
-      /// Conversion to Graph::Node
-      operator Node() const {
-	if (id > 0) {
-	  return path->graph->target(path->edges[id - 1]);
-	} else if (id == 0) {
-	  return path->start;
-	} else {
-	  return INVALID;
-        }
-      }
-
-      /// \brief Steps to the next node
-      ///
-      /// Steps to the next node
-      NodeIt& operator++() { 
-        ++id; 
-        if (id > path->length()) id = -1; 
+      /// \brief Next edge
+      EdgeIt& operator++() { 
+        ++idx;
+        if (idx >= path->length()) idx = -1; 
         return *this; 
       }
 
       /// \brief Comparison operator
-      ///
-      /// Comparison operator
-      bool operator==(const NodeIt& n) const { return id == n.id; }
-
+      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
       /// \brief Comparison operator
-      ///
-      /// Comparison operator
-      bool operator!=(const NodeIt& n) const { return id != n.id; }
-
+      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
       /// \brief Comparison operator
-      ///
-      /// Comparison operator
-      bool operator<(const NodeIt& n) const { return id < n.id; }
+      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
 
     private:
-      int id;
       const Path *path;
+      int idx;
     };
 
+    /// \brief Length of the path.
+    int length() const { return head.size() + tail.size(); }
+    /// \brief Returns whether the path is empty.
+    bool empty() const { return head.empty() && tail.empty(); }
+
+    /// \brief Resets the path to an empty path.
+    void clear() { head.clear(); tail.clear(); }
+
+    /// \brief Gives back the nth edge.
+    ///
+    /// \pre n is in the [0..length() - 1] range
+    const Edge& nth(int n) const {
+      return n < (int)head.size() ? *(head.rbegin() + n) :
+        *(tail.begin() + (n - head.size()));
+    }
+
+    /// \brief Initializes edge iterator to point to the nth edge
+    ///
+    /// \pre n is in the [0..length() - 1] range
+    EdgeIt nthIt(int n) const {
+      return EdgeIt(*this, n);
+    }
+
+    /// \brief Gives back the first edge of the path
+    const Edge& front() const {
+      return head.empty() ? tail.front() : head.back();
+    }
+
+    /// \brief Add a new edge before the current path
+    void addFront(const Edge& edge) {
+      head.push_back(edge);
+    }
+
+    /// \brief Erase the first edge of the path
+    void eraseFront() {
+      if (!head.empty()) {
+        head.pop_back();
+      } else {
+        head.clear();
+        int halfsize = tail.size() / 2;
+        head.resize(halfsize);
+        std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
+                  head.rbegin());
+        std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
+        tail.resize(tail.size() - halfsize - 1);
+      }
+    }
+
+    /// \brief Gives back the last edge of the path
+    const Edge& back() const {
+      return tail.empty() ? head.front() : tail.back();
+    }
+
+    /// \brief Add a new edge behind the current path
+    void addBack(const Edge& edge) {
+      tail.push_back(edge);
+    }
+
+    /// \brief Erase the last edge of the path
+    void eraseBack() {
+      if (!tail.empty()) {
+        tail.pop_back();
+      } else {
+        int halfsize = head.size() / 2;
+        tail.resize(halfsize);
+        std::copy(head.begin() + 1, head.begin() + halfsize + 1,
+                  tail.rbegin());
+        std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
+        head.resize(head.size() - halfsize - 1);
+      }
+    }
+
+
+
+    typedef True BuildTag;
+
+    template <typename CPath>
+    void build(const CPath& path) {
+      int len = path.length();
+      tail.reserve(len);
+      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
+        tail.push_back(it);
+      }
+    }
+
+    template <typename CPath>
+    void buildRev(const CPath& path) {
+      int len = path.length();
+      head.reserve(len);
+      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
+        head.push_back(it);
+      }
+    }
+
+  protected:
+    typedef std::vector<Edge> Container;
+    Container head, tail;
+
+  };
+
+  /// \brief A structure for representing directed paths in a graph.
+  ///
+  /// A structure for representing directed path in a graph.
+  /// \param Graph The graph type in which the path is.
+  ///
+  /// 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 source.
+  ///
+  /// This implementation is a just back insertable and erasable path
+  /// type. It can be indexed in O(1) time. The back insertion and
+  /// erasure is amortized O(1) time. This implementation is faster
+  /// then the \c Path type because it use just one vector for the
+  /// edges.
+  template <typename _Graph>
+  class SimplePath {
+  public:
+
+    typedef _Graph Graph;
+    typedef typename Graph::Edge Edge;
+
+    /// \brief Default constructor
+    ///
+    /// Default constructor
+    SimplePath() {}
+
+    /// \brief Template copy constructor
+    ///
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    SimplePath(const CPath& cpath) {
+      copyPath(*this, cpath);
+    }
+
+    /// \brief Template copy assignment
+    ///
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    SimplePath& operator=(const CPath& cpath) {
+      copyPath(*this, cpath);
+      return *this;
+    }
+
     /// \brief Iterator class to iterate on the edges of the paths
     ///
     /// This class is used to iterate on the edges of the paths
+    ///
     /// Of course it converts to Graph::Edge
     class EdgeIt {
-      friend class Path;
+      friend class SimplePath;
+    public:
+      /// Default constructor
+      EdgeIt() {}
+      /// Invalid constructor
+      EdgeIt(Invalid) : path(0), idx(-1) {}
+      /// \brief Initializate the constructor to the first edge of path
+      EdgeIt(const SimplePath &_path) 
+        : path(&_path), idx(_path.empty() ? -1 : 0) {}
+
+    private:
+
+      /// Constructor with starting point
+      EdgeIt(const SimplePath &_path, int _idx) 
+        : idx(_idx), path(&_path) {}
+
     public:
 
-      /// \brief Default constructor
-      ///
-      /// Default constructor
-      EdgeIt() {}
-
-      /// \brief Invalid constructor
-      ///
-      /// Invalid constructor
-      EdgeIt(Invalid) : id(-1), path(0) {}
-
-      /// \brief Constructor with starting point
-      ///
-      /// Constructor with starting point
-      EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 
-        if (id >= path->length()) id = -1;
+      ///Conversion to Graph::Edge
+      operator const Edge&() const {
+        return path->nth(idx);
       }
 
-      /// \brief Conversion to Graph::Edge
-      ///
-      /// Conversion to Graph::Edge
-      operator Edge() const {
-	return id != -1 ? path->edges[id] : INVALID;
-      }
-
-      /// \brief Steps to the next edge
-      ///
-      /// Steps to the next edge
+      /// Next edge
       EdgeIt& operator++() { 
-        ++id; 
-        if (id >= path->length()) id = -1;
+        ++idx;
+        if (idx >= path->length()) idx = -1; 
         return *this; 
       }
 
-      /// \brief Comparison operator
-      ///
       /// Comparison operator
-      bool operator==(const EdgeIt& e) const { return id == e.id; }
+      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
+      /// Comparison operator
+      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
+      /// Comparison operator
+      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
 
-      /// \brief Comparison operator
-      ///
+    private:
+      const SimplePath *path;
+      int idx;
+    };
+
+    /// \brief Length of the path.
+    int length() const { return data.size(); }
+    /// \brief Returns whether the path is empty.
+    bool empty() const { return data.empty(); }
+
+    /// \brief Resets the path to an empty path.
+    void clear() { data.clear(); }
+
+    /// \brief Gives back the nth edge.
+    ///
+    /// \pre n is in the [0..length() - 1] range
+    const Edge& nth(int n) const {
+      return data[n];
+    }
+
+    /// \brief  Initializes edge iterator to point to the nth edge.
+    EdgeIt nthIt(int n) const {
+      return EdgeIt(*this, n);
+    }
+
+    /// \brief Gives back the last edge of the path.
+    const Edge& back() const {
+      return data.back();
+    }
+
+    /// \brief Add a new edge behind the current path.
+    void addBack(const Edge& edge) {
+      data.push_back(edge);
+    }
+
+    /// \brief Erase the last edge of the path
+    void eraseBack() {
+      data.pop_back();
+    }
+
+    typedef True BuildTag;
+
+    template <typename CPath>
+    void build(const CPath& path) {
+      int len = path.length();
+      data.resize(len);
+      int index = 0;
+      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
+        data[index] = it;;
+        ++index;
+      }
+    }
+
+    template <typename CPath>
+    void buildRev(const CPath& path) {
+      int len = path.length();
+      data.resize(len);
+      int index = len;
+      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
+        --index;
+        data[index] = it;;
+      }
+    }
+
+  protected:
+    typedef std::vector<Edge> Container;
+    Container data;
+
+  };
+
+  /// \brief A structure for representing directed paths in a graph.
+  ///
+  /// A structure for representing directed path in a graph.
+  /// \param Graph The graph type in which the path is.
+  ///
+  /// 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 source.
+  ///
+  /// This implementation is a back and front insertable and erasable
+  /// path type. It can be indexed in O(k) time, where k is the rank
+  /// of the edge in the path. The length can be computed in O(n)
+  /// time. The front and back insertion and erasure is O(1) time
+  /// and it can be splited and spliced in O(1) time.
+  template <typename _Graph>
+  class ListPath {
+  public:
+
+    typedef _Graph Graph;
+    typedef typename Graph::Edge Edge;
+
+  protected:
+
+    // the std::list<> is incompatible 
+    // hard to create invalid iterator
+    struct Node {
+      Edge edge;
+      Node *next, *prev;
+    };
+
+    Node *first, *last;
+
+    std::allocator<Node> alloc;
+
+  public:
+ 
+    /// \brief Default constructor
+    ///
+    /// Default constructor
+    ListPath() : first(0), last(0) {}
+
+    /// \brief Template copy constructor
+    ///
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    ListPath(const CPath& cpath) : first(0), last(0) {
+      copyPath(*this, cpath);
+    }
+
+    /// \brief Destructor of the path
+    ///
+    /// Destructor of the path
+    ~ListPath() {
+      clear();
+    }
+
+    /// \brief Template copy assignment
+    ///
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    ListPath& operator=(const CPath& cpath) {
+      copyPath(*this, cpath);
+      return *this;
+    }
+
+    /// \brief Iterator class to iterate on the edges of the paths
+    ///
+    /// This class is used to iterate on the edges of the paths
+    ///
+    /// Of course it converts to Graph::Edge
+    class EdgeIt {
+      friend class ListPath;
+    public:
+      /// Default constructor
+      EdgeIt() {}
+      /// Invalid constructor
+      EdgeIt(Invalid) : path(0), node(0) {}
+      /// \brief Initializate the constructor to the first edge of path
+      EdgeIt(const ListPath &_path) 
+        : path(&_path), node(_path.first) {}
+
+    protected:
+
+      EdgeIt(const ListPath &_path, Node *_node) 
+        : path(&_path), node(_node) {}
+
+
+    public:
+
+      ///Conversion to Graph::Edge
+      operator const Edge&() const {
+        return node->edge;
+      }
+
+      /// Next edge
+      EdgeIt& operator++() { 
+        node = node->next;
+        return *this; 
+      }
+
       /// Comparison operator
-      bool operator!=(const EdgeIt& e) const { return id != e.id; }
+      bool operator==(const EdgeIt& e) const { return node==e.node; }
+      /// Comparison operator
+      bool operator!=(const EdgeIt& e) const { return node!=e.node; }
+      /// Comparison operator
+      bool operator<(const EdgeIt& e) const { return node<e.node; }
 
-      /// \brief Comparison operator
-      ///
-      /// Comparison operator
-      bool operator<(const EdgeIt& e) const { return id < e.id; }
+    private:
+      const ListPath *path;
+      Node *node;
+    };
+
+    /// \brief Gives back the nth edge.
+    ///
+    /// Gives back the nth edge in O(n) time.
+    /// \pre n is in the [0..length() - 1] range
+    const Edge& nth(int n) const {
+      Node *node = first;
+      for (int i = 0; i < n; ++i) {
+        node = node->next;
+      }
+      return node->edge;
+    }
+
+    /// \brief Initializes edge iterator to point to the nth edge.
+    EdgeIt nthIt(int n) const {
+      Node *node = first;
+      for (int i = 0; i < n; ++i) {
+        node = node->next;
+      }
+      return EdgeIt(*this, node);
+    }
+
+    /// \brief Length of the path.
+    int length() const {
+      int len = 0;
+      Node *node = first;
+      while (node != 0) {
+        node = node->next;
+        ++len;
+      }
+      return len;
+    }
+
+    /// \brief Returns whether the path is empty.
+    bool empty() const { return first == 0; }
+
+    /// \brief Resets the path to an empty path.
+    void clear() {
+      while (first != 0) {
+        last = first->next;
+        alloc.destroy(first);
+        alloc.deallocate(first, 1);
+        first = last;
+      }
+    }
+
+    /// \brief Gives back the first edge of the path
+    const Edge& front() const {
+      return first->edge;
+    }
+
+    /// \brief Add a new edge before the current path
+    void addFront(const Edge& edge) {
+      Node *node = alloc.allocate(1);
+      alloc.construct(node, Node());
+      node->prev = 0;
+      node->next = first;
+      node->edge = edge;
+      if (first) {
+        first->prev = node;
+        first = node;
+      } else {
+        first = last = node;
+      }
+    }
+
+    /// \brief Erase the first edge of the path
+    void eraseFront() {
+      Node *node = first;
+      first = first->next;
+      if (first) {
+        first->prev = 0;
+      } else {
+        last = 0;
+      }
+      alloc.destroy(node);
+      alloc.deallocate(node, 1);
+    }
+
+    /// \brief Gives back the last edge of the path.
+    const Edge& back() const {
+      return last->edge;
+    }
+
+    /// \brief Add a new edge behind the current path.
+    void addBack(const Edge& edge) {
+      Node *node = alloc.allocate(1);
+      alloc.construct(node, Node());
+      node->next = 0;
+      node->prev = last;
+      node->edge = edge;
+      if (last) {
+        last->next = node;
+        last = node;
+      } else {
+        last = first = node;
+      }
+    }
+
+    /// \brief Erase the last edge of the path
+    void eraseBack() {
+      Node *node = last;
+      last = last->prev;
+      if (last) {
+        last->next = 0;
+      } else {
+        first = 0;
+      }
+      alloc.destroy(node);
+      alloc.deallocate(node, 1);
+    }
+
+    /// \brief Splicing the given path to the current path.
+    ///
+    /// It splices the \c tpath to the back of the current path and \c
+    /// tpath becomes empty. The time complexity of this function is
+    /// O(1).
+    void spliceBack(ListPath& tpath) {
+      if (first) {
+        if (tpath.first) {
+          last->next = tpath.first;
+          tpath.first->prev = last;
+          last = tpath.last;
+        }
+      } else {
+        first = tpath.first;
+        last = tpath.last;
+      }
+      tpath.first = tpath.last = 0;
+    }
+
+    /// \brief Splicing the given path to the current path.
+    ///
+    /// It splices the \c tpath before the current path and \c tpath
+    /// becomes empty. The time complexity of this function
+    /// is O(1).
+    void spliceFront(ListPath& tpath) {
+      if (first) {
+        if (tpath.first) {
+          first->prev = tpath.last;
+          tpath.last->next = first;
+          first = tpath.first;
+        }
+      } else {
+        first = tpath.first;
+        last = tpath.last;
+      }
+      tpath.first = tpath.last = 0;
+    }
+
+    /// \brief Splicing the given path into the current path.
+    ///
+    /// It splices the \c tpath into the current path before the
+    /// position of \c it iterator and \c tpath becomes empty. The
+    /// time complexity of this function is O(1). If the \c it is \c
+    /// INVALID then it will splice behind the current path.
+    void splice(EdgeIt it, ListPath& tpath) {
+      if (it.node) {
+        if (tpath.first) {
+          tpath.first->prev = it.node->prev;
+          if (it.node->prev) {
+            it.node->prev->next = tpath.first;
+          } else {
+            first = tpath.first;
+          }
+          it.node->prev = tpath.last;
+          tpath.last->next = it.node;
+        }
+      } else {
+        if (first) {
+          if (tpath.first) {
+            last->next = tpath.first;
+            tpath.first->prev = last;
+            last = tpath.last;
+          }
+        } else {
+          first = tpath.first;
+          last = tpath.last;
+        }
+      }
+      tpath.first = tpath.last = 0;
+    }
+
+    /// \brief Spliting the current path.
+    ///
+    /// It splits the current path into two parts. The part before \c
+    /// it iterator will remain in the current path and the part from
+    /// the it will put into the \c tpath. If the \c tpath had edges
+    /// before the operation they will be removed first.  The time
+    /// complexity of this function is O(1) plus the clearing of \c
+    /// tpath. If the \c it is \c INVALID then it just clears \c
+    /// tpath.
+    void split(EdgeIt it, ListPath& tpath) {
+      tpath.clear();
+      if (it.node) {
+        tpath.first = it.node;
+        tpath.last = last;
+        if (it.node->prev) {
+          last = it.node->prev;
+          last->next = 0;
+        } else {
+          first = last = 0;
+        }
+        it.node->prev = 0;
+      }
+    }
+
+
+    typedef True BuildTag;
+
+    template <typename CPath>
+    void build(const CPath& path) {
+      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
+        addBack(it);
+      }
+    }
+
+    template <typename CPath>
+    void buildRev(const CPath& path) {
+      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
+        addFront(it);
+      }
+    }
+
+  };
+
+  /// \brief A structure for representing directed paths in a graph.
+  ///
+  /// A structure for representing directed path in a graph.
+  /// \param Graph The graph type in which the path is.
+  ///
+  /// 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 source.
+  ///
+  /// This implementation is completly static, so it cannot be
+  /// modified exclude the assign an other path. It is intented to be
+  /// used when you want to store a large amount paths because it is
+  /// the most memory efficient path type in the lemon.
+  template <typename _Graph>
+  class StaticPath {
+  public:
+
+    typedef _Graph Graph;
+    typedef typename Graph::Edge Edge;
+
+    /// \brief Default constructor
+    ///
+    /// Default constructor
+    StaticPath() : len(0), edges(0) {}
+    
+    /// \brief Template copy constructor
+    ///
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    StaticPath(const CPath& cpath) : edges(0) {
+      copyPath(*this, cpath);
+    }
+
+    /// \brief Destructor of the path
+    ///
+    /// Destructor of the path
+    ~StaticPath() {
+      if (edges) delete[] edges;
+    }
+
+    /// \brief Template copy assignment
+    ///
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    StaticPath& operator=(const CPath& cpath) {
+      copyPath(*this, cpath);
+      return *this;
+    }
+
+    /// \brief Iterator class to iterate on the edges of the paths
+    ///
+    /// This class is used to iterate on the edges of the paths
+    ///
+    /// Of course it converts to Graph::Edge
+    class EdgeIt {
+      friend class StaticPath;
+    public:
+      /// Default constructor
+      EdgeIt() {}
+      /// Invalid constructor
+      EdgeIt(Invalid) : path(0), idx(-1) {}
+      /// Initializate the constructor to the first edge of path
+      EdgeIt(const StaticPath &_path) 
+        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 
     private:
 
-      int id;
-      const Path *path;
+      /// Constructor with starting point
+      EdgeIt(const StaticPath &_path, int _idx) 
+        : idx(_idx), path(&_path) {}
+
+    public:
+
+      ///Conversion to Graph::Edge
+      operator const Edge&() const {
+        return path->nth(idx);
+      }
+
+      /// Next edge
+      EdgeIt& operator++() { 
+        ++idx;
+        if (idx >= path->length()) idx = -1; 
+        return *this; 
+      }
+
+      /// Comparison operator
+      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
+      /// Comparison operator
+      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
+      /// Comparison operator
+      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
+
+    private:
+      const StaticPath *path;
+      int idx;
     };
 
-  protected:
+    /// \brief Gives back the nth edge.
+    ///
+    /// \pre n is in the [0..length() - 1] range
+    const Edge& nth(int n) const {
+      return edges[n];
+    }
 
-    const Graph *graph;
+    /// \brief Initializes edge iterator to point to the nth edge.
+    EdgeIt nthIt(int n) const {
+      return EdgeIt(*this, n);
+    }
 
-    typedef std::vector<Edge> Container;
-    Container edges;
-    Node start;
+    /// \brief Gives back the length of the path.
+    int length() const { return len; }
 
-  public:
+    /// \brief Returns true when the path is empty.
+    int empty() const { return len == 0; }
 
-    friend class Builder;
+    /// \break Erase all edge in the graph.
+    void clear() {
+      len = 0;
+      if (edges) delete[] edges;
+      edges = 0;
+    }
 
-    /// \brief Class to build paths
-    ///
-    /// This class is used to fill a path with edges.
-    ///
-    /// You can push new edges to the front and to the back of the
-    /// path in arbitrary order then you should commit these changes
-    /// to the graph.
-    ///
-    /// Fundamentally, for most "Paths" (classes fulfilling the
-    /// PathConcept) while the builder is active (after the first
-    /// modifying operation and until the commit()) the original Path
-    /// is in a "transitional" state (operations on it have undefined
-    /// result). But in the case of Path the original path remains
-    /// unchanged until the commit. However we don't recomend that you
-    /// use this feature.
-    class Builder {
-    public:
-      /// \brief Constructor
-      ///
-      /// Constructor
-      /// \param _path the path you want to fill in.
-      Builder(Path &_path) : path(_path), start(INVALID) {}
+    /// \brief Gives back the first edge of the path.
+    const Edge& front() const {
+      return edges[0];
+    }
 
-      /// \brief Destructor
-      ///
-      /// Destructor
-      ~Builder() {
-        LEMON_ASSERT(front.empty() && back.empty() && start == INVALID, 
-                     PathError());
+    /// \brief Gives back the last edge of the path.
+    const Edge& back() const {
+      return edges[len - 1];
+    }
+
+
+    typedef True BuildTag;
+
+    template <typename CPath>
+    void build(const CPath& path) {
+      len = path.length();
+      edges = new Edge[len];
+      int index = 0;
+      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
+        edges[index] = it;
+        ++index;
       }
+    }
 
-      /// \brief Sets the starting node of the path.
-      ///
-      /// Sets the starting node of the path. Edge added to the path
-      /// afterwards have to be incident to this node.  It should be
-      /// called if and only if the path is empty and before any call
-      /// to \ref pushFront() or \ref pushBack()
-      void setStartNode(const Node &_start) {
-        LEMON_ASSERT(path.empty() && start == INVALID, PathError());
-        start = _start;
+    template <typename CPath>
+    void buildRev(const CPath& path) {
+      len = path.length();
+      edges = new Edge[len];
+      int index = len;
+      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
+        --index;
+        edges[index] = it;
       }
+    }
 
-      /// \brief Push a new edge to the front of the path
-      ///
-      /// Push a new edge to the front of the path.  
-      /// \sa setStartNode
-      void pushFront(const Edge& e) {
-        LEMON_ASSERT(front.empty() || 
-                     (path.graph->source(front.back()) == 
-                      path.graph->target(e)), PathError());
-        LEMON_ASSERT(path.empty() || 
-                     (path.source() == path.graph->target(e)), PathError());
-        LEMON_ASSERT(!path.empty() || !front.empty() ||
-                     (start == path.graph->target(e)), PathError());
-	front.push_back(e);
-      }
-
-      /// \brief Push a new edge to the back of the path
-      ///
-      /// Push a new edge to the back of the path.
-      /// \sa setStartNode
-      void pushBack(const Edge& e) {
-        LEMON_ASSERT(back.empty() || 
-                     (path.graph->target(back.back()) == 
-                      path.graph->source(e)), PathError());
-        LEMON_ASSERT(path.empty() || 
-                     (path.target() == path.graph->source(e)), PathError());
-        LEMON_ASSERT(!path.empty() || !back.empty() ||
-                     (start == path.graph->source(e)), PathError());
-	back.push_back(e);
-      }
-
-      /// \brief Commit the changes to the path.
-      ///
-      /// Commit the changes to the path.
-      void commit() {
-	if( !front.empty() || !back.empty() || start != INVALID) {
-	  Container tmp;
-	  tmp.reserve(front.size() + back.size() + path.length());
-	  tmp.insert(tmp.end(), front.rbegin(), front.rend());
-	  tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());
-	  tmp.insert(tmp.end(), back.begin(), back.end());
-	  path.edges.swap(tmp);
-          if (!front.empty()) {
-            path.start = path.graph->source(front.back());
-          } else {
-            path.start = start;
-          }
-          start = INVALID;
-	  front.clear();
-	  back.clear();
-	}
-      }
-
-      /// \brief Reserve storage for the builder in advance.
-      ///
-      /// If you know a reasonable upper bound of the number of the
-      /// edges to add to the front, using this function you can speed
-      /// up the building.
-      void reserveFront(size_t r) {front.reserve(r);}
-
-      /// \brief Reserve storage for the builder in advance.
-      ///
-      /// If you know a reasonable upper bound of the number of the
-      /// edges to add to the back, using this function you can speed
-      /// up the building.
-      void reserveBack(size_t r) {back.reserve(r);}
-
-    private:
-
-      Path &path;
-      Container front, back;
-      Node start;
-
-    };
-
+  private:
+    int len;
+    Edge* edges;
   };
 
   ///@}