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>() 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