# HG changeset patch # User deba # Date 1094119650 0 # Node ID df2e45e09652fb2d81bd99ca546871f702242362 # Parent d4d182ab75bdc4774eae4a8b86e8c4bef0d0f83f --This line, and those below, will be ignored-- A hugo/sym_map_factory.h M hugo/list_graph.h A hugo/array_map_factory.h A hugo/map_registry.h M hugo/smart_graph.h A hugo/map_defines.h A hugo/extended_pair.h M hugo/full_graph.h A hugo/vector_map_factory.h diff -r d4d182ab75bd -r df2e45e09652 src/hugo/array_map_factory.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/hugo/array_map_factory.h Thu Sep 02 10:07:30 2004 +0000 @@ -0,0 +1,366 @@ +// -*- c++ -*- +#ifndef ARRAY_MAP_FACTORY_H +#define ARRAY_MAP_FACTORY_H + +#include + +#include + +namespace hugo { + + template class ArrayMapFactory { + + public: + + typedef typename MapRegistry::Graph Graph; + typedef typename MapRegistry::Key Key; + typedef typename MapRegistry::KeyIt KeyIt; + + typedef typename MapRegistry::MapBase MapBase; + + template > + class Map : public MapBase { + + public: + + typedef V Value; + typedef A Allocator; + + + Map() : values(0), capacity(0) {} + + Map(const Graph& g, MapRegistry& r) : MapBase(g, r) { + allocate_memory(); + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { + int id = MapBase::getGraph()->id(it); + allocator.construct(&(values[id]), Value()); + } + } + + Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) { + allocate_memory(); + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { + int id = MapBase::getGraph()->id(it); + allocator.construct(&(values[id]), v); + } + } + + Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) { + capacity = copy.capacity; + if (capacity == 0) return; + values = allocator.allocate(capacity); + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { + int id = MapBase::getGraph()->id(it); + allocator.construct(&(values[id]), copy.values[id]); + } + } + + template Map(const CMap& copy) + : capacity(0), values(0), MapBase(copy) { + if (MapBase::getGraph()) { + allocate_memory(); + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { + set(it, copy[it]); + } + } + } + + Map& operator=(const Map& copy) { + if (© == this) return *this; + if (capacity != 0) { + MapBase::destroy(); + allocator.deallocate(values, capacity); + } + capacity = copy.capacity; + if (capacity == 0) return *this; + values = allocator.allocate(capacity); + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { + int id = MapBase::getGraph()->id(it); + allocator.construct(&(values[id]), copy.values[id]); + } + return *this; + } + + template Map& operator=(const CMap& copy) { + if (MapBase::getGraph()) { + MapBase::destroy(); + } + MapBase::operator=(copy); + if (MapBase::getGraph()) { + allocate_memory(); + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { + set(it, copy[it]); + } + } + return *this; + } + + virtual ~Map() { + if (capacity != 0) { + MapBase::destroy(); + allocator.deallocate(values, capacity); + } + } + + + Value& operator[](const Key& key) { + int id = MapBase::getGraph()->id(key); + return values[id]; + } + + const Value& operator[](const Key& key) const { + int id = MapBase::getGraph()->id(key); + return values[id]; + } + + const Value& get(const Key& key) const { + int id = MapBase::getGraph()->id(key); + return values[id]; + } + + void set(const Key& key, const Value& val) { + int id = MapBase::getGraph()->id(key); + values[id] = val; + } + + void add(const Key& key) { + int id = MapBase::getGraph()->id(key); + if (id >= capacity) { + int new_capacity = (capacity == 0 ? 1 : capacity); + while (new_capacity <= id) { + new_capacity <<= 1; + } + Value* new_values = allocator.allocate(new_capacity);; + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { + int jd = MapBase::getGraph()->id(it); + if (id != jd) { + allocator.construct(&(new_values[jd]), values[jd]); + allocator.destroy(&(values[jd])); + } + } + if (capacity != 0) allocator.deallocate(values, capacity); + values = new_values; + capacity = new_capacity; + } + allocator.construct(&(values[id]), Value()); + } + + void erase(const Key& key) { + int id = MapBase::getGraph()->id(key); + allocator.destroy(&(values[id])); + } + + void clear() { + if (capacity != 0) { + MapBase::destroy(); + allocator.deallocate(values, capacity); + capacity = 0; + } + } + + class iterator { + friend class Map; + friend class const_iterator; + private: + + /** Private constructor to initalize the the iterators returned + * by the begin() and end(). + */ + iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {} + + public: + + /** Default constructor. + */ + iterator() {} + + typedef extended_pair Reference; + + /** Dereference operator for map. + */ + Reference operator*() { + return Reference(it, (*map)[it]); + } + + class Pointer { + friend class iterator; + private: + Reference data; + Pointer(const Key& key, Value& val) : data(key, val) {} + public: + Reference* operator->() {return &data;} + }; + + /** Arrow operator for map. + */ + Pointer operator->() { + return Pointer(it, ((*map)[it])); + } + + /** The pre increment operator of the map. + */ + iterator& operator++() { + ++it; + return *this; + } + + /** The post increment operator of the map. + */ + iterator operator++(int) { + iterator tmp(it); + ++it; + return tmp; + } + + /** The equality operator of the map. + */ + bool operator==(const_iterator p_it) { + return p_it.it == it; + } + + /** The not-equality operator of the map. + */ + bool operator!=(const_iterator p_it) { + return !(*this == p_it); + } + + + private: + Map* map; + KeyIt it; + }; + + /** Returns the begin iterator of the map. + */ + iterator begin() { + return iterator(*this, KeyIt(*MapBase::getGraph())); + } + + /** Returns the end iterator of the map. + */ + iterator end() { + return iterator(*this, INVALID); + } + + class const_iterator { + friend class Map; + friend class iterator; + private: + + /** Private constructor to initalize the the iterators returned + * by the begin() and end(). + */ + const_iterator (const Map& pmap, const KeyIt& pit) + : map(&pmap), it(pit) {} + + public: + + /** Default constructor. + */ + const_iterator() {} + + /** Constructor to convert iterator to const_iterator. + */ + const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {} + + typedef extended_pair Reference; + + /** Dereference operator for map. + */ + Reference operator*() { + return Reference(it, (*map)[it]); + } + + + class Pointer { + friend class const_iterator; + private: + Reference data; + Pointer(const Key& key, const Value& val) : data(key, val) {} + public: + Reference* operator->() {return &data;} + }; + + /** Arrow operator for map. + */ + Pointer operator->() { + return Pointer(it, ((*map)[it])); + } + + /** The pre increment operator of the map. + */ + const_iterator& operator++() { + ++it; + return *this; + } + + /** The post increment operator of the map. + */ + const_iterator operator++(int) { + const_iterator tmp(it); + ++it; + return tmp; + } + + /** The equality operator of the map. + */ + bool operator==(const_iterator p_it) { + return p_it.it == it; + } + + /** The not-equality operator of the map. + */ + bool operator!=(const_iterator p_it) { + return !(*this == p_it); + } + + + private: + const Map* map; + KeyIt it; + }; + + /** Returns the begin const_iterator of the map. + */ + const_iterator begin() const { + return const_iterator(*this, KeyIt(*MapBase::getGraph())); + } + + /** Returns the end const_iterator of the map. + */ + const_iterator end() const { + return const_iterator(*this, INVALID); + } + + private: + + void allocate_memory() { + int max_id = -1; + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { + int id = MapBase::getGraph()->id(it); + if (id > max_id) { + max_id = id; + } + } + if (max_id == -1) { + capacity = 0; + values = 0; + return; + } + capacity = 1; + while (capacity <= max_id) { + capacity <<= 1; + } + values = allocator.allocate(capacity); + } + + int capacity; + Value* values; + Allocator allocator; + }; + }; +} + +#endif diff -r d4d182ab75bd -r df2e45e09652 src/hugo/extended_pair.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/hugo/extended_pair.h Thu Sep 02 10:07:30 2004 +0000 @@ -0,0 +1,65 @@ +// -*- c++ -*- +#ifndef EXTENDED_PAIR_H +#define EXTENDED_PAIR_H + +template +struct extended_pair { + typedef T1 first_type; + typedef T2 second_type; + + extended_pair() : first(), second() {} + + extended_pair(A1 f, A2 s) : first(f), second(s) {} + + template + extended_pair(const Pair& pair) : first(pair.first), second(pair.second) {} + + T1 first; + T2 second; +}; + +template +bool operator==(const extended_pair& left, + const extended_pair& right) { + return left.first == right.first && left.second == right.second; +} + +template +bool operator!=(const extended_pair& left, + const extended_pair& right) { + return !(left == right); +} + +template +bool operator<(const extended_pair& left, + const extended_pair& right) { + if (left.first == right.first) return left.second == right.second; + return left.first < right.first; +} + +template +bool operator>(const extended_pair& left, + const extended_pair& right) { + return right < left; +} + +template +bool operator<=(const extended_pair& left, + const extended_pair& right) { + return !(right > left); +} + +template +bool operator>=(const extended_pair& left, + const extended_pair& right) { + return !(right < left); +} + + +#endif diff -r d4d182ab75bd -r df2e45e09652 src/hugo/full_graph.h --- a/src/hugo/full_graph.h Wed Sep 01 15:37:36 2004 +0000 +++ b/src/hugo/full_graph.h Thu Sep 02 10:07:30 2004 +0000 @@ -8,10 +8,13 @@ ///\brief FullGraph and SymFullGraph classes. #include -#include +#include #include +#include +#include + namespace hugo { /// \addtogroup graphs @@ -33,18 +36,19 @@ int NodeNum; int EdgeNum; public: - template class EdgeMap; - template class NodeMap; + + typedef FullGraph Graph; class Node; class Edge; + class NodeIt; class EdgeIt; class OutEdgeIt; class InEdgeIt; - template class NodeMap; - template class EdgeMap; + CREATE_MAP_REGISTRIES; + CREATE_MAPS(ArrayMapFactory); public: @@ -85,7 +89,7 @@ /// \return The found edge or INVALID if there is no such an edge. Edge findEdge(Node u,Node v, Edge prev = INVALID) { - return prev.n==-1?Edge(*this,u.n,v.n):INVALID; + return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID; } @@ -187,110 +191,6 @@ { if(!((++n)%G->NodeNum)) n=-1; return *this; } }; - template class NodeMap - { - std::vector container; - - public: - typedef T ValueType; - typedef Node KeyType; - - NodeMap(const FullGraph &_G) : container(_G.NodeNum) { } - NodeMap(const FullGraph &_G,const T &t) : container(_G.NodeNum,t) { } - NodeMap(const NodeMap &m) : container(m.container) { } - - template friend class NodeMap; - ///\todo It can copy between different types. - template NodeMap(const NodeMap &m) - : container(m.container.size()) - { - typename std::vector::const_iterator i; - for(typename std::vector::const_iterator i=m.container.begin(); - i!=m.container.end(); - i++) - container.push_back(*i); - } - void set(Node n, T a) { container[n.n]=a; } - //'T& operator[](Node n)' would be wrong here - typename std::vector::reference - operator[](Node n) { return container[n.n]; } - //'const T& operator[](Node n)' would be wrong here - typename std::vector::const_reference - operator[](Node n) const { return container[n.n]; } - - ///\warning There is no safety check at all! - ///Using operator = between maps attached to different graph may - ///cause serious problem. - ///\todo Is this really so? - ///\todo It can copy between different types. - const NodeMap& operator=(const NodeMap &m) - { - container = m.container; - return *this; - } - template - const NodeMap& operator=(const NodeMap &m) - { - std::copy(m.container.begin(), m.container.end(), container.begin()); - return *this; - } - - void update() {} //Useless for Dynamic Maps - void update(T a) {} //Useless for Dynamic Maps - }; - - template class EdgeMap - { - std::vector container; - - public: - typedef T ValueType; - typedef Edge KeyType; - - EdgeMap(const FullGraph &_G) : container(_G.EdgeNum) { } - EdgeMap(const FullGraph &_G,const T &t) : container(_G.EdgeNum,t) { } - EdgeMap(const EdgeMap &m) : container(m.container) { } - - template friend class EdgeMap; - ///\todo It can copy between different types. - ///\todo We could use 'copy' - template EdgeMap(const EdgeMap &m) : - container(m.container.size()) - { - typename std::vector::const_iterator i; - for(typename std::vector::const_iterator i=m.container.begin(); - i!=m.container.end(); - i++) - container.push_back(*i); - } - void set(Edge n, T a) { container[n.n]=a; } - //T get(Edge n) const { return container[n.n]; } - typename std::vector::reference - operator[](Edge n) { return container[n.n]; } - typename std::vector::const_reference - operator[](Edge n) const { return container[n.n]; } - - ///\warning There is no safety check at all! - ///Using operator = between maps attached to different graph may - ///cause serious problem. - ///\todo Is this really so? - ///\todo It can copy between different types. - const EdgeMap& operator=(const EdgeMap &m) - { - container = m.container; - return *this; - } - template - const EdgeMap& operator=(const EdgeMap &m) - { - std::copy(m.container.begin(), m.container.end(), container.begin()); - return *this; - } - - void update() {} - void update(T a) {} - }; - }; /// @} diff -r d4d182ab75bd -r df2e45e09652 src/hugo/list_graph.h --- a/src/hugo/list_graph.h Wed Sep 01 15:37:36 2004 +0000 +++ b/src/hugo/list_graph.h Thu Sep 02 10:07:30 2004 +0000 @@ -8,16 +8,24 @@ ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes. #include -#include +#include #include +#include +#include + +#include + +#include + + namespace hugo { /// \addtogroup graphs /// @{ - class SymListGraph; +// class SymListGraph; ///A list graph class. @@ -56,36 +64,13 @@ //The first free edge int first_free_edge; - protected: + public: - template class DynMapBase - { - protected: - const ListGraph* G; - public: - virtual void add(const Key k) = 0; - virtual void erase(const Key k) = 0; - DynMapBase(const ListGraph &_G) : G(&_G) {} - virtual ~DynMapBase() {} - friend class ListGraph; - }; - - public: - template class EdgeMap; - template class NodeMap; + typedef ListGraph Graph; class Node; class Edge; - // protected: - // HELPME: - protected: - ///\bug It must be public because of SymEdgeMap. - /// - mutable std::vector * > dyn_node_maps; - ///\bug It must be public because of SymEdgeMap. - /// - mutable std::vector * > dyn_edge_maps; public: @@ -93,24 +78,21 @@ class EdgeIt; class OutEdgeIt; class InEdgeIt; - + + CREATE_MAP_REGISTRIES; + CREATE_MAPS(ArrayMapFactory); + public: - ListGraph() : nodes(), first_node(-1), - first_free_node(-1), edges(), first_free_edge(-1) {} - ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node), - first_free_node(_g.first_free_node), - edges(_g.edges), - first_free_edge(_g.first_free_edge) {} + ListGraph() + : nodes(), first_node(-1), + first_free_node(-1), edges(), first_free_edge(-1) {} + + ListGraph(const ListGraph &_g) + : nodes(_g.nodes), first_node(_g.first_node), + first_free_node(_g.first_free_node), edges(_g.edges), + first_free_edge(_g.first_free_edge) {} - ~ListGraph() - { - for(std::vector * >::iterator i=dyn_node_maps.begin(); - i!=dyn_node_maps.end(); ++i) (**i).G=NULL; - for(std::vector * >::iterator i=dyn_edge_maps.begin(); - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; - } - int nodeNum() const { return nodes.size(); } //FIXME: What is this? int edgeNum() const { return edges.size(); } //FIXME: What is this? @@ -170,8 +152,7 @@ Node nn; nn.n=n; //Update dynamic maps - for(std::vector * >::iterator i=dyn_node_maps.begin(); - i!=dyn_node_maps.end(); ++i) (**i).add(nn); + node_maps.add(nn); return nn; } @@ -202,8 +183,7 @@ Edge e; e.n=n; //Update dynamic maps - for(std::vector * >::iterator i=dyn_edge_maps.begin(); - i!=dyn_edge_maps.end(); ++i) (**i).add(e); + edge_maps.add(e); return e; } @@ -244,8 +224,8 @@ //Update dynamic maps Edge e; e.n=n; - for(std::vector * >::iterator i=dyn_edge_maps.begin(); - i!=dyn_edge_maps.end(); ++i) (**i).erase(e); + edge_maps.erase(e); + } public: @@ -265,16 +245,17 @@ first_free_node = n; //Update dynamic maps - for(std::vector * >::iterator i=dyn_node_maps.begin(); - i!=dyn_node_maps.end(); ++i) (**i).erase(nn); + node_maps.erase(nn); + } void erase(Edge e) { eraseEdge(e.n); } - ///\bug Dynamic maps must be updated! - /// void clear() { - nodes.clear();edges.clear(); + edge_maps.clear(); + edges.clear(); + node_maps.clear(); + nodes.clear(); first_node=first_free_node=first_free_edge=-1; } @@ -410,188 +391,6 @@ // ///Validity check // operator bool() { return Edge::operator bool(); } }; - - template class NodeMap : public DynMapBase - { - std::vector container; - - public: - typedef T ValueType; - typedef Node KeyType; - - NodeMap(const ListGraph &_G) : - DynMapBase(_G), container(_G.maxNodeId()) - { - G->dyn_node_maps.push_back(this); - } - NodeMap(const ListGraph &_G,const T &t) : - DynMapBase(_G), container(_G.maxNodeId(),t) - { - G->dyn_node_maps.push_back(this); - } - - NodeMap(const NodeMap &m) : - DynMapBase(*m.G), container(m.container) - { - G->dyn_node_maps.push_back(this); - } - - template friend class NodeMap; - - ///\todo It can copy between different types. - /// - template NodeMap(const NodeMap &m) : - DynMapBase(*m.G), container(m.container.size()) - - { - G->dyn_node_maps.push_back(this); - typename std::vector::const_iterator i; - for(typename std::vector::const_iterator i=m.container.begin(); - i!=m.container.end(); - i++) - container.push_back(*i); - } - ~NodeMap() - { - if(G) { - std::vector* >::iterator i; - for(i=G->dyn_node_maps.begin(); - i!=G->dyn_node_maps.end() && *i!=this; ++i) ; - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow... - //A better way to do that: (Is this really important?) - if(*i==this) { - *i=G->dyn_node_maps.back(); - G->dyn_node_maps.pop_back(); - } - } - } - - void add(const Node k) - { - if(k.n>=int(container.size())) container.resize(k.n+1); - } - - void erase(const Node) { } - - void set(Node n, T a) { container[n.n]=a; } - //'T& operator[](Node n)' would be wrong here - typename std::vector::reference - operator[](Node n) { return container[n.n]; } - //'const T& operator[](Node n)' would be wrong here - typename std::vector::const_reference - operator[](Node n) const { return container[n.n]; } - - ///\warning There is no safety check at all! - ///Using operator = between maps attached to different graph may - ///cause serious problem. - ///\todo Is this really so? - ///\todo It can copy between different types. - const NodeMap& operator=(const NodeMap &m) - { - container = m.container; - return *this; - } - template - const NodeMap& operator=(const NodeMap &m) - { - std::copy(m.container.begin(), m.container.end(), container.begin()); - return *this; - } - - void update() {} //Useless for Dynamic Maps - void update(T a) {} //Useless for Dynamic Maps - }; - - template class EdgeMap : public DynMapBase - { - protected: - std::vector container; - - public: - typedef T ValueType; - typedef Edge KeyType; - - EdgeMap(const ListGraph &_G) : - DynMapBase(_G), container(_G.maxEdgeId()) - { - //FIXME: What if there are empty Id's? - //FIXME: Can I use 'this' in a constructor? - G->dyn_edge_maps.push_back(this); - } - EdgeMap(const ListGraph &_G,const T &t) : - DynMapBase(_G), container(_G.maxEdgeId(),t) - { - G->dyn_edge_maps.push_back(this); - } - EdgeMap(const EdgeMap &m) : - DynMapBase(*m.G), container(m.container) - { - G->dyn_edge_maps.push_back(this); - } - - template friend class EdgeMap; - - ///\todo It can copy between different types. - /// - template EdgeMap(const EdgeMap &m) : - DynMapBase(*m.G), container(m.container.size()) - { - G->dyn_edge_maps.push_back(this); - typename std::vector::const_iterator i; - for(typename std::vector::const_iterator i=m.container.begin(); - i!=m.container.end(); - i++) - container.push_back(*i); - } - ~EdgeMap() - { - if(G) { - std::vector* >::iterator i; - for(i=G->dyn_edge_maps.begin(); - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ; - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... - //A better way to do that: (Is this really important?) - if(*i==this) { - *i=G->dyn_edge_maps.back(); - G->dyn_edge_maps.pop_back(); - } - } - } - - void add(const Edge k) - { - if(k.n>=int(container.size())) container.resize(k.n+1); - } - void erase(const Edge) { } - - void set(Edge n, T a) { container[n.n]=a; } - //T get(Edge n) const { return container[n.n]; } - typename std::vector::reference - operator[](Edge n) { return container[n.n]; } - typename std::vector::const_reference - operator[](Edge n) const { return container[n.n]; } - - ///\warning There is no safety check at all! - ///Using operator = between maps attached to different graph may - ///cause serious problem. - ///\todo Is this really so? - ///\todo It can copy between different types. - const EdgeMap& operator=(const EdgeMap &m) - { - container = m.container; - return *this; - } - template - const EdgeMap& operator=(const EdgeMap &m) - { - std::copy(m.container.begin(), m.container.end(), container.begin()); - return *this; - } - - void update() {} //Useless for DynMaps - void update(T a) {} //Useless for DynMaps - }; - }; ///Graph for bidirectional edges. @@ -615,12 +414,19 @@ /// ///\todo this date structure need some reconsiderations. Maybe it ///should be implemented independently from ListGraph. - + class SymListGraph : public ListGraph { public: - template class SymEdgeMap; - template friend class SymEdgeMap; + + typedef SymListGraph Graph; + + KEEP_NODE_MAP(ListGraph); + KEEP_EDGE_MAP(ListGraph); + + CREATE_SYM_EDGE_MAP_REGISTRY; + CREATE_SYM_EDGE_MAP_FACTORY(ArrayMapFactory); + IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory); SymListGraph() : ListGraph() { } SymListGraph(const ListGraph &_g) : ListGraph(_g) { } @@ -628,11 +434,14 @@ Edge addEdge(Node u, Node v) { Edge e = ListGraph::addEdge(u,v); - ListGraph::addEdge(v,u); + Edge f = ListGraph::addEdge(v,u); + sym_edge_maps.add(e); + sym_edge_maps.add(f); + return e; } - void erase(Node n) { ListGraph::erase(n); } + void erase(Node n) { ListGraph::erase(n);} ///The oppositely directed edge. ///Returns the oppositely directed @@ -646,109 +455,14 @@ ///Removes a pair of oppositely directed edges to the graph. void erase(Edge e) { - ListGraph::erase(opposite(e)); + Edge f = opposite(e); + sym_edge_maps.erase(e); + sym_edge_maps.erase(f); + ListGraph::erase(f); ListGraph::erase(e); - } - - ///Common data storage for the edge pairs. + } + }; - ///This map makes it possible to store data shared by the oppositely - ///directed pairs of edges. - template class SymEdgeMap : public DynMapBase - { - std::vector container; - - public: - typedef T ValueType; - typedef Edge KeyType; - - SymEdgeMap(const SymListGraph &_G) : - DynMapBase(_G), container(_G.maxEdgeId()/2) - { - static_cast(G)->dyn_edge_maps.push_back(this); - } - SymEdgeMap(const SymListGraph &_G,const T &t) : - DynMapBase(_G), container(_G.maxEdgeId()/2,t) - { - G->dyn_edge_maps.push_back(this); - } - - SymEdgeMap(const SymEdgeMap &m) : - DynMapBase(*m.G), container(m.container) - { - G->dyn_node_maps.push_back(this); - } - - // template friend class SymEdgeMap; - - ///\todo It can copy between different types. - /// - - template SymEdgeMap(const SymEdgeMap &m) : - DynMapBase(*m.G), container(m.container.size()) - { - G->dyn_node_maps.push_back(this); - typename std::vector::const_iterator i; - for(typename std::vector::const_iterator i=m.container.begin(); - i!=m.container.end(); - i++) - container.push_back(*i); - } - - ~SymEdgeMap() - { - if(G) { - std::vector* >::iterator i; - for(i=static_cast(G)->dyn_edge_maps.begin(); - i!=static_cast(G)->dyn_edge_maps.end() - && *i!=this; ++i) ; - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... - //A better way to do that: (Is this really important?) - if(*i==this) { - *i=static_cast(G)->dyn_edge_maps.back(); - static_cast(G)->dyn_edge_maps.pop_back(); - } - } - } - - void add(const Edge k) - { - if(!k.idref()%2&&k.idref()/2>=int(container.size())) - container.resize(k.idref()/2+1); - } - void erase(const Edge k) { } - - void set(Edge n, T a) { container[n.idref()/2]=a; } - //T get(Edge n) const { return container[n.idref()/2]; } - typename std::vector::reference - operator[](Edge n) { return container[n.idref()/2]; } - typename std::vector::const_reference - operator[](Edge n) const { return container[n.idref()/2]; } - - ///\warning There is no safety check at all! - ///Using operator = between maps attached to different graph may - ///cause serious problem. - ///\todo Is this really so? - ///\todo It can copy between different types. - const SymEdgeMap& operator=(const SymEdgeMap &m) - { - container = m.container; - return *this; - } - template - const SymEdgeMap& operator=(const SymEdgeMap &m) - { - std::copy(m.container.begin(), m.container.end(), container.begin()); - return *this; - } - - void update() {} //Useless for DynMaps - void update(T a) {} //Useless for DynMaps - - }; - - }; - ///A graph class containing only nodes. @@ -779,35 +493,13 @@ //The first free node int first_free_node; - protected: - - template class DynMapBase - { - protected: - const NodeSet* G; - public: - virtual void add(const Key k) = 0; - virtual void erase(const Key k) = 0; - DynMapBase(const NodeSet &_G) : G(&_G) {} - virtual ~DynMapBase() {} - friend class NodeSet; - }; - public: - template class EdgeMap; - template class NodeMap; + + typedef NodeSet Graph; class Node; class Edge; - // protected: - // HELPME: - protected: - ///\bug It must be public because of SymEdgeMap. - /// - mutable std::vector * > dyn_node_maps; - //mutable std::vector * > dyn_edge_maps; - public: class NodeIt; @@ -815,26 +507,19 @@ class OutEdgeIt; class InEdgeIt; - template class NodeMap; - template class EdgeMap; + CREATE_MAP_REGISTRIES; + CREATE_MAPS(ArrayMapFactory); public: ///Default constructor - NodeSet() : nodes(), first_node(-1), - first_free_node(-1) {} + NodeSet() + : nodes(), first_node(-1), first_free_node(-1) {} ///Copy constructor - NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node), - first_free_node(_g.first_free_node) {} + NodeSet(const NodeSet &_g) + : nodes(_g.nodes), first_node(_g.first_node), + first_free_node(_g.first_free_node) {} - ~NodeSet() - { - for(std::vector * >::iterator i=dyn_node_maps.begin(); - i!=dyn_node_maps.end(); ++i) (**i).G=NULL; - //for(std::vector * >::iterator i=dyn_edge_maps.begin(); - // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; - } - int nodeNum() const { return nodes.size(); } //FIXME: What is this? int edgeNum() const { return 0; } //FIXME: What is this? @@ -887,8 +572,7 @@ Node nn; nn.n=n; //Update dynamic maps - for(std::vector * >::iterator i=dyn_node_maps.begin(); - i!=dyn_node_maps.end(); ++i) (**i).add(nn); + node_maps.add(nn); return nn; } @@ -904,8 +588,7 @@ first_free_node = n; //Update dynamic maps - for(std::vector * >::iterator i=dyn_node_maps.begin(); - i!=dyn_node_maps.end(); ++i) (**i).erase(nn); + node_maps.erase(nn); } @@ -914,9 +597,8 @@ return INVALID; } - ///\bug Dynamic maps must be updated! - /// void clear() { + node_maps.clear(); nodes.clear(); first_node = first_free_node = -1; } @@ -1012,128 +694,6 @@ InEdgeIt operator++() { return INVALID; } }; - template class NodeMap : public DynMapBase - { - std::vector container; - - public: - typedef T ValueType; - typedef Node KeyType; - - NodeMap(const NodeSet &_G) : - DynMapBase(_G), container(_G.maxNodeId()) - { - G->dyn_node_maps.push_back(this); - } - NodeMap(const NodeSet &_G,const T &t) : - DynMapBase(_G), container(_G.maxNodeId(),t) - { - G->dyn_node_maps.push_back(this); - } - - NodeMap(const NodeMap &m) : - DynMapBase(*m.G), container(m.container) - { - G->dyn_node_maps.push_back(this); - } - - template friend class NodeMap; - - ///\todo It can copy between different types. - /// - template NodeMap(const NodeMap &m) : - DynMapBase(*m.G), container(m.container.size()) - { - G->dyn_node_maps.push_back(this); - typename std::vector::const_iterator i; - for(typename std::vector::const_iterator i=m.container.begin(); - i!=m.container.end(); - i++) - container.push_back(*i); - } - ~NodeMap() - { - if(G) { - std::vector* >::iterator i; - for(i=G->dyn_node_maps.begin(); - i!=G->dyn_node_maps.end() && *i!=this; ++i) ; - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow... - //A better way to do that: (Is this really important?) - if(*i==this) { - *i=G->dyn_node_maps.back(); - G->dyn_node_maps.pop_back(); - } - } - } - - void add(const Node k) - { - if(k.n>=int(container.size())) container.resize(k.n+1); - } - - void erase(const Node) { } - - void set(Node n, T a) { container[n.n]=a; } - //'T& operator[](Node n)' would be wrong here - typename std::vector::reference - operator[](Node n) { return container[n.n]; } - //'const T& operator[](Node n)' would be wrong here - typename std::vector::const_reference - operator[](Node n) const { return container[n.n]; } - - ///\warning There is no safety check at all! - ///Using operator = between maps attached to different graph may - ///cause serious problem. - ///\todo Is this really so? - ///\todo It can copy between different types. - const NodeMap& operator=(const NodeMap &m) - { - container = m.container; - return *this; - } - template - const NodeMap& operator=(const NodeMap &m) - { - std::copy(m.container.begin(), m.container.end(), container.begin()); - return *this; - } - - void update() {} //Useless for Dynamic Maps - void update(T a) {} //Useless for Dynamic Maps - }; - - template class EdgeMap - { - public: - typedef T ValueType; - typedef Edge KeyType; - - EdgeMap(const NodeSet &) { } - EdgeMap(const NodeSet &,const T &) { } - EdgeMap(const EdgeMap &) { } - // template friend class EdgeMap; - - ///\todo It can copy between different types. - /// - template EdgeMap(const EdgeMap &) { } - ~EdgeMap() { } - - void add(const Edge ) { } - void erase(const Edge) { } - - void set(Edge, T) { } - //T get(Edge n) const { return container[n.n]; } - ValueType &operator[](Edge) { return *((T*)(NULL)); } - const ValueType &operator[](Edge) const { return *((T*)(NULL)); } - - const EdgeMap& operator=(const EdgeMap &) { return *this; } - - template - const EdgeMap& operator=(const EdgeMap &m) { return *this; } - - void update() {} - void update(T a) {} - }; }; @@ -1166,11 +726,15 @@ NodeGraphType &G; public: + class Node; class Edge; class OutEdgeIt; class InEdgeIt; class SymEdge; + + typedef EdgeSet Graph; + int id(Node v) const; class Node : public NodeGraphType::Node { @@ -1229,44 +793,21 @@ //The first free edge int first_free_edge; - protected: - - template class DynMapBase - { - protected: - const EdgeSet* G; - public: - virtual void add(const Key k) = 0; - virtual void erase(const Key k) = 0; - DynMapBase(const EdgeSet &_G) : G(&_G) {} - virtual ~DynMapBase() {} - friend class EdgeSet; - }; - public: - //template class NodeMap; - template class EdgeMap; class Node; class Edge; - // protected: - // HELPME: - protected: - // mutable std::vector * > dyn_node_maps; - ///\bug It must be public because of SymEdgeMap. - /// - mutable std::vector * > dyn_edge_maps; - - public: - class NodeIt; class EdgeIt; class OutEdgeIt; class InEdgeIt; + + + CREATE_EDGE_MAP_REGISTRY; + CREATE_EDGE_MAP_FACTORY(ArrayMapFactory); + IMPORT_EDGE_MAP(EdgeMapFactory); - template class NodeMap; - template class EdgeMap; public: @@ -1275,25 +816,17 @@ ///Construates a new graph based on the nodeset of an existing one. ///\param _G the base graph. ///\todo It looks like a copy constructor, but it isn't. - EdgeSet(NodeGraphType &_G) : G(_G), - nodes(_G), edges(), - first_free_edge(-1) { } + EdgeSet(NodeGraphType &_G) + : G(_G), nodes(_G), edges(), + first_free_edge(-1) {} ///Copy constructor ///Makes a copy of an EdgeSet. ///It will be based on the same graph. - EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges), - first_free_edge(_g.first_free_edge) { } + EdgeSet(const EdgeSet &_g) + : G(_g.G), nodes(_g.G), edges(_g.edges), + first_free_edge(_g.first_free_edge) {} - ~EdgeSet() - { - // for(std::vector * >::iterator i=dyn_node_maps.begin(); - // i!=dyn_node_maps.end(); ++i) (**i).G=NULL; - for(typename std::vector * >::iterator - i=dyn_edge_maps.begin(); - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; - } - int nodeNum() const { return G.nodeNum(); } //FIXME: What is this? int edgeNum() const { return edges.size(); } //FIXME: What is this? @@ -1347,9 +880,7 @@ Edge e; e.n=n; //Update dynamic maps - for(typename std::vector * >::iterator - i=dyn_edge_maps.begin(); - i!=dyn_edge_maps.end(); ++i) (**i).add(e); + edge_maps.add(e); return e; } @@ -1389,10 +920,8 @@ first_free_edge = -1; //Update dynamic maps - Edge e; e.n=n; - for(typename std::vector * >::iterator - i=dyn_edge_maps.begin(); - i!=dyn_edge_maps.end(); ++i) (**i).erase(e); + Edge e; e.n = n; + edge_maps.erase(e); } public: @@ -1408,22 +937,12 @@ ///Clear all edges. (Doesn't clear the nodes!) void clear() { + edge_maps.clear(); edges.clear(); first_free_edge=-1; } -// //\bug Dynamic maps must be updated! -// // -// void clear() { -// nodes.clear();edges.clear(); -// first_node=first_free_node=first_free_edge=-1; -// } - - public: - template class EdgeMap; - - /// class Edge { public: friend class EdgeSet; @@ -1490,7 +1009,7 @@ OutEdgeIt(const EdgeSet& _G,const Node v) : Edge(_G.nodes[v].first_out), G(&_G) { } - OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; } + OutEdgeIt &operator++() { n = G->edges[n].next_out; return *this; } }; class InEdgeIt : public Edge { @@ -1505,126 +1024,41 @@ InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } }; - template class NodeMap : - public NodeGraphType::template NodeMap + + template class NodeMap + : public NodeGraphType::template NodeMap { //This is a must, the constructors need it. - typedef typename NodeGraphType::template NodeMap ParentNodeMap; + typedef typename NodeGraphType::template NodeMap MapImpl; + typedef V Value; public: - NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { } - NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { } - //It is unnecessary - NodeMap(const typename NodeGraphType::template NodeMap &m) : - ParentNodeMap(m) { } + NodeMap() : MapImpl() {} + + NodeMap(const EdgeSet& graph) + : MapImpl(graph.G) { } - ///\todo It can copy between different types. - /// - template - NodeMap(const typename NodeGraphType::template NodeMap &m) - : ParentNodeMap(m) { } - }; - - /// - template class EdgeMap : public DynMapBase - { - protected: - public: - ///\bug It should be at least protected - /// - std::vector container; + NodeMap(const EdgeSet& graph, const Value& value) + : MapImpl(graph.G, value) { } - public: - typedef T ValueType; - typedef Edge KeyType; + NodeMap(const NodeMap& copy) + : MapImpl(static_cast(copy)) {} - EdgeMap(const EdgeSet &_G) : - DynMapBase(_G), container(_G.maxEdgeId()) - { - //FIXME: What if there are empty Id's? - //FIXME: Can I use 'this' in a constructor? - this->G->dyn_edge_maps.push_back(this); - } - EdgeMap(const EdgeSet &_G,const T &t) : - DynMapBase(_G), container(_G.maxEdgeId(),t) - { - this->G->dyn_edge_maps.push_back(this); - } - EdgeMap(const EdgeMap &m) : - DynMapBase(*m.G), container(m.container) - { - this->G->dyn_edge_maps.push_back(this); + template + NodeMap(const CMap& copy) + : MapImpl(copy) { } + + NodeMap& operator=(const NodeMap& copy) { + MapImpl::operator=(static_cast(copy)); + return *this; } - ///\todo It can copy between different types. - /// - template EdgeMap(const EdgeMap &m) : - DynMapBase(*m.G), container(m.container.size()) - { - this->G->dyn_edge_maps.push_back(this); - typename std::vector::const_iterator i; - for(typename std::vector::const_iterator i=m.container.begin(); - i!=m.container.end(); - i++) - container.push_back(*i); - } - ~EdgeMap() - { - if(this->G) { - typename std::vector* >::iterator i; - for(i=this->G->dyn_edge_maps.begin(); - i!=this->G->dyn_edge_maps.end() && *i!=this; ++i) ; - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... - //A better way to do that: (Is this really important?) - if(*i==this) { - *i=this->G->dyn_edge_maps.back(); - this->G->dyn_edge_maps.pop_back(); - } - } - } - - void add(const Edge k) - { - if(k.n>=int(container.size())) container.resize(k.n+1); - } - void erase(const Edge) { } - - ///\bug This doesn't work. Why? - /// void set(Edge n, T a) { container[n.n]=a; } - void set(Edge n, T a) { container[this->G->id(n)]=a; } - //T get(Edge n) const { return container[n.n]; } - typename std::vector::reference - ///\bug This doesn't work. Why? - /// operator[](Edge n) { return container[n.n]; } - operator[](Edge n) { return container[this->G->id(n)]; } - typename std::vector::const_reference - ///\bug This doesn't work. Why? - /// operator[](Edge n) const { return container[n.n]; } - operator[](Edge n) const { return container[this->G->id(n)]; } - - ///\warning There is no safety check at all! - ///Using operator = between maps attached to different graph may - ///cause serious problem. - ///\todo Is this really so? - ///\todo It can copy between different types. - const EdgeMap& operator=(const EdgeMap &m) - { - container = m.container; + template + NodeMap& operator=(const CMap& copy) { + MapImpl::operator=(copy); return *this; } - - template friend class EdgeMap; - template - const EdgeMap& operator=(const EdgeMap &m) - { - std::copy(m.container.begin(), m.container.end(), container.begin()); - return *this; - } - - void update() {} //Useless for DynMaps - void update(T a) {} //Useless for DynMaps }; - }; template diff -r d4d182ab75bd -r df2e45e09652 src/hugo/map_defines.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/hugo/map_defines.h Thu Sep 02 10:07:30 2004 +0000 @@ -0,0 +1,212 @@ +// -*- c++ -*- +#ifndef MAP_DEFINES_H +#define MAP_DEFINES_H + +/** Creates the EdgeMapRegistry type an declare a mutable instance + * named edge_maps. + */ +#define CREATE_EDGE_MAP_REGISTRY \ +typedef MapRegistry EdgeMapRegistry; \ +mutable EdgeMapRegistry edge_maps; + +/** Creates the NodeMapRegistry type an declare a mutable instance + * named node_maps. + */ +#define CREATE_NODE_MAP_REGISTRY \ +typedef MapRegistry NodeMapRegistry; \ +mutable NodeMapRegistry node_maps; + +/** Creates both map registries. + */ +#define CREATE_MAP_REGISTRIES \ +CREATE_NODE_MAP_REGISTRY \ +CREATE_EDGE_MAP_REGISTRY + +/** Creates a concrete factory type from a template map + * factory to use as node map factory. + */ +#define CREATE_NODE_MAP_FACTORY(TemplateFactory) \ +typedef TemplateFactory NodeMapFactory; + +/** Creates a concrete factory type from a template map + * factory to use as edge map factory. + */ +#define CREATE_EDGE_MAP_FACTORY(TemplateFactory) \ +typedef TemplateFactory EdgeMapFactory; + +/** Creates both map factories. + */ +#define CREATE_MAP_FACTORIES(TemplateFactory) \ +CREATE_NODE_MAP_FACTORY(TemplateFactory) \ +CREATE_EDGE_MAP_FACTORY(TemplateFactory) + +/** Import a map from a concrete map factory. The import method is + * an overloading of the map type. + * The reason to use these macro is that the c++ does not support + * the template typedefs. If a future release of the c++ + * supports this feature it should be fixed. + */ +#define IMPORT_NODE_MAP(Factory) \ +template \ +class NodeMap : public Factory::template Map { \ +typedef typename Factory::template Map MapImpl; \ +public: \ +NodeMap() {} \ +NodeMap(const Graph& g) : MapImpl(g, g.node_maps) {} \ +NodeMap(const Graph& g, const V& v) : MapImpl(g, g.node_maps, v) {} \ +NodeMap(const NodeMap& copy) : MapImpl(static_cast(copy)) {} \ +template NodeMap(const CMap& copy) : MapImpl(copy) {} \ +NodeMap& operator=(const NodeMap& copy) { \ + MapImpl::operator=(static_cast(copy));\ + return *this; \ +} \ +template NodeMap& operator=(const CMap& copy) { \ + MapImpl::operator=(copy);\ + return *this; \ +} \ +}; + +/** Import a map from a concrete map factory. The import method is + * an overloading of the map type. + * The reason to use these macro is that the c++ does not support + * the template typedefs. If a future release of the c++ + * supports this feature it should be fixed. + */ +#define IMPORT_EDGE_MAP(Factory) \ +template \ +class EdgeMap : public Factory::template Map { \ +typedef typename Factory::template Map MapImpl; \ +public: \ +EdgeMap() {} \ +EdgeMap(const Graph& g) : MapImpl(g, g.edge_maps) {} \ +EdgeMap(const Graph& g, const V& v) : MapImpl(g, g.edge_maps, v) {} \ +EdgeMap(const EdgeMap& copy) : MapImpl(static_cast(copy)) {} \ +template EdgeMap(const CMap& copy) : MapImpl(copy) {} \ +EdgeMap& operator=(const EdgeMap& copy) { \ + MapImpl::operator=(static_cast(copy));\ + return *this; \ +} \ +template EdgeMap& operator=(const CMap& copy) { \ + MapImpl::operator=(copy);\ + return *this; \ +} \ +}; + +/** This macro creates both map factories and imports both maps. + */ +#define CREATE_MAPS(TemplateFactory) \ +CREATE_MAP_FACTORIES(TemplateFactory) \ +IMPORT_NODE_MAP(NodeMapFactory) \ +IMPORT_EDGE_MAP(EdgeMapFactory) + +/** This macro creates MapRegistry for Symmetric Edge Maps. + */ +#define CREATE_SYM_EDGE_MAP_REGISTRY \ +typedef SymEdgeIt SymEdgeIt; \ +typedef MapRegistry SymEdgeMapRegistry; \ +mutable EdgeMapRegistry sym_edge_maps; + +/** Creates a concrete factory type from a template map + * factory to use as edge map factory. + */ +#define CREATE_SYM_EDGE_MAP_FACTORY(TemplateFactory) \ +typedef SymMapFactory \ +SymEdgeMapFactory; + +/** Import a map from a concrete map factory. The import method is + * an overloading of the map type. + * The reason to use these macro is that the c++ does not support + * the template typedefs. If a future release of the c++ + * supports this feature it should be fixed. + */ +#define IMPORT_SYM_EDGE_MAP(Factory) \ +template \ +class SymEdgeMap : public Factory::template Map { \ +typedef typename Factory::template Map MapImpl; \ +public: \ +SymEdgeMap() {} \ +SymEdgeMap(const Graph& g) : MapImpl(g, g.sym_edge_maps) {} \ +SymEdgeMap(const Graph& g, const V& v) : MapImpl(g, g.sym_edge_maps, v) {} \ +SymEdgeMap(const SymEdgeMap& copy) \ + : MapImpl(static_cast(copy)) {} \ +template SymEdgeMap(const CMap& copy) : MapImpl(copy) {} \ +SymEdgeMap& operator=(const SymEdgeMap& copy) { \ + MapImpl::operator=(static_cast(copy));\ + return *this; \ +} \ +template SymEdgeMap& operator=(const CMap& copy) { \ + MapImpl::operator=(copy);\ + return *this; \ +} \ +}; + + +#define KEEP_NODE_MAP(GraphBase) \ + template class NodeMap \ + : public GraphBase::template NodeMap \ + { \ + typedef typename GraphBase::template NodeMap MapImpl; \ + typedef V Value; \ + public: \ + NodeMap() : MapImpl() {} \ +\ + NodeMap(const Graph& graph) \ + : MapImpl(static_cast(graph)) { } \ +\ + NodeMap(const Graph& graph, const Value& value) \ + : MapImpl(static_cast(graph), value) { } \ +\ + NodeMap(const NodeMap& copy) \ + : MapImpl(static_cast(copy)) {} \ +\ + template \ + NodeMap(const CMap& copy) \ + : MapImpl(copy) {} \ +\ + NodeMap& operator=(const NodeMap& copy) { \ + MapImpl::operator=(static_cast(copy)); \ + return *this; \ + } \ +\ + template \ + NodeMap& operator=(const CMap& copy) { \ + MapImpl::operator=(copy); \ + return *this; \ + } \ + }; + +#define KEEP_EDGE_MAP(GraphBase) \ + template class EdgeMap \ + : public GraphBase::template EdgeMap \ + { \ + typedef typename GraphBase::template EdgeMap MapImpl; \ + typedef V Value; \ + public: \ + EdgeMap() : MapImpl() {} \ +\ + EdgeMap(const Graph& graph) \ + : MapImpl(static_cast(graph)) { } \ +\ + EdgeMap(const Graph& graph, const Value& value) \ + : MapImpl(static_cast(graph), value) { } \ +\ + EdgeMap(const EdgeMap& copy) \ + : MapImpl(static_cast(copy)) {} \ +\ + template \ + EdgeMap(const CMap& copy) \ + : MapImpl(copy) {} \ +\ + EdgeMap& operator=(const EdgeMap& copy) { \ + MapImpl::operator=(static_cast(copy)); \ + return *this; \ + } \ +\ + template \ + EdgeMap& operator=(const CMap& copy) { \ + MapImpl::operator=(copy); \ + return *this; \ + } \ + }; + +#endif diff -r d4d182ab75bd -r df2e45e09652 src/hugo/map_registry.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/hugo/map_registry.h Thu Sep 02 10:07:30 2004 +0000 @@ -0,0 +1,265 @@ +// -*- c++ -*- +#ifndef MAP_REGISTRY_H +#define MAP_REGISTRY_H + +#include + +using namespace std; + +namespace hugo { + +/** + * Registry class to register edge or node maps into the graph. The + * registry helps you to implement an observer pattern. If you add + * or erase an edge or node you must notify all the maps about the + * event. +*/ + template + class MapRegistry { + public: + typedef G Graph; + typedef K Key; + typedef KIt KeyIt; + + + + /** + * MapBase is the base class of the registered maps. + * It defines the core modification operations on the maps and + * implements some helper functions. + */ + class MapBase { + public: + typedef G Graph; + typedef K Key; + typedef KIt KeyIt; + + typedef MapRegistry Registry; + + friend class MapRegistry; + + /** + * Default constructor for MapBase. + */ + + MapBase() : graph(0), registry(0) {} + + /** + * Simple constructor to register into a graph registry. + */ + + MapBase(const Graph& g, Registry& r) : graph(&g), registry(0) { + r.attach(*this); + } + + /** + * Copy constructor to register into the registry. + */ + + MapBase(const MapBase& copy) : registry(0), graph(copy.graph) { + if (copy.registry) { + copy.registry->attach(*this); + } + } + + /** + * Assign operator. + */ + + const MapBase& operator=(const MapBase& copy) { + if (registry) { + registry->detach(*this); + } + graph = copy.graph; + if (copy.registry) { + copy.registry->attach(*this); + } + } + + + /** + * Destructor. + */ + + virtual ~MapBase() { + if (registry) { + registry->detach(*this); + } + } + + /* + * Returns the graph that the map belongs to. + */ + + const Graph* getGraph() const { return graph; } + + protected: + + const Graph* graph; + Registry* registry; + + int registry_index; + + protected: + + /** + Helper function to implement constructors in the subclasses. + */ + + virtual void init() { + for (KeyIt it(*graph); it != INVALID; ++it) { + add(it); + } + } + + /** + Helper function to implement the destructor in the subclasses. + */ + + virtual void destroy() { + for (KeyIt it(*getGraph()); it != INVALID; ++it) { + erase(it); + } + } + + /** + The add member function should be overloaded in the subclasses. + \e Add extends the map with the new node. + */ + + virtual void add(const Key&) = 0; + /** + The erase member function should be overloaded in the subclasses. + \e Erase removes the node from the map. + */ + + virtual void erase(const Key&) = 0; + + /** + * The clear member function should be overloaded in the subclasses. + * \e Clear makes empty the data structure. + */ + + virtual void clear() = 0; + + /** + Exception class to throw at unsupported operation. + */ + + class NotSupportedOperationException {}; + + }; + + protected: + + /** + * The container type of the maps. + */ + typedef std::vector Container; + + /** + * The container of the registered maps. + */ + Container container; + + + public: + + /** + * Default Constructor of the MapRegistry. It creates an empty registry. + */ + MapRegistry() {} + + /** + * Copy Constructor of the MapRegistry. The new registry does not steal + * the maps from the right value. The new registry will be an empty. + */ + MapRegistry(const MapRegistry&) {} + + /** + * Assign operator. The left value does not steal the maps + * from the right value. The left value will be an empty registry. + */ + MapRegistry& operator=(const MapRegistry&) { + typename Container::iterator it; + for (it = container.begin(); it != container.end(); ++it) { + (*it)->destroy(); + (*it)->graph = 0; + (*it)->registry = 0; + } + } + + /** + * Destructor of the MapRegistry. + */ + ~MapRegistry() { + typename Container::iterator it; + for (it = container.begin(); it != container.end(); ++it) { + (*it)->destroy(); + (*it)->registry = 0; + (*it)->graph = 0; + } + } + + + public: + + /** + * Attach a map into thr registry. If the map has been attached + * into an other registry it is detached from that automaticly. + */ + void attach(MapBase& map) { + if (map.registry) { + map.registry->detach(map); + } + container.push_back(&map); + map.registry = this; + map.registry_index = container.size()-1; + } + + /** + * Detach the map from the registry. + */ + void detach(MapBase& map) { + container.back()->registry_index = map.registry_index; + container[map.registry_index] = container.back(); + container.pop_back(); + map.registry = 0; + map.graph = 0; + } + + + /** + * Notify all the registered maps about a Key added. + */ + virtual void add(Key& key) { + typename Container::iterator it; + for (it = container.begin(); it != container.end(); ++it) { + (*it)->add(key); + } + } + + /** + * Notify all the registered maps about a Key erased. + */ + virtual void erase(Key& key) { + typename Container::iterator it; + for (it = container.begin(); it != container.end(); ++it) { + (*it)->erase(key); + } + } + + /** + * Notify all the registered maps about the map should be cleared. + */ + virtual void clear() { + typename Container::iterator it; + for (it = container.begin(); it != container.end(); ++it) { + (*it)->clear(); + } + } + }; + +} + +#endif diff -r d4d182ab75bd -r df2e45e09652 src/hugo/smart_graph.h --- a/src/hugo/smart_graph.h Wed Sep 01 15:37:36 2004 +0000 +++ b/src/hugo/smart_graph.h Thu Sep 02 10:07:30 2004 +0000 @@ -8,15 +8,21 @@ ///\brief SmartGraph and SymSmartGraph classes. #include -#include +#include #include +#include +#include +#include + +#include + namespace hugo { /// \addtogroup graphs /// @{ - class SymSmartGraph; +// class SymSmartGraph; ///A smart graph class. @@ -53,61 +59,27 @@ std::vector edges; - protected: - - template class DynMapBase - { - protected: - const SmartGraph* G; - public: - virtual void add(const Key k) = 0; - virtual void erase(const Key k) = 0; - DynMapBase(const SmartGraph &_G) : G(&_G) {} - virtual ~DynMapBase() {} - friend class SmartGraph; - }; public: - template class EdgeMap; - template class NodeMap; + + typedef SmartGraph Graph; class Node; class Edge; - // protected: - // HELPME: - protected: - ///\bug It must be public because of SymEdgeMap. - /// - mutable std::vector * > dyn_node_maps; - ///\bug It must be public because of SymEdgeMap. - /// - mutable std::vector * > dyn_edge_maps; - - public: - - class NodeIt; class EdgeIt; class OutEdgeIt; class InEdgeIt; - template class NodeMap; - template class EdgeMap; + CREATE_MAP_REGISTRIES; + CREATE_MAPS(ArrayMapFactory); public: SmartGraph() : nodes(), edges() { } SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { } - ~SmartGraph() - { - for(std::vector * >::iterator i=dyn_node_maps.begin(); - i!=dyn_node_maps.end(); ++i) (**i).G=NULL; - for(std::vector * >::iterator i=dyn_edge_maps.begin(); - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; - } - int nodeNum() const { return nodes.size(); } //FIXME: What is this? int edgeNum() const { return edges.size(); } //FIXME: What is this? @@ -137,9 +109,8 @@ Node n; n.n=nodes.size(); nodes.push_back(NodeT()); //FIXME: Hmmm... - for(std::vector * >::iterator i=dyn_node_maps.begin(); - i!=dyn_node_maps.end(); ++i) (**i).add(n); - + + node_maps.add(n); return n; } @@ -150,8 +121,7 @@ edges[e.n].next_in=nodes[v.n].first_in; nodes[u.n].first_out=nodes[v.n].first_in=e.n; - for(std::vector * >::iterator i=dyn_edge_maps.begin(); - i!=dyn_edge_maps.end(); ++i) (**i).add(e); + edge_maps.add(e); return e; } @@ -172,7 +142,12 @@ return prev; } - void clear() {nodes.clear();edges.clear();} + void clear() { + edge_maps.clear(); + edges.clear(); + node_maps.clear(); + nodes.clear(); + } class Node { friend class SmartGraph; @@ -290,184 +265,6 @@ // operator bool() { return Edge::operator bool(); } }; - template class NodeMap : public DynMapBase - { - std::vector container; - - public: - typedef T ValueType; - typedef Node KeyType; - - NodeMap(const SmartGraph &_G) : - DynMapBase(_G), container(_G.maxNodeId()) - { - G->dyn_node_maps.push_back(this); - } - NodeMap(const SmartGraph &_G,const T &t) : - DynMapBase(_G), container(_G.maxNodeId(),t) - { - G->dyn_node_maps.push_back(this); - } - - NodeMap(const NodeMap &m) : - DynMapBase(*m.G), container(m.container) - { - G->dyn_node_maps.push_back(this); - } - - template friend class NodeMap; - - ///\todo It can copy between different types. - ///\todo We could use 'copy' - template NodeMap(const NodeMap &m) : - DynMapBase(*m.G), container(m.container.size()) - { - G->dyn_node_maps.push_back(this); - typename std::vector::const_iterator i; - for(typename std::vector::const_iterator i=m.container.begin(); - i!=m.container.end(); - i++) - container.push_back(*i); - } - ~NodeMap() - { - if(G) { - std::vector* >::iterator i; - for(i=G->dyn_node_maps.begin(); - i!=G->dyn_node_maps.end() && *i!=this; ++i) ; - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow... - //A better way to do that: (Is this really important?) - if(*i==this) { - *i=G->dyn_node_maps.back(); - G->dyn_node_maps.pop_back(); - } - } - } - - void add(const Node k) - { - if(k.n>=int(container.size())) container.resize(k.n+1); - } - - void erase(const Node) { } - - void set(Node n, T a) { container[n.n]=a; } - //'T& operator[](Node n)' would be wrong here - typename std::vector::reference - operator[](Node n) { return container[n.n]; } - //'const T& operator[](Node n)' would be wrong here - typename std::vector::const_reference - operator[](Node n) const { return container[n.n]; } - - ///\warning There is no safety check at all! - ///Using operator = between maps attached to different graph may - ///cause serious problem. - ///\todo Is this really so? - ///\todo It can copy between different types. - const NodeMap& operator=(const NodeMap &m) - { - container = m.container; - return *this; - } - template - const NodeMap& operator=(const NodeMap &m) - { - std::copy(m.container.begin(), m.container.end(), container.begin()); - return *this; - } - - void update() {} //Useless for Dynamic Maps - void update(T a) {} //Useless for Dynamic Maps - }; - - template class EdgeMap : public DynMapBase - { - std::vector container; - - public: - typedef T ValueType; - typedef Edge KeyType; - - EdgeMap(const SmartGraph &_G) : - DynMapBase(_G), container(_G.maxEdgeId()) - { - //FIXME: What if there are empty Id's? - //FIXME: Can I use 'this' in a constructor? - G->dyn_edge_maps.push_back(this); - } - EdgeMap(const SmartGraph &_G,const T &t) : - DynMapBase(_G), container(_G.maxEdgeId(),t) - { - G->dyn_edge_maps.push_back(this); - } - EdgeMap(const EdgeMap &m) : - DynMapBase(*m.G), container(m.container) - { - G->dyn_edge_maps.push_back(this); - } - - template friend class EdgeMap; - - ///\todo It can copy between different types. - template EdgeMap(const EdgeMap &m) - : DynMapBase(*m.G), container(m.container.size()) - { - G->dyn_edge_maps.push_back(this); - typename std::vector::const_iterator i; - for(typename std::vector::const_iterator i=m.container.begin(); - i!=m.container.end(); - i++) - container.push_back(*i); - } - ~EdgeMap() - { - if(G) { - std::vector* >::iterator i; - for(i=G->dyn_edge_maps.begin(); - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ; - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... - //A better way to do that: (Is this really important?) - if(*i==this) { - *i=G->dyn_edge_maps.back(); - G->dyn_edge_maps.pop_back(); - } - } - } - - void add(const Edge k) - { - if(k.n>=int(container.size())) container.resize(k.n+1); - } - void erase(const Edge) { } - - void set(Edge n, T a) { container[n.n]=a; } - //T get(Edge n) const { return container[n.n]; } - typename std::vector::reference - operator[](Edge n) { return container[n.n]; } - typename std::vector::const_reference - operator[](Edge n) const { return container[n.n]; } - - ///\warning There is no safety check at all! - ///Using operator = between maps attached to different graph may - ///cause serious problem. - ///\todo Is this really so? - ///\todo It can copy between different types. - const EdgeMap& operator=(const EdgeMap &m) - { - container = m.container; - return *this; - } - template - const EdgeMap& operator=(const EdgeMap &m) - { - std::copy(m.container.begin(), m.container.end(), container.begin()); - return *this; - } - - void update() {} //Useless for DynMaps - void update(T a) {} //Useless for DynMaps - }; - }; ///Graph for bidirectional edges. @@ -493,8 +290,14 @@ class SymSmartGraph : public SmartGraph { public: - template class SymEdgeMap; - template friend class SymEdgeMap; + typedef SymSmartGraph Graph; + + KEEP_NODE_MAP(SmartGraph); + KEEP_EDGE_MAP(SmartGraph); + + CREATE_SYM_EDGE_MAP_REGISTRY; + CREATE_SYM_EDGE_MAP_FACTORY(ArrayMapFactory); + IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory); SymSmartGraph() : SmartGraph() { } SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { } @@ -517,107 +320,10 @@ return f; } - ///Common data storage for the edge pairs. - - ///This map makes it possible to store data shared by the oppositely - ///directed pairs of edges. - template class SymEdgeMap : public DynMapBase - { - std::vector container; - - public: - typedef T ValueType; - typedef Edge KeyType; - - SymEdgeMap(const SymSmartGraph &_G) : - DynMapBase(_G), container(_G.maxEdgeId()/2) - { - static_cast(G)->dyn_edge_maps.push_back(this); - } - SymEdgeMap(const SymSmartGraph &_G,const T &t) : - DynMapBase(_G), container(_G.maxEdgeId()/2,t) - { - G->dyn_edge_maps.push_back(this); - } - - SymEdgeMap(const SymEdgeMap &m) : - DynMapBase(*m.G), container(m.container) - { - G->dyn_node_maps.push_back(this); - } - - // template friend class SymEdgeMap; - - ///\todo It can copy between different types. - /// - - template SymEdgeMap(const SymEdgeMap &m) - : DynMapBase(*m.G), container(m.container.size()) - { - G->dyn_node_maps.push_back(this); - typename std::vector::const_iterator i; - for(typename std::vector::const_iterator i=m.container.begin(); - i!=m.container.end(); - i++) - container.push_back(*i); - } - - ~SymEdgeMap() - { - if(G) { - std::vector* >::iterator i; - for(i=static_cast(G)->dyn_edge_maps.begin(); - i!=static_cast(G)->dyn_edge_maps.end() - && *i!=this; ++i) ; - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... - //A better way to do that: (Is this really important?) - if(*i==this) { - *i=static_cast(G)->dyn_edge_maps.back(); - static_cast(G)->dyn_edge_maps.pop_back(); - } - } - } - - void add(const Edge k) - { - if(!k.idref()%2&&k.idref()/2>=int(container.size())) - container.resize(k.idref()/2+1); - } - void erase(const Edge k) { } - - void set(Edge n, T a) { container[n.idref()/2]=a; } - //T get(Edge n) const { return container[n.idref()/2]; } - typename std::vector::reference - operator[](Edge n) { return container[n.idref()/2]; } - typename std::vector::const_reference - operator[](Edge n) const { return container[n.idref()/2]; } - - ///\warning There is no safety check at all! - ///Using operator = between maps attached to different graph may - ///cause serious problem. - ///\todo Is this really so? - ///\todo It can copy between different types. - const SymEdgeMap& operator=(const SymEdgeMap &m) - { - container = m.container; - return *this; - } - template - const SymEdgeMap& operator=(const SymEdgeMap &m) - { - std::copy(m.container.begin(), m.container.end(), container.begin()); - return *this; - } - - void update() {} //Useless for DynMaps - void update(T a) {} //Useless for DynMaps - - }; }; /// @} - } //namespace hugo diff -r d4d182ab75bd -r df2e45e09652 src/hugo/sym_map_factory.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/hugo/sym_map_factory.h Thu Sep 02 10:07:30 2004 +0000 @@ -0,0 +1,107 @@ +// -*- c++ -*- +#ifndef SYM_MAP_FACTORY_H +#define SYM_MAP_FACTORY_H + +namespace hugo { + + template + class SymEdgeIt : public EdgeIt { + public: + + SymEdgeIt() + : EdgeIt() {} + + SymEdgeIt(const Graph& graph) + : EdgeIt(graph) {} + + SymEdgeIt(Invalid invalid) + : EdgeIt(invalid) {} + + SymEdgeIt(const Graph& graph, Edge edge) + : EdgeIt(graph, edge) {} + + SymEdgeIt& operator++() { + EdgeIt::operator++(); + while ( n != -1 && (n & 1)) { + EdgeIt::operator++(); + } + return *this; + } + }; + + template class MapFactory> + class SymMapFactory { + + public: + + typedef typename MapRegistry::Graph Graph; + typedef typename MapRegistry::Key Key; + typedef typename MapRegistry::KeyIt KeyIt; + + typedef typename MapRegistry::MapBase MapBase; + + template + class Map : public MapFactory::template Map { + + typedef typename MapFactory::template Map MapImpl; + public: + + typedef V Value; + + Map() : MapImpl() {} + + Map(const Graph& g, MapRegistry& r) : MapImpl(g, r) {} + + Map(const Graph& g, MapRegistry& r, const Value& v) : MapImpl(g, r, v) {} + + Map(const Map& copy) : MapImpl(static_cast(copy)) {} + + template Map(const CMap& copy) : MapImpl(copy) {} + + Map& operator=(const Map& copy) { + MapImpl::operator=(static_cast(copy)); + return *this; + } + + template Map& operator=(const CMap& copy) { + MapImpl::operator=(copy); + return *this; + } + + Value& operator[](const Key& key) { + int id = MapBase::getGraph()->id(key); + return MapImpl::operator[](id >> 1); + } + + const Value& operator[](const Key& key) const { + int id = MapBase::getGraph()->id(key); + return MapImpl::operator[](id >> 1); + } + + const Value& get(const Key& key) const { + int id = MapBase::getGraph()->id(key); + return MapImpl::operator[](id >> 1); + } + + void set(const Key& key, const Value& val) { + int id = MapBase::getGraph()->id(key); + MapImpl::operator[](id >> 1) = val; + } + + void add(const Key& key) { + int id = MapBase::getGraph()->id(key); + if (id & 1) return; + MapImpl::add(key); + } + + void erase(const Key& key) { + int id = MapBase::getGraph()->id(key); + if (id & 1) return; + MapImpl::add(key); + } + + + }; + }; +} +#endif diff -r d4d182ab75bd -r df2e45e09652 src/hugo/vector_map_factory.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/hugo/vector_map_factory.h Thu Sep 02 10:07:30 2004 +0000 @@ -0,0 +1,338 @@ +// -*- c++ -*- +#ifndef VECTOR_MAP_H +#define VECTOR_MAP_H + +#include + +#include + +namespace hugo { + + /** The VectorMapFactory template class is a factory class + * to create maps for the edge and nodes. This map factory + * use the std::vector to implement the container function. + * + * The template parameter is the MapRegistry that the maps + * will belong to. + */ + + template + class VectorMapFactory { + public: + + /// The graph type of the maps. + typedef typename MapRegistry::Graph Graph; + /// The key type of the maps. + typedef typename MapRegistry::Key Key; + /// The iterator to iterate on the keys. + typedef typename MapRegistry::KeyIt KeyIt; + + /// The MapBase of the Map which imlements the core regisitry function. + typedef typename MapRegistry::MapBase MapBase; + + + /** The template Map type. + */ + template + class Map : public MapBase { + public: + + /// The value type of the map. + typedef V Value; + + typedef std::vector Container; + + /** Default constructor for the map. + */ + Map() {} + + /** Graph and Registry initialized map constructor. + */ + Map(const Graph& g, MapRegistry& r) : MapBase(g, r) { + init(); + } + + /** Constructor to use default value to initialize the map. + */ + Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) { + for (KeyIt it(*getGraph()); it != INVALID; ++it) { + int id = getGraph()->id(it); + if (id >= container.size()) { + container.resize(id + 1); + } + set(it, v); + } + } + + /** Constructor to copy a map of an other map type. + */ + template Map(const CMap& copy) : MapBase(copy) { + if (getGraph()) { + for (KeyIt it(*getGraph()); it != INVALID; ++it) { + int id = getGraph()->id(it); + if (id >= container.size()) { + container.resize(id + 1); + } + set(it, copy[it]); + } + } + } + + /** Assign operator to copy a map an other map type. + */ + template Map& operator=(const CMap& copy) { + if (getGraph()) { + destroy(); + } + this->MapBase::operator=(copy); + if (getGraph()) { + for (KeyIt it(*getGraph()); it != INVALID; ++it) { + int id = getGraph()->id(it); + if (id >= container.size()) { + container.resize(id + 1); + } + set(it, copy[it]); + } + } + } + + /** The destructor of the map. + */ + virtual ~Map() { + } + + /** + * The subscript operator. The map can be subscripted by the + * actual keys of the graph. + */ + typename Container::reference operator[](const Key& key) { + int id = getGraph()->id(key); + return container[id]; + } + + /** + * The const subscript operator. The map can be subscripted by the + * actual keys of the graph. + */ + typename Container::const_reference operator[](const Key& key) const { + int id = getGraph()->id(key); + return container[id]; + } + + /** Setter function of the map. Equivalent with map[key] = val. + * This is a compatibility feature with the not dereferable maps. + */ + void set(const Key& key, const Value& val) { + int id = getGraph()->id(key); + container[id] = val; + } + + /** Add a new key to the map. It called by the map registry. + */ + void add(const Key& key) { + int id = getGraph()->id(key); + if (id >= container.size()) { + container.resize(id + 1); + } + } + + /** Erase a key from the map. It called by the map registry. + */ + void erase(const Key& key) {} + + /** Clear the data structure. + */ + void clear() { + container.clear(); + } + + /** Compatible iterator with the stl maps' iterators. + * It iterates on pairs of a key and a value. + */ + class iterator { + friend class Map; + friend class const_iterator; + private: + + /** Private constructor to initalize the the iterators returned + * by the begin() and end(). + */ + iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {} + + public: + + /** Default constructor. + */ + iterator() {} + + typedef extended_pair Reference; + + /** Dereference operator for map. + */ + Reference operator*() { + return Reference(it, (*map)[it]); + } + + class Pointer { + friend class iterator; + private: + Reference data; + Pointer(const Key& key, Value& val) : data(key, val) {} + public: + Reference* operator->() {return &data;} + }; + + /** Arrow operator for map. + */ + Pointer operator->() { + return Pointer(it, ((*map)[it])); + } + + /** The pre increment operator of the map. + */ + iterator& operator++() { + ++it; + return *this; + } + + /** The post increment operator of the map. + */ + iterator operator++(int) { + iterator tmp(it); + ++it; + return tmp; + } + + /** The equality operator of the map. + */ + bool operator==(const_iterator p_it) { + return p_it.it == it; + } + + /** The not-equality operator of the map. + */ + bool operator!=(const_iterator p_it) { + return !(*this == p_it); + } + + + private: + Map* map; + KeyIt it; + }; + + /** Returns the begin iterator of the map. + */ + iterator begin() { + return iterator(*this, KeyIt(*getGraph())); + } + + /** Returns the end iterator of the map. + */ + iterator end() { + return iterator(*this, INVALID); + } + + class const_iterator { + friend class Map; + friend class iterator; + private: + + /** Private constructor to initalize the the iterators returned + * by the begin() and end(). + */ + const_iterator (const Map& pmap, const KeyIt& pit) + : map(&pmap), it(pit) {} + + public: + + /** Default constructor. + */ + const_iterator() {} + + /** Constructor to convert iterator to const_iterator. + */ + const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {} + + typedef extended_pair Reference; + + /** Dereference operator for map. + */ + Reference operator*() { + return Reference(it, (*map)[it]); + } + + + class Pointer { + friend class const_iterator; + private: + Reference data; + Pointer(const Key& key, const Value& val) : data(key, val) {} + public: + Reference* operator->() {return &data;} + }; + + /** Arrow operator for map. + */ + Pointer operator->() { + return Pointer(it, ((*map)[it])); + } + + /** The pre increment operator of the map. + */ + const_iterator& operator++() { + ++it; + return *this; + } + + /** The post increment operator of the map. + */ + const_iterator operator++(int) { + const_iterator tmp(it); + ++it; + return tmp; + } + + /** The equality operator of the map. + */ + bool operator==(const_iterator p_it) { + return p_it.it == it; + } + + /** The not-equality operator of the map. + */ + bool operator!=(const_iterator p_it) { + return !(*this == p_it); + } + + + private: + const Map* map; + KeyIt it; + }; + + /** Returns the begin const_iterator of the map. + */ + const_iterator begin() const { + return const_iterator(*this, KeyIt(*getGraph())); + } + + /** Returns the end const_iterator of the map. + */ + const_iterator end() const { + return const_iterator(*this, INVALID); + } + + private: + + Container container; + + }; + + }; + +} + +#endif