Open
Graph Drawing
Framework

 v.2010.10
 

Public Types | Public Member Functions | Protected Member Functions | Private Attributes

ogdf::SListPure< E > Class Template Reference

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

#include <ogdf/basic/SList.h>

Inheritance diagram for ogdf::SListPure< E >:
ogdf::QueuePure< E > ogdf::SList< E > ogdf::Queue< E >

List of all members.

Public Types

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

Public Member Functions

 SListPure ()
 Constructs an empty singly linked list.
 SListPure (const SListPure< E > &L)
 Constructs a singly linked list that is a copy of L.
 ~SListPure ()
bool empty () const
 Returns true iff the list is empty.
int size () const
 Returns the length of the list.
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.
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.
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.
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.
int pos (SListConstIterator< E > it) const
 Returns the position (starting with 0) of it in 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.
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.
SListPure< E > & operator= (const SListPure< E > &L)
 Assignment operator.
SListIterator< E > pushFront (const E &x)
 Adds element x at the begin of the list.
SListIterator< E > pushBack (const E &x)
 Adds element x at the end of the list.
SListIterator< E > insertAfter (const E &x, SListIterator< E > itBefore)
 Inserts element x after pBefore.
void popFront ()
 Removes the first element from the list.
popFrontRet ()
 Removes the first element from the list and returns it.
void delSucc (SListIterator< E > itBefore)
 Removes the succesor of pBefore.
void moveFrontToFront (SListPure< E > &L2)
 Moves the first element of this list to the begin of list L2.
void moveFrontToBack (SListPure< E > &L2)
 Moves the first element of this list to the end of list L2.
void moveFrontToSucc (SListPure< E > &L2, SListIterator< E > itBefore)
 Moves the first element of this list to list L2 inserted after itBefore.
void clear ()
 Removes all elements from the list.
void conc (SListPure< E > &L2)
 Appends L2 to this list and makes L2 empty.
void reverse ()
 Reverses the order of the list elements.
const SListPure< 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 bucketSort (BucketFunc< E > &f)
 Sorts the list using bucket sort.
void permute ()
 Randomly permutes the elements in the list.
void * operator new (size_t nBytes)
void * operator new (size_t, void *p)
void operator delete (void *p, size_t nBytes)

Protected Member Functions

void copy (const SListPure< E > &L)
void permute (const int n)

Private Attributes

SListElement< E > * m_head
 Pointer to first element.
SListElement< E > * m_tail
 Pointer to last element.

Detailed Description

template<class E>
class ogdf::SListPure< E >

The parameterized class SListPure<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 SList<E>, instances of SListPure<E> do not store the length of the list.

Definition at line 247 of file SList.h.


Member Typedef Documentation


Constructor & Destructor Documentation

template<class E>
ogdf::SListPure< E >::SListPure (  )  [inline]

Constructs an empty singly linked list.

Definition at line 253 of file SList.h.

template<class E>
ogdf::SListPure< E >::SListPure ( const SListPure< E > &  L  )  [inline]

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

Definition at line 256 of file SList.h.

template<class E>
ogdf::SListPure< E >::~SListPure (  )  [inline]

Definition at line 261 of file SList.h.


Member Function Documentation

template<class E>
const E& ogdf::SListPure< E >::back (  )  const [inline]
template<class E>
SListIterator<E> ogdf::SListPure< E >::begin (  )  [inline]
template<class E>
SListConstIterator<E> ogdf::SListPure< E >::begin (  )  const [inline]
template<class E>
void ogdf::SListPure< E >::bucketSort ( int  l,
int  h,
BucketFunc< E > &  f 
)

Sorts the list using bucket sort.

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

Reimplemented in ogdf::SList< E >, ogdf::SList< UMLGraph * >, ogdf::SList< double >, ogdf::SList< node >, ogdf::SList< DinoUmlDiagramGraph * >, ogdf::SList< EdgeElement * >, ogdf::SList< int >, ogdf::SList< SimpleCluster * >, ogdf::SList< NodeElement * >, ogdf::SList< edge >, ogdf::SList< char * >, and ogdf::SList< adjEntry >.

Definition at line 905 of file SList.h.

template<class E>
void ogdf::SListPure< E >::conc ( SListPure< E > &  L2  )  [inline]

Appends L2 to this list and makes L2 empty.

Definition at line 541 of file SList.h.

template<class E>
void ogdf::SListPure< E >::copy ( const SListPure< E > &  L  )  [inline, protected]

Definition at line 594 of file SList.h.

template<class E>
SListConstIterator<E> ogdf::SListPure< E >::cyclicSucc ( SListConstIterator< E >  it  )  const [inline]
template<class E>
SListIterator<E> ogdf::SListPure< E >::cyclicSucc ( SListIterator< E >  it  )  [inline]
template<class E>
void ogdf::SListPure< E >::delSucc ( SListIterator< E >  itBefore  )  [inline]
template<class E>
SListConstIterator<E> ogdf::SListPure< E >::end (  )  const [inline]
template<class E>
SListIterator<E> ogdf::SListPure< E >::end (  )  [inline]
template<class E>
const E& ogdf::SListPure< E >::front (  )  const [inline]
template<class E>
SListConstIterator<E> ogdf::SListPure< E >::get ( int  pos  )  const [inline]
template<class E>
SListIterator<E> ogdf::SListPure< E >::get ( int  pos  )  [inline]
template<class E>
SListIterator<E> ogdf::SListPure< E >::insertAfter ( const E &  x,
SListIterator< E >  itBefore 
) [inline]
template<class E>
void ogdf::SListPure< E >::moveFrontToBack ( SListPure< E > &  L2  )  [inline]

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

Definition at line 490 of file SList.h.

template<class E>
void ogdf::SListPure< E >::moveFrontToFront ( SListPure< E > &  L2  )  [inline]

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

Definition at line 479 of file SList.h.

template<class E>
void ogdf::SListPure< E >::moveFrontToSucc ( SListPure< 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 506 of file SList.h.

template<class E>
SListPure<E>& ogdf::SListPure< E >::operator= ( const SListPure< E > &  L  )  [inline]

Assignment operator.

Definition at line 410 of file SList.h.

template<class E >
void ogdf::SListPure< E >::permute ( const int  n  )  [protected]

Definition at line 940 of file SList.h.

template<class E>
void ogdf::SListPure< E >::popFront (  )  [inline]
template<class E>
E ogdf::SListPure< E >::popFrontRet (  )  [inline]
template<class E>
int ogdf::SListPure< 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 in ogdf::SList< E >, ogdf::SList< UMLGraph * >, ogdf::SList< double >, ogdf::SList< node >, ogdf::SList< DinoUmlDiagramGraph * >, ogdf::SList< EdgeElement * >, ogdf::SList< int >, ogdf::SList< SimpleCluster * >, ogdf::SList< NodeElement * >, ogdf::SList< edge >, ogdf::SList< char * >, and ogdf::SList< adjEntry >.

Definition at line 346 of file SList.h.

template<class E>
template<class COMPARER >
void ogdf::SListPure< E >::quicksort ( const COMPARER &  comp  )  [inline]
template<class E>
SListIterator<E> ogdf::SListPure< E >::rbegin (  )  [inline]
template<class E>
SListConstIterator<E> ogdf::SListPure< E >::rbegin (  )  const [inline]
template<class E>
int ogdf::SListPure< E >::size (  )  const [inline]

Member Data Documentation

template<class E>
SListElement<E>* ogdf::SListPure< E >::m_head [private]

Pointer to first element.

Definition at line 248 of file SList.h.

template<class E>
SListElement<E>* ogdf::SListPure< E >::m_tail [private]

Pointer to last element.

Definition at line 249 of file SList.h.


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