SoPlex Documentation
Loading...
Searching...
No Matches
classset.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 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
43namespace 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*/
93template<class T>
95{
96protected:
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
120public:
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 */
194 {
195 assert(num() < max());
196
197 if(firstfree != -themax - 1)
198 {
199 newkey.idx = -firstfree - 1;
201 }
202 else
203 newkey.idx = thesize++;
204
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 */
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.
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 {
250 --thesize;
251 }
252
253 --thenum;
254
255 if(removenum != thenum)
256 {
259 }
260 }
261 }
262
263 /// removes element with key \p removekey.
265 {
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 ///
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
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 */
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
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
522
523 theitem = newMem;
524 themax = newmax;
525
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
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 {
582 }
583 catch(const SPxMemoryException& x)
584 {
586 throw x;
587 }
588
590 }
591
592 /// copy constructor.
594 : theitem(0)
595 , thekey(0)
596 , themax(old.themax)
598 , thenum(old.thenum)
599 {
600 firstfree = (old.firstfree == -old.themax - 1)
601 ? -themax - 1
602 : old.firstfree;
603
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 {
619 }
620 catch(const SPxMemoryException& x)
621 {
623 throw x;
624 }
625
626 memcpy(thekey, old.thekey, themax * sizeof(*thekey));
627
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 */
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
671 }
672
673 return *this;
674 }
675
676 /// destructor.
678 {
679 if(theitem)
681
682 if(thekey)
684 }
685 ///@}
686};
687
688} // namespace soplex
689#endif // _CLASSSET_H_
Save arrays of arbitrary types.
Save arrays of data objects.
Set of class objects.
Definition classset.h:95
void remove(const int *nums, int n)
remove n elements with numbers nums.
Definition classset.h:343
ClassSet(const ClassSet &old)
copy constructor.
Definition classset.h:593
T * create(DataKey &newkey)
creates new class element in ClassSet.
Definition classset.h:193
void remove(int removenum)
removes the removenum 'th element.
Definition classset.h:238
bool has(int n) const
Is n a valid number of an element in ClassSet?
Definition classset.h:458
ClassSet(int pmax=8)
default constructor.
Definition classset.h:563
void remove(const DataKey &removekey)
removes element with key removekey.
Definition classset.h:264
void remove(const DataKey *keys, int n)
remove n elements given by keys.
Definition classset.h:324
bool isConsistent() const
consistency check.
Definition classset.h:532
T & operator[](int n)
Definition classset.h:367
struct soplex::ClassSet::Item * theitem
array of elements in the ClassSet
int themax
length of arrays theitem and thekey
Definition classset.h:114
void add(const ClassSet< T > &set)
adds all elements of set.
Definition classset.h:182
void add(DataKey newkey[], const ClassSet< T > &set)
adds several new items.
Definition classset.h:173
void add(DataKey &newkey, const T &item)
adds an element.
Definition classset.h:131
int number(const T *item) const
returns the number of element item in ClassSet, throws exception if it doesn't exist.
Definition classset.h:441
void remove(int perm[])
remove multiple elements.
Definition classset.h:274
T & operator[](const DataKey &k)
Definition classset.h:380
int firstfree
first unused element in theitem
Definition classset.h:117
const T & operator[](const DataKey &k) const
returns element with DataKey k.
Definition classset.h:386
int number(const DataKey &k) const
returns the number of the element with DataKey k in ClassSet or -1, if it doesn't exist.
Definition classset.h:430
void add(DataKey newkey[], const T *item, int n)
add several items.
Definition classset.h:153
int max() const
returns maximum number of elements that would fit into ClassSet.
Definition classset.h:397
DataKey key(const T *item) const
returns DataKey of element item in ClassSet.
Definition classset.h:422
ptrdiff_t reMax(int newmax=0)
resets max() to newmax.
Definition classset.h:492
T * create()
creates new (uninitialized) class element in ClassSet.
Definition classset.h:214
void add(const T &item)
adds element item.
Definition classset.h:142
int num() const
returns number of elements currently in ClassSet.
Definition classset.h:403
int thesize
highest used element in theitem
Definition classset.h:115
bool has(const T *item) const
Does item belong to ClassSet?
Definition classset.h:464
bool has(const DataKey &k) const
Is k a valid DataKey of an element in ClassSet?
Definition classset.h:452
DataKey * thekey
DataKey::idx's of elements.
Definition classset.h:113
void add(const T *items, int n)
adds n elements from items.
Definition classset.h:163
void clear()
remove all elements.
Definition classset.h:350
const T & operator[](int n) const
returns element number n.
Definition classset.h:373
DataKey key(int n) const
returns DataKey of n 'th element in ClassSet.
Definition classset.h:415
void remove(const DataKey *keys, int n, int *perm)
remove n elements given by keys and perm.
Definition classset.h:311
int thenum
number of elements in ClassSet
Definition classset.h:116
ClassSet< T > & operator=(const ClassSet< T > &rhs)
assignment operator.
Definition classset.h:637
~ClassSet()
destructor.
Definition classset.h:677
int size() const
returns the maximum DataKey::idx currently in ClassSet.
Definition classset.h:409
void remove(const int *nums, int n, int *perm)
remove n elements given by nums and perm.
Definition classset.h:330
Safe arrays of data objects.
Definition dataarray.h:75
T * get_ptr()
get a C pointer to the data.
Definition dataarray.h:123
Entry identifier class for items of a DataSet.
Definition datakey.h:56
int idx
(locally) unique key index
Definition datakey.h:65
Exception base class.
Definition exceptions.h:42
Exception class for out of memory exceptions.
Definition exceptions.h:80
Save arrays of data objects.
Entry identifier class for items of a DataSet.
Exception classes for SoPlex.
Everything should be within this namespace.
void spx_realloc(T &p, int n)
Change amount of allocated memory.
Definition spxalloc.h:90
void spx_free(T &p)
Release memory.
Definition spxalloc.h:121
void spx_alloc(T &p, int n=1)
Allocate memory.
Definition spxalloc.h:58
Memory allocation routines.
#define SPX_MSG_INCONSISTENT(name)
Definition spxdefines.h:175
int info
element number. info [0,thesize-1] iff element is used
Definition classset.h:105
Sparse vectors.