deba@703: // -*- c++ -*- deba@571: #ifndef VECTOR_MAP_H deba@571: #define VECTOR_MAP_H deba@571: deba@571: #include deba@571: deba@702: #include "extended_pair.h" deba@702: alpar@921: namespace lemon { deba@700: deba@700: /** The VectorMapFactory template class is a factory class deba@700: * to create maps for the edge and nodes. This map factory deba@700: * use the std::vector to implement the container function. deba@700: * deba@700: * The template parameter is the MapRegistry that the maps deba@700: * will belong to. deba@700: */ deba@571: deba@627: template deba@700: class VectorMapFactory { deba@700: public: deba@627: deba@700: /// The graph type of the maps. deba@627: typedef typename MapRegistry::Graph Graph; deba@700: /// The key type of the maps. deba@627: typedef typename MapRegistry::Key Key; deba@700: /// The iterator to iterate on the keys. deba@627: typedef typename MapRegistry::KeyIt KeyIt; deba@627: deba@700: /// The MapBase of the Map which imlements the core regisitry function. deba@627: typedef typename MapRegistry::MapBase MapBase; deba@698: deba@627: deba@700: /** The template Map type. deba@700: */ deba@627: template deba@700: class Map : public MapBase { deba@700: public: deba@700: deba@700: /// The value type of the map. deba@627: typedef V Value; deba@700: deba@700: typedef std::vector Container; deba@700: deba@700: /** Default constructor for the map. deba@700: */ deba@627: Map() {} deba@700: deba@700: /** Graph and Registry initialized map constructor. deba@700: */ deba@700: Map(const Graph& g, MapRegistry& r) : MapBase(g, r) { deba@627: init(); deba@627: } deba@700: deba@700: /** Constructor to use default value to initialize the map. deba@700: */ deba@700: Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) { deba@700: for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { deba@703: int id = getGraph->id(it); deba@703: if (id >= container.size) { deba@703: container.resize(id + 1); deba@703: } deba@703: set(it, v); deba@700: } deba@700: } deba@700: deba@700: /** Constructor to copy a map of an other map type. deba@700: */ deba@700: template Map(const CMap& copy) : MapBase(copy) { deba@700: if (getGraph()) { deba@700: for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { deba@703: int id = getGraph->id(it); deba@703: if (id >= container.size) { deba@703: container.resize(id + 1); deba@703: } deba@700: set(it, copy[it]); deba@700: } deba@700: } deba@700: } deba@700: deba@700: /** Assign operator to copy a map an other map type. deba@700: */ deba@700: template Map& operator=(const CMap& copy) { deba@700: if (getGraph()) { deba@700: destroy(); deba@700: } deba@700: this->MapBase::operator=(copy); deba@700: if (getGraph()) { deba@700: for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { deba@703: int id = getGraph->id(it); deba@703: if (id >= container.size) { deba@703: container.resize(id + 1); deba@703: } deba@700: set(it, copy[it]); deba@700: } deba@700: } deba@700: } deba@700: deba@700: /** The destructor of the map. deba@700: */ deba@627: virtual ~Map() { deba@627: } deba@700: deba@700: /** deba@700: * The subscript operator. The map can be subscripted by the deba@700: * actual keys of the graph. deba@700: */ deba@698: typename Container::reference operator[](const Key& key) { deba@700: int id = getGraph()->id(key); deba@627: return container[id]; deba@627: } deba@571: deba@700: /** deba@700: * The const subscript operator. The map can be subscripted by the deba@700: * actual keys of the graph. deba@700: */ deba@698: typename Container::const_reference operator[](const Key& key) const { deba@700: int id = getGraph()->id(key); deba@627: return container[id]; deba@627: } deba@700: deba@700: /** Setter function of the map. Equivalent with map[key] = val. deba@700: * This is a compatibility feature with the not dereferable maps. deba@700: */ deba@627: void set(const Key& key, const Value& val) { deba@700: int id = getGraph()->id(key); deba@627: container[id] = val; deba@627: } deba@627: deba@700: /** Add a new key to the map. It called by the map registry. deba@700: */ deba@627: void add(const Key& key) { deba@700: int id = getGraph()->id(key); deba@627: if (id >= container.size()) { deba@627: container.resize(id + 1); deba@627: } deba@627: } deba@627: deba@700: /** Erease a key from the map. It called by the map registry. deba@700: */ deba@627: void erase(const Key& key) {} deba@698: deba@700: /** Compatible iterator with the stl maps' iterators. deba@700: * It iterates on pairs of a key and a value. deba@700: */ deba@700: class iterator { deba@700: friend class Map; deba@700: friend class const_iterator; deba@698: private: deba@698: deba@700: /** Private constructor to initalize the the iterators returned deba@700: * by the begin() and end(). deba@700: */ deba@700: iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {} deba@700: deba@698: public: deba@700: deba@700: /** Default constructor. deba@700: */ deba@698: iterator() {} deba@700: deba@703: typedef extended_pair Reference; deba@703: deba@700: /** Dereference operator for map. deba@700: */ deba@703: Reference operator*() { deba@703: return Reference(it, (*map)[it]); deba@698: } deba@698: deba@702: class Pointer { deba@702: friend class iterator; deba@702: private: deba@703: Reference data; deba@702: Pointer(const Key& key, Value& val) : data(key, val) {} deba@702: public: deba@703: Reference* operator->() {return &data;} deba@702: }; deba@702: deba@700: /** Arrow operator for map. deba@700: */ deba@702: Pointer operator->() { deba@702: return Pointer(it, ((*map)[it])); deba@700: } deba@700: deba@700: /** The pre increment operator of the map. deba@700: */ deba@700: iterator& operator++() { deba@700: map->getGraph()->next(it); deba@700: return *this; deba@700: } deba@700: deba@700: /** The post increment operator of the map. deba@700: */ deba@700: iterator operator++(int) { deba@700: iterator tmp(it); deba@700: map.getGraph()->next(it); deba@700: return tmp; deba@700: } deba@700: deba@700: /** The equality operator of the map. deba@700: */ deba@700: bool operator==(const_iterator p_it) { deba@700: return p_it.it == it; deba@700: } deba@700: deba@700: /** The not-equality operator of the map. deba@700: */ deba@700: bool operator!=(const_iterator p_it) { deba@700: return !(*this == p_it); deba@700: } deba@702: deba@700: deba@698: private: deba@700: Map* map; deba@698: KeyIt it; deba@698: }; deba@698: deba@700: /** Returns the begin iterator of the map. deba@700: */ deba@700: iterator begin() { deba@700: return iterator(*this, KeyIt(*getGraph())); deba@700: } deba@700: deba@700: /** Returns the end iterator of the map. deba@700: */ deba@700: iterator end() { deba@700: return iterator(*this, INVALID); deba@700: } deba@700: deba@700: class const_iterator { deba@700: friend class Map; deba@700: friend class iterator; deba@627: private: deba@700: deba@700: /** Private constructor to initalize the the iterators returned deba@700: * by the begin() and end(). deba@700: */ deba@703: const_iterator (const Map& pmap, const KeyIt& pit) deba@703: : map(&pmap), it(pit) {} deba@700: deba@700: public: deba@700: deba@700: /** Default constructor. deba@700: */ deba@700: const_iterator() {} deba@700: deba@700: /** Constructor to convert iterator to const_iterator. deba@700: */ deba@703: const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {} deba@700: deba@703: typedef extended_pair Reference; deba@703: deba@700: /** Dereference operator for map. deba@700: */ deba@703: Reference operator*() { deba@703: return Reference(it, (*map)[it]); deba@700: } deba@700: deba@703: deba@702: class Pointer { deba@702: friend class const_iterator; deba@702: private: deba@703: Reference data; deba@702: Pointer(const Key& key, const Value& val) : data(key, val) {} deba@702: public: deba@703: Reference* operator->() {return &data;} deba@702: }; deba@703: deba@700: /** Arrow operator for map. deba@700: */ deba@703: Pointer operator->() { deba@703: return Pointer(it, ((*map)[it])); deba@700: } deba@700: deba@700: /** The pre increment operator of the map. deba@700: */ deba@700: const_iterator& operator++() { deba@700: map->getGraph()->next(it); deba@700: return *this; deba@700: } deba@700: deba@700: /** The post increment operator of the map. deba@700: */ deba@700: const_iterator operator++(int) { deba@700: const_iterator tmp(it); deba@700: map->getGraph()->next(it); deba@700: return tmp; deba@700: } deba@700: deba@700: /** The equality operator of the map. deba@700: */ deba@700: bool operator==(const_iterator p_it) { deba@700: return p_it.it == it; deba@700: } deba@700: deba@700: /** The not-equality operator of the map. deba@700: */ deba@700: bool operator!=(const_iterator p_it) { deba@700: return !(*this == p_it); deba@700: } deba@700: deba@702: deba@700: private: deba@700: const Map* map; deba@700: KeyIt it; deba@700: }; deba@700: deba@700: /** Returns the begin const_iterator of the map. deba@700: */ deba@700: const_iterator begin() const { deba@700: return const_iterator(*this, KeyIt(*getGraph())); deba@700: } deba@700: deba@700: /** Returns the end const_iterator of the map. deba@700: */ deba@700: const_iterator end() const { deba@700: return const_iterator(*this, INVALID); deba@700: } deba@700: deba@700: private: deba@571: deba@627: Container container; deba@698: deba@627: }; deba@571: deba@627: }; deba@700: deba@571: } deba@571: deba@571: #endif