1 /* 2 * 3 * Copyright (C) 2010-2018, OFFIS e.V. 4 * All rights reserved. See COPYRIGHT file for details. 5 * 6 * This software and supporting documentation were developed by 7 * 8 * OFFIS e.V. 9 * R&D Division Health 10 * Escherweg 2 11 * D-26121 Oldenburg, Germany 12 * 13 * 14 * Module: ofstd 15 * 16 * Author: Uli Schlachter 17 * 18 * Purpose: Defines a template vector class based on the STL vector class 19 * 20 */ 21 22 #ifndef OFVECTOR_H 23 #define OFVECTOR_H 24 25 #include "dcmtk/config/osconfig.h" /* make sure OS specific configuration is included first */ 26 27 #ifndef HAVE_CLASS_TEMPLATE 28 #error Your C++ compiler cannot handle class templates: 29 #endif 30 31 #ifdef HAVE_STL_VECTOR 32 33 // Use the standard template library (STL) vector class. 34 #include <vector> 35 36 #ifdef HAVE_STD_NAMESPACE 37 #define OFVector std::vector 38 #else 39 #define OFVector vector 40 #endif 41 42 #else 43 44 #define INCLUDE_CASSERT /* for assert() */ 45 #define INCLUDE_CSTDLIB /* for NULL */ 46 #include "dcmtk/ofstd/ofstdinc.h" 47 #include "dcmtk/ofstd/oftypes.h" /* for OFBool */ 48 49 /** this is a resizable array. You can add and remove elements after it was 50 * created and this class will handle all the memory management needed. This 51 * implements parts of std::vector's features. 52 */ 53 template<typename T> 54 class OFVector 55 { 56 public: 57 /** the type of elements that this OFVector stores */ 58 typedef T value_type; 59 /** the type used for sizes and indexes */ 60 typedef size_t size_type; 61 /** the type of mutable iterators on this object */ 62 typedef T* iterator; 63 /** the type of constant iterators on this object */ 64 typedef const T* const_iterator; 65 /** the type of mutable references on this object */ 66 typedef T& reference; 67 /** the type of constant references on this object */ 68 typedef const T& const_reference; 69 70 protected: 71 72 /** array that is used for storing the entries in this OFVector */ 73 T* values_; 74 75 /** the size for which values_ was allocated */ 76 size_type allocated_; 77 78 /** the number of valid entries in values_. elements past this 79 * index have undefined content. 80 */ 81 size_type size_; 82 83 public: 84 85 /** default constructor. This creates an empty OFVector. */ OFVector()86 OFVector() : values_(NULL), allocated_(0), size_(0) 87 { 88 89 } 90 91 /** copy constructor. 92 * @param other OFVector from which all elements are copied 93 */ OFVector(const OFVector & other)94 OFVector(const OFVector& other) : values_(NULL), allocated_(0), size_(0) 95 { 96 reserve(other.size()); 97 for (const_iterator it = other.begin(); it != other.end(); ++it) 98 push_back(*it); 99 } 100 101 /** construct an OFVector with predefined content. 102 * @param n number of elements that this OFVector should have. 103 * @param v The value used for all elements. 104 */ values_(NULL)105 explicit OFVector(size_type n, const T& v = T()) : values_(NULL), allocated_(0), size_(0) 106 { 107 if (n > 0) 108 resize(n, v); 109 else 110 // Make sure that values_ never is a NULL pointer 111 reserve(0); 112 } 113 114 /** construct an OFVector from a range of iterators. 115 * @param from first iterator to include 116 * @param to first iterator that should not be included anymore 117 */ OFVector(const_iterator from,const_iterator to)118 OFVector(const_iterator from, const_iterator to) : values_(NULL), allocated_(0), size_(0) 119 { 120 reserve(to - from); 121 while (from != to) 122 push_back(*(from++)); 123 } 124 125 /** destructor. Frees all memory used by this object. 126 */ ~OFVector()127 ~OFVector() 128 { 129 delete[] values_; 130 } 131 132 /** assignment operator. All elements from this object are removed and then 133 * a copy of other is made. All iterators to this object will become 134 * invalid. 135 * @param other OFVector instance to copy elements from. 136 */ 137 OFVector& operator=(const OFVector& other) 138 { 139 if (this == &other) 140 return *this; 141 142 clear(); 143 reserve(other.size()); 144 for (const_iterator it = other.begin(); it != other.end(); ++it) 145 push_back(*it); 146 return *this; 147 } 148 149 /** swap this vector's content with some other vector. 150 * All iterators will stay valid. 151 * @param other object to swap with 152 */ swap(OFVector & other)153 void swap(OFVector& other) 154 { 155 T* tmp_val = values_; 156 size_type tmp_all = allocated_; 157 size_type tmp_size = size_; 158 159 values_ = other.values_; 160 allocated_ = other.allocated_; 161 size_ = other.size_; 162 163 other.values_ = tmp_val; 164 other.allocated_ = tmp_all; 165 other.size_ = tmp_size; 166 } 167 168 /** get an iterator for the first element in this object. 169 * @return iterator that points to the first element. 170 */ begin()171 iterator begin() { return &values_[0]; } 172 173 /** get an iterator for the first element in this object. 174 * @return iterator that points to the first element. 175 */ begin()176 const_iterator begin() const { return &values_[0]; } 177 178 /** get an iterator that points past the last valid object. 179 * @return iterator that points to the end of this OFVector. 180 */ end()181 iterator end() { return &values_[size_]; } 182 183 /** get an iterator that points past the last valid object. 184 * @return iterator that points to the end of this OFVector. 185 */ end()186 const_iterator end() const { return &values_[size_]; } 187 188 /** get the size of this OFVector. 189 * @return number of elements in this instance. 190 */ size()191 size_type size() const { return size_; } 192 193 /** check whether this OFVector is empty. 194 * @return true if this OFVector is empty. 195 */ empty()196 OFBool empty() const { return size_ == 0; } 197 198 /** clear this OFVector. The existing content will be freed and all 199 * iterators become invalid. 200 */ clear()201 void clear() 202 { 203 delete[] values_; 204 values_ = NULL; 205 size_ = 0; 206 allocated_ = 0; 207 // We must never have values_ == NULL 208 reserve(0); 209 } 210 211 /** removes an entry from this OFVector. 212 * All iterators pointing to the element removed or elements that come 213 * behind it in this OFVector will become invalid. 214 * @param it iterator for the entry that should be removed. 215 */ erase(iterator it)216 void erase(iterator it) 217 { 218 size_type idx = it - begin(); 219 for (size_type i = idx + 1; i < size_; i++) { 220 values_[i - 1] = values_[i]; 221 } 222 size_--; 223 } 224 225 /** insert an entry in this OFVector. 226 * All iterators for this OFVector become invalid. 227 * @param it the new element will be inserted in front of the element to 228 * which this iterator points. 229 * @param v the element to insert 230 * @return iterator for the newly inserted element. 231 */ insert(iterator it,const T & v)232 iterator insert(iterator it, const T& v) 233 { 234 size_type idx = it - begin(); 235 236 if (size_ == allocated_) { 237 reserve(size_ * 2); 238 } 239 240 if (idx < size_) 241 for (size_type i = size_; i > idx; i--) { 242 values_[i] = values_[i - 1]; 243 } 244 values_[idx] = v; 245 size_++; 246 return &values_[idx]; 247 } 248 249 /** insert a range of elements in this OFVector. 250 * All iterators for this OFVector become invalid. 251 * @param it the new elements will be inserted in front of the element to 252 * which this iterator points. 253 * @param from iterator to the beginning of the range to insert. 254 * @param to iterator past the end of the range to insert. 255 */ 256 template<class InputIterator> insert(iterator it,InputIterator from,InputIterator to)257 void insert(iterator it, InputIterator from, InputIterator to) 258 { 259 while (from != to) 260 { 261 it = insert(it, *from); 262 it++; 263 from++; 264 } 265 } 266 267 /** get a reference to the first element of this vector. 268 * @return reference to the first element. 269 */ front()270 T& front() 271 { 272 return values_[0]; 273 } 274 275 /** get a reference to the first element of this vector. 276 * @return reference to the first element. 277 */ front()278 const T& front() const 279 { 280 return values_[0]; 281 } 282 283 /** get a reference to the last element of this vector. 284 * @return reference to the last element. 285 */ back()286 T& back() 287 { 288 return values_[size_ - 1]; 289 } 290 291 /** get a reference to the last element of this vector. 292 * @return reference to the last element. 293 */ back()294 const T& back() const 295 { 296 return values_[size_ - 1]; 297 } 298 299 /** insert an entry at the end of this object 300 * @param v the value to insert 301 */ push_back(const T & v)302 void push_back(const T& v) 303 { 304 insert(end(), v); 305 } 306 307 /** remove the last entry in this object 308 */ pop_back()309 void pop_back() 310 { 311 erase(end() - 1); 312 } 313 314 /** access an entry by index. undefined behavior occurs when the index is 315 * out of bounds (bigger than the maximum allowed index). 316 * @param i index of the element to return 317 * @return reference to the element. 318 */ 319 T& operator[](size_type i) 320 { 321 return values_[i]; 322 } 323 324 /** access an entry by index. undefined behavior occurs when the index is 325 * out of bounds (bigger than the maximum allowed index). 326 * @param i index of the element to return 327 * @return reference to the element. 328 */ 329 const T& operator[](size_type i) const 330 { 331 return values_[i]; 332 } 333 334 /** access an entry by index. 335 * @param i index of the element to return 336 * @return reference to the element. 337 */ at(size_type i)338 T& at(size_type i) 339 { 340 assert(i < size_); 341 return (*this)[i]; 342 } 343 344 /** access an entry by index. 345 * @param i index of the element to return 346 * @return reference to the element. 347 */ at(size_type i)348 const T& at(size_type i) const 349 { 350 assert(i < size_); 351 return (*this)[i]; 352 } 353 354 /** resize this OFVector. after this call, size() will be n. 355 * @param n the new size that this object should use 356 * @param v if any new elements need to be inserted, they get this value. 357 */ 358 void resize(size_type n, T v = T()) 359 { 360 if (n > size_) 361 { 362 reserve(n); 363 // Set up the new elements 364 for (size_t i = size_; i < n; i++) 365 values_[i] = v; 366 } 367 size_ = n; 368 } 369 370 /** reserves enough space for the given number of elements. from now on, no 371 * memory allocations will occur as long as this OFVector's size stays 372 * below n and clear() is not called. 373 * @param n the number of elements for which space should be reserved. 374 */ reserve(size_type n)375 void reserve(size_type n) 376 { 377 T* old_values = values_; 378 T* new_values; 379 380 if (n == 0) 381 n = 1; 382 if (n <= allocated_) 383 return; 384 385 // While we are at it, let's reserve some extra space 386 n += 10; 387 388 new_values = new T[n]; 389 if (old_values) 390 { 391 for (size_type i = 0; i < size_; i++) 392 new_values[i] = old_values[i]; 393 delete[] old_values; 394 } 395 396 values_ = new_values; 397 allocated_ = n; 398 } 399 }; 400 401 #endif 402 403 #endif 404