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 ///
69 IsElement<T>*& next()
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.
85 IsElement()
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 >
|
(1) Event rule_of_three_violation: |
Class "soplex::IsList<soplex::SVSetBase<Rational>::DLPSV>" has a user definition for at least one special function (copy constructor, copy assignment, destructor) but not all. If one of these functions requires a user definition then the others likely do as well. |
|
(2) Event remediation: |
Add user-definition for a copy constructor. |
|
(3) Event remediation: |
Add user-definition for a copy assignment operator. |
| Also see events: |
[destructor] |
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.
126 bool destroyElements;
127 ///< should the destructor be called for each element when the list is destroyed?
128
129 public:
130 typedef IsElement<T> Element;
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
483 ~IsList()
484 {
485 clear(destroyElements);
486 }
487 ///@}
488 };
489
490 } // namespace soplex
491 #endif // _ISLIST_H_
492