# HG changeset patch # User hegyi # Date 1095089401 0 # Node ID 2d50d1f045c5bbdd8d39efc58e4c0032b552cc01 # Parent f8549e3f6c5a9b2a951e75ff497062f51cfc73df Reserve is resolved. diff -r f8549e3f6c5a -r 2d50d1f045c5 src/hugo/path.h --- a/src/hugo/path.h Mon Sep 13 13:57:13 2004 +0000 +++ b/src/hugo/path.h Mon Sep 13 15:30:01 2004 +0000 @@ -40,7 +40,7 @@ //! A structure for representing directed path in a graph. //! \param Graph The graph type in which the path is. //! \param DM DebugMode, defaults to DefaultDebugMode. - //! + //! //! 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. @@ -50,7 +50,7 @@ class DirPath { public: /// Edge type of the underlying graph. - typedef typename Graph::Edge GraphEdge; + typedef typename Graph::Edge GraphEdge; /// Node type of the underlying graph. typedef typename Graph::Node GraphNode; class NodeIt; @@ -154,12 +154,12 @@ /** * \brief Iterator class to iterate on the edges of the paths - * + * * \ingroup paths * This class is used to iterate on the edges of the paths * * Of course it converts to Graph::Edge - * + * * \todo Its interface differs from the standard edge iterator. * Yes, it shouldn't. */ @@ -203,12 +203,12 @@ /** * \brief Iterator class to iterate on the nodes of the paths - * + * * \ingroup paths * This class is used to iterate on the nodes of the paths * * Of course it converts to Graph::Node - * + * * \todo Its interface differs from the standard node iterator. * Yes, it shouldn't. */ @@ -252,11 +252,11 @@ void validate() { if( size_t(idx) > p->length() ) idx=-1; } }; - friend class Builder; + friend class Builder; /** * \brief Class to build paths - * + * * \ingroup paths * This class is used to fill a path with edges. * @@ -280,7 +280,7 @@ Builder(DirPath &_P) : P(_P) {} /// 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 iff the path is empty and before any call to @@ -305,7 +305,7 @@ ///Commit the changes to the path. void commit() { - if( !(front.empty() && back.empty()) ) { + if( !front.empty() || !back.empty() ) { Container tmp; tmp.reserve(front.size()+back.size()+P.length()); tmp.insert(tmp.end(), front.rbegin(), front.rend()); @@ -317,20 +317,19 @@ } } - // FIXME: Hmm, pontosan hogy is kene ezt csinalni? - // Hogy kenyelmes egy ilyet hasznalni? - ///Reserve storage for the builder in advance. - ///If you know an reasonable upper bound of the number of the edges - ///to add, using this function you can speed up the building. - void reserve(size_t r) { - front.reserve(r); - back.reserve(r); - } + ///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) {} - void reserveBack(size_t r) {} + void reserveFront(size_t r) {front.reserve(r);} + + ///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: bool empty() { @@ -382,7 +381,7 @@ //! //! \param Graph The graph type in which the path is. //! \param DM DebugMode, defaults to DefaultDebugMode. - //! + //! //! 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. @@ -495,12 +494,12 @@ /** * \brief Iterator class to iterate on the edges of the paths - * + * * \ingroup paths * This class is used to iterate on the edges of the paths * * Of course it converts to Graph::Edge - * + * * \todo Its interface differs from the standard edge iterator. * Yes, it shouldn't. */ @@ -543,12 +542,12 @@ /** * \brief Iterator class to iterate on the nodes of the paths - * + * * \ingroup paths * This class is used to iterate on the nodes of the paths * * Of course it converts to Graph::Node - * + * * \todo Its interface differs from the standard node iterator. * Yes, it shouldn't. */ @@ -592,11 +591,11 @@ void validate() { if( size_t(idx) > p->length() ) idx=-1; } }; - friend class Builder; + friend class Builder; /** * \brief Class to build paths - * + * * \ingroup paths * This class is used to fill a path with edges. * @@ -620,7 +619,7 @@ Builder(UndirPath &_P) : P(_P) {} /// 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 iff the path is empty and before any call to @@ -657,20 +656,20 @@ } } - // FIXME: Hmm, pontosan hogy is kene ezt csinalni? - // Hogy kenyelmes egy ilyet hasznalni? ///Reserve storage for the builder in advance. - ///If you know an reasonable upper bound of the number of the edges - ///to add, using this function you can speed up the building. - void reserve(size_t r) { - front.reserve(r); - back.reserve(r); - } + ///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) {} - void reserveBack(size_t r) {} + void reserveFront(size_t r) {front.reserve(r);} + + ///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: bool empty() { @@ -703,426 +702,6 @@ }; - - - - - - - - - /**********************************************************************/ - - - /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata - elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */ - - template - class DynamicPath { - - public: - typedef typename Graph::Edge GraphEdge; - typedef typename Graph::Node GraphNode; - class NodeIt; - class EdgeIt; - - protected: - Graph& G; - // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el - // iranyitasat: - GraphNode _first, _last; - typedef std::deque Container; - Container edges; - - public: - - DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {} - - /// Subpath defined by two nodes. - /// Nodes may be in reversed order, then - /// we contstruct the reversed path. - DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b); - /// Subpath defined by two edges. Contains edges in [a,b) - /// It is an error if the two edges are not in order! - DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b); - - size_t length() const { return edges.size(); } - GraphNode tail() const { return _first; } - GraphNode head() const { return _last; } - - NodeIt& first(NodeIt &n) const { return nth(n, 0); } - EdgeIt& first(EdgeIt &e) const { return nth(e, 0); } - template - It first() const { - It e; - first(e); - return e; - } - - NodeIt& nth(NodeIt &, size_t) const; - EdgeIt& nth(EdgeIt &, size_t) const; - template - It nth(size_t n) const { - It e; - nth(e, n); - return e; - } - - bool valid(const NodeIt &n) const { return n.idx <= length(); } - bool valid(const EdgeIt &e) const { return e.it < edges.end(); } - - bool isForward(const EdgeIt &e) const { return e.forw; } - - /// index of a node on the path. Returns length+2 for the invalid NodeIt - int index(const NodeIt &n) const { return n.idx; } - /// index of an edge on the path. Returns length+1 for the invalid EdgeIt - int index(const EdgeIt &e) const { return e.it - edges.begin(); } - - EdgeIt& next(EdgeIt &e) const; - NodeIt& next(NodeIt &n) const; - template - It getNext(It it) const { - It tmp(it); return next(tmp); - } - - // A path is constructed using the following four functions. - // They return false if the requested operation is inconsistent - // with the path constructed so far. - // If your path has only one edge you MUST set either "from" or "to"! - // So you probably SHOULD call it in any case to be safe (and check the - // returned value to check if your path is consistent with your idea). - bool pushFront(const GraphEdge &e); - bool pushBack(const GraphEdge &e); - bool setFrom(const GraphNode &n); - bool setTo(const GraphNode &n); - - // WARNING: these two functions return the head/tail of an edge with - // respect to the direction of the path! - // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if - // P.forward(e) is true (or the edge is a loop)! - NodeIt head(const EdgeIt& e) const; - NodeIt tail(const EdgeIt& e) const; - - // FIXME: ezeknek valami jobb nev kellene!!! - GraphEdge graphEdge(const EdgeIt& e) const; - GraphNode graphNode(const NodeIt& n) const; - - - /*** Iterator classes ***/ - class EdgeIt { - friend class DynamicPath; - - typename Container::const_iterator it; - bool forw; - public: - // FIXME: jarna neki ilyen is... - // EdgeIt(Invalid); - - bool forward() const { return forw; } - - bool operator==(const EdgeIt& e) const { return it==e.it; } - bool operator!=(const EdgeIt& e) const { return it!=e.it; } - bool operator<(const EdgeIt& e) const { return it - typename DynamicPath::EdgeIt& - DynamicPath::next(DynamicPath::EdgeIt &e) const { - if( e.it == edges.end() ) - return e; - - GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) ); - ++e.it; - - // Invalid edgeit is always forward :) - if( e.it == edges.end() ) { - e.forw = true; - return e; - } - - e.forw = ( G.tail(*e.it) == common_node ); - return e; - } - - template - typename DynamicPath::NodeIt& DynamicPath::next(NodeIt &n) const { - if( n.idx >= length() ) { - // FIXME: invalid - n.idx = length()+1; - return n; - } - - - GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) : - G.tail(edges[n.idx]) ); - ++n.idx; - if( n.idx < length() ) { - n.tail = ( next_node == G.tail(edges[n.idx]) ); - } - else { - n.tail = true; - } - - return n; - } - - template - bool DynamicPath::edgeIncident(const GraphEdge &e, const GraphNode &a, - GraphNode &b) { - if( G.tail(e) == a ) { - b=G.head(e); - return true; - } - if( G.head(e) == a ) { - b=G.tail(e); - return true; - } - return false; - } - - template - bool DynamicPath::connectTwoEdges(const GraphEdge &e, - const GraphEdge &f) { - if( edgeIncident(f, G.tail(e), _last) ) { - _first = G.head(e); - return true; - } - if( edgeIncident(f, G.head(e), _last) ) { - _first = G.tail(e); - return true; - } - return false; - } - - template - bool DynamicPath::pushFront(const GraphEdge &e) { - if( G.valid(_first) ) { - if( edgeIncident(e, _first, _first) ) { - edges.push_front(e); - return true; - } - else - return false; - } - else if( length() < 1 || connectTwoEdges(e, edges[0]) ) { - edges.push_front(e); - return true; - } - else - return false; - } - - template - bool DynamicPath::pushBack(const GraphEdge &e) { - if( G.valid(_last) ) { - if( edgeIncident(e, _last, _last) ) { - edges.push_back(e); - return true; - } - else - return false; - } - else if( length() < 1 || connectTwoEdges(edges[0], e) ) { - edges.push_back(e); - return true; - } - else - return false; - } - - - template - bool DynamicPath::setFrom(const GraphNode &n) { - if( G.valid(_first) ) { - return _first == n; - } - else { - if( length() > 0) { - if( edgeIncident(edges[0], n, _last) ) { - _first = n; - return true; - } - else return false; - } - else { - _first = _last = n; - return true; - } - } - } - - template - bool DynamicPath::setTo(const GraphNode &n) { - if( G.valid(_last) ) { - return _last == n; - } - else { - if( length() > 0) { - if( edgeIncident(edges[0], n, _first) ) { - _last = n; - return true; - } - else return false; - } - else { - _first = _last = n; - return true; - } - } - } - - - template - typename DynamicPath::NodeIt - DynamicPath::tail(const EdgeIt& e) const { - NodeIt n; - - if( e.it == edges.end() ) { - // FIXME: invalid-> invalid - n.idx = length() + 1; - n.tail = true; - return n; - } - - n.idx = e.it-edges.begin(); - n.tail = e.forw; - return n; - } - - template - typename DynamicPath::NodeIt - DynamicPath::head(const EdgeIt& e) const { - if( e.it == edges.end()-1 ) { - return _last; - } - - EdgeIt next_edge = e; - next(next_edge); - return tail(next_edge); - } - - template - typename DynamicPath::GraphEdge - DynamicPath::graphEdge(const EdgeIt& e) const { - if( e.it != edges.end() ) { - return *e.it; - } - else { - return INVALID; - } - } - - template - typename DynamicPath::GraphNode - DynamicPath::graphNode(const NodeIt& n) const { - if( n.idx < length() ) { - return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]); - } - else if( n.idx == length() ) { - return _last; - } - else { - return INVALID; - } - } - - template - typename DynamicPath::EdgeIt& - DynamicPath::nth(EdgeIt &e, size_t k) const { - if( k>=length() ) { - // FIXME: invalid EdgeIt - e.it = edges.end(); - e.forw = true; - return e; - } - - e.it = edges.begin()+k; - if(k==0) { - e.forw = ( G.tail(*e.it) == _first ); - } - else { - e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) || - G.tail(*e.it) == G.head(edges[k-1]) ); - } - return e; - } - - template - typename DynamicPath::NodeIt& - DynamicPath::nth(NodeIt &n, size_t k) const { - if( k>length() ) { - // FIXME: invalid NodeIt - n.idx = length()+1; - n.tail = true; - return n; - } - if( k==length() ) { - n.idx = length(); - n.tail = true; - return n; - } - n = tail(nth(k)); - return n; - } - - // Reszut konstruktorok: - - - template - DynamicPath::DynamicPath(const DynamicPath &P, const EdgeIt &a, - const EdgeIt &b) : - G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up! - { - if( G.valid(P._first) && a.it < P.edges.end() ) { - _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) ); - if( b.it < P.edges.end() ) { - _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) ); - } - else { - _last = P._last; - } - } - } - - template - DynamicPath::DynamicPath(const DynamicPath &P, const NodeIt &a, - const NodeIt &b) : G(P.G) - { - if( !P.valid(a) || !P.valid(b) ) - return; - - int ai = a.idx, bi = b.idx; - if( bi