RhodeCode

namespace lemon {

  /// \addtogroup paths

  /// @{

  /// \brief A structure for representing directed paths in a digraph.

  ///

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

  /// \tparam GR The digraph type in which the path is.

  ///

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

  /// cannot enumerate the nodes of the path and the source node of

  /// a zero length path is undefined.

  ///

  /// 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 erase is done in O(1) (amortized) time. The

  /// implementation uses two vectors for storing the front and back

  /// insertions.

  template <typename GR>

  class Path {

  public:

      const Path *path;

      int idx;

    };

    /// \brief Length of the path.

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

    /// \brief Return whether the path is empty.

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

    /// \brief Reset the path to an empty one.

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

    ///

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

    const Arc& nth(int n) const {

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

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

    }

    ///

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

    ArcIt nthIt(int n) const {

      return ArcIt(*this, n);

    }

    /// \brief The first arc of the path

    const Arc& front() const {

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

    }

    /// \brief Add a new arc before the current path

  protected:

    typedef std::vector<Arc> Container;

    Container head, tail;

  };

  /// \brief A structure for representing directed paths in a digraph.

  ///

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

  /// \tparam GR The digraph type in which the path is.

  ///

  /// 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

  /// 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

  /// arcs.

  template <typename GR>

  class SimplePath {

  public:

      const SimplePath *path;

      int idx;

    };

    /// \brief Length of the path.

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

    /// \brief Return true if the path is empty.

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

    /// \brief Reset the path to an empty one.

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

    ///

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

    const Arc& nth(int n) const {

      return data[n];

    }

    ArcIt nthIt(int n) const {

      return ArcIt(*this, n);

    }

    /// \brief The first arc of the path.

    const Arc& front() const {

      return data.front();

    }

    /// \brief The last arc of the path.

    const Arc& back() const {

      return data.back();

  protected:

    typedef std::vector<Arc> Container;

    Container data;

  };

  /// \brief A structure for representing directed paths in a digraph.

  ///

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

  /// \tparam GR The digraph type in which the path is.

  ///

  /// 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

  /// 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 arc 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 GR>

  class ListPath {

  public:

      /// Comparison operator

      bool operator==(const ArcIt& e) const { return node==e.node; }

      /// Comparison operator

      bool operator!=(const ArcIt& e) const { return node!=e.node; }

      /// Comparison operator

      bool operator<(const ArcIt& e) const { return node<e.node; }

    private:

      const ListPath *path;

      Node *node;

    };

    ///

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

    const Arc& nth(int n) const {

      Node *node = first;

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

        node = node->next;

      }

      return node->arc;

    }

    ArcIt nthIt(int n) const {

      Node *node = first;

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

        node = node->next;

      }

      return ArcIt(*this, node);

    }

    /// \brief Length of the path.

    int length() const {

      int len = 0;

      Node *node = first;

        addFront(it);

      }

    }

  };

  /// \brief A structure for representing directed paths in a digraph.

  ///

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

  /// \tparam GR The digraph type in which the path is.

  ///

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

  /// cannot enumerate the nodes in the path and the source node of

  /// a zero length path is undefined.

  ///

  /// This implementation is completly static, i.e. it can be copy constucted

  /// or copy assigned from another path, but otherwise it cannot be

  /// modified.

  ///

  /// Being the the most memory efficient path type in LEMON,

  /// it is intented to be

  /// used when you want to store a large number of paths.

  template <typename GR>

  class StaticPath {

      /// Comparison operator

      bool operator==(const ArcIt& e) const { return idx==e.idx; }

      /// Comparison operator

      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }

      /// Comparison operator

      bool operator<(const ArcIt& e) const { return idx<e.idx; }

    private:

      const StaticPath *path;

      int idx;

    };

    ///

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

    const Arc& nth(int n) const {

      return arcs[n];

    }

    ArcIt nthIt(int n) const {

      return ArcIt(*this, n);

    }

    /// \brief The length of the path.

    int length() const { return len; }

    /// \brief Return true when the path is empty.

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

    /// \brief Erase all arcs in the digraph.

    void clear() {

  /// \brief The target of a path

  ///

  /// This function returns the target node of the given path.

  /// If the path is empty, then it returns \c INVALID.

  template <typename Digraph, typename Path>

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

    return path.empty() ? INVALID : digraph.target(path.back());

  }

  /// \brief Class which helps to iterate through the nodes of a path

  ///

  /// 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

  /// cannot have a source node.

  ///

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

  /// provide this feature, the underlying digraph should be passed to

  /// the constructor of the iterator.

  template <typename Path>

  class PathNodeIt {

  private:

    const typename Path::Digraph *_digraph;

    typename Path::ArcIt _it;

    typename Path::Digraph::Node _nd;