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