Class representing a collection of reversible lists. More...

#include <RlistSet.h>

Inheritance diagram for grafalgo::RlistSet:

Collaboration diagram for grafalgo::RlistSet:

Classes
struct	ListNode
Public Member Functions
	RlistSet (int=26)
	Constructor for RlistSet class.
	~RlistSet ()
	Destructor for RlistSet class.
void	clear ()
	Return all elements into singleton lists.
void	resize (int)
	Resize a RlistSet object.
void	expand (int)
	Expand the space available for this RlistSet.
void	copyFrom (const RlistSet &)
	Copy into list from source.
index	first (index) const
	Get the index of the first item on a list.
index	last (index) const
	Get the index of the last item on a list.
index	suc (index, index) const
	Get the index of the next item on a list.
index	pred (index, index) const
	Get the index of the previous item on a list.
void	advance (index &, index &) const
	Advance the indices of a pair of list items.
void	retreat (index &, index &) const
	Retreat (advance in reverse) the indices of a pair of list items.
index	pop (index)
	Remove first item from a list.
index	join (index, index)
	Combine two lists.
index	reverse (index)
	Reverse a list.
string &	toString (string &) const
	Build a string representation of the set of lists.
string &	toString (index, string &) const
	Build a string representation of a list.
Private Member Functions
void	makeSpace (int)
	Allocate and initialize space for list.
void	freeSpace ()
	Free dynamic storage used by list.
Private Attributes
ListNode *	node
bool *	canon
	canon[x] is true if x is the canonical item on its list

Detailed Description

Class representing a collection of reversible lists.

The list items are index values, with each index appearing in. a single list.

The implementation uses doubly-linked circular lists in which the role of the two pointers can change in order to enable constant time reversal. For the last element on the list, the role of the two pointers is fixed, but for all others, it can be reversed.

Definition at line 26 of file RlistSet.h.

Constructor & Destructor Documentation

grafalgo::RlistSet::RlistSet ( int nn = 26 )

Constructor for RlistSet class.

Parameters:

nn	defines the set of integers 1..nn on which the lists are defined.

Definition at line 15 of file RlistSet.cpp.

Here is the call graph for this function:

grafalgo::RlistSet::~RlistSet ( )

Destructor for RlistSet class.

Definition at line 18 of file RlistSet.cpp.

Here is the call graph for this function:

Member Function Documentation

void grafalgo::RlistSet::advance	(	index &	x,
		index &	y
	)		const `[inline]`

Advance the indices of a pair of list items.

Parameters:

x	is a reference to the index of some item on a list; on return, x is the index of the next item on the list
y	is a reference to the index of the predecessor of x; on return, y is the original value of x

Definition at line 98 of file RlistSet.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::RlistSet::clear ( ) [virtual]

Return all elements into singleton lists.

Implements grafalgo::Adt.

Definition at line 62 of file RlistSet.cpp.

Here is the caller graph for this function:

void grafalgo::RlistSet::copyFrom ( const RlistSet & source )

Copy into list from source.

Definition at line 69 of file RlistSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::RlistSet::expand ( int size ) [virtual]

Expand the space available for this RlistSet.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 55 of file RlistSet.cpp.

Here is the call graph for this function:

index grafalgo::RlistSet::first ( index x ) const [inline]

Get the index of the first item on a list.

Parameters:

x	is the index of the canonical item of a list

Returns:: the first index on the list containing x

Definition at line 66 of file RlistSet.h.

Here is the caller graph for this function:

void grafalgo::RlistSet::freeSpace ( ) [private]

Free dynamic storage used by list.

Definition at line 37 of file RlistSet.cpp.

Here is the caller graph for this function:

index grafalgo::RlistSet::join	(	index	t1,
		index	t2
	)

Combine two lists.

Parameters:

t1	is the index of the canonical item on some list
t2	is the index of the canonical item on a second list

Returns:: the index of the canonical item of the list formed by appending the second list to the end of the first

Definition at line 105 of file RlistSet.cpp.

index grafalgo::RlistSet::last ( index x ) const [inline]

Get the index of the last item on a list.

Parameters:

x	is the index of the canonical item of a list

Returns:: the last index on the list containing x

Definition at line 72 of file RlistSet.h.

void grafalgo::RlistSet::makeSpace ( int size ) [private]

Allocate and initialize space for list.

Parameters:

size	is number of index values to provide space for

Definition at line 23 of file RlistSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

index grafalgo::RlistSet::pop ( index t )

Remove first item from a list.

Has no effect on a singleton list, since all index values must be on some list.

Parameters:

t	is the index of the canonical element of some list

Returns:: the last index of the canonical element of the modified list

Definition at line 86 of file RlistSet.cpp.

Here is the call graph for this function:

index grafalgo::RlistSet::pred	(	index	x,
		index	next
	)		const `[inline]`

Get the index of the previous item on a list.

Parameters:

x	is the index of some item of a list
next	is the index of the item that comes after x on its list

Returns:: the index of the previous item on the list containing x

Definition at line 88 of file RlistSet.h.

Here is the caller graph for this function:

void grafalgo::RlistSet::resize ( int size ) [virtual]

Resize a RlistSet object.

The old value is discarded.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 43 of file RlistSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::RlistSet::retreat	(	index &	x,
		index &	y
	)		const `[inline]`

Retreat (advance in reverse) the indices of a pair of list items.

Parameters:

x	is a reference to the index of some item on a list; on return, x is the index of the previous item on the list
y	is a reference to the index of the successor of x; on return, y is the original value of x

Definition at line 108 of file RlistSet.h.

Here is the call graph for this function:

index grafalgo::RlistSet::reverse ( index t )

Reverse a list.

Parameters:

t	is the index of the canonical item on some list

Returns:: the index of the canonical item on the list obtained by reversing the original list.

Definition at line 125 of file RlistSet.cpp.

Here is the call graph for this function:

index grafalgo::RlistSet::suc	(	index	x,
		index	prev
	)		const `[inline]`

Get the index of the next item on a list.

Parameters:

x	is the index of some item of a list
prev	is the index of the item that comes before x on its list

Returns:: the last index on the list containing x

Definition at line 79 of file RlistSet.h.

Here is the caller graph for this function:

string & grafalgo::RlistSet::toString	(	index	t,
		string &	s
	)		const

Build a string representation of a list.

Parameters:

t	is the index of the canonical item of some list
s	is the string in which the result is returned

Returns:: a reference to s

Definition at line 154 of file RlistSet.cpp.

Here is the call graph for this function:

string & grafalgo::RlistSet::toString ( string & s ) const [virtual]

Build a string representation of the set of lists.

All lists with at least two items are printed, one per line.

Parameters:

s	is the string in which the result is returned

Returns:: a reference to s

Implements grafalgo::Adt.

Definition at line 139 of file RlistSet.cpp.

Here is the call graph for this function:

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

/Users/jst/src/grafalgo/cpp/include/RlistSet.h
/Users/jst/src/grafalgo/cpp/dataStructures/basic/RlistSet.cpp

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation