|
|||
|
|
|
|||
|
|
The parameterized class ListPure<E> represents doubly linked lists with content type E. More...
#include <ogdf/basic/List.h>
Public Types | |
| typedef E | value_type |
| typedef ListElement< E > | element_type |
| typedef ListConstIterator< E > | const_iterator |
| typedef ListIterator< E > | iterator |
Public Member Functions | |
| List () | |
| Constructs an empty doubly linked list. | |
| List (const List< E > &L) | |
| Constructs a doubly linked list that is a copy of L. | |
| ~List () | |
| bool | empty () const |
| Returns true iff the list is empty. | |
| int | size () const |
| Returns the length of the list. | |
| const ListConstIterator< E > | begin () const |
| Returns an iterator to the first element of the list. | |
| ListIterator< E > | begin () |
| Returns an iterator to the first element of the list. | |
| ListConstIterator< E > | end () const |
| Returns an iterator to one-past-last element of the list. | |
| ListIterator< E > | end () |
| Returns an iterator to one-past-last element of the list. | |
| const ListConstIterator< E > | rbegin () const |
| Returns an iterator to the last element of the list. | |
| ListIterator< E > | rbegin () |
| Returns an iterator to the last element of the list. | |
| ListConstIterator< E > | rend () const |
| Returns an iterator to one-before-first element of the list. | |
| ListIterator< E > | rend () |
| Returns an iterator to one-before-first element of the list. | |
| const E & | front () const |
| Returns a reference to the first element. | |
| E & | front () |
| Returns a reference to the first element. | |
| const E & | back () const |
| Returns a reference to the last element. | |
| E & | back () |
| Returns a reference to the last element. | |
| ListConstIterator< E > | cyclicSucc (ListConstIterator< E > it) const |
| Returns an iterator to the cyclic successor of it. | |
| ListIterator< E > | cyclicSucc (ListIterator< E > it) |
| Returns an iterator to the cyclic successor of it. | |
| ListConstIterator< E > | cyclicPred (ListConstIterator< E > it) const |
| Returns an iterator to the cyclic predecessor of it. | |
| ListIterator< E > | cyclicPred (ListIterator< E > it) |
| Returns an iterator to the cyclic predecessor of it. | |
| ListConstIterator< E > | get (int pos) const |
| Returns an iterator pointing to the element at position pos. | |
| ListIterator< E > | get (int pos) |
| Returns an iterator pointing to the element at position pos. | |
| int | pos (ListConstIterator< E > it) const |
| Returns the position (starting with 0) of it in the list. | |
| List< E > & | operator= (const List< E > &L) |
| bool | operator== (const List< E > &L) const |
| Equality operator. | |
| bool | operator!= (const List< E > &L) const |
| Inequality operator. | |
| ListIterator< E > | pushFront (const E &x) |
| Adds element x at the begin of the list. | |
| ListIterator< E > | pushBack (const E &x) |
| Adds element x at the end of the list. | |
| ListIterator< E > | insert (const E &x, ListIterator< E > it, Direction dir=after) |
| Inserts element x before or after it. | |
| ListIterator< E > | insertBefore (const E &x, ListIterator< E > it) |
| Inserts element x before it. | |
| ListIterator< E > | insertAfter (const E &x, ListIterator< E > it) |
| Inserts element x after it. | |
| void | popFront () |
| Removes the first element from the list. | |
| E | popFrontRet () |
| Removes the first element from the list and returns it. | |
| void | popBack () |
| Removes the last element from the list. | |
| E | popBackRet () |
| Removes the last element from the list and returns it. | |
| void | exchange (ListIterator< E > it1, ListIterator< E > it2) |
| Exchanges the positions of it1 and it2 in the list. | |
| void | moveToFront (ListIterator< E > it) |
| Moves it to the beginning of the list. | |
| void | moveToBack (ListIterator< E > it) |
| Moves it to the end of the list. | |
| void | moveToSucc (ListIterator< E > it, ListIterator< E > itBefore) |
| Moves it after itBefore. | |
| void | moveToPrec (ListIterator< E > it, ListIterator< E > itAfter) |
| Moves it before itAfter. | |
| void | moveToFront (ListIterator< E > it, List< E > &L2) |
| Moves it to the beginning of L2. | |
| void | moveToBack (ListIterator< E > it, List< E > &L2) |
| Moves it to the end of L2. | |
| void | moveToSucc (ListIterator< E > it, List< E > &L2, ListIterator< E > itBefore) |
| Moves it to list L2 and inserts it after itBefore. | |
| void | moveToPrec (ListIterator< E > it, List< E > &L2, ListIterator< E > itAfter) |
| Moves it to list L2 and inserts it after itBefore. | |
| void | del (ListIterator< E > it) |
| Removes it from the list. | |
| void | conc (List< E > &L2) |
| Appends L2 to this list and makes L2 empty. | |
| void | concFront (List< E > &L2) |
| Prepends L2 to this list and makes L2 empty. | |
| void | exchange (List< E > &L2) |
| Exchanges too complete lists in O(1). | |
| void | split (ListIterator< E > it, List< E > &L1, List< E > &L2, Direction dir=before) |
| Splits the list at element it into lists L1 and L2. | |
| void | reverse () |
| Reverses the order of the list elements. | |
| void | clear () |
| Removes all elements from the list. | |
| const ListPure< E > & | getListPure () const |
| Conversion to const SListPure. | |
| void | quicksort () |
| Sorts the list using Quicksort. | |
| template<class COMPARER > | |
| void | quicksort (const COMPARER &comp) |
| Sorts the list using Quicksort and comparer comp. | |
| void | bucketSort (int l, int h, BucketFunc< E > &f) |
| Sorts the list using bucket sort. | |
| void | permute () |
| Randomly permutes the elements in the list. | |
| int | search (const E &e) const |
| Scans the list for the specified element and returns its position in the list, or -1 if not found. | |
| template<class COMPARER > | |
| int | search (const E &e, const COMPARER &comp) const |
| Scans the list for the specified element (using the user-defined comparer) and returns its position in the list, or -1 if not found. | |
| void * | operator new (size_t nBytes) |
| void * | operator new (size_t, void *p) |
| void | operator delete (void *p, size_t nBytes) |
Private Attributes | |
| int | m_count |
| The length of the list. | |
The parameterized class ListPure<E> represents doubly linked lists with content type E.
Elements of the list are instances of type ListElement<E>. Use ListConstIterator<E> or ListIterator<E> in order to iterate over the list.
In contrast to ListPure<E>, instances of List<E> store the length of the list.
See the forall_listiterators macros for the recommended way how to easily iterate through a list. (Since this feature is rather new, you won't find many exampled in the code base yet.)
Definition at line 1117 of file List.h.
| typedef ListConstIterator<E> ogdf::List< E >::const_iterator |
Reimplemented from ogdf::ListPure< E >.
| typedef ListElement<E> ogdf::List< E >::element_type |
Reimplemented from ogdf::ListPure< E >.
| typedef ListIterator<E> ogdf::List< E >::iterator |
Reimplemented from ogdf::ListPure< E >.
| typedef E ogdf::List< E >::value_type |
Reimplemented from ogdf::ListPure< E >.
| ogdf::List< E >::List | ( | ) | [inline] |
| ogdf::List< E >::List | ( | const List< E > & | L | ) | [inline] |
| ogdf::List< E >::~List | ( | ) | [inline] |
| const E& ogdf::List< E >::back | ( | ) | const [inline] |
Returns a reference to the last element.
Reimplemented from ogdf::ListPure< E >.
| E& ogdf::List< E >::back | ( | ) | [inline] |
Returns a reference to the last element.
Reimplemented from ogdf::ListPure< E >.
| ListIterator<E> ogdf::List< E >::begin | ( | ) | [inline] |
Returns an iterator to the first element of the list.
If the list is empty, a null pointer iterator is returned.
Reimplemented from ogdf::ListPure< E >.
| const ListConstIterator<E> ogdf::List< E >::begin | ( | ) | const [inline] |
Returns an iterator to the first element of the list.
If the list is empty, a null pointer iterator is returned.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::bucketSort | ( | int | l, | |
| int | h, | |||
| BucketFunc< E > & | f | |||
| ) | [inline] |
Sorts the list using bucket sort.
| l | is the lowest bucket that will occur. | |
| h | is the highest bucket that will occur. | |
| f | returns the bucket for each element. |
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::clear | ( | ) | [inline] |
Removes all elements from the list.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::conc | ( | List< E > & | L2 | ) | [inline] |
| void ogdf::List< E >::concFront | ( | List< E > & | L2 | ) | [inline] |
| ListConstIterator<E> ogdf::List< E >::cyclicPred | ( | ListConstIterator< E > | it | ) | const [inline] |
Returns an iterator to the cyclic predecessor of it.
Reimplemented from ogdf::ListPure< E >.
| ListIterator<E> ogdf::List< E >::cyclicPred | ( | ListIterator< E > | it | ) | [inline] |
Returns an iterator to the cyclic predecessor of it.
Reimplemented from ogdf::ListPure< E >.
| ListIterator<E> ogdf::List< E >::cyclicSucc | ( | ListIterator< E > | it | ) | [inline] |
Returns an iterator to the cyclic successor of it.
Reimplemented from ogdf::ListPure< E >.
| ListConstIterator<E> ogdf::List< E >::cyclicSucc | ( | ListConstIterator< E > | it | ) | const [inline] |
Returns an iterator to the cyclic successor of it.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::del | ( | ListIterator< E > | it | ) | [inline] |
Removes it from the list.
Reimplemented from ogdf::ListPure< E >.
| bool ogdf::List< E >::empty | ( | ) | const [inline] |
Returns true iff the list is empty.
Reimplemented from ogdf::ListPure< E >.
| ListConstIterator<E> ogdf::List< E >::end | ( | ) | const [inline] |
Returns an iterator to one-past-last element of the list.
This is always a null pointer iterator.
Reimplemented from ogdf::ListPure< E >.
| ListIterator<E> ogdf::List< E >::end | ( | ) | [inline] |
Returns an iterator to one-past-last element of the list.
This is always a null pointer iterator.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::exchange | ( | ListIterator< E > | it1, | |
| ListIterator< E > | it2 | |||
| ) | [inline] |
Exchanges the positions of it1 and it2 in the list.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::exchange | ( | List< E > & | L2 | ) | [inline] |
| const E& ogdf::List< E >::front | ( | ) | const [inline] |
Returns a reference to the first element.
Reimplemented from ogdf::ListPure< E >.
| E& ogdf::List< E >::front | ( | ) | [inline] |
Returns a reference to the first element.
Reimplemented from ogdf::ListPure< E >.
| ListConstIterator<E> ogdf::List< E >::get | ( | int | pos | ) | const [inline] |
Returns an iterator pointing to the element at position pos.
The running time of this method is linear in pos.
Reimplemented from ogdf::ListPure< E >.
| ListIterator<E> ogdf::List< E >::get | ( | int | pos | ) | [inline] |
Returns an iterator pointing to the element at position pos.
The running time of this method is linear in pos.
Reimplemented from ogdf::ListPure< E >.
| const ListPure<E>& ogdf::List< E >::getListPure | ( | ) | const [inline] |
| ListIterator<E> ogdf::List< E >::insert | ( | const E & | x, | |
| ListIterator< E > | it, | |||
| Direction | dir = after | |||
| ) | [inline] |
Inserts element x before or after it.
| x | is the element to be inserted. | |
| it | is a list iterator in this list. | |
| dir | determines if x is inserted before or after it. Possible values are ogdf::before and ogdf::after. |
Reimplemented from ogdf::ListPure< E >.
| ListIterator<E> ogdf::List< E >::insertAfter | ( | const E & | x, | |
| ListIterator< E > | it | |||
| ) | [inline] |
Inserts element x after it.
Reimplemented from ogdf::ListPure< E >.
| ListIterator<E> ogdf::List< E >::insertBefore | ( | const E & | x, | |
| ListIterator< E > | it | |||
| ) | [inline] |
Inserts element x before it.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::moveToBack | ( | ListIterator< E > | it | ) | [inline] |
Moves it to the end of the list.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::moveToBack | ( | ListIterator< E > | it, | |
| List< E > & | L2 | |||
| ) | [inline] |
| void ogdf::List< E >::moveToFront | ( | ListIterator< E > | it | ) | [inline] |
Moves it to the beginning of the list.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::moveToFront | ( | ListIterator< E > | it, | |
| List< E > & | L2 | |||
| ) | [inline] |
| void ogdf::List< E >::moveToPrec | ( | ListIterator< E > | it, | |
| ListIterator< E > | itAfter | |||
| ) | [inline] |
Moves it before itAfter.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::moveToPrec | ( | ListIterator< E > | it, | |
| List< E > & | L2, | |||
| ListIterator< E > | itAfter | |||
| ) | [inline] |
| void ogdf::List< E >::moveToSucc | ( | ListIterator< E > | it, | |
| ListIterator< E > | itBefore | |||
| ) | [inline] |
Moves it after itBefore.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::moveToSucc | ( | ListIterator< E > | it, | |
| List< E > & | L2, | |||
| ListIterator< E > | itBefore | |||
| ) | [inline] |
| void ogdf::List< E >::operator delete | ( | void * | p, | |
| size_t | nBytes | |||
| ) | [inline] |
Reimplemented from ogdf::ListPure< E >.
| void* ogdf::List< E >::operator new | ( | size_t | , | |
| void * | p | |||
| ) | [inline] |
Reimplemented from ogdf::ListPure< E >.
| void* ogdf::List< E >::operator new | ( | size_t | nBytes | ) | [inline] |
Reimplemented from ogdf::ListPure< E >.
| bool ogdf::List< E >::operator!= | ( | const List< E > & | L | ) | const [inline] |
| List<E>& ogdf::List< E >::operator= | ( | const List< E > & | L | ) | [inline] |
| bool ogdf::List< E >::operator== | ( | const List< E > & | L | ) | const [inline] |
| void ogdf::List< E >::permute | ( | ) | [inline] |
Randomly permutes the elements in the list.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::popBack | ( | ) | [inline] |
Removes the last element from the list.
Reimplemented from ogdf::ListPure< E >.
| E ogdf::List< E >::popBackRet | ( | ) | [inline] |
Removes the last element from the list and returns it.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::popFront | ( | ) | [inline] |
Removes the first element from the list.
Reimplemented from ogdf::ListPure< E >.
| E ogdf::List< E >::popFrontRet | ( | ) | [inline] |
Removes the first element from the list and returns it.
Reimplemented from ogdf::ListPure< E >.
Reimplemented in ogdf::kList.
| int ogdf::List< E >::pos | ( | ListConstIterator< E > | it | ) | const [inline] |
Returns the position (starting with 0) of it in the list.
Positions are numbered 0,1,...
Reimplemented from ogdf::ListPure< E >.
| ListIterator<E> ogdf::List< E >::pushBack | ( | const E & | x | ) | [inline] |
Adds element x at the end of the list.
Reimplemented from ogdf::ListPure< E >.
| ListIterator<E> ogdf::List< E >::pushFront | ( | const E & | x | ) | [inline] |
Adds element x at the begin of the list.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::quicksort | ( | ) | [inline] |
Sorts the list using Quicksort.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::quicksort | ( | const COMPARER & | comp | ) | [inline] |
Sorts the list using Quicksort and comparer comp.
Reimplemented from ogdf::ListPure< E >.
| const ListConstIterator<E> ogdf::List< E >::rbegin | ( | ) | const [inline] |
Returns an iterator to the last element of the list.
If the list is empty, a null pointer iterator is returned.
Reimplemented from ogdf::ListPure< E >.
| ListIterator<E> ogdf::List< E >::rbegin | ( | ) | [inline] |
Returns an iterator to the last element of the list.
If the list is empty, a null pointer iterator is returned.
Reimplemented from ogdf::ListPure< E >.
| ListIterator<E> ogdf::List< E >::rend | ( | ) | [inline] |
Returns an iterator to one-before-first element of the list.
This is always a null pointer iterator.
Reimplemented from ogdf::ListPure< E >.
| ListConstIterator<E> ogdf::List< E >::rend | ( | ) | const [inline] |
Returns an iterator to one-before-first element of the list.
This is always a null pointer iterator.
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::reverse | ( | ) | [inline] |
Reverses the order of the list elements.
Reimplemented from ogdf::ListPure< E >.
| int ogdf::List< E >::search | ( | const E & | e, | |
| const COMPARER & | comp | |||
| ) | const [inline] |
Scans the list for the specified element (using the user-defined comparer) and returns its position in the list, or -1 if not found.
Reimplemented from ogdf::ListPure< E >.
| int ogdf::List< E >::search | ( | const E & | e | ) | const [inline] |
Scans the list for the specified element and returns its position in the list, or -1 if not found.
Reimplemented from ogdf::ListPure< E >.
| int ogdf::List< E >::size | ( | ) | const [inline] |
Returns the length of the list.
Notice that this method requires to run through the whole list and takes linear running time!
Reimplemented from ogdf::ListPure< E >.
| void ogdf::List< E >::split | ( | ListIterator< E > | it, | |
| List< E > & | L1, | |||
| List< E > & | L2, | |||
| Direction | dir = before | |||
| ) | [inline] |
Splits the list at element it into lists L1 and L2.
If it is not a null pointer and L = x1,...,x{k-1}, it,x_{k+1},xn, then L1 = x1,...,x{k-1} and L2 = it,x{k+1},...,xn if dir = before. If it is a null pointer, then L1 is made empty and L2 = L. Finally L is made empty if it is not identical to L1 or L2.
int ogdf::List< E >::m_count [private] |
