Scippy

SoPlex

Sequential object-oriented simPlex

IsList< T > Class Template Reference

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. 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=0, const T *end=0) 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=0, T *plast=0, bool pDestroyElements=false)
 default constructor. More...
 
 ~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...
 

Detailed Description

template<class T>
class soplex::IsList< T >

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.

Definition at line 112 of file islist.h.

Member Typedef Documentation

◆ Element

typedef IsElement<T> Element

Definition at line 121 of file islist.h.

Constructor & Destructor Documentation

◆ IsList()

IsList ( T *  pfirst = 0,
T *  plast = 0,
bool  pDestroyElements = false 
)
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 455 of file islist.h.

◆ ~IsList()

~IsList ( )

destructor

Definition at line 470 of file islist.h.

Member Function Documentation

◆ append() [1/2]

void append ( T *  elem)

appends elem to IsList.

Definition at line 127 of file islist.h.

◆ append() [2/2]

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 169 of file islist.h.

◆ clear()

void clear ( bool  pDestroyElements = false)

removes all elements from an IsList.

Definition at line 295 of file islist.h.

Referenced by SVSetBase< Rational >::clear().

◆ find()

int find ( const T *  elem) const

returns the position of element elem within IsList.

Definition at line 361 of file islist.h.

Referenced by IsList< soplex::SVSetBase::DLPSV >::sublist().

◆ first()

T* first ( ) const

returns the IsList's first element.

Definition at line 317 of file islist.h.

Referenced by IsList< soplex::SVSetBase::DLPSV >::insert().

◆ insert() [1/2]

void insert ( T *  elem,
T *  after 
)

inserts elem to IsList after its element after.

Definition at line 149 of file islist.h.

◆ insert() [2/2]

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 201 of file islist.h.

◆ isConsistent()

bool isConsistent ( ) const

consistency check.

Definition at line 427 of file islist.h.

Referenced by IdList< soplex::SVSetBase::DLPSV >::isConsistent().

◆ last()

T* last ( ) const

returns the IsList's last element.

Definition at line 323 of file islist.h.

Referenced by IsList< soplex::SVSetBase::DLPSV >::insert().

◆ length()

int length ( ) const

returns the number of elements in IsList.

Definition at line 343 of file islist.h.

◆ move()

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 412 of file islist.h.

Referenced by IdList< soplex::SVSetBase::DLPSV >::move().

◆ next()

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 337 of file islist.h.

◆ prepend() [1/2]

void prepend ( T *  elem)

prepends elem to IsList.

Definition at line 138 of file islist.h.

◆ prepend() [2/2]

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 185 of file islist.h.

◆ remove() [1/2]

void remove ( const T *  elem)

removes element elem from an IsList.

Definition at line 234 of file islist.h.

◆ remove() [2/2]

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 265 of file islist.h.

◆ remove_next()

void remove_next ( T *  after)

removes the successor of after from an IsList.

Definition at line 220 of file islist.h.

◆ sublist()

IsList<T> sublist ( const T *  start = 0,
const T *  end = 0 
) 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 380 of file islist.h.

Member Data Documentation

◆ destroyElements

bool destroyElements
protected

should the destructor be called for each element when the list is destroyed?

Definition at line 117 of file islist.h.

◆ the_first

◆ the_last