Scippy

SoPlex

Sequential object-oriented simPlex

islist.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-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 islist.h
26  * @brief Generic single linked list.
27  */
28 #ifndef _ISLIST_H_
29 #define _ISLIST_H_
30 
31 #include <assert.h>
32 #include <stddef.h>
33 #include <iostream>
34 
35 
36 namespace soplex
37 {
38 
39 //---------------------------------------------------------------------
40 // class IsElement<T>
41 //---------------------------------------------------------------------
42 
43 /**@brief Elements for \ref soplex::IsList "IsList"s.
44  @ingroup Elementary
45 
46  Class IsElement allows to easily construct list elements for an intrusive
47  single linked list IsList out of a template class T. It adds a next
48  pointer to each element. An instance of IdElement<T> a can be used just
49  like an instance of T itself, except that method next() has been
50  added (thereby overriding any method next() defined in T).
51  */
52 template < class T >
53 class IsElement : public T
54 {
55 protected:
56 
57  //--------------------------
58  /**@name Data */
59  ///@{
60  IsElement<T>* the_next; ///< pointer to next element in the IsList.
61  ///@}
62 
63 public:
64 
65  //---------------------------------
66  /**@name Successor */
67  ///@{
68  ///
70  {
71  return the_next;
72  }
73  /// returns the next element in the IsList.
74  IsElement<T>* next() const
75  {
76  return the_next;
77  }
78  ///@}
79 
80  //------------------------------------
81  /**@name Constructors / destructors */
82  ///@{
83 
84  /// default constructor.
86  {}
87 
88  ///
89  explicit
90  IsElement(const T& old)
91  : T(old)
92  , the_next(0)
93  {}
94 
95  /// copy constructor.
96  /** Only the element itself is copied, while the link to the next list
97  element is set to a zero pointer.
98  */
99  IsElement(const IsElement<T>& old)
100  : T(old)
101  , the_next(0)
102  {}
103 };
104 
105 //---------------------------------------------------------------------
106 // class IsList<T>
107 //---------------------------------------------------------------------
108 
109 /**@brief Generic single linked list.
110  @ingroup Elementary
111 
112  Class IsList implements an intrusive single linked list of elements of a
113  template class T. As an \em intrusive list, the objects of type T
114  must provide methods next() for setting and inquiring a pointer to the
115  next element in a list. The user is responsible for not modifying the
116  next() pointer of elements currently residing in a list, which may destroy
117  the lists integrity. For this, class IsList provides enough methods for
118  modifying a list in a save way. See the method list for a description.
119  */
120 template < class T >
121 class IsList
122 {
123 protected:
124  T* the_first; ///< the first element in the IsList.
125  T* the_last; ///< the last element in the IsList.
127  ///< should the destructor be called for each element when the list is destroyed?
128 
129 public:
131 
132  //--------------------------
133  /**@name Extension */
134  ///@{
135  /// appends \p elem to IsList.
136  void append(T* elem)
137  {
138  if(the_last)
139  the_last->next() = elem;
140  else
141  the_first = elem;
142 
143  the_last = elem;
144  }
145 
146  /// prepends \p elem to IsList.
147  void prepend(T* elem)
148  {
149  if(the_first)
150  elem->next() = the_first;
151  else
152  the_last = elem;
153 
154  the_first = elem;
155  }
156 
157  /// inserts \p elem to IsList after its element \p after.
158  void insert(T* elem, T* after)
159  {
160  assert(find(after));
161 
162  if(after == the_last)
163  append(elem);
164  else
165  {
166  elem->next() = after->next();
167  after->next() = elem;
168  }
169  }
170 
171  /// appends all elements of \p list to IsList.
172  /** Appending one list to another keeps the appended \p list. Instead,
173  \p list remains an own IsList which is then part of the
174  concatenated list. This means that modifying \p list will modify the
175  concateneted list as well and vice versa. The programmer is
176  responsible for such changes not to yield inconsistent lists.
177  */
178  void append(IsList<T>& list)
179  {
180  if(list.the_first)
181  {
182  append(list.the_first);
183  the_last = list.the_last;
184  }
185  }
186 
187  /// prepends all elements of \p list to IsList.
188  /** Appending one list to another keeps the appended \p list. Instead,
189  \p list remains an own IsList which is then part of the
190  concatenated list. This means that modifying \p list will modify the
191  concateneted list as well and vice versa. The programmer is
192  responsible for such changes not to yield inconsistent lists.
193  */
194  void prepend(IsList<T>& list)
195  {
196  if(list.the_first)
197  {
198  prepend(list.the_last);
199  the_first = list.the_first;
200  }
201  }
202 
203  /// inserts all elements of \p list after element \p after of an IsList.
204  /** Inserting one list into another keeps the appended \p list. Instead,
205  \p list remains an own IsList which is then part of the
206  concatenated list. This means that modifying \p list will modify the
207  concateneted list as well and vice versa. The programmer is
208  responsible for such changes not to yield inconsistent lists.
209  */
210  void insert(IsList<T>& list, T* after)
211  {
212  assert(find(after));
213 
214  if(list.the_first)
215  {
216  list.the_last->next() = after->next();
217  after->next() = list.first();
218 
219  if(after == last())
220  the_last = list.last();
221  }
222  }
223  ///@}
224 
225  //--------------------------
226  /**@name Removal */
227  ///@{
228  /// removes the successor of \p after from an IsList.
229  void remove_next(T* after)
230  {
231  assert(find(after));
232 
233  if(after->next())
234  {
235  if(after->next() == last())
236  the_last = after;
237 
238  after->next() = after->next()->next();
239  }
240  }
241 
242  /// removes element \p elem from an IsList.
243  void remove(const T* elem)
244  {
245  if(the_first)
246  {
247  if(elem == the_first)
248  {
249  the_first = next(elem);
250 
251  if(the_first == 0)
252  the_last = 0;
253  }
254  else
255  {
256  T* after = the_first;
257 
258  for(; after != the_last; after = after->next())
259  if(after->next() == elem)
260  {
261  remove_next(after);
262  return;
263  }
264  }
265  }
266  }
267 
268  /// removes all elements of \p list from an IsList.
269  /** Removing \p list from an IsList requires \p list to be part of the
270  IsList. Such a situation can be achieved by previously adding
271  (i.e., #append%ing, #insert%ing or #prepend%ing) a list or
272  explicitely constructing a sublist with method sublist().
273  */
274  void remove(IsList<T>& list)
275  {
276  if(the_first != 0 && list.the_first != 0)
277  {
278  assert(find(list.first()));
279  assert(find(list.last()));
280 
281  if(the_first == list.the_first)
282  {
283  if(the_last == list.the_last)
284  the_first = the_last = 0;
285  else
286  the_first = list.the_last->next();
287  }
288  else
289  {
290  T* after = the_first;
291 
292  for(; after->next() != list.the_first; after = after->next())
293  ;
294 
295  if(the_last == list.the_last)
296  the_last = after;
297  else
298  after->next() = list.the_last->next();
299  }
300  }
301  }
302 
303  /// removes all elements from an IsList.
304  void clear(bool pDestroyElements = false)
305  {
306  if(pDestroyElements)
307  {
308  T* nextElement;
309 
310  for(T* it = the_first; it; it = nextElement)
311  {
312  nextElement = next(it);
313  it->~T();
314  spx_free(it);
315  }
316  }
317 
318  the_first = the_last = 0;
319  }
320  ///@}
321 
322  //--------------------------
323  /**@name Access */
324  ///@{
325  /// returns the IsList's first element.
326  T* first() const
327  {
328  return the_first;
329  }
330 
331  /// returns the IsList's last element.
332  T* last() const
333  {
334  return the_last;
335  }
336 
337  /// returns successor of \p elem in an IsList.
338  /** The successor of \p elem in a list generally corresponds to the
339  element returned by elem->next(). However, if \p elem is the last
340  element in an IsList, this method will return 0, whereas
341  elem->next() may yield an arbitrary value. For example, if the
342  current list is actually a sublist of another, larger IsList,
343  elem->next() returns the successor of \p elem in this larger
344  IsList.
345  */
346  T* next(const T* elem) const
347  {
348  return (elem == the_last) ? 0 : elem->next();
349  }
350 
351  /// returns the number of elements in IsList.
352  int length() const
353  {
354  int num;
355 
356  if(the_first)
357  {
358  T* test = the_first;
359 
360  for(num = 1; test != the_last; test = test->next())
361  ++num;
362 
363  return num;
364  }
365 
366  return 0;
367  }
368 
369  /// returns the position of element \p elem within IsList.
370  int find(const T* elem) const
371  {
372  const T* test;
373 
374  assert(elem != 0);
375 
376  for(test = the_first; test != 0; test = next(test))
377  if(test == elem)
378  return 1;
379 
380  return 0;
381  }
382 
383  /// constructs sublist of an IsList.
384  /** Returns a new IsList containing a sublist of an IsList starting
385  with element \p start and reaching up to element \p end. Both must be
386  members of the IsList or 0, in which case the first and last
387  element are used, respectively.
388  */
389  IsList<T>sublist(const T* start = 0, const T* end = 0) const
390  {
391  IsList<T>part = *this;
392 
393  if(start)
394  {
395  assert(find(start));
396  part.the_first = const_cast<T*>(start);
397  }
398 
399  if(end)
400  {
401  assert(part.find(end));
402  part.the_last = const_cast<T*>(end);
403  }
404 
405  return part;
406  }
407  ///@}
408 
409  //--------------------------
410  /**@name Miscellaneous */
411  ///@{
412  /// adjusts list pointers to a new memory address.
413  /** This method is of a rather technical nature. If all list elements
414  are taken form one array of elements, in certain circumstances the
415  user may be forced to realloc this array. As a consequence all
416  next() pointers of the list elements would become invalid.
417  However, all addresses will be changed by a constant offset \p delta.
418  Then move( \p delta ) may be called, which adjusts the next()
419  pointers of all elements in the list.
420  */
421  void move(ptrdiff_t delta)
422  {
423  if(the_first)
424  {
425  T* elem;
426  the_last = reinterpret_cast<T*>(reinterpret_cast<char*>(the_last) + delta);
427  the_first = reinterpret_cast<T*>(reinterpret_cast<char*>(the_first) + delta);
428 
429  for(elem = first(); elem; elem = next(elem))
430  if(elem != last())
431  elem->next() = reinterpret_cast<T*>(reinterpret_cast<char*>(elem->next()) + delta);
432  }
433  }
434 
435  /// consistency check.
436  bool isConsistent() const
437  {
438 #ifdef ENABLE_CONSISTENCY_CHECKS
439 
440  if(first() != 0 && last() == 0)
441  return SPX_MSG_INCONSISTENT("IsList");
442 
443  if(first() == 0 && last() != 0)
444  return SPX_MSG_INCONSISTENT("IsList");
445 
446  if(first() && find(last()) == 0)
447  return SPX_MSG_INCONSISTENT("IsList");
448 
449 #endif
450 
451  return true;
452  }
453  ///@}
454 
455  //------------------------------------
456  /**@name Constructors / Destructors */
457  ///@{
458  /// default constructor.
459  /** The default constructor may be used to setup a (sub-)list, by
460  specifying a \p first and \p last element. Then \p last must be a
461  successor of \p first.
462  */
463  explicit
464  IsList(T* pfirst = 0, T* plast = 0, bool pDestroyElements = false)
465  : the_first(pfirst)
466  , the_last(plast)
467  , destroyElements(pDestroyElements)
468  {
469  if(pfirst)
470  {
471  assert(plast != 0);
472  assert(find(plast));
473  }
474 
475  assert(isConsistent());
476  }
477 
478  /// Assignment operator and copy constructor should be deleted to avoid memory problems
479  IsList(const IsList<T>&) = delete;
480  IsList<T>& operator=(const IsList<T>& old) = delete;
481 
482  /// destructor
484  {
485  clear(destroyElements);
486  }
487  ///@}
488 };
489 
490 } // namespace soplex
491 #endif // _ISLIST_H_
void clear(bool pDestroyElements=false)
removes all elements from an IsList.
Definition: islist.h:304
IsElement< T > *& next()
Definition: islist.h:69
T * first() const
returns the IsList&#39;s first element.
Definition: islist.h:326
~IsList()
destructor
Definition: islist.h:483
T * the_last
the last element in the IsList.
Definition: islist.h:125
#define SPX_MSG_INCONSISTENT(name)
Definition: spxdefines.h:175
void move(ptrdiff_t delta)
adjusts list pointers to a new memory address.
Definition: islist.h:421
FMT_CONSTEXPR bool find(Ptr first, Ptr last, T value, Ptr &out)
Definition: format.h:2471
Generic single linked list.Class IsList implements an intrusive single linked list of elements of a t...
Definition: islist.h:121
IsElement< T > Element
Definition: islist.h:130
T * last() const
returns the IsList&#39;s last element.
Definition: islist.h:332
IsElement()
default constructor.
Definition: islist.h:85
IsList(T *pfirst=0, T *plast=0, bool pDestroyElements=false)
default constructor.
Definition: islist.h:464
bool destroyElements
should the destructor be called for each element when the list is destroyed?
Definition: islist.h:126
DLPSV *& next()
Next SVectorBase.
Definition: svsetbase.h:155
int find(const T *elem) const
returns the position of element elem within IsList.
Definition: islist.h:370
void insert(IsList< T > &list, T *after)
inserts all elements of list after element after of an IsList.
Definition: islist.h:210
void prepend(IsList< T > &list)
prepends all elements of list to IsList.
Definition: islist.h:194
void remove_next(T *after)
removes the successor of after from an IsList.
Definition: islist.h:229
Everything should be within this namespace.
IsElement< T > * the_next
pointer to next element in the IsList.
Definition: islist.h:60
T * next(const T *elem) const
returns successor of elem in an IsList.
Definition: islist.h:346
void prepend(T *elem)
prepends elem to IsList.
Definition: islist.h:147
void insert(T *elem, T *after)
inserts elem to IsList after its element after.
Definition: islist.h:158
IsElement(const IsElement< T > &old)
copy constructor.
Definition: islist.h:99
void append(T *elem)
appends elem to IsList.
Definition: islist.h:136
int length() const
returns the number of elements in IsList.
Definition: islist.h:352
IsElement(const T &old)
Definition: islist.h:90
T * the_first
the first element in the IsList.
Definition: islist.h:124
void append(IsList< T > &list)
appends all elements of list to IsList.
Definition: islist.h:178
IsList< T > sublist(const T *start=0, const T *end=0) const
constructs sublist of an IsList.
Definition: islist.h:389
IsElement< T > * next() const
returns the next element in the IsList.
Definition: islist.h:74
bool isConsistent() const
consistency check.
Definition: islist.h:436
void spx_free(T &p)
Release memory.
Definition: spxalloc.h:121
Elements for IsLists.Class IsElement allows to easily construct list elements for an intrusive single...
Definition: islist.h:53