SoPlex
Sequential object-oriented simPlex
Sequential object-oriented simPlex
Generic single linked list. More...
#include <islist.h>
Public Types | |
| typedef IsElement< T > | Element |
Public Member Functions | |
Extension | |
| void | append (T *elem) |
appends elem to IsList. More... | |
| void | prepend (T *elem) |
prepends elem to IsList. More... | |
| void | insert (T *elem, T *after) |
inserts elem to IsList after its element after. More... | |
| void | append (IsList< T > &list) |
appends all elements of list to IsList. More... | |
| void | prepend (IsList< T > &list) |
prepends all elements of list to IsList. More... | |
| void | insert (IsList< T > &list, T *after) |
inserts all elements of list after element after of an IsList. More... | |
Removal | |
| void | remove_next (T *after) |
removes the successor of after from an IsList. More... | |
| void | remove (const T *elem) |
removes element elem from an IsList. More... | |
| void | remove (IsList< T > &list) |
removes all elements of list from an IsList. More... | |
| void | clear (bool pDestroyElements=false) |
| removes all elements from an IsList. More... | |
Access | |
| T * | first () const |
| returns the IsList's first element. More... | |
| T * | last () const |
| returns the IsList's last element. More... | |
| T * | next (const T *elem) const |
returns successor of elem in an IsList. More... | |
| int | length () const |
| returns the number of elements in IsList. More... | |
| int | find (const T *elem) const |
returns the position of element elem within IsList. More... | |
| IsList< T > | sublist (const T *start=nullptr, const T *end=nullptr) const |
| constructs sublist of an IsList. More... | |
Miscellaneous | |
| void | move (ptrdiff_t delta) |
| adjusts list pointers to a new memory address. More... | |
| bool | isConsistent () const |
| consistency check. More... | |
Constructors / Destructors | |
| IsList (T *pfirst=nullptr, T *plast=nullptr, bool pDestroyElements=false) | |
| default constructor. More... | |
| IsList (const IsList< T > &)=delete | |
| Assignment operator and copy constructor should be deleted to avoid memory problems. More... | |
| IsList< T > & | operator= (const IsList< T > &old)=delete |
| ~IsList () | |
| destructor More... | |
Protected Attributes | |
| T * | the_first |
| the first element in the IsList. More... | |
| T * | the_last |
| the last element in the IsList. More... | |
| bool | destroyElements |
| should the destructor be called for each element when the list is destroyed? More... | |
Generic single linked list.
Class IsList implements an intrusive single linked list of elements of a template class T. As an intrusive list, the objects of type T must provide methods next() for setting and inquiring a pointer to the next element in a list. The user is responsible for not modifying the next() pointer of elements currently residing in a list, which may destroy the lists integrity. For this, class IsList provides enough methods for modifying a list in a save way. See the method list for a description.
|
explicit |
default constructor.
The default constructor may be used to setup a (sub-)list, by specifying a first and last element. Then last must be a successor of first.
Definition at line 464 of file islist.h.
References IsList< T >::find(), and IsList< T >::isConsistent().
Assignment operator and copy constructor should be deleted to avoid memory problems.
| ~IsList | ( | ) |
destructor
Definition at line 483 of file islist.h.
References IsList< T >::clear(), and IsList< T >::destroyElements.
| void append | ( | IsList< T > & | list | ) |
appends all elements of list to IsList.
Appending one list to another keeps the appended list. Instead, list remains an own IsList which is then part of the concatenated list. This means that modifying list will modify the concateneted list as well and vice versa. The programmer is responsible for such changes not to yield inconsistent lists.
Definition at line 178 of file islist.h.
References IsList< T >::append(), IsList< T >::the_first, and IsList< T >::the_last.
| void append | ( | T * | elem | ) |
appends elem to IsList.
Definition at line 136 of file islist.h.
References IsList< T >::the_first, and IsList< T >::the_last.
Referenced by IsList< T >::append(), and IsList< T >::insert().
| void clear | ( | bool | pDestroyElements = false | ) |
removes all elements from an IsList.
Definition at line 304 of file islist.h.
References IsList< T >::next(), soplex::spx_free(), IsList< T >::the_first, and IsList< T >::the_last.
Referenced by IsList< T >::~IsList().
| int find | ( | const T * | elem | ) | const |
returns the position of element elem within IsList.
Definition at line 370 of file islist.h.
References IsList< T >::next(), and IsList< T >::the_first.
Referenced by IdList< T >::insert(), IsList< T >::insert(), IsList< T >::isConsistent(), IsList< T >::IsList(), IdList< T >::remove(), IsList< T >::remove(), IsList< T >::remove_next(), and IsList< T >::sublist().
| T * first | ( | ) | const |
returns the IsList's first element.
Definition at line 326 of file islist.h.
References IsList< T >::the_first.
Referenced by IsList< T >::insert(), IsList< T >::isConsistent(), IsList< T >::move(), and IsList< T >::remove().
| void insert | ( | IsList< T > & | list, |
| T * | after | ||
| ) |
inserts all elements of list after element after of an IsList.
Inserting one list into another keeps the appended list. Instead, list remains an own IsList which is then part of the concatenated list. This means that modifying list will modify the concateneted list as well and vice versa. The programmer is responsible for such changes not to yield inconsistent lists.
Definition at line 210 of file islist.h.
References IsList< T >::find(), IsList< T >::first(), IsList< T >::last(), IsList< T >::the_first, and IsList< T >::the_last.
| void insert | ( | T * | elem, |
| T * | after | ||
| ) |
inserts elem to IsList after its element after.
Definition at line 158 of file islist.h.
References IsList< T >::append(), IsList< T >::find(), and IsList< T >::the_last.
| bool isConsistent | ( | ) | const |
consistency check.
Definition at line 436 of file islist.h.
References IsList< T >::find(), IsList< T >::first(), IsList< T >::last(), and SPX_MSG_INCONSISTENT.
Referenced by IdList< T >::isConsistent(), and IsList< T >::IsList().
| T * last | ( | ) | const |
returns the IsList's last element.
Definition at line 332 of file islist.h.
References IsList< T >::the_last.
Referenced by IsList< T >::insert(), IsList< T >::isConsistent(), IsList< T >::move(), IsList< T >::remove(), and IsList< T >::remove_next().
| int length | ( | ) | const |
returns the number of elements in IsList.
Definition at line 352 of file islist.h.
References IsList< T >::the_first, and IsList< T >::the_last.
| void move | ( | ptrdiff_t | delta | ) |
adjusts list pointers to a new memory address.
This method is of a rather technical nature. If all list elements are taken form one array of elements, in certain circumstances the user may be forced to realloc this array. As a consequence all next() pointers of the list elements would become invalid. However, all addresses will be changed by a constant offset delta. Then move( delta ) may be called, which adjusts the next() pointers of all elements in the list.
Definition at line 421 of file islist.h.
References IsList< T >::first(), IsList< T >::last(), IsList< T >::next(), IsList< T >::the_first, and IsList< T >::the_last.
Referenced by IdList< T >::move().
| T * next | ( | const T * | elem | ) | const |
returns successor of elem in an IsList.
The successor of elem in a list generally corresponds to the element returned by elem->next(). However, if elem is the last element in an IsList, this method will return 0, whereas elem->next() may yield an arbitrary value. For example, if the current list is actually a sublist of another, larger IsList, elem->next() returns the successor of elem in this larger IsList.
Definition at line 346 of file islist.h.
References IsList< T >::the_last.
Referenced by IsList< T >::clear(), IsList< T >::find(), IsList< T >::move(), and IsList< T >::remove().
| void prepend | ( | IsList< T > & | list | ) |
prepends all elements of list to IsList.
Appending one list to another keeps the appended list. Instead, list remains an own IsList which is then part of the concatenated list. This means that modifying list will modify the concateneted list as well and vice versa. The programmer is responsible for such changes not to yield inconsistent lists.
Definition at line 194 of file islist.h.
References IsList< T >::prepend(), IsList< T >::the_first, and IsList< T >::the_last.
| void prepend | ( | T * | elem | ) |
prepends elem to IsList.
Definition at line 147 of file islist.h.
References IsList< T >::the_first, and IsList< T >::the_last.
Referenced by IsList< T >::prepend().
| void remove | ( | const T * | elem | ) |
removes element elem from an IsList.
Definition at line 243 of file islist.h.
References IsList< T >::next(), IsList< T >::remove_next(), IsList< T >::the_first, and IsList< T >::the_last.
| void remove | ( | IsList< T > & | list | ) |
removes all elements of list from an IsList.
Removing list from an IsList requires list to be part of the IsList. Such a situation can be achieved by previously adding (i.e., appending, inserting or prepending) a list or explicitely constructing a sublist with method sublist().
Definition at line 274 of file islist.h.
References IsList< T >::find(), IsList< T >::first(), IsList< T >::last(), IsList< T >::the_first, and IsList< T >::the_last.
| void remove_next | ( | T * | after | ) |
removes the successor of after from an IsList.
Definition at line 229 of file islist.h.
References IsList< T >::find(), IsList< T >::last(), and IsList< T >::the_last.
Referenced by IsList< T >::remove().
| IsList< T > sublist | ( | const T * | start = nullptr, |
| const T * | end = nullptr |
||
| ) | const |
constructs sublist of an IsList.
Returns a new IsList containing a sublist of an IsList starting with element start and reaching up to element end. Both must be members of the IsList or 0, in which case the first and last element are used, respectively.
Definition at line 389 of file islist.h.
References IsList< T >::find(), IsList< T >::the_first, and IsList< T >::the_last.
|
protected |
should the destructor be called for each element when the list is destroyed?
Definition at line 126 of file islist.h.
Referenced by IsList< T >::~IsList().
|
protected |
the first element in the IsList.
Definition at line 124 of file islist.h.
Referenced by IdList< T >::append(), IsList< T >::append(), IsList< T >::clear(), IsList< T >::find(), IdList< T >::first(), IsList< T >::first(), IsList< T >::insert(), IsList< T >::length(), IdList< T >::move(), IsList< T >::move(), IdList< T >::prepend(), IsList< T >::prepend(), IsList< T >::remove(), IdList< T >::remove(), and IsList< T >::sublist().
|
protected |
the last element in the IsList.
Definition at line 125 of file islist.h.
Referenced by IdList< T >::append(), IsList< T >::append(), IsList< T >::clear(), IdList< T >::insert(), IsList< T >::insert(), IdList< T >::last(), IsList< T >::last(), IsList< T >::length(), IsList< T >::move(), IsList< T >::next(), IdList< T >::prepend(), IsList< T >::prepend(), IsList< T >::remove(), IdList< T >::remove(), IsList< T >::remove_next(), and IsList< T >::sublist().