CSCompositeSkipList.h File Reference

Header for XBidiCompositeSkipList, XIndexedSkipList, XMultiSkipList, XMultiAutoSkipList XMultiAccessSkipList and XMultiAutoAccessSkipList. More...

#include <algorithm>
#include <functional>
#include <utility>
#include <iterator>
#include "CSSkipListTools.h"

Go to the source code of this file.

Classes
class	XList< T, NT >
	Pure virtual base class for internal containers to the multilist. More...
class	XTmpContainer< size_type, node_type >
	Internal temporary container for cutting and splicing nodes. More...
class	XData< size_type, difference_type, node_type, value_type, N, S, R >
	Shared data for use with XBidiCompositeSkipList and its internal containers. More...
class	XBidiNode< T, N, S >
	Internal Bidirection Node used with XBidiCompositeSkipList. More...
struct	XBidiNode< T, N, S >::Pointers
	Structure to store forward and backward pointers including skip amounts. More...
class	XBidiCompositeSkipList< T, N, S, R >
	Bidirectional Composite SkipList. More...
class	XIterator0< X, container_type >
	Random Access LOGN Iterator for XIndexedSkipList and XMultiAutoSkipList. More...
class	XIterator1< X, container_type >
	Random Access LOGN const_iterator for XIndexedSkipList and XMultiAutoSkipList. More...
class	XIndexedSkipList< X, CT >
	Internal container for custom multilist derived from XBidiCompositeSkipList. More...
class	XMultiAutoSkipList< X, CT, Pr >
	Internal container for custom multilist derived from XBidiCompositeSkipList. More...
class	XMultiAutoAccessSkipList< X, K, CT, A, Pr >
	Internal container for custom multilist derived from XBidiCompositeSkipList. More...
class	XMultiAutoAccessSkipList< X, K, CT, A, Pr >::value_compare
	Compares the keys found in two values. (Sorted Associative Container) More...
class	YIterator0< X, container_type >
	Bidirectional Iterator for XMultiSkipList. More...
class	YIterator1< X, container_type >
	Bidirectional const_iterator for XMultiSkipList. More...
class	XMultiSkipList< X, CT, Pr >
	Internal container for custom multilist derived from XBidiCompositeSkipList. More...
class	XMultiAccessSkipList< X, K, CT, A, Pr >
	Internal container for custom multilist derived from XBidiCompositeSkipList. More...
class	XMultiAccessSkipList< X, K, CT, A, Pr >::value_compare
	Compares the keys found in two values. (Sorted Associative Container) More...
class	XDerefT< T, Pr >
	Predicate wrapper to act on node pointers. More...
class	LessEqualT< T, Pr >
	Converts a "less than" predicate into a "less than or equal" predicate. More...
Functions
template<unsigned int X, class container_type , class Pr >
void	sort (CS::XIterator0< X, container_type > first, CS::XIterator0< X, container_type > last, const Pr pred)
	Sorts nodes in XIndexedSkipList.
template<unsigned int X, class container_type , class Pr >
void	stable_sort (CS::XIterator0< X, container_type > first, CS::XIterator0< X, container_type > last, const Pr pred)
	Sorts nodes in XIndexedSkipList.
template<unsigned int X, class container_type >
void	sort (CS::XIterator0< X, container_type > first, CS::XIterator0< X, container_type > last)
	Sorts nodes in XIndexedSkipList.
template<unsigned int X, class container_type >
void	stable_sort (CS::XIterator0< X, container_type > first, CS::XIterator0< X, container_type > last)
	Sorts nodes in XIndexedSkipList.
template<int X, class CT >
bool	operator== (const XIndexedSkipList< X, CT > &left, const XIndexedSkipList< X, CT > &right)
	Equality Operator (Forward Container)
template<int X, class CT >
bool	operator!= (const XIndexedSkipList< X, CT > &left, const XIndexedSkipList< X, CT > &right)
	NotEqual Operator (Forward Container)
template<int X, class CT >
bool	operator< (const XIndexedSkipList< X, CT > &left, const XIndexedSkipList< X, CT > &right)
	LessThan Operator (Forward Container)
