Scippy

SoPlex

Sequential object-oriented simPlex

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