Remove one remaining range checking.
7 #include <hugo/map_iterator.h>
11 ///\brief Graph maps that construates and destruates
12 ///their elements dynamically.
17 /// \addtogroup graphmaps
20 /** The ArrayMap template class is graph map structure what
21 * automatically updates the map when a key is added to or erased from
22 * the map. This map factory uses the allocators to implement
23 * the container functionality.
25 * The template parameter is the MapRegistry that the maps
26 * will belong to and the ValueType.
29 template <typename MapRegistry, typename Value>
30 class ArrayMap : public MapRegistry::MapBase {
34 /// The graph type of the maps.
35 typedef typename MapRegistry::Graph Graph;
36 /// The key type of the maps.
37 typedef typename MapRegistry::KeyType KeyType;
38 /// The iterator to iterate on the keys.
39 typedef typename MapRegistry::KeyIt KeyIt;
41 /// The MapBase of the Map which imlements the core regisitry function.
42 typedef typename MapRegistry::MapBase MapBase;
47 /// The value type of the map.
48 typedef Value ValueType;
49 /// The reference type of the map;
50 typedef Value& ReferenceType;
51 /// The pointer type of the map;
52 typedef Value* PointerType;
54 /// The const value type of the map.
55 typedef const Value ConstValueType;
56 /// The const reference type of the map;
57 typedef const Value& ConstReferenceType;
58 /// The pointer type of the map;
59 typedef const Value* ConstPointerType;
62 typedef std::allocator<Value> Allocator;
65 /** Default constructor for the map.
67 ArrayMap() : values(0), capacity(0) {}
69 /** Graph and Registry initialized map constructor.
71 ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
73 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
74 int id = MapBase::getGraph()->id(it);
75 allocator.construct(&(values[id]), Value());
79 /** Constructor to use default value to initialize the map.
81 ArrayMap(const Graph& g, MapRegistry& r, const Value& v)
84 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
85 int id = MapBase::getGraph()->id(it);
86 allocator.construct(&(values[id]), v);
90 /** Constructor to copy a map of the same map type.
92 ArrayMap(const ArrayMap& copy) : MapBase(*copy.graph, *copy.registry) {
93 capacity = copy.capacity;
94 if (capacity == 0) return;
95 values = allocator.allocate(capacity);
96 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
97 int id = MapBase::getGraph()->id(it);
98 allocator.construct(&(values[id]), copy.values[id]);
102 /** Constructor to copy a map of an other map type.
104 template <typename CMap> ArrayMap(const CMap& copy)
105 : MapBase(copy), capacity(0), values(0) {
106 if (MapBase::getGraph()) {
108 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
114 /** Assign operator to copy a map of the same map type.
116 ArrayMap& operator=(const ArrayMap& copy) {
117 if (© == this) return *this;
120 allocator.deallocate(values, capacity);
122 capacity = copy.capacity;
123 if (capacity == 0) return *this;
124 values = allocator.allocate(capacity);
125 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
126 int id = MapBase::getGraph()->id(it);
127 allocator.construct(&(values[id]), copy.values[id]);
132 /** Assign operator to copy a map an other map type.
134 template <typename CMap> ArrayMap& operator=(const CMap& copy) {
135 if (MapBase::getGraph()) {
138 MapBase::operator=(copy);
139 if (MapBase::getGraph()) {
141 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
148 /** The destructor of the map.
150 virtual ~ArrayMap() {
153 allocator.deallocate(values, capacity);
159 * The subscript operator. The map can be subscripted by the
160 * actual keys of the graph.
162 ReferenceType operator[](const KeyType& key) {
163 int id = MapBase::getGraph()->id(key);
168 * The const subscript operator. The map can be subscripted by the
169 * actual keys of the graph.
171 ConstReferenceType operator[](const KeyType& key) const {
172 int id = MapBase::getGraph()->id(key);
176 /** Setter function of the map. Equivalent with map[key] = val.
177 * This is a compatibility feature with the not dereferable maps.
179 void set(const KeyType& key, const ValueType& val) {
180 int id = MapBase::getGraph()->id(key);
184 /** Add a new key to the map. It called by the map registry.
186 void add(const KeyType& key) {
187 int id = MapBase::getGraph()->id(key);
188 if (id >= capacity) {
189 int new_capacity = (capacity == 0 ? 1 : capacity);
190 while (new_capacity <= id) {
193 Value* new_values = allocator.allocate(new_capacity);;
194 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
195 int jd = MapBase::getGraph()->id(it);
197 allocator.construct(&(new_values[jd]), values[jd]);
198 allocator.destroy(&(values[jd]));
201 if (capacity != 0) allocator.deallocate(values, capacity);
203 capacity = new_capacity;
205 allocator.construct(&(values[id]), Value());
208 /** Erase a key from the map. It called by the map registry.
210 void erase(const KeyType& key) {
211 int id = MapBase::getGraph()->id(key);
212 allocator.destroy(&(values[id]));
215 /** Clear the data structure.
220 allocator.deallocate(values, capacity);
225 /// The stl compatible pair iterator of the map.
226 typedef MapIterator<ArrayMap> Iterator;
227 /// The stl compatible const pair iterator of the map.
228 typedef MapConstIterator<ArrayMap> ConstIterator;
230 /** Returns the begin iterator of the map.
233 return Iterator(*this, KeyIt(*MapBase::getGraph()));
236 /** Returns the end iterator of the map.
239 return Iterator(*this, INVALID);
242 /** Returns the begin ConstIterator of the map.
244 ConstIterator begin() const {
245 return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
248 /** Returns the end const_iterator of the map.
250 ConstIterator end() const {
251 return ConstIterator(*this, INVALID);
254 /// The KeySet of the Map.
255 typedef MapConstKeySet<ArrayMap> ConstKeySet;
257 /// KeySet getter function.
258 ConstKeySet keySet() const {
259 return ConstKeySet(*this);
262 /// The ConstValueSet of the Map.
263 typedef MapConstValueSet<ArrayMap> ConstValueSet;
265 /// ConstValueSet getter function.
266 ConstValueSet valueSet() const {
267 return ConstValueSet(*this);
270 /// The ValueSet of the Map.
271 typedef MapValueSet<ArrayMap> ValueSet;
273 /// ValueSet getter function.
274 ValueSet valueSet() {
275 return ValueSet(*this);
280 void allocate_memory() {
282 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
283 int id = MapBase::getGraph()->id(it);
294 while (capacity <= max_id) {
297 values = allocator.allocate(capacity);