Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
frechet::data::LinkedList< T > Class Template Reference

Detailed Description

template<class T>
class frechet::data::LinkedList< T >

An intrusive double-linked list, similar to boost::intrusive.

Link references are stored inside the element objects.

Simplifies a few things:

  • small memory footprint (we don't need element container objects)
  • no iterators are needed: each element contains the information for iterating
  • concatenating two lists is easy

    Major restrictions apply: each element can only be part of one list. Shallow copies are not allowed. The list takes ownership of elements and deletes them on removal.

    The implementation is not thread-safe.

    Iterator methods (first,next,prev,last) are type-safe. but insertions are not type-safe (contrary to boost::intrusive classes).

    Optionally, LinkedList can be circular, i.e. the last element is directly linked to the first element. This property can be modified an run-time.

    Simply use T* for an iterator:

for(T* i = list.first(); i; i = i->next())
...

Modifications to the underlying list do not break the iterator (except when deleting the current object).

Concurrently iterating and deleting should be done like this:

for(T* i = list.first(); i; ) {
if (...)
i = list.remove(i);
else
i = i->next();
}
Template Parameters
Telement type; must derive from BLinkedListElement
Author
Peter Schäfer

Definition at line 252 of file linkedlist.h.

#include <linkedlist.h>

Inherits frechet::data::BLinkedList.

Public Member Functions

 LinkedList ()
 empty constructor; creates an empty list More...
 
 LinkedList (LinkedList &&that)
 move constructor; takes ownership of another list More...
 
template<typename Cloner >
 LinkedList (const LinkedList &that, Cloner cloner)
 deep copy constructor More...
 
LinkedListoperator= (LinkedList &&that)
 move assigment operator More...
 
T * first () const
 
T * last () const
 
T * remove (T *el)
 
T * operator[] (int i) const
 positional lookup (note: O(n), use with care) More...
 
void swap (LinkedList< T > &that)
 exchange all elements with another list, taking ownership of the new elements More...
 
- Public Member Functions inherited from frechet::data::BLinkedList
 BLinkedList (bool circular=false)
 default constructor; creates an empty list More...
 
 BLinkedList (BLinkedList &&that)
 move constructor More...
 
 ~BLinkedList ()
 destructor; releases all element objects More...
 
bool empty () const
 
int size () const
 
bool circular () const
 
void setCircular (bool)
 update the circularity property of this list More...
 
BLinkedListoperator= (BLinkedList &&that)
 move assigment operator More...
 
void insert_first (BLinkedListElement *el)
 insert a new element at the beginning of the list; the list takes ownership of the element. Do not delete it yourself. More...
 
void insert_last (BLinkedListElement *el)
 insert a new element at the end of the list; the list takes ownership of the element. Do not delete it yourself. More...
 
void insert_before (BLinkedListElement *el, BLinkedListElement *before)
 insert a new element before a certain element of the list; the list takes ownership of the element. Do not delete it yourself. More...
 
void insert_after (BLinkedListElement *el, BLinkedListElement *after)
 insert a new element after a certain element of the list; the list takes ownership of the element. Do not delete it yourself. More...
 
BLinkedListElementremove (BLinkedListElement *el)
 remove an element from the list and release its memory More...
 
void clear ()
 release all elements More...
 
int concat (BLinkedList &that)
 append all elements of another list, taking ownership of the new elements More...
 
int swap (BLinkedList &that)
 exchange all elements with another list, taking ownership of the new elements More...
 

Private Member Functions

 BOOST_STATIC_ASSERT ((boost::is_base_of< BLinkedListElement, T >::value))
 

Additional Inherited Members

- Protected Member Functions inherited from frechet::data::BLinkedList
BLinkedListElementoperator[] (int i) const
 positional lookup (note: O(n), use with care) More...
 
- Protected Attributes inherited from frechet::data::BLinkedList
BLinkedListElement_first
 the first element in the list (or nullptr) More...
 
BLinkedListElement_last
 the last element in the list (or nullptr) More...
 
int _size
 current number of elements More...
 
bool _circular
 if true, this is a circular list, i.e. the last element is connected to the first element More...
 

Constructor & Destructor Documentation

◆ LinkedList() [1/3]

template<class T>
frechet::data::LinkedList< T >::LinkedList ( )
inline

empty constructor; creates an empty list

Definition at line 256 of file linkedlist.h.

◆ LinkedList() [2/3]

template<class T>
frechet::data::LinkedList< T >::LinkedList ( LinkedList< T > &&  that)
inline

move constructor; takes ownership of another list

Parameters
thatlist to move elements from; will be empty on return

Definition at line 259 of file linkedlist.h.

◆ LinkedList() [3/3]

template<class T>
template<typename Cloner >
frechet::data::LinkedList< T >::LinkedList ( const LinkedList< T > &  that,
Cloner  cloner 
)
inline

deep copy constructor

Parameters
thatlist to copy from
clonera functor that creates deep copies of elements
Template Parameters
Clonera functor class that creates deep copies of elements

Definition at line 268 of file linkedlist.h.

Member Function Documentation

◆ BOOST_STATIC_ASSERT()

template<class T>
frechet::data::LinkedList< T >::BOOST_STATIC_ASSERT ( (boost::is_base_of< BLinkedListElement, T >::value)  )
private

◆ first()

template<class T>
T* frechet::data::LinkedList< T >::first ( ) const
inline
Returns
first element of the list (or nullptr if empty)

Definition at line 292 of file linkedlist.h.

◆ last()

template<class T>
T* frechet::data::LinkedList< T >::last ( ) const
inline
Returns
last element of the list (or nullptr if empty)

Definition at line 296 of file linkedlist.h.

◆ operator=()

template<class T>
LinkedList& frechet::data::LinkedList< T >::operator= ( LinkedList< T > &&  that)
inline

move assigment operator

Note that there is no copy assigment operator because we must prevent shallow copies; double-linked elements must not be part of two separate lists.

Parameters
thatlist to move elements from; will be empty on return
Returns
this list, containing the elements from 'that'

Definition at line 284 of file linkedlist.h.

◆ operator[]()

template<class T>
T* frechet::data::LinkedList< T >::operator[] ( int  i) const
inline

positional lookup (note: O(n), use with care)

Parameters
iindex in list
Returns
the i-th element, or nullptr

Definition at line 305 of file linkedlist.h.

◆ remove()

template<class T>
T* frechet::data::LinkedList< T >::remove ( T *  el)
inline

Definition at line 298 of file linkedlist.h.

◆ swap()

template<class T>
void frechet::data::LinkedList< T >::swap ( LinkedList< T > &  that)
inline

exchange all elements with another list, taking ownership of the new elements

Parameters
thatlist to move elements from
Returns
size of the list after swap

Definition at line 312 of file linkedlist.h.


The documentation for this class was generated from the following file: