Scippy

SoPlex

Sequential object-oriented simPlex

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