XBidiCompositeSkipList< T, N, S, R > Class Template Reference

Bidirectional Composite SkipList. More...

#include <CSCompositeSkipList.h>

List of all members.

Public Types
typedef XBidiCompositeSkipList < T, N, S, R >	container_type
	Type that represents this container.
typedef size_t	size_type
	An unsigned integral type that can represent any nonnegative value of the container's distance type.
typedef ptrdiff_t	difference_type
	A signed integral type used to represent the distance between two of the container's iterators.
typedef T	value_type
	The type of the object stored in a container.
typedef XBidiNode< value_type, N, S >	node_type
	Internal node type.
typedef XData< size_type, difference_type, node_type, value_type, N, S, R >	data_type
	Internal shared data type.
typedef XList< T, node_type > **	XListArray
	Type for Container array.
Public Member Functions
	XBidiCompositeSkipList ()
	Default Constructor O(1)
	XBidiCompositeSkipList (double probability, unsigned int maxLevel)
	Constructor O(1)
	XBidiCompositeSkipList (size_type maxNodes)
	Constructor O(1)
	XBidiCompositeSkipList (const container_type &source)
	Copy Constructor O(m*n)
template<class InIt >
	XBidiCompositeSkipList (InIt first, InIt last)
	Constructor O(m*n*logn)
template<class InIt >
	XBidiCompositeSkipList (InIt first, InIt last, double probability, unsigned int maxLevel)
	Constructor O(m*n*logn)
template<class InIt >
	XBidiCompositeSkipList (InIt first, InIt last, size_type maxNodes)
	Constructor O(m*n*logn)
virtual	~XBidiCompositeSkipList ()
	Destructor O(n+m)
container_type &	operator= (const container_type &source)
	Assignment Operator O(n)
void	swap (container_type &right)
	Swaps the contents of two lists. O(m)
void	clear ()
	Erases all of the elements. O(m+n)
void	destroy ()
	Deletes and erases all of the pointer elements. O(m+n)
size_type	size () const
	Returns the size of the list. O(1)
bool	empty () const
	Returns true if the list's size is 0. O(1)
XList< T, node_type > **	getContainers ()
	Returns Internal Container array.
Public Attributes
friend	XList< T, node_type >
	Base type of iterators.
XListArray	Containers
	Container array.
Protected Member Functions
void	Init (double probability, unsigned int maxLevel)
	Set probability for number of levels in a new node and maximum number of levels in the entire list. O(1)
Protected Attributes
data_type	data
	Internal shared data.

---

Detailed Description

template<class T, unsigned int N, unsigned int S = 0, class R = RNG>
class XBidiCompositeSkipList< T, N, S, R >

Bidirectional Composite SkipList.

This container is used as a base class for a user's custom composite container.

This container has very little functionality. Instead, delegate containers should be used.

In the performance notation, m is N, the number of internal containers. And n is the number of elements.

Template Parameters:

T	Type of object stored as an element in the container.
N	The total number of internal containers.
S	The index of the first non-indexed, sorted container.
R	The type for the random number generator.

---

Member Typedef Documentation

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

typedef ptrdiff_t XBidiCompositeSkipList< T, N, S, R >::difference_type

A signed integral type used to represent the distance between two of the container's iterators.

This type must be the same as the iterator's distance type.

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

typedef T XBidiCompositeSkipList< T, N, S, R >::value_type

The type of the object stored in a container.

The value type must be Assignable, but need not be DefaultConstructible.

---

Constructor & Destructor Documentation

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

XBidiCompositeSkipList< T, N, S, R >::XBidiCompositeSkipList

(

)

[inline]

Default Constructor O(1)

Probability is 0.25. Maximum level is set to 8.

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

XBidiCompositeSkipList< T, N, S, R >::XBidiCompositeSkipList	(	double	probability,
		unsigned int	maxLevel
	)		[inline]

Constructor O(1)

Parameters:

probability	Probability for number of levels in a new node.
maxLevel	Maxmimum number of levels for this list.

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

XBidiCompositeSkipList< T, N, S, R >::XBidiCompositeSkipList

(

size_type

maxNodes

)

[inline]

Constructor O(1)

Probability is 0.25. Automatically generate probability based on maximum number of nodes.

Parameters:

maxNodes

Number of nodes to calculate maximum level for this list.

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

XBidiCompositeSkipList< T, N, S, R >::XBidiCompositeSkipList

(

const container_type &

source

)

[inline]

Copy Constructor O(m*n)

TODO: This could be recoded to be O(n).

Parameters:

source

Container to copy from.

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

template<class InIt >

XBidiCompositeSkipList< T, N, S, R >::XBidiCompositeSkipList	(	InIt	first,
		InIt	last
	)		[inline]

Constructor O(m*n*logn)

Probability is 0.25. Maximum level is set to 8.

Parameters:

first	iterator to first element to copy.
last	iterator just beyond last element to copy.

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

template<class InIt >

XBidiCompositeSkipList< T, N, S, R >::XBidiCompositeSkipList	(	InIt	first,
		InIt	last,
		double	probability,
		unsigned int	maxLevel
	)		[inline]

Constructor O(m*n*logn)

Parameters:

first	iterator to first element to copy.
last	iterator just beyond last element to copy.
probability	Probability for number of levels in a new node.
maxLevel	Maxmimum number of levels for this list.

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

template<class InIt >

XBidiCompositeSkipList< T, N, S, R >::XBidiCompositeSkipList	(	InIt	first,
		InIt	last,
		size_type	maxNodes
	)		[inline]

Constructor O(m*n*logn)

Probability is 0.25. Automatically generate probability based on maximum number of nodes.

Parameters:

first	iterator to first element to copy.
last	iterator just beyond last element to copy.
maxNodes	Number of nodes to calculate maximum level for this list.

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

virtual XBidiCompositeSkipList< T, N, S, R >::~XBidiCompositeSkipList

(

)

[inline, virtual]

Destructor O(n+m)

Clears list.

---

Member Function Documentation

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

void XBidiCompositeSkipList< T, N, S, R >::Init	(	double	probability,
		unsigned int	maxLevel
	)		[inline, protected]

Set probability for number of levels in a new node and maximum number of levels in the entire list. O(1)

Parameters:

probability	Probability for number of levels in a new node.
maxLevel	Maxmimum number of levels for this list.

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

container_type& XBidiCompositeSkipList< T, N, S, R >::operator=

(

const container_type &

source

)

[inline]

Assignment Operator O(n)

Clears current list and copies source elements to current list.

Parameters:

source

list to copy from.

Returns:

reference to current list.

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

void XBidiCompositeSkipList< T, N, S, R >::swap

(

container_type &

right

)

[inline]

Swaps the contents of two lists. O(m)

Parameters:

right

list with which to swap contents.

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

size_type XBidiCompositeSkipList< T, N, S, R >::size

(

)

const [inline]

Returns the size of the list. O(1)

Returns:

size of the list.

template<class T , unsigned int N, unsigned int S = 0, class R = RNG>

bool XBidiCompositeSkipList< T, N, S, R >::empty

(

)

const [inline]

Returns true if the list's size is 0. O(1)

Returns:

true if the list's size is 0, false otherwise.

---

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

• CSCompositeSkipList.h