template<int X, class CT >
bool	operator<= (const XIndexedSkipList< X, CT > &left, const XIndexedSkipList< X, CT > &right)
	LessThanOrEqual Operator (Forward Container)
template<int X, class CT >
bool	operator> (const XIndexedSkipList< X, CT > &left, const XIndexedSkipList< X, CT > &right)
	GreaterThan Operator (Forward Container)
template<int X, class CT >
bool	operator>= (const XIndexedSkipList< X, CT > &left, const XIndexedSkipList< X, CT > &right)
	GreaterThanOrEqual Operator (Forward Container)
template<int X, class container_type , class Pr >
CS::XIterator0< X, container_type >	scan (const CS::XIterator0< X, container_type > &first, const CS::XIterator0< X, container_type > &last, typename container_type::const_reference value, const Pr &pred)
	Scans an internal container until the predicate is false and sets up the cache. O(logn)
template<int X, class CT , class Pr >
bool	operator== (const XMultiAutoSkipList< X, CT, Pr > &left, const XMultiAutoSkipList< X, CT, Pr > &right)
	Equality Operator (Forward Container)
template<int X, class CT , class Pr >
bool	operator!= (const XMultiAutoSkipList< X, CT, Pr > &left, const XMultiAutoSkipList< X, CT, Pr > &right)
	NotEqual Operator (Forward Container)
template<int X, class CT , class Pr >
bool	operator< (const XMultiAutoSkipList< X, CT, Pr > &left, const XMultiAutoSkipList< X, CT, Pr > &right)
	LessThan Operator (Forward Container)
template<int X, class CT , class Pr >
bool	operator<= (const XMultiAutoSkipList< X, CT, Pr > &left, const XMultiAutoSkipList< X, CT, Pr > &right)
	LessThanOrEqual Operator (Forward Container)
template<int X, class CT , class Pr >
bool	operator> (const XMultiAutoSkipList< X, CT, Pr > &left, const XMultiAutoSkipList< X, CT, Pr > &right)
	GreaterThan Operator (Forward Container)
template<int X, class CT , class Pr >
bool	operator>= (const XMultiAutoSkipList< X, CT, Pr > &left, const XMultiAutoSkipList< X, CT, Pr > &right)
	GreaterThanOrEqual Operator (Forward Container)
template<unsigned int X, class K , class CT , class A , class Pr >
bool	operator== (const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &left, const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &right)
	Equality Operator (Forward Container)
template<unsigned int X, class K , class CT , class A , class Pr >
bool	operator!= (const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &left, const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &right)
	NotEqual Operator (Forward Container)
template<unsigned int X, class K , class CT , class A , class Pr >
bool	operator< (const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &left, const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &right)
	LessThan Operator (Forward Container)
template<unsigned int X, class K , class CT , class A , class Pr >
bool	operator<= (const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &left, const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &right)
	LessThanOrEqual Operator (Forward Container)
template<unsigned int X, class K , class CT , class A , class Pr >
bool	operator> (const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &left, const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &right)
	GreaterThan Operator (Forward Container)
template<unsigned int X, class K , class CT , class A , class Pr >
bool	operator>= (const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &left, const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &right)
	GreaterThanOrEqual Operator (Forward Container)
template<int X, class CT , class Pr >
bool	operator== (const XMultiSkipList< X, CT, Pr > &left, const XMultiSkipList< X, CT, Pr > &right)
	Equality Operator (Forward Container)
template<int X, class CT , class Pr >
bool	operator!= (const XMultiSkipList< X, CT, Pr > &left, const XMultiSkipList< X, CT, Pr > &right)
	NotEqual Operator (Forward Container)
template<int X, class CT , class Pr >
bool	operator< (const XMultiSkipList< X, CT, Pr > &left, const XMultiSkipList< X, CT, Pr > &right)
	LessThan Operator (Forward Container)
template<int X, class CT , class Pr >
bool	operator<= (const XMultiSkipList< X, CT, Pr > &left, const XMultiSkipList< X, CT, Pr > &right)
	LessThanOrEqual Operator (Forward Container)
template<int X, class CT , class Pr >
bool	operator> (const XMultiSkipList< X, CT, Pr > &left, const XMultiSkipList< X, CT, Pr > &right)
	GreaterThan Operator (Forward Container)
