NSkipList Class Template Reference

NSkipList provides a skip-list based container class. More...

List of all members.

Public Types
typedef const iterator	const_iterator
	Const iterator for NList objects.
Public Member Functions
	NSkipList (void)
	Constructs a NSkipList object with a pre-defined max height.
	NSkipList (nint32 max)
	Constructs a NSkipList object with a defined max height.
	~NSkipList (void)
	Destroys a NSkipList object freeing resources used.
bool	isEmpty (void) const
	Checks whether the skip-list is empty.
nint32	getHeight (void) const
	Gets the max height of the skip list.
nint32	getCurrentHeight (void) const
	Gets the current height of the skip list.
bool	erase (const T &key)
	Removes the item defined by key from the list. If it is not found it will be silently ignored.
bool	contains (const T &key) const
	Checks whether a item exists in the list.
nuint64	size (void) const
	Gets the size of the list.
nuint64	count (void) const
	Gets the size of the list.
iterator	begin (void)
	Returns an iterator pointing to the first item in the list.
const_iterator	constBegin (void) const
	Returns an iterator pointing to the first item in the list.
iterator	end (void)
	Returns an iterator pointing to the last item in the list.
const_iterator	constEnd (void) const
	Returns an iterator pointing to the last item in the list.
iterator	find (const T &key)
	Finds a node containing key.
const_iterator	find_const (const T &key) const
	Finds a node containing key.
iterator	insert (const T &key)
	Inserts the data defined by key in the list. If it is already in the list it will be silently ignored.
void	clear (void)
	Removes all nodes from the list.
Classes
class	iterator
	NSkipList::iterator is the iterator object for NSkipList. More...

---

Detailed Description

template<typename T>
class NSkipList< T >

NSkipList provides a skip-list based container class.

Note:

Items used in the NSkipList class must implement the following operators: =, ==, < and >.

Todo:

This class must not accept a max height bigger than 32 (ie. sizeof(int))

Examples:

ex_nskiplist.cpp, and ex_skip_vs_sorted.cpp.

Definition at line 37 of file nskiplist.hpp.

---

Constructor & Destructor Documentation

NSkipList

(

nint32

max

)

[inline]

Constructs a NSkipList object with a defined max height.

Parameters:

max

Max height of the skip list (between 16 and 32)

Exceptions:

NException

If given a value smaller than 16 or bigger than 32

Definition at line 217 of file nskiplist.hpp.

References NException::BASE, and NException::EX_OUT_OF_BOUNDS.

---

Member Function Documentation

bool isEmpty

(

void

)

const [inline]

Checks whether the skip-list is empty.

Returns:

true if it is empty or false otherwise

Definition at line 277 of file nskiplist.hpp.

Referenced by NMap::isEmpty().

nint32 getHeight

(

void

)

const [inline]

Gets the max height of the skip list.

Returns:

The max height of the skip list

Definition at line 287 of file nskiplist.hpp.

nint32 getCurrentHeight

(

void

)

const

Gets the current height of the skip list.

Returns:

The current height of the skip list

bool erase

(

const T &

key

)

[inline]

Removes the item defined by key from the list. If it is not found it will be silently ignored.

Parameters:

key

Item to be removed from the list

Returns:

true if succeeded removing the item of false otherwise

Definition at line 347 of file nskiplist.hpp.

References NSkipNode::next.

Referenced by NMap::erase().

bool contains

(

const T &

key

)

const [inline]

Checks whether a item exists in the list.

Parameters:

key

The item to be checked

Returns:

true if the item exists or false otherwise

Note:

It returns true if key's operator==(const T &key) function returns true for any member already on the list

Definition at line 320 of file nskiplist.hpp.

References NSkipNode::next.

Referenced by insert().

nuint64 size

(

void

)

const [inline]

Gets the size of the list.

Returns:

The size of the list

Definition at line 385 of file nskiplist.hpp.

References count().

nuint64 count

(

void

)

const [inline]

Gets the size of the list.

Returns:

The size of the list

Definition at line 391 of file nskiplist.hpp.

Referenced by NMap::count(), size(), and NMap::size().

NSkipList< T >::iterator begin

(

void

)

[inline]

Returns an iterator pointing to the first item in the list.

Returns:

An iterator pointing to the first item in the list

Definition at line 547 of file nskiplist.hpp.

Referenced by NMap::begin(), NMap::count(), NMap::find(), NMap::key(), NMap::keys(), NMap::remove(), and NMap::take().

NSKIPLIST_CONST constBegin

(

void

)

const [inline]

Returns an iterator pointing to the first item in the list.

Returns:

A const iterator pointing to the first item in the list

Definition at line 557 of file nskiplist.hpp.

Referenced by NMap::constBegin(), NMap::constFind(), NMap::keys(), NMap::value(), and NMap::values().

NSkipList< T >::iterator end

(

void

)

[inline]

Returns an iterator pointing to the last item in the list.

Returns:

An iterator pointing to the last item in the list

Definition at line 567 of file nskiplist.hpp.

Referenced by NMap::count(), NMap::end(), NMap::find(), NMap::key(), NMap::keys(), NMap::remove(), and NMap::take().

NSKIPLIST_CONST constEnd

(

void

)

const [inline]

Returns an iterator pointing to the last item in the list.

Returns:

A const iterator pointing to the last item in the list

Definition at line 573 of file nskiplist.hpp.

Referenced by NMap::constEnd(), NMap::constFind(), NMap::keys(), NMap::value(), and NMap::values().

NSkipList< T >::iterator find

(

const T &

key

)

[inline]

Finds a node containing key.

Parameters:

key

The key to be searched

Returns:

An iterator pointing to key or end() if not found

Definition at line 597 of file nskiplist.hpp.

Referenced by find_const().

NSKIPLIST_CONST find_const

(

const T &

key

)

const [inline]

Finds a node containing key.

Parameters:

key

The key to be searched

Returns:

A const iterator pointing to key or end() if not found

Definition at line 603 of file nskiplist.hpp.

References find().

NSkipList< T >::iterator insert

(

const T &

key

)

[inline]

Inserts the data defined by key in the list. If it is already in the list it will be silently ignored.

Parameters:

key

Item to be added to the list

Returns:

An iterator pointing to key of end() if already exists

Definition at line 609 of file nskiplist.hpp.

References contains(), and NSkipNode::next.

Referenced by NMap::insert().

---

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

• nskiplist.hpp

---