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 classset.h 26 * @brief Set of class objects. 27 */ 28 #ifndef _CLASSSET_H_ 29 #define _CLASSSET_H_ 30 31 32 #include <string.h> 33 #include <assert.h> 34 35 #include "soplex/array.h" 36 #include "soplex/dataarray.h" 37 #include "soplex/classarray.h" 38 #include "soplex/datakey.h" 39 #include "soplex/spxalloc.h" 40 #include "soplex/exceptions.h" 41 #include "soplex/svectorbase.h" 42 43 namespace soplex 44 { 45 /**@class ClassSet 46 @brief Set of class objects. 47 @ingroup Elementary 48 49 Class ClassSet manages of sets of class objects of a 50 template type T. For constructing a ClassSet the maximum number 51 of entries must be given. The current maximum number may be inquired 52 with method max(). 53 54 Adding more then max() elements to a ClassSet will core dump. However, 55 method reMax() allows to reset max() without loss of elements currently 56 in the ClassSet. The current number of elements in a ClassSet is returned 57 by method num(). 58 59 Adding elements to a ClassSet is done via methods add() or create(), 60 while remove() removes elements from a ClassSet. When adding an element 61 to a ClassSet the new element is assigned a DataKey. DataKeys serve to 62 access CLASS elements in a set via a version of the subscript 63 operator[](DataKey). 64 65 For convenience all elements in a ClassSet are implicitely numbered 66 from 0 through num()-1 and can be accessed with these numbers 67 using a 2nd subscript operator[](int). The reason for providing 68 DataKeys to access elements of a ClassSet is that the Key of an 69 element remains unchanged as long as the element is a member of the 70 ClassSet, while the numbers will change in an undefined way, if 71 other elements are added to or removed from the ClassSet. 72 73 The elements in a ClassSet and their DataKeys are stored in two arrays: 74 - theitem keeps the objects along with their number stored in item. 75 - thekey keeps the DataKey::idx's of the elements in a ClassSet. 76 77 Both arrays have size themax. 78 79 In #thekey only elements 0 thru thenum-1 contain DataKey::idx%'s of 80 valid elements, i.e., elements currently in the ClassSet. 81 The current number of elements in the ClassSet is counted in thenum. 82 83 In #theitem only elements 0 thru thesize-1 are used, but only some of 84 them actually contain real class elements of the ClassSet. They are 85 recognized by having info >= 0, which gives the number of that 86 element. Otherwise info < 0 indicates an unused element. Unused 87 elements are linked in a single linked list: starting with element 88 <tt>-firstfree-1</tt>, the next free element is given by 89 <tt>-info-1.</tt> The last free element in the list is marked by 90 <tt>info == -themax-1.</tt> Finally all elements in theitem with 91 <tt>index >= thesize</tt> are unused as well. 92 */ 93 template<class T> 94 class ClassSet 95 { 96 protected: 97 98 //----------------------------------- 99 /**@name Types */ 100 ///@{ 101 /// 102 struct Item 103 { 104 T data; ///< T element 105 int info; ///< element number. info \f$\in\f$ [0,thesize-1] 106 ///< iff element is used 107 }* theitem; ///< array of elements in the ClassSet 108 ///@} 109 110 //----------------------------------- 111 /**@name Data */ 112 ///@{ 113 DataKey* thekey; ///< DataKey::idx's of elements 114 int themax; ///< length of arrays theitem and thekey 115 int thesize; ///< highest used element in theitem 116 int thenum; ///< number of elements in ClassSet 117 int firstfree; ///< first unused element in theitem 118 ///@} 119 120 public: 121 122 //----------------------------------- 123 /**@name Extension 124 * Whenever a new element is added to a ClassSet, the latter assigns it a 125 * DataKey. For this all methods that extend a ClassSet by one ore more 126 * elements are provided with two signatures, one of them having a 127 * parameter for returning the assigned DataKey(s). 128 */ 129 ///@{ 130 /// adds an element. 131 void add(DataKey& newkey, const T& item) 132 { 133 T* newelem = create(newkey); 134 135 assert(newelem != 0); 136 137 *newelem = item; 138 } 139 /// adds element \p item. 140 /**@return 0 on success and non-zero, if an error occured. 141 */ 142 void add(const T& item) 143 { 144 T* newelem = create(); 145 146 147 assert(newelem != 0); 148 149 *newelem = item; 150 } 151 152 /// add several items. 153 void add(DataKey newkey[], const T* item, int n) 154 { 155 assert(n >= 0); 156 assert(num() + n <= max()); 157 158 for(int i = 0; i < n; ++i) 159 add(newkey[i], item[i]); 160 } 161 162 /// adds \p n elements from \p items. 163 void add(const T* items, int n) 164 { 165 assert(n >= 0); 166 assert(num() + n <= max()); 167 168 for(int i = 0; i < n; ++i) 169 add(items[i]); 170 } 171 172 /// adds several new items. 173 void add(DataKey newkey[], const ClassSet < T >& set) 174 { 175 assert(num() + set.num() <= max()); 176 177 for(int i = 0; i < set.num(); ++i) 178 add(newkey[i], set[i]); 179 } 180 181 /// adds all elements of \p set. 182 void add(const ClassSet < T >& set) 183 { 184 assert(num() + set.num() <= max()); 185 186 for(int i = 0; i < set.num(); ++i) 187 add(set[i]); 188 } 189 190 /// creates new class element in ClassSet. 191 /**@return Pointer to the newly created element. 192 */ 193 T* create(DataKey& newkey) 194 { 195 assert(num() < max()); 196 197 if(firstfree != -themax - 1) 198 { 199 newkey.idx = -firstfree - 1; 200 firstfree = theitem[newkey.idx].info; 201 } 202 else 203 newkey.idx = thesize++; 204 205 thekey[thenum] = newkey; 206 theitem[newkey.idx].info = thenum; 207 ++thenum; 208 209 return &(theitem[newkey.idx].data); 210 } 211 /// creates new (uninitialized) class element in ClassSet. 212 /**@return Pointer to the newly created element. 213 */ 214 T* create() 215 { 216 DataKey tmp; 217 return create(tmp); 218 } 219 ///@} 220 221 //----------------------------------- 222 /**@name Shrinkage 223 * When elements are removed from a ClassSet, the remaining ones are 224 * renumbered from 0 through the new size()-1. How this renumbering is 225 * performed will not be revealed, since it might be target of future 226 * changes. However, some methods provide a parameter 227 * <tt>int* perm</tt>, which 228 * returns the new order after the removal: If <tt>perm[i] < 0</tt>, 229 * the element numbered i prior to the removal operation has been removed 230 * from the set. Otherwise, <tt>perm[i] = j >= 0</tt> means that the 231 * element with number i prior to the removal operation has been 232 * renumbered to j. Removing a single element from a ClassSet yields a 233 * simple renumbering of the elements: The last element in the set 234 * (i.e., element num()-1) is moved to the index of the removed element. 235 */ 236 ///@{ 237 /// removes the \p removenum 'th element. 238 void remove(int removenum) 239 { 240 if(has(removenum)) 241 { 242 int idx = thekey[removenum].idx; 243 244 theitem[idx].info = firstfree; 245 firstfree = -idx - 1; 246 247 while(-firstfree == thesize) 248 { 249 firstfree = theitem[ -firstfree - 1].info; 250 --thesize; 251 } 252 253 --thenum; 254 255 if(removenum != thenum) 256 { 257 thekey[removenum] = thekey[thenum]; 258 theitem[thekey[removenum].idx].info = removenum; 259 } 260 } 261 } 262 263 /// removes element with key \p removekey. 264 void remove(const DataKey& removekey) 265 { 266 remove(number(removekey)); 267 } 268 269 /// remove multiple elements. 270 /** This method removes all elements for the ClassSet with an 271 * index i such that \p perm[i] < 0. Upon completion, \p perm contains 272 * the new numbering of elements. 273 */ 274 void remove(int perm[]) 275 { 276 int k, j, first = -1; 277 278 // setup permutation and remove items 279 for(k = j = 0; k < num(); ++k) 280 { 281 if(perm[k] >= 0) // j has not been removed ... 282 perm[k] = j++; 283 else 284 { 285 int idx = thekey[k].idx; 286 theitem[idx].info = firstfree; 287 firstfree = -idx - 1; 288 289 if(first < 0) 290 first = k; 291 } 292 } 293 294 if(first >= 0) // move remaining items 295 { 296 for(k = first, j = num(); k < j; ++k) 297 { 298 if(perm[k] >= 0) 299 { 300 thekey[perm[k]] = thekey[k]; 301 theitem[thekey[k].idx].info = perm[k]; 302 thekey[k].idx = -1; 303 } 304 else 305 --thenum; 306 } 307 } 308 } 309 310 /// remove \p n elements given by \p keys and \p perm. 311 void remove(const DataKey* keys, int n, int* perm) 312 { 313 assert(perm != 0); 314 315 for(int i = num() - 1; i >= 0; --i) 316 perm[i] = i; 317 318 while(--n >= 0) 319 perm[number(keys[n])] = -1; 320 321 remove(perm); 322 } 323 /// remove \p n elements given by \p keys. 324 void remove(const DataKey* keys, int n) 325 { 326 DataArray<int> perm(num()); 327 remove(keys, n, perm.get_ptr()); 328 } 329 /// remove \p n elements given by \p nums and \p perm. 330 void remove(const int* nums, int n, int* perm) 331 { 332 assert(perm != 0); 333 334 for(int i = num() - 1; i >= 0; --i) 335 perm[i] = i; 336 337 while(--n >= 0) 338 perm[nums[n]] = -1; 339 340 remove(perm); 341 } 342 /// remove \p n elements with numbers \p nums. 343 void remove(const int* nums, int n) 344 { 345 DataArray<int> perm(num()); 346 remove(nums, n, perm.get_ptr()); 347 } 348 349 /// remove all elements. 350 void clear() 351 { 352 thesize = 0; 353 thenum = 0; 354 firstfree = -themax - 1; 355 } 356 ///@} 357 358 //----------------------------------- 359 /**@name Access 360 * When accessing elements from a ClassSet with one of the index 361 * operators, it must be ensured that the index is valid for the 362 * ClassSet. If this is not known afore, it is the programmers 363 * responsability to ensure this using the inquiry methods below. 364 */ 365 ///@{ 366 /// 367 T& operator[](int n) 368 { 369 assert(n >= 0 && n < thenum); 370 return theitem[thekey[n].idx].data; 371 } 372 /// returns element number \p n. 373 const T& operator[](int n) const 374 { 375 assert(n >= 0 && n < thenum); 376 return theitem[thekey[n].idx].data; 377 } 378 379 /// 380 T& operator[](const DataKey& k) 381 { 382 assert(k.idx < thesize); 383 return theitem[k.idx].data; 384 } 385 /// returns element with DataKey \p k. 386 const T& operator[](const DataKey& k) const 387 { 388 assert(k.idx < thesize); 389 return theitem[k.idx].data; 390 } 391 ///@} 392 393 //----------------------------------- 394 /**@name Inquiry */ 395 ///@{ 396 /// returns maximum number of elements that would fit into ClassSet. 397 int max() const 398 { 399 return themax; 400 } 401 402 /// returns number of elements currently in ClassSet. 403 int num() const 404 { 405 return thenum; 406 } 407 408 /// returns the maximum DataKey::idx currently in ClassSet. 409 int size() const 410 { 411 return thesize; 412 } 413 414 /// returns DataKey of \p n 'th element in ClassSet. 415 DataKey key(int n) const 416 { 417 assert(n >= 0 && n < num()); 418 return thekey[n]; 419 } 420 421 /// returns DataKey of element \p item in ClassSet. 422 DataKey key(const T* item) const 423 { 424 assert(number(item) >= 0); 425 return thekey[number(item)]; 426 } 427 428 /// returns the number of the element with DataKey \p k in ClassSet or -1, 429 /// if it doesn't exist. 430 int number(const DataKey& k) const 431 { 432 if(k.idx < 0 || k.idx >= size()) 433 throw SPxException("Invalid index"); 434 435 return theitem[k.idx].info; 436 } 437 438 /**@todo Please check whether this is correctly implemented! */ 439 /// returns the number of element \p item in ClassSet, 440 /// throws exception if it doesn't exist. 441 int number(const T* item) const 442 { 443 ptrdiff_t idx = reinterpret_cast<const struct Item*>(item) - theitem; 444 445 if(idx < 0 || idx >= size()) 446 throw SPxException("Invalid index"); 447 448 return theitem[idx].info; 449 } 450 451 /// Is \p k a valid DataKey of an element in ClassSet? 452 bool has(const DataKey& k) const 453 { 454 return theitem[k.idx].info >= 0; 455 } 456 457 /// Is \p n a valid number of an element in ClassSet? 458 bool has(int n) const 459 { 460 return (n >= 0 && n < num()); 461 } 462 463 /// Does \p item belong to ClassSet? 464 bool has(const T* item) const 465 { 466 int n; 467 468 try 469 { 470 n = number(item); 471 } 472 catch(...) 473 { 474 return false; 475 } 476 477 return n >= 0; 478 } 479 ///@} 480 481 //----------------------------------- 482 /**@name Miscellaneous */ 483 ///@{ 484 /// resets max() to \p newmax. 485 /** This method will not succeed if \p newmax < size(), in which case 486 * \p newmax == size() will be taken. As generally this method involves 487 * copying the #ClassSet%s elements in memory, reMax() returns the 488 * number of bytes the addresses of elements in the ClassSet have been 489 * moved. Note, that this is identical for all elements in the 490 * ClassSet. 491 */ 492 ptrdiff_t reMax(int newmax = 0) 493 { 494 int i; 495 Item* newMem = 0; 496 newmax = (newmax < size()) ? size() : newmax; 497 498 int* lastfree = &firstfree; 499 500 while(*lastfree != -themax - 1) 501 lastfree = &(theitem[ -1 - *lastfree].info); 502 503 *lastfree = -newmax - 1; 504 505 spx_alloc(newMem, newmax); 506 507 /* call copy constructor for first elements */ 508 for(i = 0; i < max(); i++) 509 { 510 newMem[i].data = std::move(theitem[i].data); 511 newMem[i].info = theitem[i].info; 512 } 513 514 /* call default constructor for remaining elements */ 515 for(; i < newmax; i++) 516 new(&(newMem[i])) Item(); 517 518 /* compute pointer difference */ 519 ptrdiff_t pshift = reinterpret_cast<char*>(newMem) - reinterpret_cast<char*>(theitem); 520 521 spx_free(theitem); 522 523 theitem = newMem; 524 themax = newmax; 525 526 spx_realloc(thekey, themax); 527 528 return pshift; 529 } 530 531 /// consistency check. 532 bool isConsistent() const 533 { 534 #ifdef ENABLE_CONSISTENCY_CHECKS 535 536 if(theitem == 0 || thekey == 0) 537 return SPX_MSG_INCONSISTENT("ClassSet"); 538 539 if(thesize > themax || thenum > themax || thenum > thesize) 540 return SPX_MSG_INCONSISTENT("ClassSet"); 541 542 if(thesize == thenum && firstfree != -themax - 1) 543 return SPX_MSG_INCONSISTENT("ClassSet"); 544 545 if(thesize != thenum && firstfree == -themax - 1) 546 return SPX_MSG_INCONSISTENT("ClassSet"); 547 548 for(int i = 0; i < thenum; ++i) 549 if(theitem[thekey[i].idx].info != i) 550 return SPX_MSG_INCONSISTENT("ClassSet"); 551 552 #endif 553 554 return true; 555 } 556 ///@} 557 558 //----------------------------------- 559 /**@name Constructors / Destructors */ 560 ///@{ 561 /// default constructor. 562 explicit 563 ClassSet(int pmax = 8) 564 : theitem(0) 565 , thekey(0) 566 , themax(pmax < 1 ? 8 : pmax) 567 , thesize(0) 568 , thenum(0) 569 570 { 571 firstfree = -themax - 1; 572 573 spx_alloc(theitem, themax); 574 575 /* call default constructor for each element */ 576 for(int i = 0; i < themax; i++) 577 new(&(theitem[i])) Item(); 578 579 try 580 { 581 spx_alloc(thekey, themax); 582 } 583 catch(const SPxMemoryException& x) 584 { 585 spx_free(theitem); 586 throw x; 587 } 588 589 assert(isConsistent()); 590 } 591 592 /// copy constructor. 593 ClassSet(const ClassSet& old) 594 : theitem(0) 595 , thekey(0) 596 , themax(old.themax) 597 , thesize(old.thesize) 598 , thenum(old.thenum) 599 { 600 firstfree = (old.firstfree == -old.themax - 1) 601 ? -themax - 1 602 : old.firstfree; 603 604 spx_alloc(theitem, themax); 605 606 /* call copy constructor for first elements */ 607 int i; 608 609 for(i = 0; i < old.thenum; i++) 610 new(&(theitem[i])) Item(old.theitem[i]); 611 612 /* call default constructor for remaining elements */ 613 for(; i < old.themax; i++) 614 new(&(theitem[i])) Item(); 615 616 try 617 { 618 spx_alloc(thekey, themax); 619 } 620 catch(const SPxMemoryException& x) 621 { 622 spx_free(theitem); 623 throw x; 624 } 625 626 memcpy(thekey, old.thekey, themax * sizeof(*thekey)); 627 628 assert(isConsistent()); 629 } 630 631 /// assignment operator. 632 /** The assignment operator involves #reMax()%ing the lvalue ClassSet 633 * to the size needed for copying all elements of the rvalue. After the 634 * assignment all DataKeys from the lvalue are valid for the rvalue as 635 * well. They refer to a copy of the corresponding class elements. 636 */ 637 ClassSet < T >& operator=(const ClassSet < T >& rhs) 638 { 639 if(this != &rhs) 640 { 641 int i; 642 643 if(rhs.size() > max()) 644 reMax(rhs.size()); 645 646 clear(); 647 648 for(i = 0; i < rhs.size(); ++i) 649 theitem[i] = std::move(rhs.theitem[i]); 650 651 for(i = 0; i < rhs.num(); ++i) 652 thekey[i] = rhs.thekey[i]; 653 654 if(rhs.firstfree == -rhs.themax - 1) 655 firstfree = -themax - 1; 656 else 657 { 658 firstfree = rhs.firstfree; 659 i = rhs.firstfree; 660 661 while(rhs.theitem[ -i - 1].info != -rhs.themax - 1) 662 i = rhs.theitem[ -i - 1].info; 663 664 theitem[ -i - 1].info = -themax - 1; 665 } 666 667 thenum = rhs.thenum; 668 thesize = rhs.thesize; 669 670 assert(isConsistent()); 671 } 672 673 return *this; 674 } 675 676 /// destructor. 677 ~ClassSet() 678 { 679 if(theitem) 680 spx_free(theitem); 681 682 if(thekey) 683 spx_free(thekey); 684 } 685 ///@} 686 }; 687 688 } // namespace soplex 689 #endif // _CLASSSET_H_ 690