deba@782: // -*- c++ -*- deba@782: #ifndef VECTOR_MAP_H deba@782: #define VECTOR_MAP_H deba@782: deba@782: #include deba@782: deba@782: #include deba@782: alpar@785: ///\ingroup graphmapfactory alpar@785: ///\file alpar@785: ///\brief Vector based graph maps. alpar@785: deba@782: namespace hugo { alpar@785: alpar@785: /// \addtogroup graphmapfactory alpar@785: /// @{ alpar@785: deba@782: /** The VectorMapFactory template class is a factory class deba@782: * to create maps for the edge and nodes. This map factory deba@798: * uses the std::vector to implement the container function. deba@782: * deba@782: * The template parameter is the MapRegistry that the maps deba@782: * will belong to. alpar@804: * alpar@804: * \todo It should use a faster initialization using the maxNodeId() or alpar@804: * maxEdgeId() function of the graph istead of iterating through each alpar@804: * edge/node. deba@782: */ deba@782: deba@782: template deba@782: class VectorMapFactory { deba@782: public: deba@782: deba@782: /// The graph type of the maps. deba@782: typedef typename MapRegistry::Graph Graph; deba@782: /// The key type of the maps. alpar@786: typedef typename MapRegistry::KeyType KeyType; deba@782: /// The iterator to iterate on the keys. deba@782: typedef typename MapRegistry::KeyIt KeyIt; deba@782: deba@782: /// The MapBase of the Map which imlements the core regisitry function. deba@782: typedef typename MapRegistry::MapBase MapBase; deba@782: deba@782: deba@782: /** The template Map type. deba@782: */ deba@782: template deba@782: class Map : public MapBase { deba@798: deba@798: typedef std::vector Container; deba@798: deba@782: public: deba@782: deba@782: /// The value type of the map. deba@798: typedef V ValueType; deba@798: deba@798: /// The value type of the map. deba@782: typedef V Value; deba@798: /// The reference type of the map; deba@798: typedef typename Container::reference Reference; deba@798: /// The pointer type of the map; deba@798: typedef typename Container::pointer Pointer; deba@782: deba@798: /// The const value type of the map. deba@798: typedef const Value ConstValue; deba@798: /// The const reference type of the map; deba@798: typedef typename Container::const_reference ConstReference; deba@798: /// The pointer type of the map; deba@798: typedef typename Container::const_pointer ConstPointer; deba@782: deba@782: /** Default constructor for the map. deba@782: */ deba@782: Map() {} deba@782: deba@782: /** Graph and Registry initialized map constructor. deba@782: */ deba@782: Map(const Graph& g, MapRegistry& r) : MapBase(g, r) { deba@782: init(); deba@782: } deba@782: deba@782: /** Constructor to use default value to initialize the map. deba@782: */ deba@782: Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) { deba@782: for (KeyIt it(*getGraph()); it != INVALID; ++it) { deba@782: int id = getGraph()->id(it); deba@798: if (id >= (int)container.size()) { deba@782: container.resize(id + 1); deba@782: } deba@782: set(it, v); deba@782: } deba@782: } deba@782: deba@782: /** Constructor to copy a map of an other map type. deba@782: */ deba@782: template Map(const CMap& copy) : MapBase(copy) { deba@782: if (getGraph()) { deba@782: for (KeyIt it(*getGraph()); it != INVALID; ++it) { deba@782: int id = getGraph()->id(it); deba@798: if (id >= (int)container.size()) { deba@782: container.resize(id + 1); deba@782: } deba@782: set(it, copy[it]); deba@782: } deba@782: } deba@782: } deba@782: deba@782: /** Assign operator to copy a map an other map type. deba@782: */ deba@782: template Map& operator=(const CMap& copy) { deba@782: if (getGraph()) { deba@782: destroy(); deba@782: } deba@782: this->MapBase::operator=(copy); deba@782: if (getGraph()) { deba@782: for (KeyIt it(*getGraph()); it != INVALID; ++it) { deba@782: int id = getGraph()->id(it); deba@798: if (id >= (int)container.size()) { deba@782: container.resize(id + 1); deba@782: } deba@782: set(it, copy[it]); deba@782: } deba@782: } deba@798: return *this; deba@782: } deba@782: deba@782: /** The destructor of the map. deba@782: */ deba@782: virtual ~Map() { deba@782: } deba@782: deba@782: /** deba@782: * The subscript operator. The map can be subscripted by the deba@782: * actual keys of the graph. deba@782: */ deba@799: Reference operator[](const KeyType& key) { deba@782: int id = getGraph()->id(key); deba@782: return container[id]; deba@782: } deba@782: deba@782: /** deba@782: * The const subscript operator. The map can be subscripted by the deba@782: * actual keys of the graph. deba@782: */ deba@799: ConstReference operator[](const KeyType& key) const { deba@782: int id = getGraph()->id(key); deba@782: return container[id]; deba@782: } deba@782: deba@782: /** Setter function of the map. Equivalent with map[key] = val. deba@782: * This is a compatibility feature with the not dereferable maps. deba@782: */ alpar@786: void set(const KeyType& key, const Value& val) { deba@782: int id = getGraph()->id(key); deba@782: container[id] = val; deba@782: } deba@782: deba@782: /** Add a new key to the map. It called by the map registry. deba@782: */ alpar@786: void add(const KeyType& key) { deba@782: int id = getGraph()->id(key); deba@798: if (id >= (int)container.size()) { deba@782: container.resize(id + 1); deba@782: } deba@782: } deba@782: deba@782: /** Erase a key from the map. It called by the map registry. deba@782: */ alpar@786: void erase(const KeyType& key) {} deba@782: deba@782: /** Clear the data structure. deba@782: */ deba@782: void clear() { deba@782: container.clear(); deba@782: } deba@782: deba@782: /** Compatible iterator with the stl maps' iterators. deba@782: * It iterates on pairs of a key and a value. deba@782: */ deba@782: class iterator { deba@782: friend class Map; deba@782: friend class const_iterator; deba@782: private: deba@782: deba@782: /** Private constructor to initalize the the iterators returned deba@782: * by the begin() and end(). deba@782: */ deba@782: iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {} deba@782: deba@782: public: deba@782: deba@782: /** Default constructor. deba@782: */ deba@782: iterator() {} deba@782: alpar@786: typedef extended_pair Reference; deba@782: deba@782: /** Dereference operator for map. deba@782: */ deba@782: Reference operator*() { deba@782: return Reference(it, (*map)[it]); deba@782: } deba@782: deba@782: class Pointer { deba@782: friend class iterator; deba@782: private: deba@782: Reference data; deba@799: Pointer(const KeyType& key, Map::Reference val) : data(key, val) {} deba@782: public: deba@782: Reference* operator->() {return &data;} deba@782: }; deba@782: deba@782: /** Arrow operator for map. deba@782: */ deba@782: Pointer operator->() { deba@782: return Pointer(it, ((*map)[it])); deba@782: } deba@782: deba@782: /** The pre increment operator of the map. deba@782: */ deba@782: iterator& operator++() { deba@782: ++it; deba@782: return *this; deba@782: } deba@782: deba@782: /** The post increment operator of the map. deba@782: */ deba@782: iterator operator++(int) { deba@782: iterator tmp(it); deba@782: ++it; deba@782: return tmp; deba@782: } deba@782: deba@782: /** The equality operator of the map. deba@782: */ deba@782: bool operator==(const_iterator p_it) { deba@782: return p_it.it == it; deba@782: } deba@782: deba@782: /** The not-equality operator of the map. deba@782: */ deba@782: bool operator!=(const_iterator p_it) { deba@782: return !(*this == p_it); deba@782: } deba@782: deba@782: deba@782: private: deba@782: Map* map; deba@782: KeyIt it; deba@782: }; deba@782: deba@782: /** Returns the begin iterator of the map. deba@782: */ deba@782: iterator begin() { deba@782: return iterator(*this, KeyIt(*getGraph())); deba@782: } deba@782: deba@782: /** Returns the end iterator of the map. deba@782: */ deba@782: iterator end() { deba@782: return iterator(*this, INVALID); deba@782: } deba@782: deba@782: class const_iterator { deba@782: friend class Map; deba@782: friend class iterator; deba@782: private: deba@782: deba@782: /** Private constructor to initalize the the iterators returned deba@782: * by the begin() and end(). deba@782: */ deba@782: const_iterator (const Map& pmap, const KeyIt& pit) deba@782: : map(&pmap), it(pit) {} deba@782: deba@782: public: deba@782: deba@782: /** Default constructor. deba@782: */ deba@782: const_iterator() {} deba@782: deba@782: /** Constructor to convert iterator to const_iterator. deba@782: */ deba@782: const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {} deba@782: alpar@786: typedef extended_pair Reference; deba@782: deba@782: /** Dereference operator for map. deba@782: */ deba@782: Reference operator*() { deba@782: return Reference(it, (*map)[it]); deba@782: } deba@782: deba@782: deba@782: class Pointer { deba@782: friend class const_iterator; deba@782: private: deba@782: Reference data; deba@799: Pointer(const KeyType& key, Map::ConstReference val) deba@799: : data(key, val) {} deba@782: public: deba@782: Reference* operator->() {return &data;} deba@782: }; deba@782: deba@782: /** Arrow operator for map. deba@782: */ deba@782: Pointer operator->() { deba@782: return Pointer(it, ((*map)[it])); deba@782: } deba@782: deba@782: /** The pre increment operator of the map. deba@782: */ deba@782: const_iterator& operator++() { deba@782: ++it; deba@782: return *this; deba@782: } deba@782: deba@782: /** The post increment operator of the map. deba@782: */ deba@782: const_iterator operator++(int) { deba@782: const_iterator tmp(it); deba@782: ++it; deba@782: return tmp; deba@782: } deba@782: deba@782: /** The equality operator of the map. deba@782: */ deba@782: bool operator==(const_iterator p_it) { deba@782: return p_it.it == it; deba@782: } deba@782: deba@782: /** The not-equality operator of the map. deba@782: */ deba@782: bool operator!=(const_iterator p_it) { deba@782: return !(*this == p_it); deba@782: } deba@782: deba@782: deba@782: private: deba@782: const Map* map; deba@782: KeyIt it; deba@782: }; deba@782: deba@782: /** Returns the begin const_iterator of the map. deba@782: */ deba@782: const_iterator begin() const { deba@782: return const_iterator(*this, KeyIt(*getGraph())); deba@782: } deba@782: deba@782: /** Returns the end const_iterator of the map. deba@782: */ deba@782: const_iterator end() const { deba@782: return const_iterator(*this, INVALID); deba@782: } deba@782: deba@782: private: deba@782: deba@782: Container container; deba@782: deba@782: }; deba@782: deba@782: }; deba@782: alpar@785: alpar@785: /// @} alpar@785: alpar@785: deba@782: } deba@782: deba@782: #endif