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