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   	
43   	namespace 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   	*/
93   	template<class T>
94   	class ClassSet
95   	{
96   	protected:
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  	
120  	public:
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  	    */
193  	   T* create(DataKey& newkey)
194  	   {
195  	      assert(num() < max());
196  	
197  	      if(firstfree != -themax - 1)
198  	      {
199  	         newkey.idx = -firstfree - 1;
200  	         firstfree = theitem[newkey.idx].info;
201  	      }
202  	      else
203  	         newkey.idx = thesize++;
204  	
205  	      thekey[thenum] = newkey;
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  	    */
214  	   T* create()
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.
238  	   void remove(int removenum)
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  	         {
249  	            firstfree = theitem[ -firstfree - 1].info;
250  	            --thesize;
251  	         }
252  	
253  	         --thenum;
254  	
255  	         if(removenum != thenum)
256  	         {
257  	            thekey[removenum] = thekey[thenum];
258  	            theitem[thekey[removenum].idx].info = removenum;
259  	         }
260  	      }
261  	   }
262  	
263  	   /// removes element with key \p removekey.
264  	   void remove(const DataKey& removekey)
265  	   {
266  	      remove(number(removekey));
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  	   ///
380  	   T& operator[](const DataKey& k)
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  	
445  	      if(idx < 0 || idx >= size())
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  	    */
492  	   ptrdiff_t reMax(int newmax = 0)
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  	
505  	      spx_alloc(newMem, newmax);
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  	
521  	      spx_free(theitem);
522  	
523  	      theitem = newMem;
524  	      themax = newmax;
525  	
526  	      spx_realloc(thekey,  themax);
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  	
573  	      spx_alloc(theitem, themax);
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  	      {
581  	         spx_alloc(thekey, themax);
582  	      }
583  	      catch(const SPxMemoryException& x)
584  	      {
585  	         spx_free(theitem);
586  	         throw x;
587  	      }
588  	
589  	      assert(isConsistent());
590  	   }
591  	
592  	   /// copy constructor.
593  	   ClassSet(const ClassSet& old)
594  	      : theitem(0)
595  	      , thekey(0)
596  	      , themax(old.themax)
597  	      , thesize(old.thesize)
598  	      , thenum(old.thenum)
599  	   {
600  	      firstfree = (old.firstfree == -old.themax - 1)
601  	                  ? -themax - 1
602  	                  : old.firstfree;
603  	
604  	      spx_alloc(theitem, themax);
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  	      {
618  	         spx_alloc(thekey, themax);
619  	      }
620  	      catch(const SPxMemoryException& x)
621  	      {
622  	         spx_free(theitem);
623  	         throw x;
624  	      }
625  	
626  	      memcpy(thekey,  old.thekey,  themax * sizeof(*thekey));
627  	
628  	      assert(isConsistent());
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  	    */
637  	   ClassSet < T >& operator=(const ClassSet < T >& rhs)
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  	
670  	         assert(isConsistent());
671  	      }
672  	
673  	      return *this;
674  	   }
675  	
676  	   /// destructor.
677  	   ~ClassSet()
678  	   {
679  	      if(theitem)
680  	         spx_free(theitem);
681  	
682  	      if(thekey)
683  	         spx_free(thekey);
684  	   }
685  	   ///@}
686  	};
687  	
688  	} // namespace soplex
689  	#endif // _CLASSSET_H_
690