1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/vector_map.h Wed Sep 08 12:06:45 2004 +0000
1.3 @@ -0,0 +1,216 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef VECTOR_MAP_H
1.6 +#define VECTOR_MAP_H
1.7 +
1.8 +#include <vector>
1.9 +
1.10 +#include <hugo/map_iterator.h>
1.11 +
1.12 +///\ingroup graphmaps
1.13 +///\file
1.14 +///\brief Vector based graph maps.
1.15 +
1.16 +namespace hugo {
1.17 +
1.18 + /// \addtogroup graphmaps
1.19 + /// @{
1.20 +
1.21 + /** The ArrayMap template class is graph map structure what
1.22 + * automatically updates the map when a key is added to or erased from
1.23 + * the map. This map factory uses the allocators to implement
1.24 + * the container functionality. This map factory
1.25 + * uses the std::vector to implement the container function.
1.26 + *
1.27 + * The template parameter is the MapRegistry that the maps
1.28 + * will belong to and the ValueType.
1.29 + *
1.30 + * \todo It should use a faster initialization using the maxNodeId() or
1.31 + * maxEdgeId() function of the graph instead of iterating through each
1.32 + * edge/node.
1.33 + */
1.34 +
1.35 + template <typename MapRegistry, typename Value>
1.36 + class VectorMap : public MapRegistry::MapBase {
1.37 + public:
1.38 +
1.39 + /// The graph type of the maps.
1.40 + typedef typename MapRegistry::Graph Graph;
1.41 + /// The key type of the maps.
1.42 + typedef typename MapRegistry::KeyType KeyType;
1.43 + /// The iterator to iterate on the keys.
1.44 + typedef typename MapRegistry::KeyIt KeyIt;
1.45 +
1.46 + /// The map type.
1.47 + typedef VectorMap Map;
1.48 + /// The MapBase of the Map which implements the core regisitry function.
1.49 + typedef typename MapRegistry::MapBase MapBase;
1.50 +
1.51 + private:
1.52 +
1.53 + /// The container type of the map.
1.54 + typedef std::vector<Value> Container;
1.55 +
1.56 + public:
1.57 +
1.58 +
1.59 + /// The value type of the map.
1.60 + typedef Value ValueType;
1.61 + /// The reference type of the map;
1.62 + typedef typename Container::reference ReferenceType;
1.63 + /// The pointer type of the map;
1.64 + typedef typename Container::pointer PointerType;
1.65 +
1.66 + /// The const value type of the map.
1.67 + typedef const Value ConstValueType;
1.68 + /// The const reference type of the map;
1.69 + typedef typename Container::const_reference ConstReferenceType;
1.70 + /// The pointer type of the map;
1.71 + typedef typename Container::const_pointer ConstPointerType;
1.72 +
1.73 + /** Default constructor for the map.
1.74 + */
1.75 + VectorMap() {}
1.76 +
1.77 + /** Graph and Registry initialized map constructor.
1.78 + */
1.79 + VectorMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
1.80 + init();
1.81 + }
1.82 +
1.83 + /** Constructor to use default value to initialize the map.
1.84 + */
1.85 + VectorMap(const Graph& g, MapRegistry& r, const Value& v)
1.86 + : MapBase(g, r) {
1.87 + for (KeyIt it(*getGraph()); it != INVALID; ++it) {
1.88 + int id = getGraph()->id(it);
1.89 + if (id >= (int)container.size()) {
1.90 + container.resize(id + 1);
1.91 + }
1.92 + set(it, v);
1.93 + }
1.94 + }
1.95 +
1.96 + /** Constructor to copy a map of an other map type.
1.97 + */
1.98 + template <typename CMap> VectorMap(const CMap& copy) : MapBase(copy) {
1.99 + if (getGraph()) {
1.100 + for (KeyIt it(*getGraph()); it != INVALID; ++it) {
1.101 + int id = getGraph()->id(it);
1.102 + if (id >= (int)container.size()) {
1.103 + container.resize(id + 1);
1.104 + }
1.105 + set(it, copy[it]);
1.106 + }
1.107 + }
1.108 + }
1.109 +
1.110 + /** Assign operator to copy a map an other map type.
1.111 + */
1.112 + template <typename CMap> VectorMap& operator=(const CMap& copy) {
1.113 + if (getGraph()) {
1.114 + destroy();
1.115 + }
1.116 + this->MapBase::operator=(copy);
1.117 + if (getGraph()) {
1.118 + for (KeyIt it(*getGraph()); it != INVALID; ++it) {
1.119 + int id = getGraph()->id(it);
1.120 + if (id >= (int)container.size()) {
1.121 + container.resize(id + 1);
1.122 + }
1.123 + set(it, copy[it]);
1.124 + }
1.125 + }
1.126 + return *this;
1.127 + }
1.128 +
1.129 + /** The destructor of the map.
1.130 + */
1.131 + virtual ~VectorMap() {
1.132 + }
1.133 +
1.134 + /**
1.135 + * The subscript operator. The map can be subscripted by the
1.136 + * actual keys of the graph.
1.137 + */
1.138 + ReferenceType operator[](const KeyType& key) {
1.139 + int id = getGraph()->id(key);
1.140 + return container[id];
1.141 + }
1.142 +
1.143 + /**
1.144 + * The const subscript operator. The map can be subscripted by the
1.145 + * actual keys of the graph.
1.146 + */
1.147 + ConstReferenceType operator[](const KeyType& key) const {
1.148 + int id = getGraph()->id(key);
1.149 + return container[id];
1.150 + }
1.151 +
1.152 + /** Setter function of the map. Equivalent with map[key] = val.
1.153 + * This is a compatibility feature with the not dereferable maps.
1.154 + */
1.155 + void set(const KeyType& key, const ValueType& val) {
1.156 + int id = getGraph()->id(key);
1.157 + container[id] = val;
1.158 + }
1.159 +
1.160 + /** Add a new key to the map. It called by the map registry.
1.161 + */
1.162 + void add(const KeyType& key) {
1.163 + int id = getGraph()->id(key);
1.164 + if (id >= (int)container.size()) {
1.165 + container.resize(id + 1);
1.166 + }
1.167 + }
1.168 +
1.169 + /** Erase a key from the map. It called by the map registry.
1.170 + */
1.171 + void erase(const KeyType& key) {}
1.172 +
1.173 + /** Clear the data structure.
1.174 + */
1.175 + void clear() {
1.176 + container.clear();
1.177 + }
1.178 +
1.179 + /// The stl compatible pair iterator of the map.
1.180 + typedef MapIterator<VectorMap> Iterator;
1.181 + /// The stl compatible const pair iterator of the map.
1.182 + typedef MapConstIterator<VectorMap> ConstIterator;
1.183 +
1.184 + /** Returns the begin iterator of the map.
1.185 + */
1.186 + Iterator begin() {
1.187 + return Iterator(*this, KeyIt(*MapBase::getGraph()));
1.188 + }
1.189 +
1.190 + /** Returns the end iterator of the map.
1.191 + */
1.192 + Iterator end() {
1.193 + return Iterator(*this, INVALID);
1.194 + }
1.195 +
1.196 + /** Returns the begin ConstIterator of the map.
1.197 + */
1.198 + ConstIterator begin() const {
1.199 + return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
1.200 + }
1.201 +
1.202 + /** Returns the end const_iterator of the map.
1.203 + */
1.204 + ConstIterator end() const {
1.205 + return ConstIterator(*this, INVALID);
1.206 + }
1.207 +
1.208 + private:
1.209 +
1.210 + Container container;
1.211 +
1.212 +
1.213 + };
1.214 +
1.215 + /// @}
1.216 +
1.217 +}
1.218 +
1.219 +#endif