SoPlex Documentation
Loading...
Searching...
No Matches
svsetbase.h
Go to the documentation of this file.
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
48namespace 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 */
71template < class R >
72class SVSetBase : protected ClassArray < Nonzero<R> >
73{
74 template < class S > friend class SVSetBase;
75
76private:
77
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.
112 : SVectorBase<R>()
113 {}
114
115 /// Copy constructor.
117 : SVectorBase<R>(copy)
118 {}
119
121 : SVectorBase<R>(copy)
122 {}
123
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.
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.
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
194 {
195#ifdef SOPLEX_DEBUG
196 MSG_DEBUG(std::cout << "counting unused memory (unusedMem = " << unusedMem <<
197 ", numUnusedMemUpdates = " << numUnusedMemUpdates << ", this = " << (void*)this << ")\n");
198#endif
199
200 unusedMem = memSize();
201
202 for(DLPSV* ps = list.first(); ps; ps = list.next(ps))
203 unusedMem -= ps->size();
204
206
207#ifdef SOPLEX_DEBUG
208 MSG_DEBUG(std::cout << " --> NEW: unusedMem = " << unusedMem << "\n");
209#endif
210 }
211
212 /// update estimation of unused memory
214 {
215 unusedMem += change;
217
220 }
221
222 /// Provides enough vector memory for \p n more SVectorBase%s.
223 void ensurePSVec(int n)
224 {
225 if(num() + n > max())
226 {
227 assert(factor > 1);
228
229 reMax(int(factor * max()) + 8 + n);
230 }
231 }
232
233 /// Provides enough nonzero memory for \p n more Nonzero%s.
234 void ensureMem(int n, bool shortenLast = true)
235 {
236 if(memSize() + n <= memMax())
237 return;
238
239 if(list.last() && shortenLast)
240 {
241 // get last vector and compute its unused memory
242 DLPSV* ps = list.last();
243 int unusedPsMem = ps->max() - ps->size();
244 assert(unusedPsMem >= 0);
245
246 // return vector's unused memory to common memory
248 ps->set_max(ps->size());
249
250 // decrease counter of unused memory
251#ifdef SOPLEX_DEBUG
252 MSG_DEBUG(std::cout << "ensureMem, this = " << (void*)this << ": updateUnusedMemEstimation -= " <<
253 unusedPsMem << "\n");
254#endif
256 }
257
258 // if the missing memory can be acquired by packing the memory, we prefer this to allocating new memory
259 int missingMem = (memSize() + n - memMax());
260
261 ///@todo use an independent parameter "memwastefactor" here
262 if(missingMem > 0 && missingMem <= unusedMem
264 memPack();
265
266 // if the unused memory was overestimated and packing did not help, we need to reallocate
267 if(memSize() + n > memMax())
268 {
270
271 if(memSize() + n > newMax)
272 newMax = memSize() + n;
273
275 }
276 }
277
278 /// Deleting a vector from the data array and the list.
280 {
281 /* delete last entries */
282 if(ps == list.last())
283 {
285
286 // decrease counter of unused memory
287#ifdef SOPLEX_DEBUG
288 MSG_DEBUG(std::cout << "deleteVec (1), this = " << (void*)this << ": updateUnusedMemEstimation -= "
289 << ps->max() - ps->size() << "\n");
290#endif
292 }
293 /* merge space of predecessor with position which will be deleted, therefore we do not need to delete any memory
294 * or do an expensive memory reallocation
295 */
296 else if(ps != list.first())
297 {
298 SVectorBase<R>* prev = ps->prev();
299 int sz = prev->size();
300
301 prev->setMem(prev->max() + ps->max(), prev->mem());
302 prev->set_size(sz);
303
304 // increase counter of unused memory
305#ifdef SOPLEX_DEBUG
306 MSG_DEBUG(std::cout << "deleteVec (2), this = " << (void*)this << ": updateUnusedMemEstimation += "
307 << ps->size() << "\n");
308#endif
310 }
311 /* simply remove the front entries; we do not shift the second vector to the front, because we count the unused
312 * memory exactly and rely on the automatic call of memPack()
313 */
314 else
315 {
316 // increase counter of unused memory
317#ifdef SOPLEX_DEBUG
318 MSG_DEBUG(std::cout << "deleteVec (3), this = " << (void*)this << ": updateUnusedMemEstimation += "
319 << ps->size() << "\n");
320#endif
322 }
323
324 list.remove(ps);
325 }
326
327 ///@}
328
329public:
330
331 // ------------------------------------------------------------------------------------------------------------------
332 /**@name Extension */
333 ///@{
334
335 /// Adds \p svec to the %set.
336 /** This includes copying its nonzeros to the sets nonzero memory and creating an additional SVectorBase entry in
337 * vector memory. If neccessary, the memory blocks are enlarged appropriately.
338 */
340 {
341 // create empty vector
342 ensurePSVec(1);
344
345 // assign values
346 *new_svec = svec;
347 }
348
349 /// Adds \p svec to SVSetBase.
350 /** Adds SVectorBase \p svec to the %set. This includes copying its nonzeros to the sets nonzero memory and creating
351 * an additional SVectorBase entry in vector memory. If neccessary, the memory blocks are enlarged appropriately.
352 *
353 * @return \p nkey contains the DataKey, that the SVSetBase has assosicated to the new SVectorBase.
354 */
356 {
357 // create empty vector
358 ensurePSVec(1);
360
361 // assign values
362 *new_svec = svec;
363 }
364
365 /// Adds \p svec to SVSetBase.
366 /** Adds SVectorBase \p svec to the %set. This includes copying its nonzeros to the sets nonzero memory and creating
367 * an additional SVectorBase entry in vector memory. If neccessary, the memory blocks are enlarged appropriately.
368 *
369 * @return \p nkey contains the DataKey, that the SVSetBase has assosicated to the new SVectorBase.
370 */
371 template < class S >
372 void add(DataKey& nkey, const S* rowValues, const int* rowIndices, int rowSize)
373 {
374 assert(rowSize <= 0 || rowIndices != 0);
375 assert(rowSize <= 0 || rowValues != 0);
376
377 // create empty vector
378 ensurePSVec(1);
380
381 // assign values
382 if(rowSize > 0)
383 new_svec->assignArray(rowValues, rowIndices, rowSize);
384 }
385
386 /// Adds all \p n SVectorBase%s in the array \p svec to the %set.
387 /** @pre \p svec must hold at least \p n entries.
388 */
389 void add(const SVectorBase<R> svec[], int n)
390 {
391 assert(n >= 0);
392
393 int i;
394 int len;
395
396 for(i = len = 0; i < n; ++i)
397 len += svec[i].size();
398
399 ensurePSVec(n);
400 ensureMem(len);
401
402 for(i = 0; i < n; ++i)
403 *create(svec[i].size()) = svec[i];
404 }
405
406 /// Adds n SVectorBase%s to SVSetBase.
407 /** Adds all \p n SVectorBase%s in the array \p svec to the %set.
408 *
409 * @return \p nkey contains the DataKey%s, that the SVSetBase has assosicated to the new SVectorBase%s.
410 *
411 * @pre \p nkey must be large enough to fit \p n DataKey%s.
412 */
413 void add(DataKey nkey[], const SVectorBase<R> svec[], int n)
414 {
415 add(svec, n);
416
417 for(int i = num() - 1; --n; --i)
418 nkey[n] = key(i);
419 }
420
421 /// Adds all SVectorBase%s in \p pset to SVSetBase.
422 template < class S >
423 void add(const SVSetBase<S>& pset)
424 {
425 int i;
426 int n;
427 int len;
428
429 n = pset.num();
430
431 for(i = len = 0; i < n; ++i)
432 len += pset[i].size();
433
434 ensurePSVec(n);
435 ensureMem(len);
436
437 for(i = 0; i < n; ++i)
438 *create(pset[i].size()) = pset[i];
439 }
440
441 /// Adds all SVectorBase%s of \p pset to SVSetBase.
442 /** Adds all \p n SVectorBase%s in the \p pset to an SVSetBase.
443 *
444 * @return \p nkey contains the DataKey%s, that the SVSetBase has assosicated to the new SVectorBase%s.
445 *
446 * @pre \p nkey must be large enough to fit \p pset.num() DataKey%s.
447 */
448 template < class S >
450 {
451 add(pset);
452
453 int i = num();
454 int n = pset.num();
455
456 while(n > 0)
457 nkey[--n] = key(--i);
458 }
459
460 /// Creates new SVectorBase in %set.
461 /** The new SVectorBase will be ready to fit at least \p idxmax nonzeros.
462 */
464 {
465 DLPSV* ps;
466
467 if(idxmax < 0)
468 idxmax = 0;
469
470 if(memSize() == 0 && idxmax <= 0)
471 idxmax = 1;
472
474
475 // resize the data array
476#ifndef NDEBUG
480#else
482#endif
483
484 ensurePSVec(1);
485 ps = set.create();
486 list.append(ps);
487
488 ps->setMem(idxmax, &SVSetBaseArray::last() - idxmax + 1);
489
490 return ps;
491 }
492
493 /// Creates new SVectorBase in %set.
494 /** The new SVectorBase will be ready to fit at least \p idxmax nonzeros.
495 *
496 * @return \p nkey contains the DataKey associated to the new SVectorBase.
497 */
499 {
501
502 nkey = key(num() - 1);
503
504 return ps;
505 }
506
507 /// Extends \p svec to fit \p newmax nonzeros.
508 /** @pre \p svec must be an SVectorBase of the SVSetBase.
509 */
511 {
512 if(svec.max() < newmax)
513 {
514 assert(has(&svec));
515
516 DLPSV* ps = static_cast<DLPSV*>(&svec);
517 int sz = ps->size();
518
519 if(ps == list.last())
520 {
521 // because we want to extend the last vector we must not shrink its max memory usage
522 // in order to ensure the missing memory
523 ensureMem(newmax - ps->max(), false);
524#ifndef NDEBUG
528#else
530#endif
531
532 // decrease counter of unused memory (assume that new entries will be used)
533#ifdef SOPLEX_DEBUG
534 MSG_DEBUG(std::cout << "xtend (1), this = " << (void*)this << ": updateUnusedMemEstimation -= " <<
535 ps->max() - sz << "\n");
536#endif
538
539 ps->setMem(newmax, ps->mem());
540 ps->set_size(sz);
541 }
542 else
543 {
545 SVectorBase<R> newps(0, 0);
546
547 if(SVSetBaseArray::size() > 0)
548 newps.setMem(newmax, &SVSetBaseArray::last() + 1);
549 else
551
552#ifndef NDEBUG
556#else
558#endif
559
560 newps = svec;
561
562 if(ps != list.first())
563 {
564 SVectorBase<R>* prev = ps->prev();
565 int prevsz = prev->size();
566 prev->setMem(prev->max() + ps->max(), prev->mem());
567 prev->set_size(prevsz);
568 }
569
570 // increase counter of unused memory (assume that new entries will be used)
571#ifdef SOPLEX_DEBUG
572 MSG_DEBUG(std::cout << "xtend (2), this = " << (void*)this << ": updateUnusedMemEstimation += " <<
573 ps->size() << "\n");
574#endif
576
577 list.remove(ps);
578 list.append(ps);
579
580 ps->setMem(newmax, newps.mem());
581 ps->set_size(sz);
582 }
583 }
584 }
585
586 /// Adds nonzero (\p idx, \p val) to \p svec of this SVSetBase.
587 /** Adds one nonzero (\p idx, \p val) to SVectorBase \p svec in the SVSetBase. If \p svec is not large enough to
588 * hold the additional nonzero, it will be automatically enlarged within the %set.
589 *
590 * @pre \p svec must be an SVectorBase of the SVSetBase.
591 */
592 void add2(SVectorBase<R>& svec, int idx, R val)
593 {
594 xtend(svec, svec.size() + 1);
595 svec.add(idx, val);
596 }
597
598 /// Adds \p n nonzeros to \p svec of this SVSetBase.
599 /** Adds \p n nonzeros to SVectorBase \p svec in the SVSetBase. If \p svec is not large enough to hold the additional
600 * nonzeros, it will be automatically enlarged within the %set.
601 *
602 * @pre \p svec must be an SVectorBase of the SVSetBase.
603 */
604 void add2(SVectorBase<R>& svec, int n, const int idx[], const R val[])
605 {
606 xtend(svec, svec.size() + n);
607 svec.add(n, idx, val);
608 }
609
610 /// Adds \p n nonzeros to \p svec of this SVSetBase.
611 /** Adds \p n nonzeros to SVectorBase \p svec in the SVSetBase. If \p svec is not large enough to hold the additional
612 * nonzeros, it will be automatically enlarged within the %set.
613 *
614 * @pre \p svec must be an SVectorBase of the SVSetBase.
615 */
616 template < class S >
617 void add2(SVectorBase<R>& svec, int n, const int idx[], const S val[])
618 {
619 xtend(svec, svec.size() + n);
620 svec.add(n, idx, val);
621 }
622
623 ///@}
624
625 // ------------------------------------------------------------------------------------------------------------------
626 /**@name Shrinking */
627 ///@{
628
629 /// Removes the vector with key \p removekey from the %set.
630 /** @pre \p removekey must be a key from SVSetBase
631 */
633 {
636 }
637
638 /// Removes the vector with number \p removenum from the %set.
639 /** @pre \p removenum must be a valid vector number from SVSetBase
640 */
642 {
644 }
645
646 /// Removes one SVectorBase from %set.
647 /** @pre \p svec must be from SVSetBase
648 */
650 {
651 remove(key(svec));
652 }
653
654 /// Removes multiple elements.
655 /** Removes all SVectorBase%s for the SVSetBase with an index \c i such that \p perm[i] < 0. Upon completion, \p
656 * perm[i] >= 0 indicates the new index where the \c i 'th SVectorBase has been moved to due to this removal.
657 *
658 * @pre \p perm must point to an array of at least num() integers.
659 */
660 void remove(int perm[])
661 {
662 int j = num();
663
664 /* due to performance reasons we use a backwards loop to delete entries, because it could result instead of only
665 * decreasing the number of elements j times in memmoving the whole array j times
666 */
667 for(int i = j - 1; i >= 0; --i)
668 {
669 if(perm[i] < 0)
670 {
671 deleteVec(&set[i]);
672 }
673 }
674
675 set.remove(perm);
676 }
677
678 /// Removes \p n SVectorBase%s from %set.
679 /** @pre \p keys must be at least of size \p n and valid keys
680 */
681 void remove(const DataKey keys[], int n)
682 {
683 DataArray < int > perm(num());
684 remove(keys, n, perm.get_ptr());
685 }
686
687 /// Removes \p n SVectorBase%s from %set.
688 /** @pre \p nums must be at least of size \p n and valid vector numbers
689 */
690 void remove(const int nums[], int n)
691 {
692 DataArray < int > perm(num());
693 remove(nums, n, perm.get_ptr());
694 }
695
696 ///
697 void remove(const DataKey keys[], int n, int* perm)
698 {
699 for(int i = num() - 1; i >= 0; --i)
700 perm[i] = i;
701
702 while(n--)
703 perm[number(*keys++)] = -1;
704
705 remove(perm);
706 }
707
708 /** Removes \p n SVectorBase%s from %set.
709 * @pre \p nums must be at least of size \p n
710 * @pre \p perm must be at least of size num()
711 * @return \p perm is the permutations resulting from this removal: \p perm[i] < 0 indicates
712 * that the element to index \p i has been removed. Otherwise, \p perm[i] is the new
713 * index of the element with index \p i before the removal.
714 */
715 void remove(const int nums[], int n, int* perm)
716 {
717 for(int i = num() - 1; i >= 0; --i)
718 perm[i] = i;
719
720 while(n--)
721 perm[*nums++] = -1;
722
723 remove(perm);
724 }
725
726 /// Removes all SVectorBase%s from %set.
727 void clear(int minNewSize = -1)
728 {
730
731 if(minNewSize <= 0)
732 {
733 if(SVSetBaseArray::max() > 10000)
735 }
736 else
737 {
738 if(SVSetBaseArray::max() > minNewSize + 10000)
740 }
741
742 set.clear();
743 list.clear();
744 unusedMem = 0;
746 }
747
748 ///@}
749
750 // ------------------------------------------------------------------------------------------------------------------
751 /**@name Access */
752 ///@{
753
754 /// Gets SVectorBase by number, writeable.
756 {
757 return set[n];
758 }
759
760 /// Gets SVectorBase by number.
761 const SVectorBase<R>& operator[](int n) const
762 {
763 return set[n];
764 }
765
766 /// Gets SVectorBase by DataKey, writeable.
768 {
769 return set[k];
770 }
771
772 /// Gets SVectorBase by DataKey.
773 const SVectorBase<R>& operator[](const DataKey& k) const
774 {
775 return set[k];
776 }
777
778 ///@}
779
780 // ------------------------------------------------------------------------------------------------------------------
781 /**@name Inquiry */
782 ///@{
783
784 /// Current number of SVectorBase%s.
785 int num() const
786 {
787 return set.num();
788 }
789
790 /// Current maximum number of SVectorBase%s.
791 int max() const
792 {
793 return set.max();
794 }
795
796 /// Gets DataKey of vector number.
797 DataKey key(int n) const
798 {
799 return set.key(n);
800 }
801
802 /// Gets DataKey of SVectorBase.
804 {
805 return set.key(static_cast<const DLPSV*>(svec));
806 }
807
808 /// Gets vector number of DataKey.
809 int number(const DataKey& k) const
810 {
811 return set.number(k);
812 }
813
814 /// Gets vector number of SVectorBase.
815 int number(const SVectorBase<R>* svec) const
816 {
817 return set.number(static_cast<const DLPSV*>(svec));
818 }
819
820 /// True iff SVSetBase contains a SVectorBase for DataKey \p k.
821 bool has(const DataKey& k) const
822 {
823 return set.has(k);
824 }
825
826 /// True iff SVSetBase contains a SVectorBase for vector number n.
827 bool has(int n) const
828 {
829 return set.has(n);
830 }
831
832 /// Is an SVectorBase in the %set?
833 bool has(const SVectorBase<R>* svec) const
834 {
835 return set.has(static_cast<const DLPSV*>(svec));
836 }
837
838 ///@}
839
840 // ------------------------------------------------------------------------------------------------------------------
841 /**@name Memory Management */
842 ///@{
843
844 /// Used nonzero memory.
845 int memSize() const
846 {
847 return SVSetBaseArray::size();
848 }
849
850 /// Length of nonzero memory.
851 int memMax() const
852 {
853 return SVSetBaseArray::max();
854 }
855
856 /// Reset length of nonzero memory.
857 void memRemax(int newmax)
858 {
860
861 if(delta != 0)
862 {
863#ifdef SOPLEX_DEBUG
864 MSG_DEBUG(std::cout << "counting unused memory (unusedMem = " << unusedMem <<
865 ", numUnusedMemUpdates = " << numUnusedMemUpdates << ", this = " << (void*)this << ")\n");
866#endif
867
868 int used = 0;
869
870 for(DLPSV* ps = list.first(); ps; ps = list.next(ps))
871 {
872 // get new shifted nonzero memory of the SVectorBase
873 Nonzero<R>* newmem = reinterpret_cast<Nonzero<R>*>(reinterpret_cast<char*>(ps->mem()) + delta);
874
875 // get the size and maximum capacity of the SVectorBase
876 int sz = ps->size();
877 int l_max = ps->max();
878 assert(l_max >= sz);
879
880 // set new nonzero memory
881 ps->setMem(l_max, newmem);
882 ps->set_size(sz);
883
884 // count used memory
885 used += sz;
886 }
887
888 // update estimation of unused memory to exact value
889 unusedMem = memSize() - used;
891
892#ifdef SOPLEX_DEBUG
893 MSG_DEBUG(std::cout << " --> NEW: unusedMem = " << unusedMem << " after memRemax(" <<
894 newmax << ")\n");
895#endif
896 }
897 }
898
899 /// Garbage collection in nonzero memory.
900 /** Pack the svectors together as tightly as possible. This removes all additional unused memory, i.e., size = max
901 * for every svector after the call.
902 *
903 * Note: do *not* call isConsistent() here, because the following might happen: In SPxLP::doAddRows(const LPRowSet&
904 * p_set), when adding rows, the sizes of the vectors for the columns of the LP are increased (without yet filling
905 * in the data) to recieve the additional entries. This is done by calling xtend() above. xtend() in turn might call
906 * this method, which checks the yet unfilled positions, i.e., isConsistent() is likely to fail. In general,
907 * isConsistent() should not be called within this class, but in classes further up in the hierarchy.
908 */
909 void memPack()
910 {
911 DLPSV* ps;
912 int used;
913 int j;
914
915 for(used = 0, ps = list.first(); ps; ps = list.next(ps))
916 {
917 const int sz = ps->size();
918
919 if(ps->mem() != &this->SVSetBaseArray::operator[](used))
920 {
921 // cannot use memcpy, because the memory might overlap
922 for(j = 0; j < sz; ++j)
923 this->SVSetBaseArray::operator[](used + j) = ps->mem()[j];
924
925 ps->setMem(sz, &this->SVSetBaseArray::operator[](used));
926 ps->set_size(sz);
927 }
928 else
929 ps->set_max(sz);
930
931 used += sz;
932 }
933
934#ifdef SOPLEX_DEBUG
935 MSG_DEBUG(std::cout << "counting unused memory (unusedMem = " << unusedMem <<
936 ", numUnusedMemUpdates = " << numUnusedMemUpdates << ", this = " << (void*)this << ")\n");
937 MSG_DEBUG(std::cout << " --> NEW: unusedMem = " << memSize() - used <<
938 ", zero after memPack() at memMax() = " << memMax() << "\n");
939#endif
940#ifndef NDEBUG
944#else
946#endif
947
948 unusedMem = 0;
950 }
951
952 ///@}
953
954 // ------------------------------------------------------------------------------------------------------------------
955 /**@name Miscellaneous */
956 ///@{
957
958 /// Resets maximum number of SVectorBase%s.
959 void reMax(int newmax = 0)
960 {
961 list.move(set.reMax(newmax));
962 }
963
964 /// Consistency check.
965 bool isConsistent() const
966 {
967#ifdef ENABLE_CONSISTENCY_CHECKS
968 DLPSV* ps;
969 DLPSV* next;
970
971 for(ps = list.first(); ps; ps = next)
972 {
973 if(!ps->isConsistent())
974 return MSGinconsistent("SVSetBase");
975
976 if(ps->mem() > &SVSetBaseArray::last())
977 return MSGinconsistent("SVSetBase");
978
979 next = list.next(ps);
980
981 if(next && ps->mem() + ps->max() != next->mem())
982 return MSGinconsistent("SVSetBase");
983 }
984
986#else
987 return true;
988#endif
989 }
990
991 ///@}
992
993 // ------------------------------------------------------------------------------------------------------------------
994 /**@name Constructors / destructors */
995 ///@{
996
997 /// Default constructor.
998 explicit
999 SVSetBase<R>(int pmax = -1, int pmemmax = -1, double pfac = 1.1, double pmemFac = 1.2)
1000 : SVSetBaseArray(0, (pmemmax > 0) ? pmemmax : 8 * ((pmax > 0) ? pmax : 8), pmemFac)
1001 , set((pmax > 0) ? pmax : 8)
1002 , unusedMem(0)
1004 , factor(pfac)
1005 {
1007 }
1008
1009 /// Destructor
1010 virtual ~SVSetBase<R>()
1011 {}
1012
1013 /// Assignment operator.
1015 {
1016 if(this != &rhs)
1017 {
1018 clear(rhs.size());
1019
1020 if(rhs.size() > 0)
1021 {
1023 set = rhs.set;
1024
1025 DLPSV* ps;
1026 DLPSV* newps;
1027
1028 void* delta0 = &(*(static_cast<SVSetBaseArray*>(this)))[0];
1029 void* delta1 = &(*(static_cast<SVSetBaseArray*>(const_cast<SVSetBase<R>*>(&rhs))))[0];
1030 ptrdiff_t delta = reinterpret_cast<char*>(delta0) - reinterpret_cast<char*>(delta1);
1031
1032 for(ps = rhs.list.first(); ps; ps = rhs.list.next(ps))
1033 {
1034 newps = &set[rhs.number(ps)];
1035 list.append(newps);
1036 newps->setMem(ps->max(),
1037 reinterpret_cast<Nonzero<R>*>(reinterpret_cast<char*>(ps->mem()) + delta));
1038 newps->set_size(ps->size());
1039 }
1040 }
1041 }
1042
1044
1045 return *this;
1046 }
1047
1048 /// Assignment operator.
1049 template < class S >
1051 {
1052 if(this != (const SVSetBase<R>*)(&rhs))
1053 {
1054 clear(rhs.size());
1055
1056 if(rhs.size() > 0)
1057 this->add(rhs);
1058 }
1059
1061
1062 return *this;
1063 }
1064
1065 /// Copy constructor.
1067 : SVSetBaseArray()
1070 , factor(old.factor)
1071 {
1072 *this = old;
1073
1075 }
1076
1077 /// Copy constructor.
1078 template < class S >
1079 SVSetBase<R>(const SVSetBase<S>& old)
1080 : SVSetBaseArray()
1081 , unusedMem(old.unusedMem)
1083 , factor(old.factor)
1084 {
1085 *this = old;
1086
1087 assert(SVSetBase::isConsistent());
1088 }
1089
1090 ///@}
1091};
1092
1093} // namespace soplex
1094
1095/* reset the SOPLEX_DEBUG flag to its original value */
1096#undef SOPLEX_DEBUG
1097#ifdef SOPLEX_DEBUG_SVSETBASE
1098#define SOPLEX_DEBUG
1099#undef SOPLEX_DEBUG_SVSETBASE
1100#endif
1101
1102#endif // _SVSETBASE_H_
Save arrays of data objects.
Set of class objects.
Safe arrays of class objects.
Definition classarray.h:65
bool isConsistent() const
Consistency check.
Definition classarray.h:324
Nonzero< R > & operator[](int n)
Reference to n 'th element.
Definition classarray.h:81
ClassArray & operator=(const ClassArray &rhs)
Assignment operator.
Definition classarray.h:308
Nonzero< R > * get_ptr()
Gets a C pointer to the data.
Definition classarray.h:111
int max() const
Returns maximum number of elements.
Definition classarray.h:243
void insert(int i, int n)
Inserts n uninitialized elements before i 'th element.
Definition classarray.h:141
ptrdiff_t reMax(int newMax=1, int newSize=-1)
Resets maximum number of elements.
Definition classarray.h:257
void reSize(int newsize)
Resets size to newsize.
Definition classarray.h:227
void removeLast(int m=1)
Removes m last elements.
Definition classarray.h:202
Nonzero< R > * data
the array of elements
Definition classarray.h:69
void clear()
Removes all elements.
Definition classarray.h:211
double memFactor
memory extension factor.
Definition classarray.h:76
Nonzero< R > & last()
Reference to last element.
Definition classarray.h:97
int size() const
Returns number of elements.
Definition classarray.h:217
Safe arrays of data objects.
Definition dataarray.h:75
bool isConsistent() const
consistency check
Definition dataarray.h:311
T * get_ptr()
get a C pointer to the data.
Definition dataarray.h:123
int max() const
return maximum number of elements.
Definition dataarray.h:256
void reMax(int newMax=1, int newSize=-1)
reset maximum number of elements.
Definition dataarray.h:271
void append(const T &t)
append element t.
Definition dataarray.h:134
void clear()
remove all elements.
Definition dataarray.h:221
void remove(int n=0, int m=1)
remove m elements starting at n.
Definition dataarray.h:202
T & last()
reference last element.
Definition dataarray.h:110
int size() const
return nr. of elements.
Definition dataarray.h:227
Entry identifier class for items of a DataSet.
Definition datakey.h:56
SVectorBase with prev/next pointers.
Definition svsetbase.h:92
DLPSV()
Default constructor.
Definition svsetbase.h:111
DLPSV * thenext
next SVectorBase
Definition svsetbase.h:99
DLPSV *const & prev() const
Previous SVectorBase.
Definition svsetbase.h:155
DLPSV *& prev()
Previous SVectorBase.
Definition svsetbase.h:161
DLPSV *const & next() const
Next SVectorBase.
Definition svsetbase.h:149
DLPSV * theprev
previous SVectorBase
Definition svsetbase.h:100
DLPSV *& next()
Next SVectorBase.
Definition svsetbase.h:143
DLPSV & operator=(DLPSV &&rhs)
Definition svsetbase.h:124
DLPSV(const DLPSV &copy)
Copy constructor.
Definition svsetbase.h:116
Sparse vector set.
Definition svsetbase.h:73
void add2(SVectorBase< R > &svec, int n, const int idx[], const S val[])
Adds n nonzeros to svec of this SVSetBase.
Definition svsetbase.h:617
void countUnusedMem()
count size of unused memory exactly
Definition svsetbase.h:193
void remove(int removenum)
Removes the vector with number removenum from the set.
Definition svsetbase.h:641
bool has(int n) const
True iff SVSetBase contains a SVectorBase for vector number n.
Definition svsetbase.h:827
void updateUnusedMemEstimation(int change)
update estimation of unused memory
Definition svsetbase.h:213
void remove(const DataKey keys[], int n, int *perm)
Definition svsetbase.h:697
void add(const SVectorBase< R > svec[], int n)
Adds all n SVectorBases in the array svec to the set.
Definition svsetbase.h:389
void add(const SVSetBase< S > &pset)
Adds all SVectorBases in pset to SVSetBase.
Definition svsetbase.h:423
int numUnusedMemUpdates
counter for how often unusedMem has been updated since last exact value
Definition svsetbase.h:176
SVectorBase< R > * create(DataKey &nkey, int idxmax=-1)
Creates new SVectorBase in set.
Definition svsetbase.h:498
void remove(const DataKey &removekey)
Removes the vector with key removekey from the set.
Definition svsetbase.h:632
double factor
sparse vector memory enlargment factor
Definition svsetbase.h:184
void xtend(SVectorBase< R > &svec, int newmax)
Extends svec to fit newmax nonzeros.
Definition svsetbase.h:510
IdList< DLPSV > list
doubly linked list for non-zero management
Definition svsetbase.h:174
void remove(const DataKey keys[], int n)
Removes n SVectorBases from set.
Definition svsetbase.h:681
bool isConsistent() const
Consistency check.
Definition svsetbase.h:965
void ensureMem(int n, bool shortenLast=true)
Provides enough nonzero memory for n more Nonzeros.
Definition svsetbase.h:234
void add2(SVectorBase< R > &svec, int idx, R val)
Adds nonzero (idx, val) to svec of this SVSetBase.
Definition svsetbase.h:592
void ensurePSVec(int n)
Provides enough vector memory for n more SVectorBases.
Definition svsetbase.h:223
const SVectorBase< R > & operator[](int n) const
Gets SVectorBase by number.
Definition svsetbase.h:761
int memSize() const
Used nonzero memory.
Definition svsetbase.h:845
void remove(int perm[])
Removes multiple elements.
Definition svsetbase.h:660
SVectorBase< R > & operator[](int n)
Gets SVectorBase by number, writeable.
Definition svsetbase.h:755
int number(const DataKey &k) const
Gets vector number of DataKey.
Definition svsetbase.h:809
int max() const
Current maximum number of SVectorBases.
Definition svsetbase.h:791
ClassSet< DLPSV > set
set of SVectorBases
Definition svsetbase.h:173
void remove(const int nums[], int n, int *perm)
Definition svsetbase.h:715
int unusedMem
an estimate of the unused memory (the difference of max() and size() summed up over all vectors) due ...
Definition svsetbase.h:175
void deleteVec(DLPSV *ps)
Deleting a vector from the data array and the list.
Definition svsetbase.h:279
SVectorBase< R > & operator[](const DataKey &k)
Gets SVectorBase by DataKey, writeable.
Definition svsetbase.h:767
int number(const SVectorBase< R > *svec) const
Gets vector number of SVectorBase.
Definition svsetbase.h:815
int memMax() const
Length of nonzero memory.
Definition svsetbase.h:851
void memRemax(int newmax)
Reset length of nonzero memory.
Definition svsetbase.h:857
int num() const
Current number of SVectorBases.
Definition svsetbase.h:785
void add(DataKey &nkey, const S *rowValues, const int *rowIndices, int rowSize)
Adds svec to SVSetBase.
Definition svsetbase.h:372
void add2(SVectorBase< R > &svec, int n, const int idx[], const R val[])
Adds n nonzeros to svec of this SVSetBase.
Definition svsetbase.h:604
SVSetBase< R > & operator=(const SVSetBase< R > &rhs)
Assignment operator.
Definition svsetbase.h:1014
bool has(const SVectorBase< R > *svec) const
Is an SVectorBase in the set?
Definition svsetbase.h:833
SVSetBase< R > & operator=(const SVSetBase< S > &rhs)
Assignment operator.
Definition svsetbase.h:1050
bool has(const DataKey &k) const
True iff SVSetBase contains a SVectorBase for DataKey k.
Definition svsetbase.h:821
void add(DataKey nkey[], const SVectorBase< R > svec[], int n)
Adds n SVectorBases to SVSetBase.
Definition svsetbase.h:413
void clear(int minNewSize=-1)
Removes all SVectorBases from set.
Definition svsetbase.h:727
DataKey key(const SVectorBase< R > *svec) const
Gets DataKey of SVectorBase.
Definition svsetbase.h:803
void reMax(int newmax=0)
Resets maximum number of SVectorBases.
Definition svsetbase.h:959
void remove(const int nums[], int n)
Removes n SVectorBases from set.
Definition svsetbase.h:690
void add(DataKey nkey[], const SVSetBase< S > &pset)
Adds all SVectorBases of pset to SVSetBase.
Definition svsetbase.h:449
void memPack()
Garbage collection in nonzero memory.
Definition svsetbase.h:909
DataKey key(int n) const
Gets DataKey of vector number.
Definition svsetbase.h:797
SVectorBase< R > * create(int idxmax=0)
Creates new SVectorBase in set.
Definition svsetbase.h:463
void remove(const SVectorBase< R > *svec)
Removes one SVectorBase from set.
Definition svsetbase.h:649
ClassArray< Nonzero< R > > SVSetBaseArray
Definition svsetbase.h:78
void add(const SVectorBase< R > &svec)
Adds svec to the set.
Definition svsetbase.h:339
void add(DataKey &nkey, const SVectorBase< R > &svec)
Adds svec to SVSetBase.
Definition svsetbase.h:355
const SVectorBase< R > & operator[](const DataKey &k) const
Gets SVectorBase by DataKey.
Definition svsetbase.h:773
Sparse vectors.
Nonzero< R > * mem() const
get pointer to internal memory.
SVectorBase< R > & operator=(const VectorBase< S > &vec)
Assignment operator.
Entry identifier class for items of a DataSet.
Set of data objects.
Generic Real linked list.
Everything should be within this namespace.
Debugging, floating point type and parameter definitions.
#define MSG_DEBUG(x)
Definition spxdefines.h:180
#define MSGinconsistent(name)
Definition spxdefines.h:174
Sparse vectors.