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