1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (C) 1996-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SoPlex is distributed under the terms of the ZIB Academic Licence. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SoPlex; see the file COPYING. If not email to soplex@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file dataarray.h
17 * @brief Save arrays of data objects.
18 */
19 #ifndef _DATAARRAY_H_
20 #define _DATAARRAY_H_
21
22 #include <assert.h>
23 #include <stddef.h>
24 #include <string.h>
25 #include <iostream>
26 #include <type_traits>
27
28 #include "soplex/spxdefines.h"
29 #include "soplex/spxalloc.h"
30 #include "soplex/spxid.h"
31
32 namespace soplex
33 {
34 /**@brief Safe arrays of data objects.
35 @ingroup Elementary
36
37 Class DataArray provides safe arrays of \ref DataObjects. For general
38 C++ objects (in contrast to data objects) class Array is provided which
39 manages memory in a C++ compliant way.
40
41 The elements of an instance of DataArray can be accessed just like
42 ordinary C++ array elements by means of the index operator[](). Safety is
43 provided by
44
45 - automatic memory management in constructor and destructor
46 preventing memory leaks
47 - checking of array bounds when accessing elements with the
48 indexing operator[]() (only when compiled without \c -DNDEBUG).
49
50 Moreover, #DataArray%s may easily be extended by #insert%ing or #append%ing
51 elements to the DataArray or shrunken by \ref remove() "removing" elements.
52 Method reSize(int n) resets the DataArray%s length to \p n thereby possibly
53 appending elements or truncating the DataArray to the required size.
54
55 A DataArray may be used as arguments for standard C functions requiring
56 pointers through the use of get_ptr() and get_const_ptr().
57
58 Internally, a DataArray object allocates a block of memory that fits up
59 to max() elements, only size() of them are used. This makes extension
60 and shrinking methods perform better.
61
62 @see Array, \ref DataObjects "Data Objects"
63 */
64 template < class T >
65 class DataArray
66 {
67 static_assert(std::is_trivially_copyable<T>::value,
68 "Only trivially copyable types are allowed with DataArray, since it does memcopy");
69 private:
70 int thesize; ///< number of used elements in array data
71 int themax; ///< the length of array data and
72 T* data; ///< the array of elements
73
74 protected:
75 /** When a DataArray is reSize()%d to more than max() elements, the
76 new value for max() is not just set to the new size but rather to
77 \p memFactor * \p size. This makes #reSize%ing perform better in codes
78 where a DataArray is extended often by a small number of elements
79 only.
80 */
81 Real memFactor; ///< memory extension factor.
82
83 public:
84
85 /// reference \p n 'th element.
86 T& operator[](int n)
87 {
88 assert(n >= 0);
89 assert(n < thesize);
90 return data[n];
91 }
92 /// reference \p n 'th const element.
93 const T& operator[](int n) const
94 {
95 assert(n >= 0);
96 assert(n < thesize);
97 return data[n];
98 }
99
100 /// reference last element.
101 T& last()
102 {
103 assert(thesize > 0);
104 return data[thesize - 1];
105 }
106 /// reference last const element.
107 const T& last() const
108 {
109 assert(thesize > 0);
110 return data[thesize - 1];
111 }
112
113 /// get a C pointer to the data.
114 T* get_ptr()
115 {
116 return data;
117 }
118 /// get a const C pointer to the data.
119 const T* get_const_ptr() const
120 {
121 return data;
122 }
123
124 /// append element \p t.
125 void append(const T& t)
126 {
127 insert(thesize, 1, &t);
128 }
129 /// append \p n elements with value \p t.
130 void append(int n, const T& t)
131 {
132 insert(thesize, n, t);
133 }
134 /// append \p n elements from \p t.
135 void append(int n, const T t[])
136 {
137 insert(thesize, n, t);
138 }
139 /// append all elements from \p t.
140 void append(const DataArray<T>& t)
141 {
142 insert(thesize, t);
143 }
144
145 /// insert \p n uninitialized elements before \p i 'th element.
146 void insert(int i, int n)
147 {
148 int j = thesize;
149
150 assert(i >= 0);
151 assert(n >= 0);
152
153 reSize(thesize + n);
154
155 /// move \p n elements in memory from insert position \p i to the back
156 if(j > i)
157 memmove(&(data[i + n]), &(data[i]), (unsigned int)(j - i) * sizeof(T));
158 }
159
160 /// insert \p n elements with value \p t before \p i 'the element.
161 void insert(int i, int n, const T& t)
162 {
163 if(n > 0)
164 {
165 insert(i, n);
166
167 for(int j = 0; j < n; j++)
168 data[i + j] = t;
169 }
170 }
171
172 /// insert \p n elements from \p t before \p i 'the element.
173 void insert(int i, int n, const T t[])
174 {
175 if(n > 0)
176 {
177 insert(i, n);
178 memcpy(&(data[i]), t, (unsigned int) n * sizeof(T));
179 }
180 }
181
182 /// insert all elements from \p t before \p i 'th element.
183 void insert(int i, const DataArray<T>& t)
184 {
185 if(t.size())
186 {
187 insert(i, t.size());
188 memcpy(&(data[i]), t.data, (unsigned int)t.size() * sizeof(T));
189 }
190 }
191
192 /// remove \p m elements starting at \p n.
193 void remove(int n = 0, int m = 1)
194 {
195 assert(n < size() && n >= 0);
196
197 /* use memmove instead of memcopy because the destination and the source might overlap */
198 if(n + m < size())
199 memmove(&(data[n]), &(data[n + m]), (unsigned int)(size() - (n + m)) * sizeof(T));
200 else
201 m = size() - n;
202
203 thesize -= m;
204 }
205 /// remove \p m last elements.
206 void removeLast(int m = 1)
207 {
208 assert(m <= size() && m >= 0);
209 thesize -= m;
210 }
211 /// remove all elements.
212 void clear()
213 {
214 thesize = 0;
215 }
216
217 /// return nr. of elements.
218 int size() const
219 {
220 return thesize;
221 }
222
223 /// reset size to \p newsize.
224 /** Resizing a DataArray to less than the previous size, involves
225 discarding its last elements. Resizing to a larger value involves
226 adding uninitialized elements (similar to append()). If neccessary,
227 also memory will be reallocated.
228 @param newsize the new number of elements the array can hold.
229 */
230 void reSize(int newsize)
231 {
232 assert(memFactor >= 1);
233
234 if(newsize > themax)
235 reMax(int(memFactor * newsize), newsize);
236 else if(newsize < 0)
237 thesize = 0;
238 else
239 thesize = newsize;
240 }
241
242 /// return maximum number of elements.
243 /** Even though the DataArray currently holds no more than size()
244 elements, up to max() elements could be added without need to
245 reallocated free store.
246 */
247 int max() const
248 {
249 return themax;
250 }
251
252 /// reset maximum number of elements.
253 /** The value of max() is reset to \p newMax thereby setting size()
254 to \p newSize. However, if \p newSize has a value \c < \c 0 (as the
255 default argument does) size() remains unchanged and max() is set
256 to MIN(size(), newMax). Hence, calling reMax() without the
257 default arguments, will reduce the memory consumption to a minimum.
258 In no instance max() will be set to a value less than 1 (even if
259 specified).
260
261 */
262 void reMax(int newMax = 1, int newSize = -1)
263 {
264 if(newSize >= 0)
265 thesize = newSize;
266
267 if(newMax < newSize)
268 newMax = newSize;
269
270 if(newMax < 1)
271 newMax = 1;
272
273 if(newMax == themax)
274 return;
275
276 themax = newMax;
277
278 if(thesize <= 0)
279 {
280 /* no data needs to be copied so do a clean free and alloc */
281 spx_free(data);
282 spx_alloc(data, themax);
283 }
284 else
285 spx_realloc(data, themax);
286 }
287 /// assignment operator
288 DataArray& operator=(const DataArray& rhs)
289 {
290 if(this != &rhs)
291 {
292 reSize(rhs.size());
293 memcpy(data, rhs.data, (unsigned int) size() * sizeof(T));
294
295 assert(isConsistent());
296 }
297
298 return *this;
299 }
300
301 /// consistency check
302 bool isConsistent() const
303 {
304 #ifdef ENABLE_CONSISTENCY_CHECKS
305
306 if((data == 0)
307 || (themax < 1)
308 || (themax < thesize)
309 || (thesize < 0)
310 || (memFactor < 1.0))
311 return MSGinconsistent("DataArray");
312
313 #endif
314
315 return true;
316 }
317
318 /// copy constructor
319 DataArray(const DataArray& old)
320 : thesize(old.thesize)
321 , themax(old.themax)
322 , data(0)
323 , memFactor(old.memFactor)
324 {
325 spx_alloc(data, max());
326
327 assert(thesize >= 0);
328
329 if(thesize)
330 memcpy(data, old.data, (unsigned int)thesize * sizeof(T));
331
332 assert(isConsistent());
333 }
334
335 /// default constructor.
336 /** The constructor allocates an Array containing \p size uninitialized
337 elements. The internal array is allocated to have \p max nonzeros,
338 and the memory extension factor is set to \p fac.
339
340 @param p_size number of unitialised elements.
341 @param p_max maximum number of elements the array can hold.
342 @param p_fac value for memFactor.
343 */
344 explicit DataArray(int p_size = 0, int p_max = 0, Real p_fac = 1.2)
345 : data(0)
346 , memFactor(p_fac)
347 {
348 thesize = (p_size < 0) ? 0 : p_size;
349
350 if(p_max > thesize)
351 themax = p_max;
352 else
353 themax = (thesize == 0) ? 1 : thesize;
354
355 spx_alloc(data, themax);
356
357 assert(isConsistent());
358 }
359
360 /// destructor
361 ~DataArray()
362 {
363 if(data)
364 spx_free(data);
365 }
366 };
367
368 } // namespace soplex
369 #endif // _DATAARRAY_H_
370