A sorted Skip List class. More...

#include "skipList.h"

Collaboration diagram for SkipList:

Public Member Functions
	SkipList ()
	Default constructs the SkipList. More...

	SkipList (int probability, int maxlevel)
	Constructs an empty list with the specified probability and maxlevel. More...

	SkipList (int key, HSLAPixel value)
	Constructs the SkipList with one initial node, which is constructed with the provided values. More...

	SkipList (int key, HSLAPixel value, int probability, int maxlevel)
	Constructs the SkipList with one initial node, which is constructed with the provided values. More...

	SkipList (const SkipList &other)
	Copy constructs the current SkipList. More...

	~SkipList ()
	The destructor for SkipList. More...

const SkipList &	operator= (const SkipList &other)
	The assignment= operator. More...

void	insert (int key, HSLAPixel value)
	Inserts a new node into the sorted order in the list, initialized with the provided values. More...

bool	remove (int key)
	Removes the node with the given key from the list. More...

PNG	makeImage (int imgSize, HSLAPixel fg, HSLAPixel bg)
	Makes and returns an image showing how degenerate the list is. More...

int	levelGenerator ()
	Returns the height to use for the next node. More...

void	printKeys ()
	A function that prints the keys of the list using only next pointers. More...

HSLAPixel	search (int key)
	A function that searches for the given key and returns the associated HSLAPixel Returns (0, 0, 0, 50) if it's not found. More...

void	printKeysReverse ()
	A function that prints the keys in the list using only prev pointers. More...

vector< int >	traverse ()
	A function that returns the keys of the list in a vector, using only next pointers. More...

vector< int >	traverseReverse ()
	A function that returns the keys of the list in a vector, using only prev pointers. More...

PNG	toPNG (int maxHeight=100, HSLAPixel fg=HSLAPixel(0, 0, 0), HSLAPixel bg=HSLAPixel(0, 0, 1)) const
	A function that returns a PNG showing the structure of the current list NOTE: This draws the sentinel nodes as well. More...

Private Member Functions
SkipNode *	findR (int key)
	Finds the given key in the list if it exists, and returns a pointer to the node containing it. More...

SkipNode *	findRHelper (int key, int level, SkipNode *curr)
	Helper function for findR. More...

SkipNode *	findI (int key)
	An iterative find function. More...

SkipNode *	find (int key)
	Finds the given key in the list if it exists, and returns a pointer to the node containing it. More...

void	printKeysReverse (SkipNode *curr)
	A helper function for printKeysReverse(). More...

void	traverseReverse (SkipNode *curr, vector< int > &out)
	A helper function for traverseReverse() More...

void	clear ()
	Clears up all memory associated with this SkipList. More...

void	copy (const SkipList &other)
	The copy() helper method - used in the copy constructor and assignment= operator. More...

SkipPointer	gdbGetPointer (SkipNode *node, size_t index) const
	A function that will return the index-th SkipPointer from node. More...

string	gdbGetNode (SkipNode *node) const
	A function that will get the current node's next and previous node's keys at each level Used because STL containers don't play well with gdb. More...

void	gdbPrintNode (SkipNode *node) const
	A function that will print out the current node's next and previous node's keys at each level Used because STL containers don't play well with gdb. More...

Detailed Description

A sorted Skip List class.

Constructor & Destructor Documentation

SkipList::SkipList ( )

Default constructs the SkipList.

Uses two sentinel nodes, each initially of height 1

SkipList::SkipList	(	int	probability,
		int	maxlevel
	)

Constructs an empty list with the specified probability and maxlevel.

Parameters

probability	The probability of increasing the height of a node
maxlevel	The maximum allowable height of the skiplist

SkipList::SkipList	(	int	key,
		HSLAPixel	value
	)

Constructs the SkipList with one initial node, which is constructed with the provided values.

Parameters

key	The key to associate with the initial node
value	The pixel to associate with the initial node

SkipList::SkipList	(	int	key,
		HSLAPixel	value,
		int	probability,
		int	maxlevel
	)

Constructs the SkipList with one initial node, which is constructed with the provided values.

Also sets probability and maxlevel of the skiplist

Parameters

key	The key to associate with the initial node
value	The pixel to associate with the initial node
probability	The probability of increasing the height of a node
maxlevel	The maximum allowable height of the skiplist

SkipList::SkipList ( const SkipList & other )

Copy constructs the current SkipList.

Parameters

other The SkipList to copy

See also: copy()

SkipList::~SkipList ( )

The destructor for SkipList.

See also: clear()

Member Function Documentation

const SkipList & SkipList::operator= ( const SkipList & other )

The assignment= operator.

Parameters

other The SkipList to copy into ourselves.

Returns: The current object

See also: copy()

void SkipList::insert	(	int	key,
		HSLAPixel	value
	)

Inserts a new node into the sorted order in the list, initialized with the provided values.

Parameters

key	The key to associate with the new Node
value	The value to associate with the new Node

