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 | * Raduly, Csaba | |
14 | * Szabados, Kristof | |
15 | * Szabo, Janos Zoltan – initial implementation | |
16 | * | |
17 | ******************************************************************************/ | |
970ed795 EL |
18 | #ifndef _Common_vector_HH |
19 | #define _Common_vector_HH | |
20 | ||
21 | #ifdef __SUNPRO_CC | |
22 | /** | |
23 | * Inclusion of the STL vector header file prevents the Sun Forte 6.2 C++ | |
24 | * compiler from a mysterious internal error. | |
25 | */ | |
26 | #include <vector> | |
27 | #include <stdio.h> | |
28 | #endif | |
29 | ||
30 | #include "error.h" | |
31 | #include "../common/memory.h" | |
32 | #include <string.h> // for memmove | |
33 | ||
34 | /** | |
35 | * Container optimized to store elements sequentially, | |
36 | * and access them randomly, referenced by indices. | |
37 | * | |
38 | * Accessing an element has constant time cost. | |
39 | * Adding an element at the end has amortized constant time const. | |
40 | * Other operations (adding at the beginning, replacing/deleting elements) | |
41 | * have linear time cost. | |
42 | * | |
43 | * If there aren't elements in the buffer, then no space is allocated. | |
44 | * If there are, the size of the allocated buffer is the smallest power of 2 | |
45 | * that is not smaller than the number of elements (num_e). | |
46 | * | |
47 | * The container stores pointers to objects of type T; it doesn't own them. | |
48 | * It is the responsibility of the caller to create and destroy the objects | |
49 | * and supply the pointers to the container. | |
50 | * | |
51 | * \ingroup containers | |
52 | */ | |
53 | template<class T> | |
54 | class vector { | |
55 | ||
56 | private: | |
57 | ||
58 | size_t num_e; | |
59 | T **e_ptr; | |
60 | ||
61 | static const size_t initial_size = 1, increment_factor = 2; | |
62 | ||
63 | /** Copy constructor: DO NOT IMPLEMENT! */ | |
64 | vector(const vector&); | |
65 | /** Copy assignment: DO NOT IMPLEMENT! */ | |
66 | vector& operator=(const vector&); | |
67 | ||
68 | public: | |
69 | ||
70 | static const size_t max_vector_length = -1; | |
71 | ||
72 | /** Creates an empty vector. */ | |
73 | vector() : num_e(0), e_ptr(NULL) { } | |
74 | ||
75 | /** Deallocates its memory. If the container is not empty, | |
76 | * FATAL_ERROR occurs, so before destructing, clear() must be | |
77 | * invoked explicitly. | |
78 | */ | |
79 | ~vector() { | |
80 | if (num_e > 0) FATAL_ERROR("vector::~vector(): vector is not empty"); | |
81 | Free(e_ptr); | |
82 | } | |
83 | ||
84 | /** Returns the number of elements in the container. */ | |
85 | size_t size() const { return num_e; } | |
86 | ||
87 | /** Returns true if the container has no elements. */ | |
88 | bool empty() const { return num_e == 0; } | |
89 | ||
90 | /** Erases the entire container. */ | |
91 | void clear() { | |
92 | num_e = 0; | |
93 | Free(e_ptr); | |
94 | e_ptr = NULL; | |
95 | } | |
96 | ||
97 | /** Appends the \a elem to the end of vector. */ | |
98 | void add(T *elem) { | |
99 | if (e_ptr == NULL) { | |
100 | e_ptr = static_cast<T**>(Malloc(initial_size * sizeof(*e_ptr))); | |
101 | } else { | |
102 | size_t max_e = initial_size; | |
103 | while (max_e < num_e) max_e *= increment_factor; | |
104 | if (max_e <= num_e) { | |
105 | if (max_e >= max_vector_length / increment_factor) | |
106 | FATAL_ERROR("vector::add(): vector index overflow"); | |
107 | e_ptr = static_cast<T**> | |
108 | (Realloc(e_ptr, max_e * increment_factor * sizeof(*e_ptr))); | |
109 | } | |
110 | } | |
111 | e_ptr[num_e++] = elem; | |
112 | } | |
113 | ||
114 | /** Inserts the \a elem to the beginning of vector. */ | |
115 | void add_front(T *elem) { | |
116 | if (e_ptr == NULL) { | |
117 | e_ptr = static_cast<T**>(Malloc(initial_size * sizeof(*e_ptr))); | |
118 | } else { | |
119 | size_t max_e = initial_size; | |
120 | while (max_e < num_e) max_e *= increment_factor; | |
121 | if (max_e <= num_e) { | |
122 | if (max_e >= max_vector_length / increment_factor) | |
123 | FATAL_ERROR("vector::add_front(): vector index overflow"); | |
124 | e_ptr = static_cast<T**> | |
125 | (Realloc(e_ptr, max_e * increment_factor * sizeof(*e_ptr))); | |
126 | } | |
127 | } | |
128 | memmove(e_ptr + 1, e_ptr, num_e * sizeof(*e_ptr)); | |
129 | num_e++; | |
130 | e_ptr[0] = elem; | |
131 | } | |
132 | ||
133 | /** Returns the <em>n</em>th element. The index of the first element is | |
134 | * zero. If no such index, then FATAL_ERROR occurs. */ | |
135 | T* operator[](size_t n) const { | |
136 | if (n >= num_e) | |
137 | FATAL_ERROR("vector::operator[](size_t) const: index overflow"); | |
138 | return e_ptr[n]; | |
139 | } | |
140 | ||
141 | /** Returns the <em>n</em>th element. The index of the first element is | |
142 | * zero. If no such index, then FATAL_ERROR occurs. */ | |
143 | T*& operator[](size_t n) { | |
144 | if (n >= num_e) | |
145 | FATAL_ERROR("vector::operator[](size_t): index overflow"); | |
146 | return e_ptr[n]; | |
147 | } | |
148 | ||
149 | /** Replaces \a n elements beginning from position \a pos | |
150 | * with elements in \a v. If \a pos+n > size() then FATAL_ERROR occurs. | |
151 | * If \a v == NULL then deletes the elements. | |
152 | */ | |
153 | void replace(size_t pos, size_t n, const vector *v = NULL) { | |
154 | if (pos > num_e) FATAL_ERROR("vector::replace(): position points over " \ | |
155 | "the last element"); | |
156 | else if (n > num_e - pos) FATAL_ERROR("vector::replace(): not enough " \ | |
157 | "elements after the start position"); | |
158 | else if (v == this) FATAL_ERROR("vector::replace(): trying to replace " \ | |
159 | "the original vector"); | |
160 | size_t v_len = v != NULL ? v->num_e : 0; | |
161 | if (v_len > max_vector_length - num_e + n) | |
162 | FATAL_ERROR("vector::replace(): resulting vector size exceeds maximal " \ | |
163 | "length"); | |
164 | size_t new_len = num_e - n + v_len; | |
165 | if (new_len > num_e) { | |
166 | size_t max_e = initial_size; | |
167 | if (e_ptr == NULL) { | |
168 | while (max_e < new_len) max_e *= increment_factor; | |
169 | e_ptr = static_cast<T**>(Malloc(max_e * sizeof(*e_ptr))); | |
170 | } else { | |
171 | while (max_e < num_e) max_e *= increment_factor; | |
172 | if (new_len > max_e) { | |
173 | while (max_e < new_len) max_e *= increment_factor; | |
174 | e_ptr = static_cast<T**>(Realloc(e_ptr, max_e * sizeof(*e_ptr))); | |
175 | } | |
176 | } | |
177 | } | |
178 | if (pos + n < num_e && v_len != n) memmove(e_ptr + pos + v_len, | |
179 | e_ptr + pos + n, (num_e - pos - n) * sizeof(*e_ptr)); | |
180 | if (v_len > 0) memcpy(e_ptr + pos, v->e_ptr, v_len * sizeof(*e_ptr)); | |
181 | if (new_len < num_e) { | |
182 | if (new_len == 0) { | |
183 | Free(e_ptr); | |
184 | e_ptr = NULL; | |
185 | } else { | |
186 | size_t max_e = initial_size; | |
187 | while (max_e < num_e) max_e *= increment_factor; | |
188 | size_t max_e2 = initial_size; | |
189 | while (max_e2 < new_len) max_e2 *= increment_factor; | |
190 | if (max_e2 < max_e) | |
191 | e_ptr = static_cast<T**>(Realloc(e_ptr, max_e2 * sizeof(*e_ptr))); | |
192 | } | |
193 | } | |
194 | num_e = new_len; | |
195 | } | |
196 | ||
197 | /** | |
198 | * Copies a part of the vector to a new vector. The part is | |
199 | * specified by the starting position (<em>pos</em>) and the number | |
200 | * of elements (<em>n</em>) to copy. If <em>n</em> is greater than | |
201 | * the number of elements beginning from the given <em>pos</em>, | |
202 | * then the returned vector contains less elements. | |
203 | * | |
204 | * \note The pointers are copied, the objects they refer to will not | |
205 | * be duplicated. | |
206 | */ | |
207 | vector* subvector(size_t pos = 0, size_t n = max_vector_length) const | |
208 | { | |
209 | if (pos > num_e) FATAL_ERROR("vector::subvector(): position points " \ | |
210 | "over last vector element"); | |
211 | if (n > num_e - pos) n = num_e - pos; | |
212 | vector *tmp_vector = new vector; | |
213 | if (n > 0) { | |
214 | size_t max_e = initial_size; | |
215 | while (max_e < n) max_e *= increment_factor; | |
216 | tmp_vector->e_ptr = static_cast<T**>(Malloc(max_e * sizeof(*e_ptr))); | |
217 | memcpy(tmp_vector->e_ptr, e_ptr + pos, n * sizeof(*e_ptr)); | |
218 | tmp_vector->num_e = n; | |
219 | } | |
220 | return tmp_vector; | |
221 | } | |
222 | ||
223 | }; // class vector | |
224 | ||
225 | /** | |
226 | * Container to store simple types (can have constructor, but it should be fast) | |
227 | * that are simple and small, stores the objects and not the pointers (copy | |
228 | * constructor must be implemented). The capacity is increased to be always the | |
229 | * power of two, the container capacity is never decreased. An initial | |
230 | * capacity value can be supplied to the constructor, this can be used to avoid | |
231 | * any further memory allocations during the life of the container. | |
232 | */ | |
233 | template<class T> | |
234 | class dynamic_array { | |
235 | private: | |
236 | size_t count; | |
237 | size_t capacity; // 0,1,2,4,8,... | |
238 | T* data; | |
239 | ||
240 | void clean_up(); | |
241 | void copy_content(const dynamic_array& other); | |
242 | public: | |
243 | ||
244 | dynamic_array() : count(0), capacity(0), data(NULL) {} | |
245 | // to avoid reallocations and copying | |
246 | dynamic_array(size_t init_capacity) : count(0), capacity(init_capacity), data(NULL) | |
247 | { if (capacity>0) data = new T[capacity]; } | |
248 | dynamic_array(const dynamic_array& other) : count(0), capacity(0), data(NULL) { copy_content(other); } | |
249 | dynamic_array& operator=(const dynamic_array& other) { clean_up(); copy_content(other); return *this; } | |
250 | ~dynamic_array() { clean_up(); } | |
251 | ||
252 | bool operator==(const dynamic_array& other) const; | |
253 | bool operator!=(const dynamic_array& other) const { return (!(*this==other)); } | |
254 | ||
255 | /** Returns the number of elements in the container. */ | |
256 | size_t size() const { return count; } | |
257 | ||
258 | /** Erases the entire container. */ | |
259 | void clear() { clean_up(); } | |
260 | ||
261 | /** Appends the \a elem to the end of vector. */ | |
262 | void add(const T& elem); | |
263 | ||
264 | /** Removes an element that is at index \a idx */ | |
265 | void remove(size_t idx); | |
266 | ||
267 | /** Returns the <em>n</em>th element. The index of the first element is | |
268 | * zero. If no such index, then FATAL_ERROR occurs. */ | |
269 | const T& operator[](size_t n) const { | |
270 | if (n>=count) FATAL_ERROR("dynamic_array::operator[] const: index overflow"); | |
271 | return data[n]; | |
272 | } | |
273 | ||
274 | /** Returns the <em>n</em>th element. The index of the first element is | |
275 | * zero. If no such index, then FATAL_ERROR occurs. */ | |
276 | T& operator[](size_t n) { | |
277 | if (n>=count) FATAL_ERROR("dynamic_array::operator[]: index overflow"); | |
278 | return data[n]; | |
279 | } | |
280 | }; // class dynamic_array | |
281 | ||
282 | template<class T> | |
283 | void dynamic_array<T>::clean_up() | |
284 | { | |
285 | delete[] data; | |
286 | data = NULL; | |
287 | capacity = 0; | |
288 | count = 0; | |
289 | } | |
290 | ||
291 | template<class T> | |
292 | void dynamic_array<T>::copy_content(const dynamic_array<T>& other) | |
293 | { | |
294 | capacity = other.capacity; | |
295 | count = other.count; | |
296 | if (capacity>0) { | |
297 | data = new T[capacity]; | |
298 | for (size_t i=0; i<count; i++) data[i] = other.data[i]; | |
299 | } | |
300 | } | |
301 | ||
302 | template<class T> | |
303 | bool dynamic_array<T>::operator==(const dynamic_array<T>& other) const | |
304 | { | |
305 | if (count!=other.count) return false; | |
306 | for (size_t i=0; i<count; i++) if (!(data[i]==other.data[i])) return false; | |
307 | return true; | |
308 | } | |
309 | ||
310 | template<class T> | |
311 | void dynamic_array<T>::add(const T& elem) | |
312 | { | |
313 | if (data==NULL) { | |
314 | capacity = 1; | |
315 | count = 1; | |
316 | data = new T[1]; | |
317 | data[0] = elem; | |
318 | } else { | |
319 | if (count<capacity) { | |
320 | data[count] = elem; | |
321 | count++; | |
322 | } else { | |
323 | // no more room, need to allocate new memory | |
324 | if (capacity==0) FATAL_ERROR("dynamic_array::add()"); | |
325 | capacity *= 2; | |
326 | T* new_data = new T[capacity]; | |
327 | for (size_t i=0; i<count; i++) new_data[i] = data[i]; | |
328 | delete[] data; | |
329 | data = new_data; | |
330 | data[count] = elem; | |
331 | count++; | |
332 | } | |
333 | } | |
334 | } | |
335 | ||
336 | template<class T> | |
337 | void dynamic_array<T>::remove(size_t idx) | |
338 | { | |
339 | if (idx>=count) FATAL_ERROR("dynamic_array::remove(): index overflow"); | |
340 | for (size_t i=idx+1; i<count; i++) data[i-1] = data[i]; | |
341 | count--; | |
342 | } | |
343 | ||
344 | #endif // _Common_vector_HH |