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  svsetbase.h
26   	 * @brief Set of sparse vectors.
27   	 */
28   	
29   	#ifndef _SVSETBASE_H_
30   	#define _SVSETBASE_H_
31   	
32   	/* undefine SOPLEX_DEBUG flag from including files; if SOPLEX_DEBUG should be defined in this file, do so below */
33   	#ifdef SOPLEX_DEBUG
34   	#define SOPLEX_DEBUG_SVSETBASE
35   	#undef SOPLEX_DEBUG
36   	#endif
37   	
38   	#include <assert.h>
39   	
40   	#include "soplex/spxdefines.h"
41   	#include "soplex/svectorbase.h"
42   	#include "soplex/classarray.h"
43   	#include "soplex/dataset.h"
44   	#include "soplex/classset.h"
45   	#include "soplex/datakey.h"
46   	#include "soplex/idlist.h"
47   	
48   	namespace soplex
49   	{
50   	/**@brief   Sparse vector set.
51   	 * @ingroup Algebra
52   	 *
53   	 *   Class SVSetBase provides a set of sparse vectors SVectorBase. All SVectorBase%s in an SVSetBase share one big
54   	 *   memory block for their nonzeros. This memory is referred to as the \em nonzero \em memory. The SVectorBase%s
55   	 *   themselves are saved in another memory block referred to as the \em vector \em memory. Both memory blocks will grow
56   	 *   automatically if required, when adding more SVectorBase%s to the set or enlarging SVectorBase%s within the set. For
57   	 *   controlling memory consumption, methods are provided to inquire and reset the size of the memory blocks used for
58   	 *   vectors and nonzeros.
59   	 *
60   	 *   SVectorBase%s in an SVSetBase are numbered from 0 thru num()-1. They can be accessed using the index
61   	 *   operator[](). When removing SVectorBase%s of a SVSetBase the remaining ones will be renumbered. However, all
62   	 *   SVectorBase with a smaller number than the lowest number of the removed SVectorBase%s will remain unchanged.
63   	 *
64   	 *   For providing a uniform access to SVectorBase%s in a %set even if others are removed or added, SVSetBase assigns a
65   	 *   DataKey to each SVectorBase in the %set. Such a DataKey remains unchanged as long as the corresponding SVectorBase
66   	 *   is in the SVSetBase, no matter what other SVectorBase%s are added to or removed from the SVSetBase. Methods are
67   	 *   provided for getting the DataKey to a SVectorBase or its number and vice versa.  Further, each add() method for
68   	 *   enlarging an SVSetBase is provided with two signatures. One of them returns the DataKey%s assigned to the
69   	 *   SVectorBase%s added to the SVSetBase.
70   	 */
71   	template < class R >
72   	class SVSetBase : protected ClassArray < Nonzero<R> >
73   	{
74   	   template < class S > friend class SVSetBase;
75   	
76   	private:
77   	
78   	   typedef ClassArray < Nonzero<R> > SVSetBaseArray;
79   	
80   	   /**@class DLPSV
81   	    * @brief SVectorBase with prev/next pointers
82   	    * @todo  Check whether SVSetBase::DLPSV can be implemented as IdElement<SVectorBase>
83   	    *
84   	    *  The management of the SVectorBase%s is implemented by a DataSet<DLPSV>, the keys used externally are DataKey%s.
85   	    *
86   	    *  The management of nonzeros is done by a Real linked list IdList<DLPSV>, where the SVectorBase%s are kept in the
87   	    *  order in which their indices occurr in the Array. The SVectorBase%s are kept without holes: If one is removed or
88   	    *  moved to the end, the SVectorBase preceeding it obtains the space for all the nonzeros that previously belonged
89   	    *  to the (re-)moved one.  However, the nonzeros in use are uneffected by this.
90   	    */
(1) Event rule_of_five_violation: Class "soplex::SVSetBase<double>::DLPSV" has a user definition for at least one special function (copy constructor, move constructor, copy assignment, move assignment, destructor) but not all. If one of these functions requires a user definition then the others likely do as well.
(3) Event remediation: Add user-definition for a copy assignment operator.
(4) Event remediation: Add user-definition for a destructor.
Also see events: [copy_ctor][move_ctor][move_assign]
91   	   class DLPSV : public SVectorBase<R>
92   	   {
93   	   private:
94   	
95   	      // ---------------------------------------------------------------------------------------------------------------
96   	      /**@name Data */
97   	      ///@{
98   	
99   	      DLPSV* thenext; ///< next SVectorBase
100  	      DLPSV* theprev; ///< previous SVectorBase
101  	
102  	      ///@}
103  	
104  	   public:
105  	
106  	      // ---------------------------------------------------------------------------------------------------------------
107  	      /**@name Construction / destruction */
108  	      ///@{
109  	
110  	      /// Default constructor.
111  	      DLPSV()
112  	         : SVectorBase<R>()
113  	      {}
114  	
115  	      /// Copy constructor.
(2) Event copy_ctor: User-defined copy constructor.
Also see events: [rule_of_five_violation][remediation][remediation][move_ctor][move_assign]
116  	      DLPSV(const DLPSV& copy)
117  	         : SVectorBase<R>(copy)
118  	      {}
119  	
(5) Event move_ctor: User-defined move constructor.
Also see events: [rule_of_five_violation][copy_ctor][remediation][remediation][move_assign]
120  	      DLPSV(DLPSV&& copy)
121  	         : SVectorBase<R>(copy)
122  	      {}
123  	
(6) Event move_assign: User-defined move assignment operator.
Also see events: [rule_of_five_violation][copy_ctor][remediation][remediation][move_ctor]
124  	      DLPSV& operator=(DLPSV&& rhs)
125  	      {
126  	         SVectorBase<R>::operator=(std::move(rhs));
127  	
128  	         if(this != & rhs)
129  	         {
130  	            this->thenext = rhs.thenext;
131  	            this->theprev = rhs.theprev;
132  	         }
133  	
134  	         return *this;
135  	      }
136  	      ///@}
137  	
138  	      // ---------------------------------------------------------------------------------------------------------------
139  	      /**@name Successor / predecessor */
140  	      ///@{
141  	
142  	      /// Next SVectorBase.
143  	      DLPSV*& next()
144  	      {
145  	         return thenext;
146  	      }
147  	
148  	      /// Next SVectorBase.
149  	      DLPSV* const& next() const
150  	      {
151  	         return thenext;
152  	      }
153  	
154  	      /// Previous SVectorBase.
155  	      DLPSV* const& prev() const
156  	      {
157  	         return theprev;
158  	      }
159  	
160  	      /// Previous SVectorBase.
161  	      DLPSV*& prev()
162  	      {
163  	         return theprev;
164  	      }
165  	
166  	      ///@}
167  	   };
168  	
169  	   // ------------------------------------------------------------------------------------------------------------------
170  	   /**@name Data */
171  	   ///@{
172  	
173  	   ClassSet < DLPSV > set;  ///< %set of SVectorBase%s
174  	   IdList < DLPSV > list;  ///< doubly linked list for non-zero management
175  	   int unusedMem;  ///< an estimate of the unused memory (the difference of max() and size() summed up over all vectors) due to deleteVec() and xtend()
176  	   int numUnusedMemUpdates;  ///< counter for how often unusedMem has been updated since last exact value
177  	
178  	   ///@}
179  	
180  	   // ------------------------------------------------------------------------------------------------------------------
181  	   /**@name Control Parameters */
182  	   ///@{
183  	
184  	   double factor;          ///< sparse vector memory enlargment factor
185  	
186  	   ///@}
187  	
188  	   // ------------------------------------------------------------------------------------------------------------------
189  	   /**@name Helpers */
190  	   ///@{
191  	
192  	   /// count size of unused memory exactly
193  	   void countUnusedMem()
194  	   {
195  	#ifdef SOPLEX_DEBUG
196  	      SPxOut::debug(this,
197  	                    "counting unused memory (unusedMem = {}, numUnusedMemUpdates = {}, this = {})\n",
198  	                    unusedMem, numUnusedMemUpdates, (void*)this);
199  	#endif
200  	
201  	      unusedMem = memSize();
202  	
203  	      for(DLPSV* ps = list.first(); ps; ps = list.next(ps))
204  	         unusedMem -= ps->size();
205  	
206  	      numUnusedMemUpdates = 0;
207  	
208  	#ifdef SOPLEX_DEBUG
209  	      SPxOut::debug(this, "               --> NEW: unusedMem = {}\n", unusedMem);
210  	#endif
211  	   }
212  	
213  	   /// update estimation of unused memory
214  	   void updateUnusedMemEstimation(int change)
215  	   {
216  	      unusedMem += change;
217  	      numUnusedMemUpdates++;
218  	
219  	      if(unusedMem < 0 || unusedMem > memSize() || numUnusedMemUpdates >= 1000000)
220  	         countUnusedMem();
221  	   }
222  	
223  	   /// Provides enough vector memory for \p n more SVectorBase%s.
224  	   void ensurePSVec(int n)
225  	   {
226  	      if(num() + n > max())
227  	      {
228  	         assert(factor > 1);
229  	
230  	         reMax(int(factor * max()) + 8 + n);
231  	      }
232  	   }
233  	
234  	   /// Provides enough nonzero memory for \p n more Nonzero%s.
235  	   void ensureMem(int n, bool shortenLast = true)
236  	   {
237  	      if(memSize() + n <= memMax())
238  	         return;
239  	
240  	      if(list.last() && shortenLast)
241  	      {
242  	         // get last vector and compute its unused memory
243  	         DLPSV* ps = list.last();
244  	         int unusedPsMem = ps->max() - ps->size();
245  	         assert(unusedPsMem >= 0);
246  	
247  	         // return vector's unused memory to common memory
248  	         SVSetBaseArray::removeLast(unusedPsMem);
249  	         ps->set_max(ps->size());
250  	
251  	         // decrease counter of unused memory
252  	#ifdef SOPLEX_DEBUG
253  	         SPxOut::debug(this, "ensureMem, this = {} : updateUnusedMemEstimation -= {}\n", (void*)this,
254  	                       unusedPsMem);
255  	#endif
256  	         updateUnusedMemEstimation(-unusedPsMem);
257  	      }
258  	
259  	      // if the missing memory can be acquired by packing the memory, we prefer this to allocating new memory
260  	      int missingMem = (memSize() + n - memMax());
261  	
262  	      ///@todo use an independent parameter "memwastefactor" here
263  	      if(missingMem > 0 && missingMem <= unusedMem
264  	            && unusedMem > (SVSetBaseArray::memFactor - 1.0) * memMax())
265  	         memPack();
266  	
267  	      // if the unused memory was overestimated and packing did not help, we need to reallocate
268  	      if(memSize() + n > memMax())
269  	      {
270  	         int newMax = int(SVSetBaseArray::memFactor * memMax());
271  	
272  	         if(memSize() + n > newMax)
273  	            newMax = memSize() + n;
274  	
275  	         memRemax(newMax);
276  	      }
277  	   }
278  	
279  	   /// Deleting a vector from the data array and the list.
280  	   void deleteVec(DLPSV* ps)
281  	   {
282  	      /* delete last entries */
283  	      if(ps == list.last())
284  	      {
285  	         SVSetBaseArray::removeLast(ps->max());
286  	
287  	         // decrease counter of unused memory
288  	#ifdef SOPLEX_DEBUG
289  	         SPxOut::debug(this, "deleteVec (1), this = {} : updateUnusedMemEstimation -= {}\n", (void*)this,
290  	                       ps->max() - ps->size());
291  	#endif
292  	         updateUnusedMemEstimation(ps->size() - ps->max());
293  	      }
294  	      /* merge space of predecessor with position which will be deleted, therefore we do not need to delete any memory
295  	       * or do an expensive memory reallocation
296  	       */
297  	      else if(ps != list.first())
298  	      {
299  	         SVectorBase<R>* prev = ps->prev();
300  	         int sz = prev->size();
301  	
302  	         prev->setMem(prev->max() + ps->max(), prev->mem());
303  	         prev->set_size(sz);
304  	
305  	         // increase counter of unused memory
306  	#ifdef SOPLEX_DEBUG
307  	         SPxOut::debug(this, "deleteVec (2), this = {} : updateUnusedMemEstimation += {}\n", (void*)this,
308  	                       ps->size());
309  	#endif
310  	         updateUnusedMemEstimation(ps->size());
311  	      }
312  	      /* simply remove the front entries; we do not shift the second vector to the front, because we count the unused
313  	       * memory exactly and rely on the automatic call of memPack()
314  	       */
315  	      else
316  	      {
317  	         // increase counter of unused memory
318  	#ifdef SOPLEX_DEBUG
319  	         SPxOut::debug(this, "deleteVec (3), this = {} : updateUnusedMemEstimation += {}\n", (void*)this,
320  	                       ps->size());
321  	#endif
322  	         updateUnusedMemEstimation(ps->size());
323  	      }
324  	
325  	      list.remove(ps);
326  	   }
327  	
328  	   ///@}
329  	
330  	public:
331  	
332  	   // ------------------------------------------------------------------------------------------------------------------
333  	   /**@name Extension */
334  	   ///@{
335  	
336  	   /// Adds \p svec to the %set.
337  	   /** This includes copying its nonzeros to the sets nonzero memory and creating an additional SVectorBase entry in
338  	    *  vector memory. If neccessary, the memory blocks are enlarged appropriately.
339  	    */
340  	   void add(const SVectorBase<R>& svec)
341  	   {
342  	      // create empty vector
343  	      ensurePSVec(1);
344  	      SVectorBase<R>* new_svec = create(svec.size());
345  	
346  	      // assign values
347  	      *new_svec = svec;
348  	   }
349  	
350  	   /// Adds \p svec to SVSetBase.
351  	   /** Adds SVectorBase \p svec to the %set. This includes copying its nonzeros to the sets nonzero memory and creating
352  	    *  an additional SVectorBase entry in vector memory. If neccessary, the memory blocks are enlarged appropriately.
353  	    *
354  	    *  @return \p nkey contains the DataKey, that the SVSetBase has assosicated to the new SVectorBase.
355  	    */
356  	   void add(DataKey& nkey, const SVectorBase<R>& svec)
357  	   {
358  	      // create empty vector
359  	      ensurePSVec(1);
360  	      SVectorBase<R>* new_svec = create(nkey, svec.size());
361  	
362  	      // assign values
363  	      *new_svec = svec;
364  	   }
365  	
366  	   /// Adds \p svec to SVSetBase.
367  	   /** Adds SVectorBase \p svec to the %set. This includes copying its nonzeros to the sets nonzero memory and creating
368  	    *  an additional SVectorBase entry in vector memory. If neccessary, the memory blocks are enlarged appropriately.
369  	    *
370  	    *  @return \p nkey contains the DataKey, that the SVSetBase has assosicated to the new SVectorBase.
371  	    */
372  	   template < class S >
373  	   void add(DataKey& nkey, const S* rowValues, const int* rowIndices, int rowSize)
374  	   {
375  	      assert(rowSize <= 0 || rowIndices != 0);
376  	      assert(rowSize <= 0 || rowValues != 0);
377  	
378  	      // create empty vector
379  	      ensurePSVec(1);
380  	      SVectorBase<R>* new_svec = create(nkey, rowSize);
381  	
382  	      // assign values
383  	      if(rowSize > 0)
384  	         new_svec->assignArray(rowValues, rowIndices, rowSize);
385  	   }
386  	
387  	   /// Adds all \p n SVectorBase%s in the array \p svec to the %set.
388  	   /** @pre \p svec must hold at least \p n entries.
389  	    */
390  	   void add(const SVectorBase<R> svec[], int n)
391  	   {
392  	      assert(n >= 0);
393  	
394  	      int i;
395  	      int len;
396  	
397  	      for(i = len = 0; i < n; ++i)
398  	         len += svec[i].size();
399  	
400  	      ensurePSVec(n);
401  	      ensureMem(len);
402  	
403  	      for(i = 0; i < n; ++i)
404  	         *create(svec[i].size()) = svec[i];
405  	   }
406  	
407  	   /// Adds n SVectorBase%s to SVSetBase.
408  	   /** Adds all \p n SVectorBase%s in the array \p svec to the %set.
409  	    *
410  	    *  @return \p nkey contains the DataKey%s, that the SVSetBase has assosicated to the new SVectorBase%s.
411  	    *
412  	    *  @pre \p nkey must be large enough to fit \p n DataKey%s.
413  	    */
414  	   void add(DataKey nkey[], const SVectorBase<R> svec[], int n)
415  	   {
416  	      add(svec, n);
417  	
418  	      for(int i = num() - 1; --n; --i)
419  	         nkey[n] = key(i);
420  	   }
421  	
422  	   /// Adds all SVectorBase%s in \p pset to SVSetBase.
423  	   template < class S >
424  	   void add(const SVSetBase<S>& pset)
425  	   {
426  	      int i;
427  	      int n;
428  	      int len;
429  	
430  	      n = pset.num();
431  	
432  	      for(i = len = 0; i < n; ++i)
433  	         len += pset[i].size();
434  	
435  	      ensurePSVec(n);
436  	      ensureMem(len);
437  	
438  	      for(i = 0; i < n; ++i)
439  	         *create(pset[i].size()) = pset[i];
440  	   }
441  	
442  	   /// Adds all SVectorBase%s of \p pset to SVSetBase.
443  	   /** Adds all \p n SVectorBase%s in the \p pset to an SVSetBase.
444  	    *
445  	    * @return \p nkey contains the DataKey%s, that the SVSetBase has assosicated to the new SVectorBase%s.
446  	    *
447  	    * @pre \p nkey must be large enough to fit \p pset.num() DataKey%s.
448  	    */
449  	   template < class S >
450  	   void add(DataKey nkey[], const SVSetBase<S>& pset)
451  	   {
452  	      add(pset);
453  	
454  	      int i = num();
455  	      int n = pset.num();
456  	
457  	      while(n > 0)
458  	         nkey[--n] = key(--i);
459  	   }
460  	
461  	   /// Creates new SVectorBase in %set.
462  	   /** The new SVectorBase will be ready to fit at least \p idxmax nonzeros.
463  	    */
464  	   SVectorBase<R>* create(int idxmax = 0)
465  	   {
466  	      DLPSV* ps;
467  	
468  	      if(idxmax < 0)
469  	         idxmax = 0;
470  	
471  	      if(memSize() == 0 && idxmax <= 0)
472  	         idxmax = 1;
473  	
474  	      ensureMem(idxmax);
475  	
476  	      // resize the data array
477  	#ifndef NDEBUG
478  	      Nonzero<R>* olddata = SVSetBaseArray::data;
479  	      SVSetBaseArray::reSize(memSize() + idxmax);
480  	      assert(olddata == SVSetBaseArray::data);
481  	#else
482  	      SVSetBaseArray::reSize(memSize() + idxmax);
483  	#endif
484  	
485  	      ensurePSVec(1);
486  	      ps = set.create();
487  	      list.append(ps);
488  	
489  	      ps->setMem(idxmax, &SVSetBaseArray::last() - idxmax + 1);
490  	
491  	      return ps;
492  	   }
493  	
494  	   /// Creates new SVectorBase in %set.
495  	   /** The new SVectorBase will be ready to fit at least \p idxmax nonzeros.
496  	    *
497  	    * @return \p nkey contains the DataKey associated to the new SVectorBase.
498  	    */
499  	   SVectorBase<R>* create(DataKey& nkey, int idxmax = -1)
500  	   {
501  	      SVectorBase<R>* ps = create(idxmax);
502  	
503  	      nkey = key(num() - 1);
504  	
505  	      return ps;
506  	   }
507  	
508  	   /// Extends \p svec to fit \p newmax nonzeros.
509  	   /** @pre \p svec must be an SVectorBase of the SVSetBase.
510  	    */
511  	   void xtend(SVectorBase<R>& svec, int newmax)
512  	   {
513  	      if(svec.max() < newmax)
514  	      {
515  	         assert(has(&svec));
516  	
517  	         DLPSV* ps = static_cast<DLPSV*>(&svec);
518  	         int sz = ps->size();
519  	
520  	         if(ps == list.last())
521  	         {
522  	            // because we want to extend the last vector we must not shrink its max memory usage
523  	            // in order to ensure the missing memory
524  	            ensureMem(newmax - ps->max(), false);
525  	#ifndef NDEBUG
526  	            Nonzero<R>* olddata = SVSetBaseArray::data;
527  	            SVSetBaseArray::insert(memSize(), newmax - ps->max());
528  	            assert(olddata == SVSetBaseArray::data);
529  	#else
530  	            SVSetBaseArray::insert(memSize(), newmax - ps->max());
531  	#endif
532  	
533  	            // decrease counter of unused memory (assume that new entries will be used)
534  	#ifdef SOPLEX_DEBUG
535  	            SPxOut::debug(this, "xtend (1), this = {} : updateUnusedMemEstimation -= {}\n", (void*)this,
536  	                          ps->max() - sz);
537  	#endif
538  	            updateUnusedMemEstimation(sz - ps->max());
539  	
540  	            ps->setMem(newmax, ps->mem());
541  	            ps->set_size(sz);
542  	         }
543  	         else
544  	         {
545  	            ensureMem(newmax);
546  	            SVectorBase<R> newps(0, 0);
547  	
548  	            if(SVSetBaseArray::size() > 0)
549  	               newps.setMem(newmax, &SVSetBaseArray::last() + 1);
550  	            else
551  	               newps.setMem(newmax, SVSetBaseArray::get_ptr());
552  	
553  	#ifndef NDEBUG
554  	            Nonzero<R>* olddata = SVSetBaseArray::data;
555  	            SVSetBaseArray::insert(memSize(), newmax);
556  	            assert(olddata == SVSetBaseArray::data);
557  	#else
558  	            SVSetBaseArray::insert(memSize(), newmax);
559  	#endif
560  	
561  	            newps = svec;
562  	
563  	            if(ps != list.first())
564  	            {
565  	               SVectorBase<R>* prev = ps->prev();
566  	               int prevsz = prev->size();
567  	               prev->setMem(prev->max() + ps->max(), prev->mem());
568  	               prev->set_size(prevsz);
569  	            }
570  	
571  	            // increase counter of unused memory (assume that new entries will be used)
572  	#ifdef SOPLEX_DEBUG
573  	            SPxOut::debug(this, "xtend (2), this = {} : updateUnusedMemEstimation += {}\n", (void*)this,
574  	                          ps->size());
575  	#endif
576  	            updateUnusedMemEstimation(ps->size());
577  	
578  	            list.remove(ps);
579  	            list.append(ps);
580  	
581  	            ps->setMem(newmax, newps.mem());
582  	            ps->set_size(sz);
583  	         }
584  	      }
585  	   }
586  	
587  	   /// Adds nonzero (\p idx, \p val) to \p svec of this SVSetBase.
588  	   /** Adds one nonzero (\p idx, \p val) to SVectorBase \p svec in the SVSetBase.  If \p svec is not large enough to
589  	    *  hold the additional nonzero, it will be automatically enlarged within the %set.
590  	    *
591  	    *  @pre \p svec must be an SVectorBase of the SVSetBase.
592  	    */
593  	   void add2(SVectorBase<R>& svec, int idx, R val)
594  	   {
595  	      xtend(svec, svec.size() + 1);
596  	      svec.add(idx, val);
597  	   }
598  	
599  	   /// Adds \p n nonzeros to \p svec of this SVSetBase.
600  	   /** Adds \p n nonzeros to SVectorBase \p svec in the SVSetBase. If \p svec is not large enough to hold the additional
601  	    *  nonzeros, it will be automatically enlarged within the %set.
602  	    *
603  	    * @pre \p svec must be an SVectorBase of the SVSetBase.
604  	    */
605  	   void add2(SVectorBase<R>& svec, int n, const int idx[], const R val[])
606  	   {
607  	      xtend(svec, svec.size() + n);
608  	      svec.add(n, idx, val);
609  	   }
610  	
611  	   /// Adds \p n nonzeros to \p svec of this SVSetBase.
612  	   /** Adds \p n nonzeros to SVectorBase \p svec in the SVSetBase. If \p svec is not large enough to hold the additional
613  	    *  nonzeros, it will be automatically enlarged within the %set.
614  	    *
615  	    * @pre \p svec must be an SVectorBase of the SVSetBase.
616  	    */
617  	   template < class S >
618  	   void add2(SVectorBase<R>& svec, int n, const int idx[], const S val[])
619  	   {
620  	      xtend(svec, svec.size() + n);
621  	      svec.add(n, idx, val);
622  	   }
623  	
624  	   ///@}
625  	
626  	   // ------------------------------------------------------------------------------------------------------------------
627  	   /**@name Shrinking */
628  	   ///@{
629  	
630  	   /// Removes the vector with key \p removekey from the %set.
631  	   /** @pre \p removekey must be a key from SVSetBase
632  	    */
633  	   void remove(const DataKey& removekey)
634  	   {
635  	      deleteVec(&set[removekey]);
636  	      set.remove(removekey);
637  	   }
638  	
639  	   /// Removes the vector with number \p removenum from the %set.
640  	   /** @pre \p removenum must be a valid vector number from SVSetBase
641  	    */
642  	   void remove(int removenum)
643  	   {
644  	      remove(key(removenum));
645  	   }
646  	
647  	   /// Removes one SVectorBase from %set.
648  	   /** @pre \p svec must be from SVSetBase
649  	    */
650  	   void remove(const SVectorBase<R>* svec)
651  	   {
652  	      remove(key(svec));
653  	   }
654  	
655  	   /// Removes multiple elements.
656  	   /** Removes all SVectorBase%s for the SVSetBase with an index \c i such that \p perm[i] < 0. Upon completion, \p
657  	    *  perm[i] >= 0 indicates the new index where the \c i 'th SVectorBase has been moved to due to this removal.
658  	    *
659  	    *  @pre \p perm must point to an array of at least num() integers.
660  	    */
661  	   void remove(int perm[])
662  	   {
663  	      int j = num();
664  	
665  	      /* due to performance reasons we use a backwards loop to delete entries, because it could result instead of only
666  	       * decreasing the number of elements j times in memmoving the whole array j times
667  	       */
668  	      for(int i = j - 1; i >= 0; --i)
669  	      {
670  	         if(perm[i] < 0)
671  	         {
672  	            deleteVec(&set[i]);
673  	         }
674  	      }
675  	
676  	      set.remove(perm);
677  	   }
678  	
679  	   /// Removes \p n SVectorBase%s from %set.
680  	   /** @pre \p keys must be at least of size \p n and valid keys
681  	    */
682  	   void remove(const DataKey keys[], int n)
683  	   {
684  	      DataArray < int > perm(num());
685  	      remove(keys, n, perm.get_ptr());
686  	   }
687  	
688  	   /// Removes \p n SVectorBase%s from %set.
689  	   /** @pre \p nums must be at least of size \p n and valid vector numbers
690  	    */
691  	   void remove(const int nums[], int n)
692  	   {
693  	      DataArray < int > perm(num());
694  	      remove(nums, n, perm.get_ptr());
695  	   }
696  	
697  	   ///
698  	   void remove(const DataKey keys[], int n, int* perm)
699  	   {
700  	      for(int i = num() - 1; i >= 0; --i)
701  	         perm[i] = i;
702  	
703  	      while(n--)
704  	         perm[number(*keys++)] = -1;
705  	
706  	      remove(perm);
707  	   }
708  	
709  	   /** Removes \p n SVectorBase%s from %set.
710  	    * @pre    \p nums must be at least of size \p n
711  	    * @pre    \p perm must be at least of size num()
712  	    * @return \p perm is the permutations resulting from this removal: \p perm[i] < 0 indicates
713  	    *   that the element to index \p i has been removed. Otherwise, \p perm[i] is the new
714  	    *   index of the element with index \p i before the removal.
715  	    */
716  	   void remove(const int nums[], int n, int* perm)
717  	   {
718  	      for(int i = num() - 1; i >= 0; --i)
719  	         perm[i] = i;
720  	
721  	      while(n--)
722  	         perm[*nums++] = -1;
723  	
724  	      remove(perm);
725  	   }
726  	
727  	   /// Removes all SVectorBase%s from %set.
728  	   void clear(int minNewSize = -1)
729  	   {
730  	      SVSetBaseArray::clear();
731  	
732  	      if(minNewSize <= 0)
733  	      {
734  	         if(SVSetBaseArray::max() > 10000)
735  	            SVSetBaseArray::reMax(10000);
736  	      }
737  	      else
738  	      {
739  	         if(SVSetBaseArray::max() > minNewSize + 10000)
740  	            SVSetBaseArray::reMax(minNewSize);
741  	      }
742  	
743  	      set.clear();
744  	      list.clear();
745  	      unusedMem = 0;
746  	      numUnusedMemUpdates = 0;
747  	   }
748  	
749  	   ///@}
750  	
751  	   // ------------------------------------------------------------------------------------------------------------------
752  	   /**@name Access */
753  	   ///@{
754  	
755  	   /// Gets SVectorBase by number, writeable.
756  	   SVectorBase<R>& operator[](int n)
757  	   {
758  	      return set[n];
759  	   }
760  	
761  	   /// Gets SVectorBase by number.
762  	   const SVectorBase<R>& operator[](int n) const
763  	   {
764  	      return set[n];
765  	   }
766  	
767  	   /// Gets SVectorBase by DataKey, writeable.
768  	   SVectorBase<R>& operator[](const DataKey& k)
769  	   {
770  	      return set[k];
771  	   }
772  	
773  	   /// Gets SVectorBase by DataKey.
774  	   const SVectorBase<R>& operator[](const DataKey& k) const
775  	   {
776  	      return set[k];
777  	   }
778  	
779  	   ///@}
780  	
781  	   // ------------------------------------------------------------------------------------------------------------------
782  	   /**@name Inquiry */
783  	   ///@{
784  	
785  	   /// Current number of SVectorBase%s.
786  	   int num() const
787  	   {
788  	      return set.num();
789  	   }
790  	
791  	   /// Current maximum number of SVectorBase%s.
792  	   int max() const
793  	   {
794  	      return set.max();
795  	   }
796  	
797  	   /// Gets DataKey of vector number.
798  	   DataKey key(int n) const
799  	   {
800  	      return set.key(n);
801  	   }
802  	
803  	   /// Gets DataKey of SVectorBase.
804  	   DataKey key(const SVectorBase<R>* svec) const
805  	   {
806  	      return set.key(static_cast<const DLPSV*>(svec));
807  	   }
808  	
809  	   /// Gets vector number of DataKey.
810  	   int number(const DataKey& k) const
811  	   {
812  	      return set.number(k);
813  	   }
814  	
815  	   /// Gets vector number of SVectorBase.
816  	   int number(const SVectorBase<R>* svec) const
817  	   {
818  	      return set.number(static_cast<const DLPSV*>(svec));
819  	   }
820  	
821  	   /// True iff SVSetBase contains a SVectorBase for DataKey \p k.
822  	   bool has(const DataKey& k) const
823  	   {
824  	      return set.has(k);
825  	   }
826  	
827  	   /// True iff SVSetBase contains a SVectorBase for vector number n.
828  	   bool has(int n) const
829  	   {
830  	      return set.has(n);
831  	   }
832  	
833  	   /// Is an SVectorBase in the %set?
834  	   bool has(const SVectorBase<R>* svec) const
835  	   {
836  	      return set.has(static_cast<const DLPSV*>(svec));
837  	   }
838  	
839  	   ///@}
840  	
841  	   // ------------------------------------------------------------------------------------------------------------------
842  	   /**@name Memory Management */
843  	   ///@{
844  	
845  	   /// Used nonzero memory.
846  	   int memSize() const
847  	   {
848  	      return SVSetBaseArray::size();
849  	   }
850  	
851  	   /// Length of nonzero memory.
852  	   int memMax() const
853  	   {
854  	      return SVSetBaseArray::max();
855  	   }
856  	
857  	   /// Reset length of nonzero memory.
858  	   void memRemax(int newmax)
859  	   {
860  	      ptrdiff_t delta = SVSetBaseArray::reMax(newmax);
861  	
862  	      if(delta != 0)
863  	      {
864  	#ifdef SOPLEX_DEBUG
865  	         SPxOut::debug(this,
866  	                       "counting unused memory (unusedMem = {}, numUnusedMemUpdates = {}, this = {})\n",
867  	                       unusedMem, numUnusedMemUpdates, (void*)this);
868  	#endif
869  	
870  	         int used = 0;
871  	
872  	         for(DLPSV* ps = list.first(); ps; ps = list.next(ps))
873  	         {
874  	            // get new shifted nonzero memory of the SVectorBase
875  	            Nonzero<R>* newmem = reinterpret_cast<Nonzero<R>*>(reinterpret_cast<char*>(ps->mem()) + delta);
876  	
877  	            // get the size and maximum capacity of the SVectorBase
878  	            int sz = ps->size();
879  	            int l_max = ps->max();
880  	            assert(l_max >= sz);
881  	
882  	            // set new nonzero memory
883  	            ps->setMem(l_max, newmem);
884  	            ps->set_size(sz);
885  	
886  	            // count used memory
887  	            used += sz;
888  	         }
889  	
890  	         // update estimation of unused memory to exact value
891  	         unusedMem = memSize() - used;
892  	         numUnusedMemUpdates = 0;
893  	
894  	#ifdef SOPLEX_DEBUG
895  	         SPxOut::debug(this, "               --> NEW: unusedMem = {}, after memRemax({})\n", unusedMem,
896  	                       newmax);
897  	#endif
898  	      }
899  	   }
900  	
901  	   /// Garbage collection in nonzero memory.
902  	   /** Pack the svectors together as tightly as possible. This removes all additional unused memory, i.e., size = max
903  	    *  for every svector after the call.
904  	    *
905  	    *  Note: do *not* call isConsistent() here, because the following might happen: In SPxLP::doAddRows(const LPRowSet&
906  	    *  p_set), when adding rows, the sizes of the vectors for the columns of the LP are increased (without yet filling
907  	    *  in the data) to recieve the additional entries. This is done by calling xtend() above. xtend() in turn might call
908  	    *  this method, which checks the yet unfilled positions, i.e., isConsistent() is likely to fail. In general,
909  	    *  isConsistent() should not be called within this class, but in classes further up in the hierarchy.
910  	    */
911  	   void memPack()
912  	   {
913  	      DLPSV* ps;
914  	      int used;
915  	      int j;
916  	
917  	      for(used = 0, ps = list.first(); ps; ps = list.next(ps))
918  	      {
919  	         const int sz = ps->size();
920  	
921  	         if(ps->mem() != &this->SVSetBaseArray::operator[](used))
922  	         {
923  	            // cannot use memcpy, because the memory might overlap
924  	            for(j = 0; j < sz; ++j)
925  	               this->SVSetBaseArray::operator[](used + j) = ps->mem()[j];
926  	
927  	            ps->setMem(sz, &this->SVSetBaseArray::operator[](used));
928  	            ps->set_size(sz);
929  	         }
930  	         else
931  	            ps->set_max(sz);
932  	
933  	         used += sz;
934  	      }
935  	
936  	#ifdef SOPLEX_DEBUG
937  	      SPxOut::debug(this,
938  	                    "counting unused memory (unusedMem = {}, numUnusedMemUpdates = {}, this = {})\n", unusedMem,
939  	                    numUnusedMemUpdates, (void*)this);
940  	      SPxOut::debug(this,
941  	                    "               --> NEW: unusedMem = {}, zero after memPack() at memMax() = {}\n",
942  	                    memSize() - used, memMax());
943  	#endif
944  	#ifndef NDEBUG
945  	      Nonzero<R>* olddata = SVSetBaseArray::data;
946  	      SVSetBaseArray::reSize(used);
947  	      assert(olddata == SVSetBaseArray::data);
948  	#else
949  	      SVSetBaseArray::reSize(used);
950  	#endif
951  	
952  	      unusedMem = 0;
953  	      numUnusedMemUpdates = 0;
954  	   }
955  	
956  	   ///@}
957  	
958  	   // ------------------------------------------------------------------------------------------------------------------
959  	   /**@name Miscellaneous */
960  	   ///@{
961  	
962  	   /// Resets maximum number of SVectorBase%s.
963  	   void reMax(int newmax = 0)
964  	   {
965  	      list.move(set.reMax(newmax));
966  	   }
967  	
968  	   /// Consistency check.
969  	   bool isConsistent() const
970  	   {
971  	#ifdef ENABLE_CONSISTENCY_CHECKS
972  	      DLPSV* ps;
973  	      DLPSV* next;
974  	
975  	      for(ps = list.first(); ps; ps = next)
976  	      {
977  	         if(!ps->isConsistent())
978  	            return SPX_MSG_INCONSISTENT("SVSetBase");
979  	
980  	         if(ps->mem() > &SVSetBaseArray::last())
981  	            return SPX_MSG_INCONSISTENT("SVSetBase");
982  	
983  	         next = list.next(ps);
984  	
985  	         if(next && ps->mem() + ps->max() != next->mem())
986  	            return SPX_MSG_INCONSISTENT("SVSetBase");
987  	      }
988  	
989  	      return SVSetBaseArray::isConsistent() && set.isConsistent() && list.isConsistent();
990  	#else
991  	      return true;
992  	#endif
993  	   }
994  	
995  	   ///@}
996  	
997  	   // ------------------------------------------------------------------------------------------------------------------
998  	   /**@name Constructors / destructors */
999  	   ///@{
1000 	
1001 	   /// Default constructor.
1002 	   explicit
1003 	   SVSetBase(int pmax = -1, int pmemmax = -1, double pfac = 1.1, double pmemFac = 1.2)
1004 	      : SVSetBaseArray(0, (pmemmax > 0) ? pmemmax : 8 * ((pmax > 0) ? pmax : 8), pmemFac)
1005 	      , set((pmax > 0) ? pmax : 8)
1006 	      , unusedMem(0)
1007 	      , numUnusedMemUpdates(0)
1008 	      , factor(pfac)
1009 	   {
1010 	      assert(isConsistent());
1011 	   }
1012 	
1013 	   /// Destructor
1014 	   virtual ~SVSetBase()
1015 	   {}
1016 	
1017 	   /// Assignment operator.
1018 	   SVSetBase<R>& operator=(const SVSetBase<R>& rhs)
1019 	   {
1020 	      if(this != &rhs)
1021 	      {
1022 	         clear(rhs.size());
1023 	
1024 	         if(rhs.size() > 0)
1025 	         {
1026 	            SVSetBaseArray::operator=(rhs);
1027 	            set = rhs.set;
1028 	
1029 	            DLPSV* ps;
1030 	            DLPSV* newps;
1031 	
1032 	            void* delta0 = &(*(static_cast<SVSetBaseArray*>(this)))[0];
1033 	            void* delta1 = &(*(static_cast<SVSetBaseArray*>(const_cast<SVSetBase<R>*>(&rhs))))[0];
1034 	            ptrdiff_t delta = reinterpret_cast<char*>(delta0) - reinterpret_cast<char*>(delta1);
1035 	
1036 	            for(ps = rhs.list.first(); ps; ps = rhs.list.next(ps))
1037 	            {
1038 	               newps = &set[rhs.number(ps)];
1039 	               list.append(newps);
1040 	               newps->setMem(ps->max(),
1041 	                             reinterpret_cast<Nonzero<R>*>(reinterpret_cast<char*>(ps->mem()) + delta));
1042 	               newps->set_size(ps->size());
1043 	            }
1044 	         }
1045 	      }
1046 	
1047 	      assert(isConsistent());
1048 	
1049 	      return *this;
1050 	   }
1051 	
1052 	   /// Assignment operator.
1053 	   template < class S >
1054 	   SVSetBase<R>& operator=(const SVSetBase<S>& rhs)
1055 	   {
1056 	      if(this != (const SVSetBase<R>*)(&rhs))
1057 	      {
1058 	         clear(rhs.size());
1059 	
1060 	         if(rhs.size() > 0)
1061 	            this->add(rhs);
1062 	      }
1063 	
1064 	      assert(isConsistent());
1065 	
1066 	      return *this;
1067 	   }
1068 	
1069 	   /// Copy constructor.
1070 	   SVSetBase(const SVSetBase<R>& old)
1071 	      : SVSetBaseArray()
1072 	      , unusedMem(old.unusedMem)
1073 	      , numUnusedMemUpdates(old.numUnusedMemUpdates)
1074 	      , factor(old.factor)
1075 	   {
1076 	      *this = old;
1077 	
1078 	      assert(SVSetBase::isConsistent());
1079 	   }
1080 	
1081 	   /// Copy constructor.
1082 	   template < class S >
1083 	   SVSetBase(const SVSetBase<S>& old)
1084 	      : SVSetBaseArray()
1085 	      , unusedMem(old.unusedMem)
1086 	      , numUnusedMemUpdates(old.numUnusedMemUpdates)
1087 	      , factor(old.factor)
1088 	   {
1089 	      *this = old;
1090 	
1091 	      assert(SVSetBase::isConsistent());
1092 	   }
1093 	
1094 	   ///@}
1095 	};
1096 	
1097 	} // namespace soplex
1098 	
1099 	/* reset the SOPLEX_DEBUG flag to its original value */
1100 	#undef SOPLEX_DEBUG
1101 	#ifdef SOPLEX_DEBUG_SVSETBASE
1102 	#define SOPLEX_DEBUG
1103 	#undef SOPLEX_DEBUG_SVSETBASE
1104 	#endif
1105 	
1106 	#endif // _SVSETBASE_H_
1107