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