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