LinkedList< T > Class Template Reference

List class holding a list of objects derived from LinkedListBase (not thread-safe). More...

#include <linkedlist.h>

Collaboration diagram for LinkedList< T >:

[legend]List of all members.

Public Member Functions
	LinkedList ()
	Construct empty list:.
	~LinkedList ()
T *	first () const
	Get first and last element of the list (or NULL).
T *	last () const
bool	IsEmpty () const
	Returns true if the list is empty otherwise false.
T *	next (T *p) const
T *	prev (T *p) const
const T *	next (const T *p) const
const T *	prev (const T *p) const
void	AssignList (const LinkedList< T > *l)
void	SwapList (LinkedList< T > *l)
	This is similar, just that the list pointers are swapped.
void	insert (T *p)
	Insert p at the beginning of the list:.
void	append (T *p)
	Append p to the end of the list:.
T *	replace (T *newp, T *oldp)
void	QueueBefore (T *p, T *where)
void	QueueAfter (T *p, T *where)
void	queue (T *p, T *where, int loc)
T *	dequeue (T *p)
	Dequeues element p (and returns p).
T *	PopFirst ()
	Dequeue first/last element and return it (or NULL):.
T *	PopLast ()
const T *	search (const T *p) const
	Find element p in this list; returns either p or NULL.
const T *	SearchRev (const T *p) const
	The same as search() but traverse the list from last to first.
int	count () const
	Cound the elements in the list:.
void	clear ()
	Clear list by deleting all entries.
void	AppendList (LinkedList< T > &b)
	Append content of passed list to this list.
T *	MiddleNode () const
	Find (left) middle element in list.
template<typename OP> void	MergeLists (LinkedList< T > &a, LinkedList< T > &b, const OP &_OP)
	Merge two sorted lists.
template<typename OP> void	MergeSort (const OP &_OP)
	Sort the list.
Private Member Functions
LinkedList &	operator= (const LinkedList &l)
	Don't use: (use AssignList in rare cases):.
	LinkedList (const LinkedList &l)
Private Attributes
T *	lfirst
T *	llast

---

Detailed Description

template<typename T>
class LinkedList< T >

List class holding a list of objects derived from LinkedListBase (not thread-safe).

See also:

File linkedlist.h for more information.

Author:

