| 1 | /////////////////////////////////////////////////////////////////////////////// |
| 2 | // Copyright (c) 2000-2014 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 | #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 |