template<int X, class CT , class Pr >
bool	operator>= (const XMultiSkipList< X, CT, Pr > &left, const XMultiSkipList< X, CT, Pr > &right)
	GreaterThanOrEqual Operator (Forward Container)
template<unsigned int X, class K , class CT , class A , class Pr >
bool	operator== (const XMultiAcessSkipList< X, K, CT, A, Pr > &left, const XMultiAcessSkipList< X, K, CT, A, Pr > &right)
	Equality Operator (Forward Container)
template<unsigned int X, class K , class CT , class A , class Pr >
bool	operator!= (const XMultiAcessSkipList< X, K, CT, A, Pr > &left, const XMultiAcessSkipList< X, K, CT, A, Pr > &right)
	NotEqual Operator (Forward Container)
template<unsigned int X, class K , class CT , class A , class Pr >
bool	operator< (const XMultiAcessSkipList< X, K, CT, A, Pr > &left, const XMultiAcessSkipList< X, K, CT, A, Pr > &right)
	LessThan Operator (Forward Container)
template<unsigned int X, class K , class CT , class A , class Pr >
bool	operator<= (const XMultiAcessSkipList< X, K, CT, A, Pr > &left, const XMultiAcessSkipList< X, K, CT, A, Pr > &right)
	LessThanOrEqual Operator (Forward Container)
template<unsigned int X, class K , class CT , class A , class Pr >
bool	operator> (const XMultiAcessSkipList< X, K, CT, A, Pr > &left, const XMultiAcessSkipList< X, K, CT, A, Pr > &right)
	GreaterThan Operator (Forward Container)
template<unsigned int X, class K , class CT , class A , class Pr >
bool	operator>= (const XMultiAcessSkipList< X, K, CT, A, Pr > &left, const XMultiAcessSkipList< X, K, CT, A, Pr > &right)
	GreaterThanOrEqual Operator (Forward Container)
template<unsigned int X, class container_type >
void	iter_swap (CS::XIterator0< X, container_type > left, CS::XIterator0< X, container_type > right)
	Swaps element nodes for XIndexedSkipList iterators.
template<unsigned int X, class container_type >
void	reverse (CS::XIterator0< X, container_type > first, CS::XIterator0< X, container_type > last)
	Reverses the nodes in XIndexedSkipList.
template<unsigned int X, class container_type >
void	quick_sort (CS::XIterator0< X, container_type > first, CS::XIterator0< X, container_type > last)
	QuickSort for XIndexedSkipList.
template<unsigned int X, class container_type , class Pr >
void	insert_sort_N (const CS::XIterator0< X, container_type > &first, const CS::XIterator0< X, container_type > &last, const Pr &pred)
	An optimized insertion sort for XIndexedSkipList.
template<unsigned int X, class container_type , class Pr >
void	insert_sort (const CS::XIterator0< X, container_type > &first, const CS::XIterator0< X, container_type > &last, const Pr &pred)
	Default insertion sort for XIndexedSkipList.
template<unsigned int X, class container_type >
void	insert_sort (const CS::XIterator0< X, container_type > &first, const CS::XIterator0< X, container_type > &last)
	Default insertion sort for XIndexedSkipList.
template<unsigned int X, class container_type , class Pr >
void	merge_sort (CS::XIterator0< X, container_type > &first, CS::XIterator0< X, container_type > &last, const Pr &pred)
	Optimized merge sort for XIndexedSkipList.
template<unsigned int X, class container_type >
void	merge_sort (CS::XIterator0< X, container_type > &first, CS::XIterator0< X, container_type > &last)
	Optimized merge sort for XIndexedSkipList.

---

Detailed Description

Header for XBidiCompositeSkipList, XIndexedSkipList, XMultiSkipList, XMultiAutoSkipList XMultiAccessSkipList and XMultiAutoAccessSkipList.

XBidiCompositeSkipList is a composite skiplist. XIndexedSkipList is an internal container used within XBidiCompositeSkipList for indexed ordering. XMultiSkipList is an internal container used within XBidiCompositeSkipList for sorted ordering. XMultiAutoSkipList is an internal container used within XBidiCompositeSkipList for sorted and automatically indexed ordering. XMultiAccessSkipList is an internal container used within XBidiCompositeSkipList for sorted ordering where the key is a member of the element. XMultiAutoAccessSkipList is an internal container used within XBidiCompositeSkipList for sorted and automatically indexed ordering where the key is a member of the element.

