Scippy

SoPlex

Sequential object-oriented simPlex

array.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-2015 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 array.h
17  * @brief Save arrays of arbitrary types.
18  */
19 #ifndef _ARRAY_H_
20 #define _ARRAY_H_
21 
22 #include <assert.h>
23 #include <string.h>
24 #include "spxalloc.h"
25 
26 namespace soplex
27 {
28 /**@brief Safe arrays of arbitrary types.
29  @ingroup Elementary
30 
31  Class Array provides safe arrays of arbitrary type. Array elements are
32  accessed just like ordinary C++ array elements by means of the index
33  operator[](). Safety is provided by
34 
35  - automatic memory management in constructor and destructure
36  preventing memory leaks
37  - checking of array bound when accessing elements with the
38  indexing operator[]() (only when compiled without \c -DNDEBUG).
39 
40  Moreover, #Array%s may easily be extended by #insert%ing or
41  #append%ing elements to the Array or shrunken by
42  \ref remove() "removing"
43  elements. Method reSize(int n) resets the Array's length to \p n,
44  thereby appending elements or truncating the Array to the
45  required size.
46 
47  An Array is implemented in a C++-compliant way with respect to
48  how memory is managed: Only operators new and delete are
49  used for allocating memory. This involves some overhead for all
50  methods effecting the length of an Array, i.e., all methods
51  insert(), append(), remove() and reSize(). This involves
52  allocating a new C++ array of the new size and copying all
53  elements with the template parameters operator=().
54 
55  For this reason, it is not convenient to use class Array if its elements
56  are \ref DataObjects "Data Objects". In this case use class DataArray
57  instead.
58 
59  @see DataArray, \ref DataObjects "Data Objects"
60 */
61 template < class T >
62 class Array
63 {
64 protected:
65 
66  //----------------------------------------
67  /**@name Data */
68  //@{
69  int num; ///< the length of array data
70  T* data; ///< the array of elements
71  //@}
72 
73 public:
74 
75  //----------------------------------------
76  /**@name Access / modification */
77  //@{
78  /// reference \p n 'th element.
79  T& operator[](int n)
80  {
81  assert(n >= 0 && n < num);
82  return data[n];
83  }
84  /// reference \p n 'th element.
85  const T& operator[](int n) const
86  {
87  assert(n >= 0 && n < num);
88  return data[n];
89  }
90 
91  /** This function serves for using a Vector in an C-style
92  * function. It returns a pointer to the first value of the array.
93  */
94  T* get_ptr()
95  {
96  return data;
97  }
98 
99  /// append \p n uninitialized elements.
100  void append(int n)
101  {
102  insert(num, n);
103  }
104  /// append \p n elements from \p p_array.
105  void append(int n, const T* p_array)
106  {
107  insert(num, n, p_array);
108  }
109  /// append all elements from \p p_array.
110  void append(const Array<T>& p_array)
111  {
112  insert(num, p_array);
113  }
114 
115  /** insert \p n uninitialized elements before \p i 'th element.
116  *
117  * You must not! use realloc, memcpy or memmove, because some data element points inside itself, and therefore you
118  * always need to copy all elements by hand.
119  */
120  void insert(int i, int n)
121  {
122  assert(i <= num);
123  assert(num >= 0);
124  if (n > 0)
125  {
126  T* newdata = 0;
127  int k;
128 
129  spx_alloc(newdata, num + n);
130  assert(newdata != 0);
131 
132  // copy front segment to new array
133  for( k = 0; k < i; ++k )
134  {
135  new (&(newdata[k])) T();
136  newdata[k] = data[k];
137  data[k].~T();
138  }
139 
140  // call constructor for new elements
141  for( ; k < i+n; ++k )
142  new (&(newdata[k])) T();
143 
144  // copy rear segment to new array
145  for( k = i; k < num; ++k )
146  {
147  new (&(newdata[n + k])) T();
148  newdata[n + k] = data[k];
149  data[k].~T();
150  }
151 
152  if( data )
153  spx_free(data);
154  data = newdata;
155  num += n;
156  }
157  }
158 
159  /// insert \p n elements from \p p_array before \p i 'th element.
160  void insert(int i, int n, const T* p_array)
161  {
162  insert(i, n);
163  for (n--; n >= 0; --n)
164  data[n + i] = p_array[n];
165  }
166 
167  /// insert all elements from \p p_array before \p i 'th element.
168  void insert(int i, const Array<T>& p_array)
169  {
170  int n = p_array.size();
171  insert(i, n);
172  for (n--; n >= 0; --n)
173  data[n + i] = p_array.data[n];
174  }
175 
176  /** remove \p m elements starting at \p n.
177  *
178  * You must not! use realloc, memcpy or memmove, because some data element points inside itself, and therefore you
179  * always need to copy all elements by hand.
180  */
181  void remove(int n = 0, int m = 1)
182  {
183  assert(n >= 0 && m >= 0);
184  if (m > 0 && n < num)
185  {
186  T* newdata = 0;
187  int k;
188 
189  assert(num == size());
190  m -= (n + m <= num) ? 0 : n + m - num;
191 
192  if( num > m )
193  {
194  spx_alloc(newdata, num - m);
195  assert(newdata != 0);
196 
197  // copy rear segment to new array
198  for( k = num - 1; k >= n + m; --k )
199  {
200  new (&(newdata[k - m])) T();
201  newdata[k - m] = data[k];
202  data[k].~T();
203  }
204 
205  // call destructor for old elements
206  for( ; k >= n; --k )
207  data[k].~T();
208 
209  // copy front segment to new array
210  for( ; k >= 0; --k )
211  {
212  new (&(newdata[k])) T();
213  newdata[k] = data[k];
214  data[k].~T();
215  }
216  }
217  else
218  {
219  assert(num == m);
220  assert(n == 0);
221 
222  // call destructor for old elements
223  for( k = m - 1; k >= 0; --k )
224  data[k].~T();
225  }
226 
227  assert(data != 0);
228  spx_free(data);
229  data = newdata;
230 
231  num -= m;
232  assert((data == 0) == (num == 0));
233  }
234  }
235 
236  /// remove all elements.
237  void clear()
238  {
239  // call destructors of all elements
240  while( num > 0 )
241  {
242  --num;
243  data[num].~T();
244  }
245  if( data )
246  spx_free(data);
247  assert(num == 0);
248  }
249 
250  /// return the number of elements.
251  int size() const
252  {
253  return num;
254  }
255 
256  /// reset the number of elements.
257  void reSize(int newsize)
258  {
259  if (newsize < num)
260  remove(newsize, num - newsize);
261  else if (newsize > num)
262  append(newsize - num);
263  }
264  //@}
265 
266  //----------------------------------------
267  /**@name Construction / destruction */
268  //@{
269  /// assignment operator.
270  /** Assigning an rvalue Array to an lvalue Array involves resizing
271  * the lvalue to the rvalues size() and copying all elements via
272  * the Array element's assignment operator=().
273  */
275  {
276  if (this != &rhs)
277  {
278  reSize(rhs.size());
279  for (int i = 0; i < num; ++i)
280  data[i] = rhs.data[i];
281  assert(Array::isConsistent());
282  }
283  return *this;
284  }
285 
286  /// default constructor.
287  /** The constructor allocates an Array of \p n uninitialized elements.
288  */
289  explicit
290  Array(int n = 0)
291  : data(0)
292  {
293  assert(n >= 0);
294  num = n;
295  if (num > 0)
296  {
297  int k;
298 
299  spx_alloc(data, num);
300  assert(data != 0);
301 
302  for( k = 0; k < num; ++k )
303  new (&(data[k])) T();
304  }
305  assert(Array::isConsistent());
306  }
307 
308  /// copy constructor
309  Array(const Array<T>& old)
310  : num(old.num)
311  {
312  if (num > 0)
313  {
314  int k;
315 
316  data = 0;
317  spx_alloc(data, num);
318  assert(data != 0);
319 
320  for( k = 0; k < num; ++k )
321  {
322  new (&(data[k])) T();
323  data[k] = old.data[k];
324  }
325  }
326  else
327  data = 0;
328  assert(Array::isConsistent());
329  }
330 
331  /// destructor
333  {
334  while( num > 0 )
335  {
336  --num;
337  data[num].~T();
338  }
339  if( data )
340  spx_free(data);
341  }
342 
343  /// consistency check
344  bool isConsistent() const
345  {
346 #ifdef ENABLE_CONSISTENCY_CHECKS
347  if (num < 0 || (num > 0 && data == 0))
348  return MSGinconsistent("Array");
349 #endif
350 
351  return true;
352  }
353  //@}
354 };
355 } // namespace soplex
356 #endif // _ARRAY_H_