RhodeCode

  ///

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

  class Path {

  public:

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    /// \brief Default constructor

    ///

    /// Default constructor

    Path() {}

    /// \brief Template copy constructor

    ///

    /// This constuctor initializes the path from any other path type.

    /// It simply makes a copy of the given path.

    template <typename CPath>

    Path(const CPath& cpath) {

    }

    /// \brief Template copy assignment

    ///

    /// This operator makes a copy of a path of any other type.

    template <typename CPath>

    Path& operator=(const CPath& cpath) {

      return *this;

    }

    /// \brief LEMON style iterator for path arcs

    ///

    /// This class is used to iterate on the arcs of the paths.

    class ArcIt {

      friend class Path;

    public:

      /// \brief Default constructor

      ArcIt() {}

      /// \brief Invalid constructor

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

      /// \brief Initializate the iterator to the first arc of path

      ArcIt(const Path &_path)

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

    private:

      ArcIt(const Path &_path, int _idx)

        : path(&_path), idx(_idx) {}

    public:

  ///

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

  class SimplePath {

  public:

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    /// \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) {

    }

    /// \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) {

      return *this;

    }

    /// \brief Iterator class to iterate on the arcs of the paths

    ///

    /// This class is used to iterate on the arcs of the paths

    ///

    /// Of course it converts to Digraph::Arc

    class ArcIt {

      friend class SimplePath;

    public:

      /// Default constructor

      ArcIt() {}

      /// Invalid constructor

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

      /// \brief Initializate the constructor to the first arc of path

      ArcIt(const SimplePath &_path)

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

    private:

      /// Constructor with starting point

      ArcIt(const SimplePath &_path, int _idx)

        : idx(_idx), path(&_path) {}

    // the std::list<> is incompatible

    // hard to create invalid iterator

    struct Node {

      Arc arc;

      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) {

    }

    /// \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) {

      return *this;

    }

    /// \brief Iterator class to iterate on the arcs of the paths

    ///

    /// This class is used to iterate on the arcs of the paths

    ///

    /// Of course it converts to Digraph::Arc

    class ArcIt {

      friend class ListPath;

    public:

      /// Default constructor

      ArcIt() {}

      /// Invalid constructor

      ArcIt(Invalid) : path(0), node(0) {}

      /// \brief Initializate the constructor to the first arc of path

      ArcIt(const ListPath &_path)

        : path(&_path), node(_path.first) {}

    protected:

      ArcIt(const ListPath &_path, Node *_node)

        : path(&_path), node(_node) {}

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

  class StaticPath {

  public:

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    /// \brief Default constructor

    ///

    /// Default constructor

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

    /// \brief Template copy constructor

    ///

    /// This path can be initialized from any other path type.

    template <typename CPath>

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

    }

    /// \brief Destructor of the path

    ///

    /// Destructor of the path

    ~StaticPath() {

      if (arcs) delete[] arcs;

    }

    /// \brief Template copy assignment

    ///

    /// This path can be made equal to any other path type. It simply

    /// makes a copy of the given path.

    template <typename CPath>

    StaticPath& operator=(const CPath& cpath) {

      return *this;

    }

    /// \brief Iterator class to iterate on the arcs of the paths

    ///

    /// This class is used to iterate on the arcs of the paths

    ///

    /// Of course it converts to Digraph::Arc

    class ArcIt {

      friend class StaticPath;

    public:

      /// Default constructor

      ArcIt() {}

      /// Invalid constructor

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

      /// Initializate the constructor to the first arc of path

      ArcIt(const StaticPath &_path)

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

    private:

      /// Constructor with starting point

      ArcIt(const StaticPath &_path, int _idx)

        : idx(_idx), path(&_path) {}

      static const bool value = false;

    };

    template <typename Path>

    struct RevPathTagIndicator<

      Path,

      typename enable_if<typename Path::RevPathTag, void>::type

      > {

      static const bool value = true;

    };

    template <typename Path, typename Enable = void>

    struct BuildTagIndicator {

      static const bool value = false;

    };

    template <typename Path>

    struct BuildTagIndicator<

      Path,

      typename enable_if<typename Path::BuildTag, void>::type

    > {

      static const bool value = true;

    };

    struct PathCopySelectorForward {

        }

      }

    };

      }

    };

    struct PathCopySelectorBackward {

        }

      }

    };

      }

    };

    struct PathCopySelector {

      }      

    };

      }      

    };

  }

  /// \brief Make a copy of a path.

  ///

  }

  /// \brief Check the consistency of a path.

  ///

  /// This function checks that the target of each arc is the same

  /// as the source of the next one.

  ///

  template <typename Digraph, typename Path>

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

    typename Path::ArcIt it(path);

    if (it == INVALID) return true;

    typename Digraph::Node node = digraph.target(it);

    ++it;

    while (it != INVALID) {

      if (digraph.source(it) != node) return false;

      node = digraph.target(it);

      ++it;

    }

    return true;

  }

  /// \brief The source of a path

  ///

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