Wolfgang Wieser ] wwieser (a) gmx <*> de [

Definition at line 126 of file linkedlist.h.

---

Constructor & Destructor Documentation

template<typename T> LinkedList< T >::LinkedList (  const LinkedList< T > &  l  )  [inline, private]

Definition at line 134 of file linkedlist.h.

template<typename T> LinkedList< T >::LinkedList (   )  [inline]

Construct empty list:. Definition at line 138 of file linkedlist.h.

template<typename T> LinkedList< T >::~LinkedList (   )  [inline]

It is your responsibility to properly empty the list before destroying it. Definition at line 141 of file linkedlist.h.

---

Member Function Documentation

template<typename T> void LinkedList< T >::append (  T *  p  )  [inline]

Append p to the end of the list:. Definition at line 182 of file linkedlist.h. Referenced by LinkedList< FileNode >::MergeLists(), and LinkedList< FileNode >::QueueAfter().

template<typename T> void LinkedList< T >::AppendList (  LinkedList< T > &  b  )  [inline]

Append content of passed list to this list. All elements in the passed list will be appended to this list and the passed list will be empty afterwards. This is much faster than while(!b.IsEmpty()) a.append(b.PopFirst()); (Runtime is O(1).) Definition at line 310 of file linkedlist.h. Referenced by LinkedList< FileNode >::MergeLists().

template<typename T> void LinkedList< T >::AssignList (  const LinkedList< T > *  l  )  [inline]

Use with care!! Just copies pointer to head and tail of list; if you modify one of the lists, the other one will get inconsistent if lfirst/llast get modified. Definition at line 161 of file linkedlist.h.

template<typename T> void LinkedList< T >::clear (   )  [inline]

Clear list by deleting all entries. Definition at line 295 of file linkedlist.h.

template<typename T> int LinkedList< T >::count (   )  const [inline]

Cound the elements in the list:. Definition at line 287 of file linkedlist.h.

template<typename T> T* LinkedList< T >::dequeue (  T *  p  )  [inline]

Dequeues element p (and returns p). Definition at line 238 of file linkedlist.h.

template<typename T> T* LinkedList< T >::first (   )  const [inline]

Get first and last element of the list (or NULL). Definition at line 144 of file linkedlist.h.

template<typename T> void LinkedList< T >::insert (  T *  p  )  [inline]

Insert p at the beginning of the list:. Definition at line 170 of file linkedlist.h. Referenced by LinkedList< FileNode >::QueueBefore().

template<typename T> bool LinkedList< T >::IsEmpty (   )  const [inline]

Returns true if the list is empty otherwise false. Definition at line 148 of file linkedlist.h. Referenced by LinkedList< FileNode >::AppendList(), LinkedList< FileNode >::clear(), and LinkedList< FileNode >::MergeSort().

template<typename T> T* LinkedList< T >::last (   )  const [inline]

Definition at line 145 of file linkedlist.h.

template<typename T> template<typename OP> void LinkedList< T >::MergeLists (  LinkedList< T > &  a, LinkedList< T > &  b, const OP &  _OP )  [inline]

Merge two sorted lists. The two lists a and b must be ascentingly sorted and will be merged into this list by successively appending the elements from the beginning of a or b to this list. In the end, lists a and b will be empty and all elements will have been appended to this list. Runtime is O(n_a+n_b). This algorithm will use elements of a before those in b in case they are equally large (hence, if list a holds the elements "left" of those in b, it is stable). The passed operator template is used to compare elements; it must implement the le (lesser equal) relation. (Arguments to le are of type "const T &".) Definition at line 368 of file linkedlist.h. Referenced by LinkedList< FileNode >::MergeSort().

template<typename T> template<typename OP> void LinkedList< T >::MergeSort (  const OP &  _OP  )  [inline]

Sort the list. This implements the merge sort algorithm on the list. The runtime is O(n*log(n)) and no additional memory besides the call stack of depth O(log(n)) is required. The sorting algorithm is stable. The passed operator template must implement the le (lesser equal) relation; see MergeLists(). Todo: MergeSort: This could be optimized (count elems once, not in MiddleNode(), (de)queuing overhead...). FIXME!!! Definition at line 391 of file linkedlist.h. Referenced by LinkedList< FileNode >::MergeSort().

template<typename T> T* LinkedList< T >::MiddleNode (   )  const [inline]

Find (left) middle element in list. This function finds the middle node element in the list by walking the list from start and end until "colliding" in the middle. Runtime is O(n). Returns: Pointer to the middle element; if the number of elemets is odd, then there are equally many elements before and after the returned element; if it is even, the number of elements before the returned is equal to the number of elements in the sublist started with the returned element. I.e.: In the list [0] [1] [2], the middle element is [1]. In the list [0] [1] [2] [3], the middle element is [2] (note: list has 4 elements; 4/2 = 2) Returns NULL for empty list. Definition at line 342 of file linkedlist.h. Referenced by LinkedList< FileNode >::MergeSort().

template<typename T> const T* LinkedList< T >::next (  const T *  p  )  const [inline]

Definition at line 155 of file linkedlist.h.

template<typename T> T* LinkedList< T >::next (  T *  p  )  const [inline]

Get next/prev element from passed element. May be used if you experience ambiguities using multiple inheritance. Definition at line 153 of file linkedlist.h.

template<typename T> LinkedList& LinkedList< T >::operator= (  const LinkedList< T > &  l  )  [inline, private]

Don't use: (use AssignList in rare cases):. Definition at line 132 of file linkedlist.h.

template<typename T> T* LinkedList< T >::PopFirst (   )  [inline]

Dequeue first/last element and return it (or NULL):. Definition at line 250 of file linkedlist.h. Referenced by LinkedList< FileNode >::clear(), and LinkedList< FileNode >::MergeLists().

template<typename T> T* LinkedList< T >::PopLast (   )  [inline]

Definition at line 260 of file linkedlist.h.

template<typename T> const T* LinkedList< T >::prev (  const T *  p  )  const [inline]

Definition at line 156 of file linkedlist.h.

template<typename T> T* LinkedList< T >::prev (  T *  p  )  const [inline]

Definition at line 154 of file linkedlist.h.

template<typename T> void LinkedList< T >::queue (  T *  p, T *  where, int  loc )  [inline]

Queue before/after `where´, depending on loc. loc<0 -> before; loc>0 -> after; loc==0 -> do nothing Definition at line 231 of file linkedlist.h.

template<typename T> void LinkedList< T >::QueueAfter (  T *  p, T *  where )  [inline]

Definition at line 218 of file linkedlist.h. Referenced by LinkedList< FileNode >::queue().

template<typename T> void LinkedList< T >::QueueBefore (  T *  p, T *  where )  [inline]

Put p before/after `where´ into the queue: Make sure, `where´ is not NULL. Definition at line 208 of file linkedlist.h. Referenced by LinkedList< FileNode >::queue().

template<typename T> T* LinkedList< T >::replace (  T *  newp, T *  oldp )  [inline]

Dequeues *oldp and puts newp at the place where oldp was. Make sure neither oldp nor newp are NULL. Returns oldp (so that you may pass it to operator delete). Definition at line 196 of file linkedlist.h.

template<typename T> const T* LinkedList< T >::search (  const T *  p  )  const [inline]

Find element p in this list; returns either p or NULL. Definition at line 272 of file linkedlist.h.

template<typename T> const T* LinkedList< T >::SearchRev (  const T *  p  )  const [inline]

The same as search() but traverse the list from last to first. Definition at line 279 of file linkedlist.h.

template<typename T> void LinkedList< T >::SwapList (  LinkedList< T > *  l  )  [inline]

This is similar, just that the list pointers are swapped. Definition at line 165 of file linkedlist.h.

---

Member Data Documentation

template<typename T> T* LinkedList< T >::lfirst [private]

Definition at line 129 of file linkedlist.h. Referenced by LinkedList< FileNode >::AppendList(), LinkedList< FileNode >::AssignList(), LinkedList< FileNode >::LinkedList(), LinkedList< FileNode >::MergeLists(), LinkedList< FileNode >::MergeSort(), LinkedList< FileNode >::operator=(), and LinkedList< FileNode >::SwapList().

template<typename T> T * LinkedList< T >::llast [private]

Definition at line 129 of file linkedlist.h. Referenced by LinkedList< FileNode >::AppendList(), LinkedList< FileNode >::AssignList(), LinkedList< FileNode >::LinkedList(), LinkedList< FileNode >::MergeSort(), LinkedList< FileNode >::operator=(), and LinkedList< FileNode >::SwapList().

---

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

• /ray/src/lib/tl/linkedlist.h

---