Will replace the value at key if it already exists

Parameters

key	The key to associate with the new Node
value	The value to associate with the new Node

bool SkipList::remove ( int key )

Removes the node with the given key from the list.

Parameters

key	The key to search for and remove from the list

Returns: A boolean indicating whether a node was successfully removed from the list

PNG SkipList::makeImage	(	int	imgSize,
		HSLAPixel	fg,
		HSLAPixel	bg
	)

Makes and returns an image showing how degenerate the list is.

The less degenerate the faster and more efficient the skip list will be. More black pixels in the image == more degenerate

Parameters

imgSize	How large to make each side of the image
fg	The color of the foreground, or degenerate pixels in this case
bg	The color of the background, or normal pixels in this case

Returns: A pointer to a PNG representing how degenerate the list is

int SkipList::levelGenerator ( )

Returns the height to use for the next node.

Is based on the probability and maxLevels global variables

Returns: The height to use for the next node

void SkipList::printKeys ( )

A function that prints the keys of the list using only next pointers.

HSLAPixel SkipList::search ( int key )

A function that searches for the given key and returns the associated HSLAPixel Returns (0, 0, 0, 50) if it's not found.

A function that searches for the given key and returns the associated HSLAPixel Returns (0, 0, 0, 0.5) if it's not found.

Parameters

key	The key to search for

Returns: The pixel with the specified key, or (0, 0, 0, 50) if not found

Parameters

key	The key to search for

Returns: The pixel with the specified key, or (0, 0, 0, 0.5) if not found

void SkipList::printKeysReverse ( )

A function that prints the keys in the list using only prev pointers.

vector< int > SkipList::traverse ( )

A function that returns the keys of the list in a vector, using only next pointers.

Returns: a vector containing the keys from head to tail, including the sentinel values; a vector containing the keys from head_ to tail_, including the sentinel values

vector< int > SkipList::traverseReverse ( )

A function that returns the keys of the list in a vector, using only prev pointers.

Returns: a vector containing the keys from head to tail, including the sentinel values

PNG SkipList::toPNG	(	int	maxHeight = `100`,
		HSLAPixel	fg = `HSLAPixel(0, 0, 0)`,
		HSLAPixel	bg = `HSLAPixel(0, 0, 1)`
	)		const

A function that returns a PNG showing the structure of the current list NOTE: This draws the sentinel nodes as well.

Parameters

maxHeight	the height of the PNG; scales heights into the range [0, maxHeight)
fg	The color to draw the nodes
bg	The color of the background

Returns: a new PNG object representing the current list

SkipNode * SkipList::findR ( int key )

private

Finds the given key in the list if it exists, and returns a pointer to the node containing it.

Parameters

key	The key to search for in the list

Returns: A pointer to the node containing key, or NULL if not found in the list

SkipNode * SkipList::findRHelper	(	int	key,
		int	level,
		SkipNode *	curr
	)

private

Helper function for findR.

Parameters

key	The key to search for
level	The level we're searching through
curr	The current node we're searching through

Returns: A pointer to the node with the given key, or NULL if it could not be found

SkipNode * SkipList::findI ( int key )

private

An iterative find function.

Parameters

key	The key to search for

Returns: A pointer to the node with the given key, or NULL if it could not be found

SkipNode * SkipList::find ( int key )

private

Finds the given key in the list if it exists, and returns a pointer to the node containing it.

Randomly calls findR or findI

Parameters

key	The key to search for in the list

Returns: A pointer to the node containing key, or NULL if not found in the list

void SkipList::printKeysReverse ( SkipNode * curr )

private

A helper function for printKeysReverse().

Parameters

curr	The current node we are printing

See also: printKeysReverse()

void SkipList::traverseReverse	(	SkipNode *	curr,
		vector< int > &	out
	)

private

A helper function for traverseReverse()

Parameters

curr	The current node
out	The vector we are adding to

void SkipList::clear ( )

private

Clears up all memory associated with this SkipList.

void SkipList::copy ( const SkipList & other )

private

The copy() helper method - used in the copy constructor and assignment= operator.

Parameters

other The SkipList to copy into ourselves

SkipPointer SkipList::gdbGetPointer	(	SkipNode *	node,
		size_t	index
	)		const

private

A function that will return the index-th SkipPointer from node.

Used because STL containers don't play well with gdb

Parameters

node	The node to consider
index	The level of the node to get a SkipPointer for

Returns: A copy of the SkipPointer in node's index-th level

string SkipList::gdbGetNode ( SkipNode * node ) const

private

A function that will get the current node's next and previous node's keys at each level Used because STL containers don't play well with gdb.

Parameters

node	The node to get out

Returns: A string representing the node

void SkipList::gdbPrintNode ( SkipNode * node ) const

private

A function that will print out the current node's next and previous node's keys at each level Used because STL containers don't play well with gdb.

Note that this doesn't work well if you are using layour src

Parameters

node	The node to print out

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

Public Member Functions

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation