Dox readable more even.
7 #include <hugo/map_iterator.h>
8 #include <hugo/map_bits.h>
12 ///\brief Graph maps that construates and destruates
13 ///their elements dynamically.
18 /// \addtogroup graphmaps
21 /** The ArrayMap template class is graph map structure what
22 * automatically updates the map when a key is added to or erased from
23 * the map. This map factory uses the allocators to implement
24 * the container functionality.
26 * The template parameter is the MapRegistry that the maps
27 * will belong to and the ValueType.
30 template <typename MapRegistry, typename Value>
31 class ArrayMap : public MapRegistry::MapBase {
35 /// The graph type of the maps.
36 typedef typename MapRegistry::Graph Graph;
37 /// The key type of the maps.
38 typedef typename MapRegistry::KeyType KeyType;
39 /// The iterator to iterate on the keys.
40 typedef typename MapRegistry::KeyIt KeyIt;
42 /// The MapBase of the Map which imlements the core regisitry function.
43 typedef typename MapRegistry::MapBase MapBase;
48 /// The value type of the map.
49 typedef Value ValueType;
50 /// The reference type of the map;
51 typedef Value& ReferenceType;
52 /// The pointer type of the map;
53 typedef Value* PointerType;
55 /// The const value type of the map.
56 typedef const Value ConstValueType;
57 /// The const reference type of the map;
58 typedef const Value& ConstReferenceType;
59 /// The pointer type of the map;
60 typedef const Value* ConstPointerType;
63 typedef std::allocator<Value> Allocator;
66 /** Default constructor for the map.
68 ArrayMap() : capacity(0), values(0) {}
70 /** Graph and Registry initialized map constructor.
72 ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
74 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
75 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
76 allocator.construct(&(values[id]), Value());
80 /** Constructor to use default value to initialize the map.
82 ArrayMap(const Graph& g, MapRegistry& r, const Value& v)
85 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
86 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
87 allocator.construct(&(values[id]), v);
91 /** Constructor to copy a map of the same map type.
93 ArrayMap(const ArrayMap& copy) : MapBase(copy) {
94 capacity = copy.capacity;
95 if (capacity == 0) return;
96 values = allocator.allocate(capacity);
97 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
98 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
99 allocator.construct(&(values[id]), copy.values[id]);
103 /** Constructor to copy a map of an other map type.
105 template <typename TT>
106 ArrayMap(const ArrayMap<MapRegistry, TT>& copy)
108 capacity = copy.capacity;
109 if (capacity == 0) return;
110 values = allocator.allocate(capacity);
111 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
112 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
113 allocator.construct(&(values[id]), copy.values[id]);
117 /** Assign operator to copy a map of the same map type.
119 ArrayMap& operator=(const ArrayMap& copy) {
120 if (© == this) return *this;
124 allocator.deallocate(values, capacity);
127 MapBase::operator=(copy);
129 capacity = copy.capacity;
130 if (capacity == 0) return *this;
131 values = allocator.allocate(capacity);
133 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
134 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
135 allocator.construct(&(values[id]), copy.values[id]);
141 /** Assign operator to copy a map of an other map type.
143 template <typename TT>
144 ArrayMap& operator=(const ArrayMap<MapRegistry, TT>& copy) {
147 allocator.deallocate(values, capacity);
150 MapBase::operator=(copy);
152 capacity = copy.capacity;
153 if (capacity == 0) return *this;
154 values = allocator.allocate(capacity);
156 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
157 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
158 allocator.construct(&(values[id]), copy.values[id]);
164 /** The destructor of the map.
166 virtual ~ArrayMap() {
169 allocator.deallocate(values, capacity);
175 * The subscript operator. The map can be subscripted by the
176 * actual keys of the graph.
178 ReferenceType operator[](const KeyType& key) {
179 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
184 * The const subscript operator. The map can be subscripted by the
185 * actual keys of the graph.
187 ConstReferenceType operator[](const KeyType& key) const {
188 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
192 /** Setter function of the map. Equivalent with map[key] = val.
193 * This is a compatibility feature with the not dereferable maps.
195 void set(const KeyType& key, const ValueType& val) {
196 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
200 /** Add a new key to the map. It called by the map registry.
202 void add(const KeyType& key) {
203 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
204 if (id >= capacity) {
205 int new_capacity = (capacity == 0 ? 1 : capacity);
206 while (new_capacity <= id) {
209 Value* new_values = allocator.allocate(new_capacity);;
210 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
211 int jd = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
213 allocator.construct(&(new_values[jd]), values[jd]);
214 allocator.destroy(&(values[jd]));
217 if (capacity != 0) allocator.deallocate(values, capacity);
219 capacity = new_capacity;
221 allocator.construct(&(values[id]), Value());
224 /** Erase a key from the map. It called by the map registry.
226 void erase(const KeyType& key) {
227 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
228 allocator.destroy(&(values[id]));
231 /** Clear the data structure.
236 allocator.deallocate(values, capacity);
241 /// The stl compatible pair iterator of the map.
242 typedef MapIterator<ArrayMap> Iterator;
243 /// The stl compatible const pair iterator of the map.
244 typedef MapConstIterator<ArrayMap> ConstIterator;
246 /** Returns the begin iterator of the map.
249 return Iterator(*this, KeyIt(*MapBase::getGraph()));
252 /** Returns the end iterator of the map.
255 return Iterator(*this, INVALID);
258 /** Returns the begin ConstIterator of the map.
260 ConstIterator begin() const {
261 return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
264 /** Returns the end const_iterator of the map.
266 ConstIterator end() const {
267 return ConstIterator(*this, INVALID);
270 /// The KeySet of the Map.
271 typedef MapConstKeySet<ArrayMap> ConstKeySet;
273 /// KeySet getter function.
274 ConstKeySet keySet() const {
275 return ConstKeySet(*this);
278 /// The ConstValueSet of the Map.
279 typedef MapConstValueSet<ArrayMap> ConstValueSet;
281 /// ConstValueSet getter function.
282 ConstValueSet valueSet() const {
283 return ConstValueSet(*this);
286 /// The ValueSet of the Map.
287 typedef MapValueSet<ArrayMap> ValueSet;
289 /// ValueSet getter function.
290 ValueSet valueSet() {
291 return ValueSet(*this);
296 void allocate_memory() {
297 int max_id = KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph());
304 while (capacity <= max_id) {
307 values = allocator.allocate(capacity);
315 // STL compatibility typedefs.
316 typedef Iterator iterator;
317 typedef ConstIterator const_iterator;
318 typedef typename Iterator::PairValueType value_type;
319 typedef typename Iterator::KeyType key_type;
320 typedef typename Iterator::ValueType data_type;
321 typedef typename Iterator::PairReferenceType reference;
322 typedef typename Iterator::PairPointerType pointer;
323 typedef typename ConstIterator::PairReferenceType const_reference;
324 typedef typename ConstIterator::PairPointerType const_pointer;
325 typedef int difference_type;