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