RhodeCode

  /// A structure for representing directed path in a digraph.

  /// \param Digraph The digraph type in which the path is.

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  ///

  /// This implementation is a back and front insertable and erasable

  /// path type. It can be indexed in O(1) time. The front and back

  template <typename _Digraph>

  class Path {

  public:

    Path() {}

    /// \brief Template copy constructor

    ///

    template <typename CPath>

    Path(const CPath& cpath) {

      copyPath(*this, cpath);

    }

    /// \brief Template copy assignment

    ///

    template <typename CPath>

    Path& operator=(const CPath& cpath) {

      copyPath(*this, cpath);

      return *this;

      /// \brief Default constructor

      ArcIt() {}

      /// \brief Invalid constructor

      ArcIt(Invalid) : path(0), idx(-1) {}

      ArcIt(const Path &_path) 

        : path(&_path), idx(_path.empty() ? -1 : 0) {}

    private:

    };

    /// \brief Length of the path.

    int length() const { return head.size() + tail.size(); }

    bool empty() const { return head.empty() && tail.empty(); }

    void clear() { head.clear(); tail.clear(); }

    ///

    /// \pre n is in the [0..length() - 1] range

    const Arc& nth(int n) const {

      return n < int(head.size()) ? *(head.rbegin() + n) :

        *(tail.begin() + (n - head.size()));

    }

    ///

    /// \pre n is in the [0..length() - 1] range

    ArcIt nthIt(int n) const {

      return ArcIt(*this, n);

    }

    const Arc& front() const {

      return head.empty() ? tail.front() : head.back();

    }

        tail.resize(tail.size() - halfsize - 1);

      }

    }

    const Arc& back() const {

      return tail.empty() ? head.front() : tail.back();

    }

        head.resize(head.size() - halfsize - 1);

      }

    }

    typedef True BuildTag;

    template <typename CPath>

    void build(const CPath& path) {

    };

    /// \brief Length of the path.

    int length() const { return data.size(); }

    bool empty() const { return data.empty(); }

    void clear() { data.clear(); }

    ///

    /// \pre n is in the [0..length() - 1] range

    const Arc& nth(int n) const {

      return data[n];

    ArcIt nthIt(int n) const {

      return ArcIt(*this, n);

    }

    const Arc& front() const {

      return data.front();

    }

    const Arc& back() const {

      return data.back();

    }

      const ListPath *path;

      Node *node;

    };

    ///

    /// \pre n is in the [0..length() - 1] range

    const Arc& nth(int n) const {

      Node *node = first;

      for (int i = 0; i < n; ++i) {

      }

      return len;

    }

    bool empty() const { return first == 0; }

    void clear() {

      while (first != 0) {

        last = first->next;

        alloc.destroy(first);

        first = last;

      }

    }

    const Arc& front() const {

      return first->arc;

    }

      alloc.destroy(node);

      alloc.deallocate(node, 1);

    }

    const Arc& back() const {

      return last->arc;

    }

      alloc.destroy(node);

      alloc.deallocate(node, 1);

    }

    ///

    /// tpath becomes empty. The time complexity of this function is

    /// O(1).

    void spliceBack(ListPath& tpath) {

      if (first) {

      }

      tpath.first = tpath.last = 0;

    }

    ///

    /// becomes empty. The time complexity of this function

    /// is O(1).

    void spliceFront(ListPath& tpath) {

      if (first) {

      }

      tpath.first = tpath.last = 0;

    }

    ///

    /// It splices the \c tpath into the current path before the

    /// position of \c it iterator and \c tpath becomes empty. The

    void splice(ArcIt it, ListPath& tpath) {

      if (it.node) {

        if (tpath.first) {

          tpath.first->prev = it.node->prev;

      }

      tpath.first = tpath.last = 0;

    }

    ///

    void split(ArcIt it, ListPath& tpath) {

      tpath.clear();

      if (it.node) {

        tpath.first = it.node;

  /// \param Digraph The digraph type in which the path is.

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// lemon path type stores just this list. As a consequence it

  ///

  template <typename _Digraph>

  class StaticPath {

  public:

    StaticPath() : len(0), arcs(0) {}

    /// \brief Template copy constructor

    ///

    template <typename CPath>

    StaticPath(const CPath& cpath) : arcs(0) {

      copyPath(*this, cpath);

    }

    }

    /// \brief Template copy assignment

    ///

    /// makes a copy of the given path.

    template <typename CPath>

    StaticPath& operator=(const CPath& cpath) {

      copyPath(*this, cpath);

      const StaticPath *path;

      int idx;

    };

    ///

    /// \pre n is in the [0..length() - 1] range

    const Arc& nth(int n) const {

      return arcs[n];

    }

    ArcIt nthIt(int n) const {

      return ArcIt(*this, n);

    }

    int length() const { return len; }

    int empty() const { return len == 0; }

    void clear() {

      len = 0;

      if (arcs) delete[] arcs;

      arcs = 0;

    }

    const Arc& front() const {

      return arcs[0];

    }

    const Arc& back() const {

      return arcs[len - 1];

    }

  }

  ///

  template <typename Target, typename Source>

  void copyPath(Target& target, const Source& source) {

    checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();

    _path_bits::PathCopySelector<Target, Source>::copy(target, source);

  }

  ///

  /// 

  template <typename Digraph, typename Path>

  bool checkPath(const Digraph& digraph, const Path& path) {

    typename Path::ArcIt it(path);

    }

    return true;

  }

  ///

  template <typename Digraph, typename Path>

  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {

    return digraph.source(path.front());

  }

  ///

  template <typename Digraph, typename Path>

  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {

    return digraph.target(path.back());

  }

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// cannot enumerate the nodes in the path and the zero length paths

  ///

  /// This class implements the node iterator of a path structure. To

  /// the constructor of the iterator.

  template <typename Path>

  class PathNodeIt {

  private: