Newer
Older
/******************************************************************************
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v2.0
* which accompanies this distribution, and is available at
* https://www.eclipse.org/org/documents/epl-2.0/EPL-2.0.html
*
* Contributors:
* Balasko, Jeno
* Delic, Adam
* Forstner, Matyas
* Gecse, Roland
* Koppany, Csaba
* Raduly, Csaba
* Szabados, Kristof
* Szabo, Janos Zoltan – initial implementation
*
******************************************************************************/
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#ifndef _Common_map_HH
#define _Common_map_HH
#include "error.h"
#include "../common/dbgnew.hh"
/**
* This container associates a \e key with its elements, and is
* optimized to access the elements referenced by their keys.
* The keys -- in contrast with the elements -- are owned by
* the container. The keys in this container are unique.
*
* Accessing an element by its key has logarithmic cost.
* Adding or removing an element has linear cost (proportional to the number
* of elements in the map).
* \pre
* \arg The type of the key (<em>T_key</em>) must be a type which has
* equality operator (==) and less-than operator (<). Other
* comparison operators are not assumed.
* \arg \a T_key must have copy constructor and destructor.
* \arg See also
* \ref container_concepts "General rules and concepts about containers".
*
* There is a possibility to iterate through all
* elements using integral indices. This index of an element can
* change when inserting/deleting other elements. Accessing elements
* by this integral index is not cost-optimal.
*
* \ingroup containers
*/
template<class T_key, class T>
class map {
private:
struct map_struct {
T_key key;
T *dat;
map_struct(const T_key& p_key, T *p_dat)
: key(p_key), dat(p_dat) { }
map_struct(const map_struct& other)
: key(other.key), dat(other.dat) {}
private:
map_struct& operator=(const map_struct& other);
};
size_t num_m; ///< Number of elements (size)
size_t max_m; ///< Available storage (capacity)
/// Cache for the last search result.
/// This will remember the index of the element last searched for;
/// thus after checking the existence of the item, reaching it
/// won't be logarithmical but constant
mutable size_t last_searched_key;
/// Array of pointers to map data. It is kept sorted (ascending) by keys.
map_struct **m_ptr;
static const size_t initial_size = 1, increment_factor = 2;
/** Copy constructor: DO NOT IMPLEMENT! */
map(const map&);
/** Copy assignment: DO NOT IMPLEMENT! */
map& operator=(const map&);
public:
static const size_t max_map_length = static_cast<size_t>( -1 );
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
/** Creates an empty map. */
map() : num_m(0), max_m(0), last_searched_key(0), m_ptr(NULL) { }
/** Deallocates its memory, including the keys.
* If the container is not empty, FATAL_ERROR occurs,
* so before destructing, clear() must be invoked explicitly.
*/
~map() {
if (num_m > 0) FATAL_ERROR("map:~map(): map is not empty");
Free(m_ptr);
}
/** Returns the number of elements in the container. */
size_t size() const { return num_m; }
/** Returns true if the container has no elements. */
bool empty() const { return num_m == 0; }
/** Erases the entire container. */
void clear() {
for (size_t r = 0; r < num_m; r++) delete m_ptr[r];
num_m = 0;
last_searched_key = 0;
}
/** Adds the elem \a T identified by \a key to the container.
* If an element with the given key already exists, FATAL_ERROR occurs. */
void add(const T_key& key, T *elem) {
size_t l = 0;
if (num_m > 0) {
size_t r = num_m - 1;
while (l < r) { // binary search
size_t m = l + (r - l) / 2;
if (m_ptr[m]->key < key) l = m + 1;
else r = m;
}
if (m_ptr[l]->key < key) l++;
else if (m_ptr[l]->key == key)
FATAL_ERROR("map::add(): key already exists");
if (num_m >= max_m) {
// Array is full
if (num_m > max_m) FATAL_ERROR("map::add(): num_m > max_m");
if (max_m <= max_map_length / increment_factor)
max_m *= increment_factor; // room for doubling
else if (max_m < max_map_length) max_m = max_map_length;
else FATAL_ERROR("map::add(): cannot enlarge map");
m_ptr = static_cast<map_struct**>
(Realloc(m_ptr, max_m * sizeof(*m_ptr)));
}
memmove(m_ptr + l + 1, m_ptr + l, (num_m - l) * sizeof(*m_ptr));
} else if (m_ptr == NULL) {
max_m = initial_size;
m_ptr = static_cast<map_struct**>(Malloc(initial_size * sizeof(*m_ptr)));
}
m_ptr[l] = new map_struct(key, elem);
num_m++;
last_searched_key = num_m;
}
/** Returns the index of k within *m_ptr[] or num_m if key was not found */
size_t find_key(const T_key& k) const {
if (last_searched_key < num_m && m_ptr[last_searched_key]->key == k)
return last_searched_key;
else if (num_m == 0) return 0;
size_t l = 0, r = num_m - 1;
while (l < r) {
size_t m = l + (r - l) / 2;
if (m_ptr[m]->key < k) l = m + 1;
else r = m;
}
if (m_ptr[l]->key == k) last_searched_key = l;
else last_searched_key = num_m;
return last_searched_key;
}
/** Erases the element identified by \a key. If no such element,
* then silently ignores the request. */
void erase(const T_key& key) {
size_t n = find_key(key);
if (n < num_m) {
delete m_ptr[n];
num_m--;
memmove(m_ptr + n, m_ptr + n + 1, (num_m - n) * sizeof(*m_ptr));
last_searched_key = num_m;
}
}
/** Returns true if an element with the given \a key
* already exists. */
bool has_key(const T_key& key) const {
return find_key(key) < num_m;
}
/** Returns the copy of the key contained in the map.
*
* The copy of the key may be longer-lived than the argument.
* They are otherwise identical (operator== would return true).
*
* @param \a key
* @return copy of \a key contained in the map
* @pre key must exist in the map
*/
const T_key& get_key(const T_key& key) const {
size_t n = find_key(key);
if (n >= num_m) FATAL_ERROR("map::get_key() const: key not found");
return m_ptr[n]->key;
}
/** Returns the element identified by \a key.
* If no such element, then a FATAL_ERROR occurs. */
T *operator[](const T_key& key) const {
size_t n = find_key(key);
if (n >= num_m) FATAL_ERROR("map::operator[]() const: key not found");
return m_ptr[n]->dat;
}
/** Returns the element identified by \a key.
* If no such element, then a FATAL_ERROR occurs.
* \note This member can not be used to add new elements to
* the collection.
*/
T*& operator[](const T_key& key) {
size_t n = find_key(key);
if (n >= num_m) FATAL_ERROR("map::operator[]() const: key not found");
return m_ptr[n]->dat;
}
/** Returns the <em>n</em>th element. This is used to iterate through
* the ordered list of elements. Elements are ordered by their keys.
* If \a n >= size(), then a FATAL_ERROR occurs.
* The key of the element is accessible via get_nth_key(). */
T *get_nth_elem(size_t n) const {
if (n >= num_m) FATAL_ERROR("map::get_nth_elem() const: index overflow");
/* do not break the previous line, suncc doesn't like it... */
return m_ptr[n]->dat;
}
/** Returns the <em>n</em>th element. This is used to iterate through
* the elements. If \a n >= size(), then a FATAL_ERROR occurs.
* The key of the element is accessible via get_nth_key(). */
T*& get_nth_elem(size_t n) {
if (n >= num_m) FATAL_ERROR("map::get_nth_elem(): index overflow");
return m_ptr[n]->dat;
}
/** Returns the key of the <em>n</em>th element.
* This is used to iterate through the keys of elements.
* If \a n >= size(), then a FATAL_ERROR occurs.
* \note There is only \c const version of this member. If you
* want to modify the key of an element, you have to erase it from
* the container, then add with the new key.
*/
const T_key& get_nth_key(size_t n) const {
if (n >= num_m) FATAL_ERROR("map::get_nth_key() const: index overflow");
return m_ptr[n]->key;
}
};
#endif // _Common_map_HH