---

Function Documentation

template<unsigned int X, class container_type , class Pr >

void sort	(	CS::XIterator0< X, container_type >	first,
		CS::XIterator0< X, container_type >	last,
		const Pr	pred
	)

Sorts nodes in XIndexedSkipList.

WARNING: Do not use on iterators for containers other than XIndexedSkiplist.

Sorts nodes of range in an XIndexedSkipList internal container. This is a stable sort where equal elements remain in their original order.

This function currently uses an optimized Merge Sort.

All iterators within the range will continue to point to their original elements, but will be partially invalidated. Call refresh() to revalidate. last remains validated.

Parameters:

first	Iterator that points to start of range.
last	Iterator that points to one element past the end of the range.
pred	LessThan predicate for comparisons.

template<unsigned int X, class container_type , class Pr >

void stable_sort	(	CS::XIterator0< X, container_type >	first,
		CS::XIterator0< X, container_type >	last,
		const Pr	pred
	)

Sorts nodes in XIndexedSkipList.

WARNING: Do not use on iterators for containers other than XIndexedSkiplist.

Sorts nodes of range in an XIndexedSkipList internal container. This is a stable sort where equal elements remain in their original order.

This function currently uses an optimized Merge Sort.

All iterators within the range will continue to point to their original elements, but will be partially invalidated. Call refresh() to revalidate. last remains validated.

Parameters:

first	Iterator that points to start of range.
last	Iterator that points to one element past the end of the range.
pred	LessThan predicate for comparisons.

template<unsigned int X, class container_type >

void sort	(	CS::XIterator0< X, container_type >	first,
		CS::XIterator0< X, container_type >	last
	)

Sorts nodes in XIndexedSkipList.

WARNING: Do not use on iterators for containers other than XIndexedSkiplist.

Sorts nodes of range in an XIndexedSkipList internal container. Currently uses Merge Sort which is stable, but do not rely on this feature. Future versions may use a faster unstable sort. Uses operator<() for comparisons.

All iterators within the range will continue to point to their original elements, but will be partially invalidated. Call refresh() to revalidate. last remains validated.

Parameters:

first	Iterator that points to start of range.
last	Iterator that points to one element past the end of the range.

template<unsigned int X, class container_type >

void stable_sort	(	CS::XIterator0< X, container_type >	first,
		CS::XIterator0< X, container_type >	last
	)

Sorts nodes in XIndexedSkipList.

WARNING: Do not use on iterators for containers other than XIndexedSkiplist.

Sorts nodes of range in an XIndexedSkipList internal container. This is a stable sort where equal elements remain in their original order. Uses operator<() for comparisons.

This function currently uses an optimized Merge Sort.

All iterators within the range will continue to point to their original elements, but will be partially invalidated. Call refresh() to revalidate. last remains validated.

Parameters:

first	Iterator that points to start of range.
last	Iterator that points to one element past the end of the range.

template<int X, class CT >

bool operator==	(	const XIndexedSkipList< X, CT > &	left,
		const XIndexedSkipList< X, CT > &	right
	)

Equality Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is equal to right. false, otherwise.

template<int X, class CT >

bool operator!=	(	const XIndexedSkipList< X, CT > &	left,
		const XIndexedSkipList< X, CT > &	right
	)

NotEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is not equal to right. false, otherwise.

template<int X, class CT >

bool operator<	(	const XIndexedSkipList< X, CT > &	left,
		const XIndexedSkipList< X, CT > &	right
	)

LessThan Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is less than right. false, otherwise.

template<int X, class CT >

bool operator<=	(	const XIndexedSkipList< X, CT > &	left,
		const XIndexedSkipList< X, CT > &	right
	)

LessThanOrEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is less than or equal to right. false, otherwise.

template<int X, class CT >

bool operator>	(	const XIndexedSkipList< X, CT > &	left,
		const XIndexedSkipList< X, CT > &	right
	)

GreaterThan Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is greater than right. false, otherwise.

