1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the class library */ 4 /* SoPlex --- the Sequential object-oriented simPlex. */ 5 /* */ 6 /* Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file classarray.h 26 * @brief Save arrays of data objects. 27 */ 28 #ifndef _CLASSARRAY_H_ 29 #define _CLASSARRAY_H_ 30 31 #include <assert.h> 32 #include <stddef.h> 33 #include <string.h> 34 #include <iostream> 35 36 #include "soplex/spxdefines.h" 37 #include "soplex/spxalloc.h" 38 39 namespace soplex 40 { 41 /**@brief Safe arrays of class objects. 42 * @ingroup Elementary 43 * 44 * Class ClassArray provides safe arrays of general C++ objects (in contrast to data objects). The elements of an 45 * instance of ClassArray can be accessed just like ordinary C++ array elements by means of the index 46 * operator[](). Safety is provided by 47 * 48 * - automatic memory management in constructor and destructor preventing memory leaks 49 * - checking of array bounds when accessing elements with the indexing operator[]() when compiled without \c -DNDEBUG 50 * 51 * Moreover, #ClassArray%s may easily be extended by #insert%ing or #append%ing elements to the ClassArray or shrunken 52 * by \ref remove() "removing" elements. Method reSize(int n) resets the ClassArray%s length to \p n thereby possibly 53 * appending elements or truncating the ClassArray to the required size. 54 * 55 * A ClassArray may be used as arguments for standard C functions requiring pointers through the use of get_ptr() and 56 * get_const_ptr(). 57 * 58 * Internally, a ClassArray object allocates a block of memory that fits up to max() elements, only size() of them are 59 * used. This makes extension and shrinking methods perform better. 60 * 61 * @see Array, \ref DataObjects "Data Objects" 62 */ 63 template < class T > 64 class ClassArray 65 { 66 protected: 67 int thesize; ///< number of used elements in array data 68 int themax; ///< the length of array data and 69 T* data; ///< the array of elements 70 71 protected: 72 /** When a ClassArray is reSize()%d to more than max() elements, the new value for max() is not just set to the new 73 * size but rather to \p memFactor * \p size. This makes #reSize%ing perform better in codes where a ClassArray is 74 * extended often by a small number of elements only. 75 */ 76 double memFactor; ///< memory extension factor. 77 78 public: 79 80 /// Reference to \p n 'th element. 81 T& operator[](int n) 82 { 83 assert(n >= 0); 84 assert(n < thesize); 85 return data[n]; 86 } 87 88 /// Reference to \p n 'th const element. 89 const T& operator[](int n) const 90 { 91 assert(n >= 0); 92 assert(n < thesize); 93 return data[n]; 94 } 95 96 /// Reference to last element. 97 T& last() 98 { 99 assert(thesize > 0); 100 return data[thesize - 1]; 101 } 102 103 /// Reference to last const element. 104 const T& last() const 105 { 106 assert(thesize > 0); 107 return data[thesize - 1]; 108 } 109 110 /// Gets a C pointer to the data. 111 T* get_ptr() 112 { 113 return data; 114 } 115 116 /// Gets a const C pointer to the data. 117 const T* get_const_ptr() const 118 { 119 return data; 120 } 121 122 /// Appends element \p t. 123 void append(const T& t) 124 { 125 insert(thesize, 1, &t); 126 } 127 128 /// Appends \p n elements from \p t. 129 void append(int n, const T t[]) 130 { 131 insert(thesize, n, t); 132 } 133 134 /// Appends all elements from \p t. 135 void append(const ClassArray<T>& t) 136 { 137 insert(thesize, t); 138 } 139 140 /// Inserts \p n uninitialized elements before \p i 'th element. 141 void insert(int i, int n) 142 { 143 assert(n >= 0); 144 assert(i >= 0); 145 assert(i <= thesize); 146 147 if(n > 0) 148 { 149 int j = thesize; 150 151 reSize(thesize + n); 152 assert(thesize == j + n); 153 154 /// move \p n elements in memory from insert position \p i to the back 155 while(j > i) 156 { 157 j--; 158 data[j + n] = data[j]; 159 } 160 } 161 } 162 163 /// Inserts \p n elements from \p t before \p i 'the element. 164 void insert(int i, int n, const T t[]) 165 { 166 if(n > 0) 167 { 168 insert(i, n); 169 170 for(int j = 0; j < n; j++) 171 data[i + j] = t[j]; 172 } 173 } 174 175 /// Inserts all elements from \p t before \p i 'th element. 176 void insert(int i, const ClassArray<T>& t) 177 { 178 if(t.size()) 179 { 180 insert(i, t.size()); 181 182 for(int j = 0; j < t.size(); j++) 183 data[i + j] = t[j]; 184 } 185 } 186 187 /// Removes \p m elements starting at \p n. 188 void remove(int n = 0, int m = 1) 189 { 190 assert(n >= 0); 191 assert(n < size()); 192 assert(m >= 0); 193 assert(n + m <= size()); 194 195 for(int j = n + m; j < size(); j++) 196 data[j - m] = data[j]; 197 198 thesize -= m; 199 } 200 201 /// Removes \p m last elements. 202 void removeLast(int m = 1) 203 { 204 assert(m >= 0); 205 assert(m <= size()); 206 207 thesize -= m; 208 } 209 210 /// Removes all elements. 211 void clear() 212 { 213 thesize = 0; 214 } 215 216 /// Returns number of elements. 217 int size() const 218 { 219 return thesize; 220 } 221 222 /// Resets size to \p newsize. 223 /** Resizing a ClassArray to less than the previous size, involves discarding its last elements. Resizing to a larger 224 * value involves adding uninitialized elements (similar to append()). If neccessary, also memory will be 225 * reallocated. 226 */ 227 void reSize(int newsize) 228 { 229 assert(memFactor >= 1); 230 231 if(newsize > themax) 232 reMax(int(memFactor * newsize), newsize); 233 else if(newsize < 0) 234 thesize = 0; 235 else 236 thesize = newsize; 237 } 238 239 /// Returns maximum number of elements. 240 /** Even though the ClassArray currently holds no more than size() elements, up to max() elements could be added 241 * without need to reallocated free store. 242 */ 243 int max() const 244 { 245 return themax; 246 } 247 248 /// Resets maximum number of elements. 249 /** The value of max() is reset to \p newMax thereby setting size() to \p newSize. However, if \p newSize has a value 250 * \c < \c 0 (as the default argument does) size() remains unchanged and max() is set to MIN(size(), newMax). Hence, 251 * calling reMax() without the default arguments, will reduce the memory consumption to a minimum. In no instance 252 * max() will be set to a value less than 1 (even if specified). 253 * 254 * @return reMax returns the difference in bytes of the new and the old memory block, which can be used to update 255 * pointers pointing to elements of the memory block. 256 */ 257 ptrdiff_t reMax(int newMax = 1, int newSize = -1) 258 { 259 /* process input */ 260 if(newSize < 0) 261 newSize = size(); 262 263 if(newMax < 1) 264 newMax = 1; 265 266 if(newMax < newSize) 267 newMax = newSize; 268 269 /* nothing to reallocate */ 270 if(newMax == themax) 271 { 272 thesize = newSize; 273 return 0; 274 } 275 276 /* allocate new memory */ 277 T* newMem = 0; 278 spx_alloc(newMem, newMax); 279 280 /* call copy constructor for first elements */ 281 int i; 282 283 for(i = 0; i < size() && i < newSize; i++) 284 new(&(newMem[i])) T(data[i]); 285 286 /* call default constructor for remaining elements */ 287 for(; i < newMax; i++) 288 new(&(newMem[i])) T(); 289 290 /* compute pointer difference */ 291 ptrdiff_t pshift = reinterpret_cast<char*>(newMem) - reinterpret_cast<char*>(data); 292 293 /* free old memory */ 294 for(i = themax - 1; i >= 0; i--) 295 data[i].~T(); 296 297 spx_free(data); 298 299 /* assign new memory */ 300 data = newMem; 301 themax = newMax; 302 thesize = newSize; 303 304 return pshift; 305 } 306 307 /// Assignment operator. 308 ClassArray& operator=(const ClassArray& rhs) 309 { 310 if(this != &rhs) 311 { 312 reSize(rhs.size()); 313 314 for(int i = 0; i < size(); i++) 315 data[i] = rhs.data[i]; 316 317 assert(isConsistent()); 318 } 319 320 return *this; 321 } 322 323 /// Consistency check. 324 bool isConsistent() const 325 { 326 #ifdef ENABLE_CONSISTENCY_CHECKS 327 328 if((data == 0) 329 || (themax < 1) 330 || (themax < thesize) 331 || (thesize < 0) 332 || (memFactor < 1.0)) 333 return SPX_MSG_INCONSISTENT("ClassArray"); 334 335 #endif 336 return true; 337 } 338 339 /// Copy constructor. 340 ClassArray(const ClassArray& old) 341 : thesize(old.thesize) 342 , themax(old.themax) 343 , data(0) 344 , memFactor(old.memFactor) 345 { 346 /* allocate memory */ 347 spx_alloc(data, max()); 348 349 /* call copy constructor for first elements */ 350 int i; 351 352 for(i = 0; i < size(); i++) 353 new(&(data[i])) T(old.data[i]); 354 355 /* call default constructor for remaining elements */ 356 for(; i < max(); i++) 357 new(&(data[i])) T(); 358 359 assert(isConsistent()); 360 } 361 362 /// Default constructor. 363 /** The constructor allocates a ClassArray containing \p size uninitialized elements. The internal array is allocated 364 * to have \p max nonzeros, and the memory extension factor is set to \p fac. 365 * 366 * @param p_size number of unitialised elements. 367 * @param p_max maximum number of elements the array can hold. 368 * @param p_fac value for memFactor. 369 */ 370 explicit ClassArray(int p_size = 0, int p_max = 0, double p_fac = 1.2) 371 : data(0) 372 , memFactor(p_fac) 373 { 374 thesize = (p_size < 0) ? 0 : p_size; 375 376 if(p_max > thesize) 377 themax = p_max; 378 else 379 themax = (thesize == 0) ? 1 : thesize; 380 381 spx_alloc(data, max()); 382 383 /* call default constructor for each element */ 384 for(int i = 0; i < max(); i++) 385 new(&(data[i])) T(); 386 387 assert(isConsistent()); 388 } 389 390 /// Destructor. 391 virtual ~ClassArray() 392 { 393 if(data) 394 { 395 for(int i = themax - 1; i >= 0; i--) 396 data[i].~T(); 397 398 spx_free(data); 399 } 400 } 401 }; 402 403 } // namespace soplex 404 #endif // _CLASSARRAY_H_ 405