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 */
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>()
(2) Event uninit_member: |
Non-static class member "thenext" is not initialized in this constructor nor in any functions that it calls. |
(4) Event uninit_member: |
Non-static class member "theprev" is not initialized in this constructor nor in any functions that it calls. |
Also see events: |
[member_decl][member_decl] |
113 {}
114
115 /// Copy constructor.
116 DLPSV(const DLPSV& copy)
117 : SVectorBase<R>(copy)
118 {}
119
120 DLPSV(DLPSV&& copy)
121 : SVectorBase<R>(copy)
122 {}
123
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