Open
Graph Drawing
Framework

 v.2012.07
 

ogdf::SList< E > Class Template Reference

The parameterized class SList<E> represents singly linked lists with content type E. More...

#include <ogdf/basic/SList.h>

+ Inheritance diagram for ogdf::SList< E >:

List of all members.

Public Types

typedef SListConstIterator< E > const_iterator
typedef SListElement< E > element_type
typedef SListIterator< E > iterator
typedef E value_type

Public Member Functions

 SList ()
 Constructs an empty singly linked list.
 SList (const SList< E > &L)
 Constructs a singly linked list that is a copy of L.
 ~SList ()
const E & back () const
 Returns a reference to the last element.
E & back ()
 Returns a reference to the last element.
const SListConstIterator< E > begin () const
 Returns an iterator to the first element of the list.
SListIterator< E > begin ()
 Returns an iterator to the first element of the list.
void bucketSort (int l, int h, BucketFunc< E > &f)
 Sorts the list using bucket sort.
void bucketSort (BucketFunc< E > &f)
 Sorts the list using bucket sort.
void clear ()
 Removes all elements from the list.
void conc (SList< E > &L2)
 Appends L2 to this list and makes L2 empty.
SListConstIterator< E > cyclicSucc (SListConstIterator< E > it) const
 Returns an iterator to the cyclic successor of it.
SListIterator< E > cyclicSucc (SListIterator< E > it)
 Returns an iterator to the cyclic successor of it.
void delSucc (SListIterator< E > itBefore)
 Removes the succesor of pBefore.
bool empty () const
 Returns true iff the list is empty.
SListConstIterator< E > end () const
 Returns an iterator to one-past-last element of the list.
SListIterator< E > end ()
 Returns an iterator to one-past-last element of the list.
const E & front () const
 Returns a reference to the first element.
E & front ()
 Returns a reference to the first element.
SListConstIterator< E > get (int pos) const
 Returns an iterator pointing to the element at position pos.
SListIterator< E > get (int pos)
 Returns an iterator pointing to the element at position pos.
const SListPure< E > & getListPure () const
 Conversion to const SListPure.
SListIterator< E > insertAfter (const E &x, SListIterator< E > itBefore)
 Inserts element x after pBefore.
void moveFrontToBack (SList< E > &L2)
 Moves the first element of this list to the end of list L2.
void moveFrontToFront (SList< E > &L2)
 Moves the first element of this list to the begin of list L2.
void moveFrontToSucc (SList< E > &L2, SListIterator< E > itBefore)
 Moves the first element of this list to list L2 inserted after itBefore.
SList< E > & operator= (const SList< E > &L)
 Assignment operator.
void permute ()
 Randomly permutes the elements in the list.
void popFront ()
 Removes the first element from the list.
popFrontRet ()
 Removes the first element from the list and returns it.
int pos (SListConstIterator< E > it) const
 Returns the position (starting with 0) of it in the list.
SListIterator< E > pushBack (const E &x)
 Adds element x at the end of the list.
SListIterator< E > pushFront (const E &x)
 Adds element x at the begin of the list.
void quicksort ()
 Sorts the list using Quicksort.
template<class COMPARER >
void quicksort (const COMPARER &comp)
 Sorts the list using Quicksort and comparer comp.
const SListConstIterator< E > rbegin () const
 Returns an iterator to the last element of the list.
SListIterator< E > rbegin ()
 Returns an iterator to the last element of the list.
void reverse ()
 Reverses the order of the list elements.
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.
int size () const
 Returns the length of the list.

Private Attributes

int m_count
 The length of the list.

Additional Inherited Members

- Private Types inherited from ogdf::SListPure< E >
- Private Member Functions inherited from ogdf::SListPure< E >
 SListPure ()
 Constructs an empty singly linked list.
 SListPure (const SListPure< E > &L)
 Constructs a singly linked list that is a copy of L.
 ~SListPure ()
void conc (SListPure< E > &L2)
 Appends L2 to this list and makes L2 empty.
void moveFrontToBack (SListPure< E > &L2)
 Moves the first element of this list to the end of list L2.
void moveFrontToFront (SListPure< E > &L2)
 Moves the first element of this list to the begin of list L2.
void moveFrontToSucc (SListPure< E > &L2, SListIterator< E > itBefore)
 Moves the first element of this list to list L2 inserted after itBefore.
SListPure< E > & operator= (const SListPure< E > &L)
 Assignment operator.
void copy (const SListPure< E > &L)
void permute (const int n)

Detailed Description

template<class E>
class ogdf::SList< E >

The parameterized class SList<E> represents singly linked lists with content type E.

Elements of the list are instances of type SListElement<E>. Use SListConstIterator<E> or SListIterator<E> in order to iterate over the list. In contrast to SListPure<E>, instances of SList<E> store the length of the list and thus allow constant time access to the length.

Template Parameters:
Eis the data type stored in list elements.

Definition at line 627 of file SList.h.


Member Typedef Documentation

template<class E>
typedef SListConstIterator<E> ogdf::SList< E >::const_iterator

Reimplemented from ogdf::SListPure< E >.

Definition at line 643 of file SList.h.

template<class E>
typedef SListElement<E> ogdf::SList< E >::element_type

Reimplemented from ogdf::SListPure< E >.

Definition at line 642 of file SList.h.

template<class E>
typedef SListIterator<E> ogdf::SList< E >::iterator

Reimplemented from ogdf::SListPure< E >.

Definition at line 644 of file SList.h.

template<class E>
typedef E ogdf::SList< E >::value_type

Reimplemented from ogdf::SListPure< E >.

Definition at line 641 of file SList.h.


Constructor & Destructor Documentation

template<class E>
ogdf::SList< E >::SList ( )
inline

Constructs an empty singly linked list.

Definition at line 633 of file SList.h.

template<class E>
ogdf::SList< E >::SList ( const SList< E > &  L)
inline

Constructs a singly linked list that is a copy of L.

Definition at line 636 of file SList.h.

template<class E>
ogdf::SList< E >::~SList ( )
inline

Definition at line 639 of file SList.h.


Member Function Documentation

template<class E>
const E& ogdf::SList< E >::back ( ) const
inline

Returns a reference to the last element.

Precondition:
The list is not empty!

Reimplemented from ogdf::SListPure< E >.

Definition at line 731 of file SList.h.

template<class E>
E& ogdf::SList< E >::back ( )
inline

Returns a reference to the last element.

Precondition:
The list is not empty!

Reimplemented from ogdf::SListPure< E >.

Definition at line 737 of file SList.h.

template<class E>
const SListConstIterator<E> ogdf::SList< 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::SListPure< E >.

Definition at line 656 of file SList.h.

template<class E>
SListIterator<E> ogdf::SList< 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::SListPure< E >.

Definition at line 662 of file SList.h.

template<class E>
void ogdf::SList< E >::bucketSort ( int  l,
int  h,
BucketFunc< E > &  f 
)
inline

Sorts the list using bucket sort.

Parameters:
lis the lowest bucket that will occur.
his the highest bucket that will occur.
freturns the bucket for each element.
Precondition:
The bucket function f will only return bucket values between l and h for this list.

Reimplemented from ogdf::SListPure< E >.

Definition at line 872 of file SList.h.

template<class E>
void ogdf::SList< E >::bucketSort ( BucketFunc< E > &  f)
inline

Sorts the list using bucket sort.

Reimplemented from ogdf::SListPure< E >.

Definition at line 877 of file SList.h.

template<class E>
void ogdf::SList< E >::clear ( )
inline

Removes all elements from the list.

Reimplemented from ogdf::SListPure< E >.

Reimplemented in ogdf::Queue< E >.

Definition at line 833 of file SList.h.

template<class E>
void ogdf::SList< E >::conc ( SList< E > &  L2)
inline

Appends L2 to this list and makes L2 empty.

Definition at line 839 of file SList.h.

template<class E>
SListConstIterator<E> ogdf::SList< E >::cyclicSucc ( SListConstIterator< E >  it) const
inline

Returns an iterator to the cyclic successor of it.

Precondition:
it points to an element in this list!

Reimplemented from ogdf::SListPure< E >.

Definition at line 743 of file SList.h.

template<class E>
SListIterator<E> ogdf::SList< E >::cyclicSucc ( SListIterator< E >  it)
inline

Returns an iterator to the cyclic successor of it.

Precondition:
it points to an element in this list!

Reimplemented from ogdf::SListPure< E >.

Definition at line 751 of file SList.h.

template<class E>
void ogdf::SList< E >::delSucc ( SListIterator< E >  itBefore)
inline

Removes the succesor of pBefore.

Precondition:
pBefore points to an element in this list.

Reimplemented from ogdf::SListPure< E >.

Definition at line 806 of file SList.h.

template<class E>
bool ogdf::SList< E >::empty ( ) const
inline

Returns true iff the list is empty.

Reimplemented from ogdf::SListPure< E >.

Reimplemented in ogdf::Queue< E >.

Definition at line 647 of file SList.h.

template<class E>
SListConstIterator<E> ogdf::SList< 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::SListPure< E >.

Definition at line 668 of file SList.h.

template<class E>
SListIterator<E> ogdf::SList< E >::end ( )
inline

Returns an iterator to one-past-last element of the list.

This is always a null pointer iterator.

Reimplemented from ogdf::SListPure< E >.

Definition at line 674 of file SList.h.

template<class E>
const E& ogdf::SList< E >::front ( ) const
inline

Returns a reference to the first element.

Precondition:
The list is not empty!

Reimplemented from ogdf::SListPure< E >.

Definition at line 719 of file SList.h.

template<class E>
E& ogdf::SList< E >::front ( )
inline

