Scippy

SoPlex

Sequential object-oriented simPlex

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 
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  */
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.
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_
DataKey * thekey
DataKey::idx&#39;s of elements.
Definition: dataset.h:117
int thenum
number of elements in DataSet
Definition: dataset.h:120
struct soplex::DataSet::Item * theitem
array of elements in the DataSet
DATA & operator[](const DataKey &k)
Definition: dataset.h:383
DataKey key(int n) const
returns DataKey of n &#39;th element in DataSet.
Definition: dataset.h:418
Entry identifier class for items of a DataSet.
void add(const DATA *items, int n)
adds n elements from items.
Definition: dataset.h:166
Memory allocation routines.
void add(const DataSet< DATA > &set)
adds all elements of set.
Definition: dataset.h:185
T * get_ptr()
get a C pointer to the data.
Definition: dataarray.h:123
Exception classes for SoPlex.
#define SPX_MSG_INCONSISTENT(name)
Definition: spxdefines.h:175
ptrdiff_t reMax(int newmax=0)
resets max() to newmax.
Definition: dataset.h:495
int info
element number. info [0,thesize-1] iff element is used
Definition: dataset.h:109
int number(const DATA *item) const
returns the number of element item in DataSet, throws exception if it doesn&#39;t exist.
Definition: dataset.h:444
bool has(const DATA *item) const
Does item belong to DataSet?
Definition: dataset.h:467
Entry identifier class for items of a DataSet.Every item in a DataSet is assigned a DataKey by which ...
Definition: datakey.h:55
DATA & operator[](int n)
Definition: dataset.h:370
Exception class for out of memory exceptions.This class is derived from the SoPlex exception base cla...
Definition: exceptions.h:79
void spx_alloc(T &p, int n=1)
Allocate memory.
Definition: spxalloc.h:58
Set of data objects.Class DataSet manages of sets of data objects of a template type DATA...
Definition: dataset.h:96
DataSet(const DataSet &old)
copy constructor.
Definition: dataset.h:573
void add(DataKey &newkey, const DATA &item)
adds an element.
Definition: dataset.h:135
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< DATA > & operator=(const DataSet< DATA > &rhs)
assignment operator.
Definition: dataset.h:608
int thesize
highest used element in theitem
Definition: dataset.h:119
void clear()
remove all elements.
Definition: dataset.h:353
bool isConsistent() const
consistency check.
Definition: dataset.h:516
DataKey key(const DATA *item) const
returns DataKey of element item in DataSet.
Definition: dataset.h:425
int firstfree
first unused element in theitem
Definition: dataset.h:121
void spx_realloc(T &p, int n)
Change amount of allocated memory.
Definition: spxalloc.h:90
Exception base class.This class implements a base class for our SoPlex exceptions We provide a what()...
Definition: exceptions.h:41
Everything should be within this namespace.
~DataSet()
destructor.
Definition: dataset.h:648
bool has(const DataKey &k) const
Is k a valid DataKey of an element in DataSet?
Definition: dataset.h:455
DataSet(int pmax=8)
default constructor.
Definition: dataset.h:547
void add(DataKey newkey[], const DataSet< DATA > &set)
adds several new items.
Definition: dataset.h:176
Save arrays of arbitrary types.
int size() const
returns the maximum DataKey::idx currently in DataSet.
Definition: dataset.h:412
const DATA & operator[](const DataKey &k) const
returns element with DataKey k.
Definition: dataset.h:389
int max() const
returns maximum number of elements that would fit into DataSet.
Definition: dataset.h:400
int number(const DataKey &k) const
returns the number of the element with DataKey k in DataSet or -1, if it doesn&#39;t exist.
Definition: dataset.h:433
DATA * create(DataKey &newkey)
creates new data element in DataSet.
Definition: dataset.h:196
DATA data
data element
Definition: dataset.h:108
Save arrays of data objects.
void add(const DATA &item)
adds element item.
Definition: dataset.h:146
int num() const
returns number of elements currently in DataSet.
Definition: dataset.h:406
int idx
(locally) unique key index
Definition: datakey.h:65
void spx_free(T &p)
Release memory.
Definition: spxalloc.h:121
const DATA & operator[](int n) const
returns element number n.
Definition: dataset.h:376
void add(DataKey newkey[], const DATA *item, int n)
add several items.
Definition: dataset.h:156
int themax
length of arrays theitem and thekey
Definition: dataset.h:118