Data structure representing a list of indexes. More...

#include <List.h>

Inheritance diagram for grafalgo::List:

Collaboration diagram for grafalgo::List:

Public Member Functions
	List (int=26)
	Create a list with space for index values in 1..nn1.
	~List ()
	Destructor for List.
void	clear ()
	Remove all elements from list.
void	resize (int)
	Resize a List object.
void	expand (int)
	Expand the space available for this List.
void	copyFrom (const List &)
	Copy into list from source.
index	get (position) const
	Get an index based on its position in the list.
index	next (index) const
	Get the next index in a list.
index	first () const
	Get first index on list.
index	last () const
	Get the last index on list.
int	length () const
	Determine the length of the list.
bool	valid (index) const
	Test if a given index is valid for this List.
bool	empty () const
	Test if list is empty.
bool	member (index) const
	Test if an index is in the list.
bool	equals (List &) const
	Compare two lists for equality.
bool	isConsistent () const
	Check the data structure for consistency.
virtual bool	insert (index, index)
	Insert an index into the list, relative to another.
virtual bool	removeNext (index)
	Remove the index following a specified index.
bool	addFirst (index)
	Add index to the front of the list.
bool	addLast (index)
	Add index to the end of the list.
bool	removeFirst ()
	Remove the first index in the list.
string &	toString (string &) const
	Create a string representation of a given string.
Protected Member Functions
void	makeSpace (int)
	Allocate and initialize space for list.
void	freeSpace ()
	Free dynamic storage used by list.
Private Attributes
int	len
	number of elements in list
index	head
	first index in list
index	tail
	last index in list
index *	nxt
	nxt[i] is successor of i in list
Friends
istream &	operator>> (istream &, List &)

Detailed Description

Data structure representing a list of indexes.

An index is a postive integer in 1..n where n is an upper bound on the size of the list. An index can appear on a list at most once. Index-based lists are handy in contexts where we need a common "handle" for a piece of data in several different data structures. They are also compact, efficient and support constant-time membership tests (based on the index).

Note: List has several virtual members, insert() and removeNext() to allow facilitate extension by other classes.

Definition at line 29 of file List.h.

Constructor & Destructor Documentation

grafalgo::List::~List ( )

Destructor for List.

Definition at line 22 of file List.cpp.

Here is the call graph for this function:

Member Function Documentation

bool grafalgo::List::addFirst ( index i ) [inline]

Add index to the front of the list.

Parameters:

index to be added.

Returns:: true if the list was modified, else false

Definition at line 125 of file List.h.

Here is the call graph for this function:

bool grafalgo::List::addLast ( index i ) [inline]

Add index to the end of the list.

Parameters:

index to be added.

Returns:: true if the list was modified, else false

Definition at line 131 of file List.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Remove all elements from list.

Implements grafalgo::Adt.

Definition at line 75 of file List.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Copy into list from source.

Definition at line 44 of file List.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool grafalgo::List::empty ( ) const [inline]

Test if list is empty.

Returns:: true if list is empty, else false.

Definition at line 101 of file List.h.

Here is the call graph for this function:

Here is the caller graph for this function:

bool grafalgo::List::equals ( List & other ) const

Compare two lists for equality.

Parameters:

other is the list to be compared to this one

Returns:: true if they are the same list or have the same contents (in the same order); they need not have the same storage capacity to be equal

Definition at line 146 of file List.cpp.

Here is the call graph for this function:

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

Expand the space available for this List.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Reimplemented in grafalgo::Dlist.

Definition at line 68 of file List.cpp.

Here is the call graph for this function:

index grafalgo::List::first ( ) const [inline]

Get first index on list.

Returns:: the first index on the list or 0 if the list is empty

Definition at line 85 of file List.h.

Here is the caller graph for this function:

void grafalgo::List::freeSpace ( ) [protected]

Free dynamic storage used by list.

Reimplemented in grafalgo::Dlist.

Definition at line 41 of file List.cpp.

Here is the caller graph for this function:

index grafalgo::List::get ( position i ) const

Get an index based on its position in the list.

Parameters:

i	is position of index to be returned; must be between 1 and n()

Returns:: index at position i, or 0 if no such index

Reimplemented in grafalgo::Dlist.

Definition at line 82 of file List.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool grafalgo::List::insert	(	index	i,
		index	j
	)		`[virtual]`

Insert an index into the list, relative to another.

Parameters:

i	is index to insert; if i is 0 or already in the list, no change is made
j	is index after which i is to be inserted; if zero, i is inserted at the front of the list