DWFCore::DWFSkipList< K, V, E, L, Z > Class Template Reference

#include "dwfcore/SkipList.h"

Inheritance diagram for DWFCore::DWFSkipList< K, V, E, L, Z >:

Inheritance graph
[legend]
Collaboration diagram for DWFCore::DWFSkipList< K, V, E, L, Z >:

Collaboration graph
[legend]
List of all members.

Detailed Description

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
class DWFCore::DWFSkipList< K, V, E, L, Z >

Skip list collection template.

Since:
1.0.1
Implementation of a generic Skip List. This is a collection that maintains sort order using a highly efficient probabalistic distribution algorithm over a linked list using "skip links". The performance of this collection is excellent across search, insert, delete and linear-lookup. The algorithm was developed by William Pugh (University of Maryland, College Park). An explanation of the algorithm is available at: ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

This class may be used in place of the STL map collection though some profiling is suggested to determine which performs better for given data types and application needs.

Parameters:
K The key type.
V The value type.
E Defines equality between two keys.
L Defines ordering between two keys.
Z Defines the empty or zero-value for the key type.

Definition at line 106 of file SkipList.h.

Public Types

typedef K KeyType
 Typedef to get the key type of the skip list.
typedef V ValueType
 Typedef to get the value type of the skip list.

Public Member Functions

 DWFSkipList () throw ( DWFMemoryException )
virtual ~DWFSkipList () throw ()
virtual void clear () throw ( DWFMemoryException )
virtual size_t size () const throw ()
virtual Iteratoriterator () throw ()
virtual ConstIteratorconstIterator () const throw ()
virtual Iteratoriterator (const K &rKey) throw ()
virtual ConstIteratorconstIterator (const K &rKey) const throw ()
virtual V * find (const K &rKey) const throw ()
virtual K * key (uint64_t iPos) throw ( DWFException )
virtual V * value (uint64_t iPos) throw ( DWFException )
virtual bool erase (const K &rKey) throw ()
virtual bool insert (const K &rKey, const V &rValue, bool bReplace=true) throw ( DWFException )

Classes

class  ConstIterator
 An implementation of a key-value const iterator for skip lists. More...
class  Iterator
 An implementation of a key-value iterator for skip lists. More...


Constructor & Destructor Documentation

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
DWFCore::DWFSkipList< K, V, E, L, Z >::DWFSkipList  )  throw ( DWFMemoryException ) [inline]
 

Constructor

Exceptions:
DWFMemoryException 

Definition at line 127 of file SkipList.h.

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
virtual DWFCore::DWFSkipList< K, V, E, L, Z >::~DWFSkipList  )  throw () [inline, virtual]
 

Destructor

Exceptions:
None 

Definition at line 146 of file SkipList.h.


Member Function Documentation

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
virtual void DWFCore::DWFSkipList< K, V, E, L, Z >::clear  )  throw ( DWFMemoryException ) [inline, virtual]
 

Empties the list and restores the initial state.

Exceptions:
DWFMemoryException 

Definition at line 639 of file SkipList.h.

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
virtual ConstIterator* DWFCore::DWFSkipList< K, V, E, L, Z >::constIterator const K &  rKey  )  const throw () [inline, virtual]
 

Returns a const iterator from the keyed element in the list. The caller owns the iterator and is responsible for releasing it with the DWFCORE_FREE_OBJECT macro.

Parameters:
rKey The key of the first list element from which to start the iterator.
Returns:
A pointer to a new list iterator.
Exceptions:
None 
Since:
1.2

Definition at line 742 of file SkipList.h.

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
virtual ConstIterator* DWFCore::DWFSkipList< K, V, E, L, Z >::constIterator  )  const throw () [inline, virtual]
 

Returns a const iterator from the first element in the list. The caller owns the iterator and is responsible for releasing it with the DWFCORE_FREE_OBJECT macro.

Returns:
A pointer to a new list iterator.
Exceptions:
None 
Since:
1.2

Definition at line 711 of file SkipList.h.

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
virtual bool DWFCore::DWFSkipList< K, V, E, L, Z >::erase const K &  rKey  )  throw () [inline, virtual]
 

Removes an element from the list.

Parameters:
rKey The key of the element to erase.
Returns:
true if keyed element was erased, false if the element was not found.
Exceptions:
None 

Definition at line 830 of file SkipList.h.

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
virtual V* DWFCore::DWFSkipList< K, V, E, L, Z >::find const K &  rKey  )  const throw () [inline, virtual]
 

Search the list with a given key and return the associated value if it exists.

Parameters:
rKey The key for which to search the list.
Returns:
A pointer to the value associated with the key or NULL if the key was not found.
Exceptions:
None 

Definition at line 755 of file SkipList.h.

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
virtual bool DWFCore::DWFSkipList< K, V, E, L, Z >::insert const K &  rKey,
const V &  rValue,
bool  bReplace = true
throw ( DWFException ) [inline, virtual]
 

Adds an element to the list.

Parameters:
rKey The key of the element to add.
rValue The value of the element to add.
bReplace If the new element uses a key that already exists, this flag determines whether or not the new element will be inserted and replace the previous element or ignored.
Returns:
false the the element key is a duplicate, true otherwise.
Exceptions:
DWFException 

Definition at line 920 of file SkipList.h.

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
virtual Iterator* DWFCore::DWFSkipList< K, V, E, L, Z >::iterator const K &  rKey  )  throw () [inline, virtual]
 

Returns an iterator from the keyed element in the list. The caller owns the iterator and is responsible for releasing it with the DWFCORE_FREE_OBJECT macro.

Parameters:
rKey The key of the first list element from which to start the iterator.
Returns:
A pointer to a new list iterator.
Exceptions:
None 

Definition at line 726 of file SkipList.h.

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
virtual Iterator* DWFCore::DWFSkipList< K, V, E, L, Z >::iterator  )  throw () [inline, virtual]
 

Returns an iterator from the first element in the list. The caller owns the iterator and is responsible for releasing it with the DWFCORE_FREE_OBJECT macro.

Returns:
A pointer to a new list iterator.
Exceptions:
None 

Definition at line 696 of file SkipList.h.

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
virtual K* DWFCore::DWFSkipList< K, V, E, L, Z >::key uint64_t  iPos  )  throw ( DWFException ) [inline, virtual]
 

Return the element key at a given position if it exists.

Parameters:
iPos The position at which the element resides.
Returns:
A pointer to the key or NULL if no elements was found at iPos.
Exceptions:
DWFException 

Definition at line 780 of file SkipList.h.

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
virtual size_t DWFCore::DWFSkipList< K, V, E, L, Z >::size  )  const throw () [inline, virtual]
 

Returns the number of elements stored in the list.

Returns:
The number of list elements.
Exceptions:
None 

Definition at line 682 of file SkipList.h.

template<class K, class V, class E = tDWFCompareEqual<K>, class L = tDWFCompareLess<K>, class Z = tDWFDefinedEmpty<K>>
virtual V* DWFCore::DWFSkipList< K, V, E, L, Z >::value uint64_t  iPos  )  throw ( DWFException ) [inline, virtual]
 

Return the element value at a given position if it exists.

Parameters:
iPos The position at which the element resides.
Returns:
A pointer to the value or NULL if no elements was found at iPos.
Exceptions:
DWFException 

Definition at line 805 of file SkipList.h.


The documentation for this class was generated from the following file:
Generated on Tue Jan 6 22:39:39 2009 for Autodesk DWF Core Library by  doxygen 1.4.5