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