template<int X, class CT >

bool operator>=	(	const XIndexedSkipList< X, CT > &	left,
		const XIndexedSkipList< X, CT > &	right
	)

GreaterThanOrEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is greater than or equal right. false, otherwise.

template<int X, class container_type , class Pr >

CS::XIterator0<X,container_type> scan	(	const CS::XIterator0< X, container_type > &	first,
		const CS::XIterator0< X, container_type > &	last,
		typename container_type::const_reference	value,
		const Pr &	pred
	)

Scans an internal container until the predicate is false and sets up the cache. O(logn)

Used by custom merge sort routine to find merge points.

Suppose you have a list of integers and you want to find the next element within a sorted range that is greator or equal to 42. You would have a value of 42 and call the following.

iterator i=scan(first,last,42,std::less<int>()); i would point to an element equal to or greater than 42, or end() if no element was found.

Template Parameters:

X	Index of internal container.
container_type	Type of internal container being scanned.
Pr	Predicate used to compare two elements.

Parameters:

first	Start of range to scan.
last	One position beyond end of range to scan.
value	Value to scan for.
pred	Scan until pred(*iter++,value) is false.

Returns:

iterator that points to element where pred(*iter,value) is false.

template<int X, class CT , class Pr >

bool operator==	(	const XMultiAutoSkipList< X, CT, Pr > &	left,
		const XMultiAutoSkipList< X, CT, Pr > &	right
	)

Equality Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is equal to right. false, otherwise.

template<int X, class CT , class Pr >

bool operator!=	(	const XMultiAutoSkipList< X, CT, Pr > &	left,
		const XMultiAutoSkipList< X, CT, Pr > &	right
	)

NotEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is not equal to right. false, otherwise.

template<int X, class CT , class Pr >

bool operator<	(	const XMultiAutoSkipList< X, CT, Pr > &	left,
		const XMultiAutoSkipList< X, CT, Pr > &	right
	)

LessThan Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is less than right. false, otherwise.

template<int X, class CT , class Pr >

bool operator<=	(	const XMultiAutoSkipList< X, CT, Pr > &	left,
		const XMultiAutoSkipList< X, CT, Pr > &	right
	)

LessThanOrEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is less than or equal to right. false, otherwise.

template<int X, class CT , class Pr >

bool operator>	(	const XMultiAutoSkipList< X, CT, Pr > &	left,
		const XMultiAutoSkipList< X, CT, Pr > &	right
	)

GreaterThan Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is greater than right. false, otherwise.

template<int X, class CT , class Pr >

bool operator>=	(	const XMultiAutoSkipList< X, CT, Pr > &	left,
		const XMultiAutoSkipList< X, CT, Pr > &	right
	)

GreaterThanOrEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is greater than or equal right. false, otherwise.

template<unsigned int X, class K , class CT , class A , class Pr >

bool operator==	(	const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &	left,
		const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &	right
	)

Equality Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is equal to right. false, otherwise.

template<unsigned int X, class K , class CT , class A , class Pr >

bool operator!=	(	const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &	left,
		const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &	right
	)

NotEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is not equal to right. false, otherwise.

template<unsigned int X, class K , class CT , class A , class Pr >

bool operator<	(	const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &	left,
		const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &	right
	)

LessThan Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is less than right. false, otherwise.

template<unsigned int X, class K , class CT , class A , class Pr >

bool operator<=	(	const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &	left,
		const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &	right
	)

LessThanOrEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is less than or equal to right. false, otherwise.

template<unsigned int X, class K , class CT , class A , class Pr >

bool operator>	(	const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &	left,
		const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &	right
	)

GreaterThan Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is greater than right. false, otherwise.

template<unsigned int X, class K , class CT , class A , class Pr >

bool operator>=	(	const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &	left,
		const XMultiAutoAcessSkipList< X, K, CT, A, Pr > &	right
	)

GreaterThanOrEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is greater than or equal right. false, otherwise.

template<int X, class CT , class Pr >

bool operator==	(	const XMultiSkipList< X, CT, Pr > &	left,
		const XMultiSkipList< X, CT, Pr > &	right
	)

Equality Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is equal to right. false, otherwise.

template<int X, class CT , class Pr >

bool operator!=	(	const XMultiSkipList< X, CT, Pr > &	left,
		const XMultiSkipList< X, CT, Pr > &	right
	)

NotEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is not equal to right. false, otherwise.

template<int X, class CT , class Pr >

bool operator<	(	const XMultiSkipList< X, CT, Pr > &	left,
		const XMultiSkipList< X, CT, Pr > &	right
	)

LessThan Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is less than right. false, otherwise.

template<int X, class CT , class Pr >

bool operator<=	(	const XMultiSkipList< X, CT, Pr > &	left,
		const XMultiSkipList< X, CT, Pr > &	right
	)

LessThanOrEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is less than or equal to right. false, otherwise.

template<int X, class CT , class Pr >

bool operator>	(	const XMultiSkipList< X, CT, Pr > &	left,
		const XMultiSkipList< X, CT, Pr > &	right
	)

GreaterThan Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is greater than right. false, otherwise.

template<int X, class CT , class Pr >

bool operator>=	(	const XMultiSkipList< X, CT, Pr > &	left,
		const XMultiSkipList< X, CT, Pr > &	right
	)

GreaterThanOrEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is greater than or equal right. false, otherwise.

template<unsigned int X, class K , class CT , class A , class Pr >

bool operator==	(	const XMultiAcessSkipList< X, K, CT, A, Pr > &	left,
		const XMultiAcessSkipList< X, K, CT, A, Pr > &	right
	)

Equality Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is equal to right. false, otherwise.

template<unsigned int X, class K , class CT , class A , class Pr >

bool operator!=	(	const XMultiAcessSkipList< X, K, CT, A, Pr > &	left,
		const XMultiAcessSkipList< X, K, CT, A, Pr > &	right
	)

NotEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is not equal to right. false, otherwise.

template<unsigned int X, class K , class CT , class A , class Pr >

bool operator<	(	const XMultiAcessSkipList< X, K, CT, A, Pr > &	left,
		const XMultiAcessSkipList< X, K, CT, A, Pr > &	right
	)

LessThan Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is less than right. false, otherwise.

template<unsigned int X, class K , class CT , class A , class Pr >

bool operator<=	(	const XMultiAcessSkipList< X, K, CT, A, Pr > &	left,
		const XMultiAcessSkipList< X, K, CT, A, Pr > &	right
	)

LessThanOrEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is less than or equal to right. false, otherwise.

template<unsigned int X, class K , class CT , class A , class Pr >

bool operator>	(	const XMultiAcessSkipList< X, K, CT, A, Pr > &	left,
		const XMultiAcessSkipList< X, K, CT, A, Pr > &	right
	)

GreaterThan Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is greater than right. false, otherwise.

template<unsigned int X, class K , class CT , class A , class Pr >

bool operator>=	(	const XMultiAcessSkipList< X, K, CT, A, Pr > &	left,
		const XMultiAcessSkipList< X, K, CT, A, Pr > &	right
	)

GreaterThanOrEqual Operator (Forward Container)

Parameters:

left	first list to compare
right	second list to compare

Returns:

true if left is greater than or equal right. false, otherwise.

template<unsigned int X, class container_type >

void iter_swap	(	CS::XIterator0< X, container_type >	left,
		CS::XIterator0< X, container_type >	right
	)

Swaps element nodes for XIndexedSkipList iterators.

WARNING: Do not use on iterators for containers other than XIndexedSkiplist.

Element objects may not be swapped for XBidiCompositeSkipList's as this would mean that the list may no longer be sorted in other internal containers. Instead, the nodes are swapped in this internal container only. This has an unfortunate side effect that the iterators will continue to point to the same elements, but in different positions. A refresh() will revalidate both iterators.

Parameters:

left	Iterator of first node to swap.
right	Iterator of second node to swap.

template<unsigned int X, class container_type >

void reverse	(	CS::XIterator0< X, container_type >	first,
		CS::XIterator0< X, container_type >	last
	)

Reverses the nodes in XIndexedSkipList.

WARNING: Do not use on iterators for containers other than XIndexedSkiplist.

Nodes for all elements in range [first, last) will be reversed. All iterators within the range will continue to point to their original elements, but will be partially invalidated. Call refresh() to revalidate. last remains validated.

