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