SoPlex Documentation
Loading...
Searching...
No Matches
dataset.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 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
41namespace 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*/
95template<class DATA>
97{
98 static_assert(std::is_trivially_copyable<DATA>::value,
99 "Only trivially copyable types are allowed with DataSet, since it does memcopy");
100protected:
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
124public:
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 */
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
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 */
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.
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 {
262 }
263 }
264 }
265
266 /// removes element with key \p removekey.
268 {
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 ///
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 ///
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
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 */
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;
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 MSGinconsistent("DataSet");
522
523 if(thesize > themax || thenum > themax || thenum > thesize)
524 return MSGinconsistent("DataSet");
525
526 if(thesize == thenum && firstfree != -themax - 1)
527 return MSGinconsistent("DataSet");
528
529 if(thesize != thenum && firstfree == -themax - 1)
530 return MSGinconsistent("DataSet");
531
532 for(int i = 0; i < thenum; ++i)
533 if(theitem[thekey[i].idx].info != i)
534 return MSGinconsistent("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
558
559 try
560 {
562 }
563 catch(const SPxMemoryException& x)
564 {
566 throw x;
567 }
568
570 }
571
572 /// copy constructor.
574 : theitem(0)
575 , thekey(0)
576 , themax(old.themax)
578 , thenum(old.thenum)
579 {
580 firstfree = (old.firstfree == -old.themax - 1)
581 ? -themax - 1
582 : old.firstfree;
583
585
586 try
587 {
589 }
590 catch(const SPxMemoryException& x)
591 {
593 throw x;
594 }
595
596 memcpy(theitem, old.theitem, themax * sizeof(*theitem));
597 memcpy(thekey, old.thekey, themax * sizeof(*thekey));
598
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 */
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
642 }
643
644 return *this;
645 }
646
647 /// destructor.
649 {
650 if(theitem)
652
653 if(thekey)
655 }
656 ///@}
657};
658
659} // namespace soplex
660#endif // _DATASET_H_
Save arrays of arbitrary types.
Safe arrays of data objects.
Definition dataarray.h:75
T * get_ptr()
get a C pointer to the data.
Definition dataarray.h:123
int themax
the length of array data and
Definition dataarray.h:80
int thesize
number of used elements in array data
Definition dataarray.h:79
T * data
the array of elements
Definition dataarray.h:81
int size() const
return nr. of elements.
Definition dataarray.h:227
Entry identifier class for items of a DataSet.
Definition datakey.h:56
int idx
(locally) unique key index
Definition datakey.h:65
Set of data objects.
Definition dataset.h:97
void remove(const int *nums, int n)
remove n elements with numbers nums.
Definition dataset.h:346
void remove(int removenum)
removes the removenum 'th element.
Definition dataset.h:241
DATA * create()
creates new (uninitialized) data element in DataSet.
Definition dataset.h:217
bool has(int n) const
Is n a valid number of an element in DataSet?
Definition dataset.h:461
DataSet(int pmax=8)
default constructor.
Definition dataset.h:547
void remove(const DataKey &removekey)
removes element with key removekey.
Definition dataset.h:267
void remove(const DataKey *keys, int n)
remove n elements given by keys.
Definition dataset.h:327
bool isConsistent() const
consistency check.
Definition dataset.h:516
void add(DataKey newkey[], const DataSet< DATA > &set)
adds several new items.
Definition dataset.h:176
int number(const DATA *item) const
returns the number of element item in DataSet, throws exception if it doesn't exist.
Definition dataset.h:444
void add(DataKey &newkey, const DATA &item)
adds an element.
Definition dataset.h:135
DataSet(const DataSet &old)
copy constructor.
Definition dataset.h:573
int themax
length of arrays theitem and thekey
Definition dataset.h:118
DATA & operator[](int n)
Definition dataset.h:370
~DataSet()
destructor.
Definition dataset.h:648
void add(const DATA *items, int n)
adds n elements from items.
Definition dataset.h:166
void add(const DataSet< DATA > &set)
adds all elements of set.
Definition dataset.h:185
void remove(int perm[])
remove multiple elements.
Definition dataset.h:277
int firstfree
first unused element in theitem
Definition dataset.h:121
DATA * create(DataKey &newkey)
creates new data element in DataSet.
Definition dataset.h:196
int number(const DataKey &k) const
returns the number of the element with DataKey k in DataSet or -1, if it doesn't exist.
Definition dataset.h:433
const DATA & operator[](int n) const
returns element number n.
Definition dataset.h:376
int max() const
returns maximum number of elements that would fit into DataSet.
Definition dataset.h:400
void add(const DATA &item)
adds element item.
Definition dataset.h:146
ptrdiff_t reMax(int newmax=0)
resets max() to newmax.
Definition dataset.h:495
struct soplex::DataSet::Item * theitem
array of elements in the DataSet
int num() const
returns number of elements currently in DataSet.
Definition dataset.h:406
DATA & operator[](const DataKey &k)
Definition dataset.h:383
int thesize
highest used element in theitem
Definition dataset.h:119
bool has(const DataKey &k) const
Is k a valid DataKey of an element in DataSet?
Definition dataset.h:455
DataKey * thekey
DataKey::idx's of elements.
Definition dataset.h:117
bool has(const DATA *item) const
Does item belong to DataSet?
Definition dataset.h:467
void add(DataKey newkey[], const DATA *item, int n)
add several items.
Definition dataset.h:156
void clear()
remove all elements.
Definition dataset.h:353
DataSet< DATA > & operator=(const DataSet< DATA > &rhs)
assignment operator.
Definition dataset.h:608
DataKey key(int n) const
returns DataKey of n 'th element in DataSet.
Definition dataset.h:418
const DATA & operator[](const DataKey &k) const
returns element with DataKey k.
Definition dataset.h:389
void remove(const DataKey *keys, int n, int *perm)
remove n elements given by keys and perm.
Definition dataset.h:314
DataKey key(const DATA *item) const
returns DataKey of element item in DataSet.
Definition dataset.h:425
int thenum
number of elements in DataSet
Definition dataset.h:120
int size() const
returns the maximum DataKey::idx currently in DataSet.
Definition dataset.h:412
void remove(const int *nums, int n, int *perm)
remove n elements given by nums and perm.
Definition dataset.h:333
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 MSGinconsistent(name)
Definition spxdefines.h:174
int info
element number. info [0,thesize-1] iff element is used
Definition dataset.h:109
DATA data
data element
Definition dataset.h:108