Returns a reference to the first element.

Precondition:
The list is not empty!

Reimplemented from ogdf::SListPure< E >.

Definition at line 725 of file SList.h.

template<class E>
SListConstIterator<E> ogdf::SList< 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::SListPure< E >.

Definition at line 693 of file SList.h.

template<class E>
SListIterator<E> ogdf::SList< 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::SListPure< E >.

Definition at line 701 of file SList.h.

template<class E>
const SListPure<E>& ogdf::SList< E >::getListPure ( ) const
inline

Conversion to const SListPure.

Reimplemented from ogdf::SListPure< E >.

Reimplemented in ogdf::Queue< E >.

Definition at line 851 of file SList.h.

template<class E>
SListIterator<E> ogdf::SList< E >::insertAfter ( const E &  x,
SListIterator< E >  itBefore 
)
inline

Inserts element x after pBefore.

Precondition:
pBefore points to an element in this list.

Reimplemented from ogdf::SListPure< E >.

Definition at line 778 of file SList.h.

template<class E>
void ogdf::SList< E >::moveFrontToBack ( SList< E > &  L2)
inline

Moves the first element of this list to the end of list L2.

Definition at line 818 of file SList.h.

template<class E>
void ogdf::SList< E >::moveFrontToFront ( SList< E > &  L2)
inline

Moves the first element of this list to the begin of list L2.

Definition at line 812 of file SList.h.

template<class E>
void ogdf::SList< E >::moveFrontToSucc ( SList< E > &  L2,
SListIterator< E >  itBefore 
)
inline

Moves the first element of this list to list L2 inserted after itBefore.

Precondition:
itBefore points to an element in L2.

Definition at line 827 of file SList.h.

template<class E>
SList<E>& ogdf::SList< E >::operator= ( const SList< E > &  L)
inline

Assignment operator.

Definition at line 756 of file SList.h.

template<class E>
void ogdf::SList< E >::permute ( )
inline

Randomly permutes the elements in the list.

Reimplemented from ogdf::SListPure< E >.

Definition at line 882 of file SList.h.

template<class E>
void ogdf::SList< E >::popFront ( )
inline

Removes the first element from the list.

Precondition:
The list is not empty!

Reimplemented from ogdf::SListPure< E >.

Definition at line 787 of file SList.h.

template<class E>
E ogdf::SList< E >::popFrontRet ( )
inline

Removes the first element from the list and returns it.

Precondition:
The list is not empty!

Reimplemented from ogdf::SListPure< E >.

Definition at line 796 of file SList.h.

template<class E>
int ogdf::SList< E >::pos ( SListConstIterator< E >  it) const
inline

Returns the position (starting with 0) of it in the list.

Positions are numbered 0,1,...

Precondition:
it is an iterator pointing to an element in this list.

Reimplemented from ogdf::SListPure< E >.

Definition at line 710 of file SList.h.

template<class E>
SListIterator<E> ogdf::SList< E >::pushBack ( const E &  x)
inline

Adds element x at the end of the list.

Reimplemented from ogdf::SListPure< E >.

Definition at line 769 of file SList.h.

template<class E>
SListIterator<E> ogdf::SList< E >::pushFront ( const E &  x)
inline

Adds element x at the begin of the list.

Reimplemented from ogdf::SListPure< E >.

Definition at line 763 of file SList.h.

template<class E>
void ogdf::SList< E >::quicksort ( )
inline

Sorts the list using Quicksort.

Reimplemented from ogdf::SListPure< E >.

Definition at line 854 of file SList.h.

template<class E>
template<class COMPARER >
void ogdf::SList< E >::quicksort ( const COMPARER &  comp)
inline

Sorts the list using Quicksort and comparer comp.

Reimplemented from ogdf::SListPure< E >.

Definition at line 860 of file SList.h.

template<class E>
const SListConstIterator<E> ogdf::SList< 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::SListPure< E >.

Definition at line 680 of file SList.h.

template<class E>
SListIterator<E> ogdf::SList< 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::SListPure< E >.

Definition at line 686 of file SList.h.

template<class E>
void ogdf::SList< E >::reverse ( )
inline

Reverses the order of the list elements.

Reimplemented from ogdf::SListPure< E >.

Definition at line 846 of file SList.h.

template<class E>
int ogdf::SList< 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::SListPure< E >.

Definition at line 887 of file SList.h.

template<class E>
template<class COMPARER >
int ogdf::SList< 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::SListPure< E >.

Definition at line 893 of file SList.h.

template<class E>
int ogdf::SList< E >::size ( ) const
inline

Returns the length of the list.

Reimplemented from ogdf::SListPure< E >.

Reimplemented in ogdf::Queue< E >.

Definition at line 650 of file SList.h.


Member Data Documentation

template<class E>
int ogdf::SList< E >::m_count
private

The length of the list.

Definition at line 629 of file SList.h.


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