Parameters:

first	Iterator that points to start of range.
last	Iterator that points to one element past the end of the range.

template<unsigned int X, class container_type >

void quick_sort	(	CS::XIterator0< X, container_type >	first,
		CS::XIterator0< X, container_type >	last
	)

QuickSort for XIndexedSkipList.

WARNING: Do not use on iterators for containers other than XIndexedSkiplist.

Sorts nodes of range in an XIndexedSkipList internal container.

All iterators within the range will continue to point to their original elements, but will be partially invalidated. Call refresh() to revalidate. last remains validated.

Parameters:

first	Iterator that points to start of range.
last	Iterator that points to one element past the end of the range.

template<unsigned int X, class container_type , class Pr >

void insert_sort_N	(	const CS::XIterator0< X, container_type > &	first,
		const CS::XIterator0< X, container_type > &	last,
		const Pr &	pred
	)

An optimized insertion sort for XIndexedSkipList.

WARNING: Do not use on iterators for containers other than XIndexedSkiplist.

Sorts nodes of range in an XIndexedSkipList internal container. If the range has X elements, then an array of size X is allocated during the sort. Therefore, do not to use this function for a large number of elements.

All iterators within the range will continue to point to their original elements, but will be partially invalidated. Call refresh() to revalidate. last remains validated.

Parameters:

first	Iterator that points to start of range.
last	Iterator that points to one element past the end of the range.
pred	LessThan predicate that works on the elements of type T.

template<unsigned int X, class container_type , class Pr >

void insert_sort	(	const CS::XIterator0< X, container_type > &	first,
		const CS::XIterator0< X, container_type > &	last,
		const Pr &	pred
	)

Default insertion sort for XIndexedSkipList.

WARNING: Do not use on iterators for containers other than XIndexedSkiplist.

Sorts nodes of range in an XIndexedSkipList internal container. Do not use this unless insert_sort_N() cannot do the job.

All iterators within the range will continue to point to their original elements, but will be partially invalidated. Call refresh() to revalidate. last remains validated.

Parameters:

first	Iterator that points to start of range.
last	Iterator that points to one element past the end of the range.
pred	LessThan predicate that works on the elements of type T.

template<unsigned int X, class container_type >

void insert_sort	(	const CS::XIterator0< X, container_type > &	first,
		const CS::XIterator0< X, container_type > &	last
	)

Default insertion sort for XIndexedSkipList.

WARNING: Do not use on iterators for containers other than XIndexedSkiplist.

Sorts nodes of range in an XIndexedSkipList internal container. Do not use this unless insert_sort_N() cannot do the job.

Uses operator<() for comparisons.

All iterators within the range will continue to point to their original elements, but will be partially invalidated. Call refresh() to revalidate. last remains validated.

Parameters:

first	Iterator that points to start of range.
last	Iterator that points to one element past the end of the range.

template<unsigned int X, class container_type , class Pr >

void merge_sort	(	CS::XIterator0< X, container_type > &	first,
		CS::XIterator0< X, container_type > &	last,
		const Pr &	pred
	)

Optimized merge sort for XIndexedSkipList.

WARNING: Do not use on iterators for containers other than XIndexedSkiplist.

Sorts nodes of range in an XIndexedSkipList internal container. This is a stable sort where equal elements remain in their original order.

All iterators within the range will continue to point to their original elements, but will be partially invalidated. Call refresh() to revalidate. last remains validated.

Parameters:

first	Iterator that points to start of range.
last	Iterator that points to one element past the end of the range.
pred	LessThan predicate for comparisons.

template<unsigned int X, class container_type >

void merge_sort	(	CS::XIterator0< X, container_type > &	first,
		CS::XIterator0< X, container_type > &	last
	)

Optimized merge sort for XIndexedSkipList.

WARNING: Do not use on iterators for containers other than XIndexedSkiplist.

Sorts nodes of range in an XIndexedSkipList internal container. This is a stable sort where equal elements remain in their original order. Uses operator<() for comparisons.

All iterators within the range will continue to point to their original elements, but will be partially invalidated. Call refresh() to revalidate. last remains validated.

Parameters:

first	Iterator that points to start of range.
last	Iterator that points to one element past the end of the range.