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  idlist.h
26   	 * @brief Generic Real linked list.
27   	 */
28   	#ifndef _IDLIST_H_
29   	#define _IDLIST_H_
30   	
31   	#include <assert.h>
32   	#include <stddef.h>
33   	
34   	#include "soplex/spxdefines.h"
35   	#include "soplex/islist.h"
36   	
37   	namespace soplex
38   	{
39   	//---------------------------------------------------------------------
40   	//  class IdElement<T>
41   	//---------------------------------------------------------------------
42   	
43   	/**@brief   Elements for \ref soplex::IdList "IdList"s.
44   	   @ingroup Elementary
45   	
46   	   #IdElement%s are derived from the template parameter class T and can hence
47   	   be used as such. The additional methods next() and prev() provide access
48   	   to the links for the list. They may freely be used by the programmer as long
49   	   as an IdElement is not member of a IdList. In this case, the IdList
50   	   controls members next() and prev(). However, IdList should provide
51   	   enough functionality for the user not to require any modification to these
52   	   members.
53   	 */
54   	/* The use of this->the_last and this->the_first instead of just the_last
55   	 * and the_first is bcause the HP aCC Compiler claims that according to the
56   	 * Standard these otherwise could not be seen. And since I was not able to
57   	 * even identify a hint on this in the Draft Standard we just do it, so
58   	 * the HP compiler is happy since it will not hurt the others.
59   	 */
60   	template < class T >
61   	class IdElement : public T
62   	{
63   	   //--------------------------
64   	   /**@name Data */
65   	   ///@{
66   	   IdElement<T>* theprev;   ///< pointer to previous element in the IdList
67   	   IdElement<T>* thenext;   ///< pointer to next element in the IdList
68   	   ///@}
69   	
70   	public:
71   	
72   	   //---------------------------------------
73   	   /**@name Successors and predecessors */
74   	   ///@{
75   	   /// returns the next element in the IdList (writeable).
76   	   IdElement<T>*& next()
77   	   {
78   	      return thenext;
79   	   }
80   	   /// returns the next element in the IdList.
81   	   IdElement<T>* const& next() const
82   	   {
83   	      return thenext;
84   	   }
85   	
86   	   /// returns the previous element in the IdList (writeable).
87   	   IdElement<T>*& prev()
88   	   {
89   	      return theprev;
90   	   }
91   	   /// returns the previous element in the IdList.
92   	   IdElement<T>* const& prev() const
93   	   {
94   	      return theprev;
95   	   }
96   	   ///@}
97   	
98   	   //---------------------------------------
99   	   /**@name Construction / destruction */
100  	   ///@{
101  	   /// default constructor.
102  	   IdElement()
103  	      : theprev(0)
104  	      , thenext(0)
105  	   {}
106  	
107  	   /// copy constructor.
108  	   /** Only the element itself is copied, while the links to the previous and
109  	       the next list element are set to zero pointers.
110  	   */
111  	   IdElement(const T& old)
112  	      : T(old)
113  	      , theprev(0)
114  	      , thenext(0)
115  	   {}
116  	};
117  	
118  	//---------------------------------------------------------------------
119  	//  class IdList<T>
120  	//---------------------------------------------------------------------
121  	
122  	
123  	/**@brief   Generic Real linked list.
124  	   @ingroup Elementary
125  	
126  	   Class IdList implements an intrusive Real linked list as a template
127  	   class.  As such, the list elements must provide the links themselfs. For
128  	   conveniance, we also provide class IdElement that adds both links to an
129  	   arbitrary class as template parameter.
130  	 */
131  	template < class T >
132  	class IdList : public IsList<T>
133  	{
134  	public:
135  	
136  	   //---------------------------------------
137  	   /**@name Access */
138  	   ///@{
139  	   /// returns first element in list.
140  	   T* first() const
141  	   {
142  	      return static_cast<T*>(this->the_first);
143  	   }
144  	
145  	   /// returns last element in list.
146  	   T* last() const
147  	   {
148  	      return static_cast<T*>(this->the_last);
149  	   }
150  	
151  	   /// returns successor of \p elem or 0, if \p elem is the last element.
152  	   T* next(const T* elem) const
153  	   {
154  	      return (elem == last()) ? 0 : elem->next();
155  	   }
156  	
157  	   /// returns predecessor of \p elem or 0, if \p elem is the first element.
158  	   T* prev(const T* elem) const
159  	   {
160  	      return (elem == first()) ? 0 : elem->prev();
161  	   }
162  	   ///@}
163  	
164  	
165  	   //---------------------------------------
166  	   /**@name Extension */
167  	   ///@{
168  	   /// appends \p elem to end of list.
169  	   void append(T* elem)
170  	   {
171  	      if(last())
172  	      {
173  	         last()->next() = elem;
174  	         elem->prev() = last();
175  	      }
176  	      else
177  	         this->the_first = elem;
178  	
179  	      this->the_last = elem;
180  	   }
181  	
182  	   /// prepends \p elem at beginnig of list.
183  	   void prepend(T* elem)
184  	   {
185  	      if(first())
186  	      {
187  	         elem->next() = first();
188  	         first()->prev() = elem;
189  	      }
190  	      else
191  	         this->the_last = elem;
192  	
193  	      this->the_first = elem;
194  	   }
195  	
196  	   /// inserts \p elem after \p after.
197  	   void insert(T* elem, T* after)
198  	   {
199  	      assert(find(after));
200  	
201  	      if(after == last())
202  	         append(elem);
203  	      else
204  	      {
205  	         elem->next() = after->next();
206  	         elem->prev() = after;
207  	         after->next() = elem->next()->prev() = elem;
208  	      }
209  	   }
210  	
211  	   /// appends \p list to end of list.
212  	   void append(IdList<T>& list)
213  	   {
214  	      if(list.first())
215  	      {
216  	         append(list.first());
217  	         this->the_last = list.last();
218  	      }
219  	   }
220  	
221  	   /// prepends \p list at beginnig of list.
222  	   void prepend(IdList<T>& list)
223  	   {
224  	      if(list.first())
225  	      {
226  	         prepend(list.last());
227  	         this->the_first = list.the_first;
228  	      }
229  	   }
230  	
231  	   /// inserts \p list after \p after.
232  	   void insert(IdList<T>& list, T* after)
233  	   {
234  	      assert(find(after));
235  	
236  	      if(list.first())
237  	      {
238  	         list.last()->next() = after->next();
239  	         list.first()->prev() = after;
240  	         after->next() = list.first();
241  	
242  	         if(after == last())
243  	            this->the_last = list.last();
244  	         else
245  	            list.last()->next()->prev() = list.last();
246  	      }
247  	   }
248  	   ///@}
249  	
250  	   //---------------------------------------
251  	   /**@name Removal */
252  	   ///@{
253  	   /// removes element following \p after.
254  	   void remove_next(T* after)
255  	   {
256  	      remove(next(after));
257  	   }
258  	
259  	   /// removes \p elem from list.
260  	   void remove(T* elem)
261  	   {
262  	      if(elem == first())
263  	      {
264  	         this->the_first = next(elem);
265  	
266  	         if(first() == 0)
267  	            this->the_last = 0;
268  	      }
269  	      else if(elem == last())
270  	         this->the_last = elem->prev();
271  	      else
272  	      {
273  	         elem->next()->prev() = elem->prev();
274  	         elem->prev()->next() = elem->next();
275  	      }
276  	   }
277  	
278  	   /// removes sublist \p list.
279  	   void remove(IdList<T>& list)
280  	   {
281  	      if(first() != 0 && list.first() != 0)
282  	      {
283  	         assert(find(list.first()));
284  	         assert(find(list.last()));
285  	
286  	         if(first() == list.first())
287  	         {
288  	            if(last() == list.last())
289  	               this->the_first = this->the_last = 0;
290  	            else
291  	               this->the_first = list.last()->next();
292  	         }
293  	         else if(last() == list.last())
294  	            this->the_last = list.last()->prev();
295  	         else
296  	         {
297  	            T* after = first();
298  	
299  	            for(; after->next() != list.first(); after = after->next())
300  	               ;
301  	
302  	            if(last() == list.last())
303  	               this->the_last = after;
304  	            else
305  	               after->next() = list.last()->next();
306  	         }
307  	      }
308  	   }
309  	   ///@}
310  	
311  	   //---------------------------------------
312  	   /**@name Miscellaneous */
313  	   ///@{
314  	   /// adjusts list pointers to a new memory address.
315  	   /** When all elements have been moved in memory (e.g. because of
316  	       reallocation) with a fixed offset \p delta, the list will be reset
317  	       to the new adresses.
318  	   */
319  	   void move(ptrdiff_t delta)
320  	   {
321  	      if(this->the_first)
322  	      {
323  	         T* elem;
324  	         IsList<T>::move(delta);
325  	
326  	         for(elem = last(); elem; elem = prev(elem))
327  	            if(elem != first())
328  	               elem->prev() = reinterpret_cast<T*>(
329  	                                 reinterpret_cast<char*>(elem->prev()) + delta);
330  	      }
331  	   }
332  	
333  	   /// consistency check.
334  	   bool isConsistent() const
335  	   {
336  	#ifdef ENABLE_CONSISTENCY_CHECKS
337  	      const T* my_first = first();
338  	      const T* my_last  = last();
339  	
340  	      for(const T* it = my_first; it; it = next(it))
341  	      {
342  	         if(it != my_first && it->prev()->next() != it)
343  	            return SPX_MSG_INCONSISTENT("IdList");
344  	
345  	         if(it != my_last && it->next()->prev() != it)
346  	            return SPX_MSG_INCONSISTENT("IdList");
347  	      }
348  	
349  	      return IsList<T>::isConsistent();
350  	#else
351  	      return true;
352  	#endif
353  	   }
354  	   ///@}
355  	
356  	   //---------------------------------------
357  	   /**@name Constructors / Destructors */
358  	   ///@{
359  	   /// default constructor.
360  	   /** The default constructor may also be used to construct a sublist, by
361  	       providing a \p first and a \p last element. Element \p last must be a
362  	       successor of \p first.
363  	    */
364  	   explicit
365  	   IdList(T* pfirst = 0, T* plast = 0, bool pDestroyElements = false)
366  	      : IsList<T>(pfirst, plast, pDestroyElements)
367  	   {
368  	      assert(isConsistent());
369  	   }
370  	   ///@}
371  	};
372  	
373  	} // namespace soplex
374  	#endif // _IDLIST_H_
375