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