Appendix A

Quick reference for pclasses

These class definitions are copied from the pclasses web page, http://www.ibiblio.org/obp/pclasses/, with a few minor formatting changes.

pstring

template <class T>
class pstringT
{

public:
pstringT<T>(); //default constructor
pstringT<T>(const pstringT<T> &); //copy constructor
pstringT<T>(const T *copy); //copy constructor from C-style string
pstringT<T>(T ch); //copy constructor from single character
virtual ~pstringT<T>(); //destructor

inline T * c_str() const; //returns a null-terminated, C-style string
inline int length() const; //returns the number of characters in the string

int find(const pstringT<T> &str) const; //return index of str or -1 if not found
int find(const T ch) const; //return index of ch or -1 if not found
pstringT<T> substr(int pos, int len) const; //returns substring from pos of length len

T & operator [] (int n); //access a character (mutable)
const T operator [] (int n) const; //access a character (immutable)

const pstringT<T> & operator = (const pstringT<T> &); //assignment operator
const pstringT<T> & operator = (const T * const); //assignment operator from C-style string
const pstringT<T> & operator = (const T); //assignment operator from single character

const pstringT<T> & operator += (const pstringT<T> &); //concatenation operator
const pstringT<T> & operator += (const T * const); //concatenation operator from C-style string
const pstringT<T> & operator += (const T); //concatenation operator from single character

protected:
T *mystring;

};

//typedef for regular pstrings
typedef pstringT<char> pstring;

//concatenation operators
template <class T> pstringT<T> operator + (const pstringT<T> &, const pstringT<T> &);
template <class T> pstringT<T> operator + (const pstringT<T> &, T);
template <class T> pstringT<T> operator + (T, const pstringT<T> &);
template <class T> pstringT<T> operator + (const pstringT<T> &, const T * const);
template <class T> pstringT<T> operator + (const T * const, const pstringT<T> &);

//stream operators
template <class T> inline ostream & operator << (ostream &, const pstringT<T> &);
template <class T> istream & operator >> (istream &, pstringT<T> &);
template <class T> istream & getline(istream &, pstringT<T> &);

//comparison operators
template <class T> inline bool operator == (const pstringT<T> &, const pstringT<T> &);
template <class T> inline bool operator != (const pstringT<T> &, const pstringT<T> &);
template <class T> inline bool operator < (const pstringT<T> &, const pstringT<T> &);
template <class T> inline bool operator <= (const pstringT<T> &, const pstringT<T> &);
template <class T> inline bool operator > (const pstringT<T> &, const pstringT<T> &);
template <class T> inline bool operator >= (const pstringT<T> &, const pstringT<T> &);

template <class T>
ostream & operator << (ostream &os, const pstringT<T> &out)
{
return os << out.c_str() << flush;
}

template <class T>
istream & operator >> (istream &is, pstringT<T> &in)
{
fflush(stdin);
T input_buffer[4096];
is >> input_buffer;
in = input_buffer;
return is;
}

template <class T>
istream & getline(istream &is, pstringT<T> &to_get)
{
fflush(stdin);
T getline_buffer[4096];
getline(is, getline_buffer, 4095);
to_get = getline_buffer;
return is;
}

template <class T>
pstringT<T>::pstringT()
{
mystring = new T[1];
mystring[0] = 0;
}

template <class T>
pstringT<T>::pstringT(const T *copy)
{
mystring = new T[strlen(copy) + 1]; //allocate memory
strcpy(mystring, copy); //copy string
}

template <class T>
pstringT<T>::pstringT(T ch)
{
mystring = new T[2];
mystring[0] = ch;
mystring[1] = 0;
}

template <class T>
pstringT<T>::pstringT(const pstringT<T> & to_create_from)
{
mystring = new T[to_create_from.length()+1];
strcpy(mystring, to_create_from.c_str()); //copy string
}

template <class T>
pstringT<T>::~pstringT<T>()
{
delete[] mystring;
}

template <class T>
T* pstringT<T>::c_str() const
{
return mystring;
}

template <class T>
int pstringT<T>::length() const
{
return strlen(mystring);
}

template <class T>
int pstringT<T>::find(const pstringT<T> & str) const
{
int i, j, endsearch = length() - str.length() + 1;
for(i = 0; i < endsearch; i++)
{
for(; i < endsearch && mystring[i] != str[0]; i++);
if(i == endsearch)
break;

for(j = 0; j < str.length() && mystring[i+j] == str[j]; j++);
if(j == str.length())
return i;
}
return -1;
}

template <class T>
int pstringT<T>::find(const T ch) const
{
for(int i = 0; i < length(); i++)
if(mystring[i] == ch)
return i;

return -1;
}

template <class T>
pstringT<T> pstringT<T>::substr(int pos, int len) const
{
if(pos < 0 || len < 0 || pos >= length())
{
cerr << "\nError: substring (" << pos << "," << len
<< ") out of bounds for string \"" << mystring << '\"' << endl;
exit(1);
}
if(pos + len > length())
len = length() - pos;
T *result = new T[len + 1];
memcpy(result, mystring + pos, len * sizeof(T));
result[len] = 0;
pstringT<T> to_return(result);
delete[] result;
return to_return;
}

template <class T>
const pstringT<T> & pstringT<T>::operator = (const T * const to_copy)
{
delete[] mystring; //deallocate mem
mystring = new T[strlen(to_copy)+1];
strcpy(mystring, to_copy); //copy string
return *this;
}

template <class T>
const pstringT<T> & pstringT<T>::operator = (const T ch)
{
delete[] mystring; //deallocate memory
mystring = new T[2];
mystring[0] = ch;
mystring[1] = 0;
return *this;
}

template <class T>
const pstringT<T> & pstringT<T>::operator = (const pstringT<T> ©)
{
return *this = copy.c_str(); //call T pointer copier
}

template <class T>
const pstringT<T> & pstringT<T>::operator += (const T * const to_append)
{
T *newbuffer = new T[length() + strlen(to_append) + 1];
strcpy(newbuffer, mystring);
strcat(newbuffer, to_append);
delete[] mystring;
mystring = newbuffer;
return *this;
}

template <class T>
const pstringT<T> & pstringT<T>::operator += (const pstringT<T> &to_append)
{
return *this += to_append.c_str(); //append T pointer
}

template <class T>
const pstringT<T> & pstringT<T>::operator += (const T to_append)
{
T *newstring = new T[length()+2];
strcpy(newstring, mystring);
delete[] mystring;
mystring = newstring; //points to new string
mystring[length()+1] = 0; //null terminator
mystring[length()] = to_append;
return *this;
}

template <class T>
pstringT<T> operator + (const pstringT<T> & lval, const pstringT<T> & rval)
{
pstringT<T> to_return(lval);
return to_return += rval;
}

template <class T>
pstringT<T> operator + (const pstringT<T> & lval, const T & rval)
{
pstringT<T> to_return(lval);
return to_return += rval;
}

template <class T>
pstringT<T> operator + (T lval, const pstringT<T> & rval)
{
pstringT<T> to_return(lval);
return to_return += rval;
}

template <class T>
pstringT<T> operator + (const pstringT<T> & lval, const T * const rval)
{
pstringT<T> to_return(lval);
return to_return += rval;
}

template <class T>
pstringT<T> operator + (const T * const lval, const pstringT<T> & rval)

{
pstringT<T> to_return(lval);
return to_return += rval;
}

template <class T>
T & pstringT<T>::operator [] (int n)
{
if(n<0 || n>=length())
{
cerr << "\nError: index out of range: " << n << " in string \""
<< mystring << "\" of length " << length() << endl;
exit(1);
}
return mystring[n];
}

template <class T>
const T pstringT<T>::operator [] (int n) const
{
if(n<0 || n>=length())
{
cerr << "\nError: index out of range: " << n << " in string \""
<< mystring << "\" of length " << length() << endl;
exit(1);
}
return mystring[n];
}

template <class T>
bool operator == (const pstringT<T> &lval, const pstringT<T> &rval)
{
return strcmp(lval.c_str(), rval.c_str()) == 0;
}

template <class T>
bool operator != (const pstringT<T> &lval, const pstringT<T> &rval)
{
return strcmp(lval.c_str(),rval.c_str()) != 0;
}

template <class T>
bool operator < (const pstringT<T> &lval, const pstringT<T> &rval)
{
return strcmp(lval.c_str(), rval.c_str()) < 0;
}

template <class T>
bool operator <= (const pstringT<T> &lval, const pstringT<T> &rval)
{
return strcmp(lval.c_str(), rval.c_str()) <= 0;
}

template <class T>
bool operator > (const pstringT<T> &lval, const pstringT<T> &rval)
{
return strcmp(lval.c_str(), rval.c_str()) > 0;
}

template <class T>
bool operator >= (const pstringT<T> &lval, const pstringT<T> &rval)
{
return strcmp(lval.c_str(), rval.c_str()) >= 0;
}

pvector

template <class T>
class pvector
{

public:
pvector(); //default constructor
pvector(int size); //constructor with specific dimension
pvector(int size, const T &fill_val); //create a pvector with a default fill value
pvector(const pvector<T> &); //copy constructor
virtual ~pvector(); //destructor

void resize(int new_size); //resize the vector

inline int length() const; //returns number of elements in pvector

T & operator [] (int index); //access a particular array element (mutable)
const T & operator [] (int index) const; //access a particular array element (immutable)

const pvector<T> & operator = (const pvector<T> &); //assignment operator

protected:
T *array;
int len;

};

template <class T>
pvector<T>::pvector() :array(0), len(0)
{}

template <class T>
pvector<T>::pvector(int size)
{
if(size <= 0)
{
cerr << "\nError: invalid pvector dimension: " << size << endl;
exit(1);
}
array = new T[size];
len = size;
}

template <class T>
pvector<T>::pvector(int size, const T &fill_val)
{
array = new T[size];
len = size;

for(int i=0; i<size; i++)
array[i] = fill_val;
}

template <class T>
pvector<T>::pvector(const pvector<T> &vec)
{
array = new T[vec.length()];
for(int i=0; i<vec.length(); i++)
array[i] = vec[i];
len = vec.length();
}

template <class T>
pvector<T>::~pvector()
{
delete[] array;
}

template <class T>
int pvector<T>::length() const
{
return len;
}

template <class T>
T & pvector<T>::operator [] (int index)
{
if(index < 0 || index >= length())
{
cerr << "\nError: index out of range: " << index
<< " in pvector of length " << length() << endl;
exit(1);
}
return array[index];
}

template <class T>
const T & pvector<T>::operator [] (int index) const
{
if(index < 0 || index >= length())
{
cerr << "\nError: index out of range: " << index
<< " in pvector of length " << length() << endl;
exit(1);
}
return array[index];
}

template <class T>
const pvector<T> & pvector<T>::operator = (const pvector<T> & vec)
{
delete[] array;
array = new T[vec.length()];
for(int i=0; i<vec.length(); i++)
array[i] = vec[i];
len = vec.length();
return *this;
}

template <class T>
void pvector<T>::resize(int new_size)
{
if(new_size <= 0)
{
cerr << "\nError: invalid pvector dimension: " << new_size << endl;
exit(1);
}

T *newarray = new T[new_size];

int minsize = (new_size<len)?new_size:len;
for(int i=0; i<minsize; i++)
newarray[i] = array[i];

delete[] array;
array = newarray;
len = new_size;
}

pmatrix

template <class T>
class pmatrix
{

public:
pmatrix(); //default constructor
pmatrix(int rows, int cols); //constructor with dimensions
pmatrix(int rows, int cols, const T & fillvalue); //constructor with default fill value
pmatrix(const pmatrix<T> &); //copy constructor
virtual ~pmatrix(); //destructor

void resize(int rows, int cols); //change matrix dimensions
inline int numrows() const; //returns number of rows in pmatrix
inline int numcols() const; //returns number of columns in pmatrix

inline pvector<T> & operator [] (int index); //access a particular array element (mutable)
inline const pvector<T> & operator [] (int index) const;//access a particular array element (immutable)

const pmatrix<T> & operator = (const pmatrix<T> &); //assignment operator

protected:
pvector< pvector<T> > matrix;

};

template <class T>
pmatrix<T>::pmatrix()
{}

template <class T>
pmatrix<T>::pmatrix(int rows, int cols)
{
resize(rows,cols);
}

template <class T>
pmatrix<T>::pmatrix(int rows, int cols, const T & fillvalue)
{
resize(rows,cols);
for(int x = 0; x < rows; x++)
for(int y = 0; y < cols; y++)
matrix[x][y] = fillvalue;
}

template <class T>
pmatrix<T>::pmatrix(const pmatrix<T> & copy)
{
*this = copy;
}

template <class T>
pmatrix<T>::~pmatrix()
{}

template <class T>
int pmatrix<T>::numrows() const
{
return matrix.length();
}

template <class T>
int pmatrix<T>::numcols() const
{
return (matrix.length())?matrix[0].length():0;
}

template <class T>
void pmatrix<T>::resize(int rows, int cols)
{
matrix.resize(rows);
for(int x = 0; x < rows; x++)
matrix[x].resize(cols); //resize each individual vector
}

template <class T>
const pmatrix<T> & pmatrix<T>::operator = (const pmatrix<T> & copy)
{
matrix = copy.matrix; //copy vector of vectors
return *this;
}

template <class T>
const pvector<T> & pmatrix<T>::operator [] (int index) const
{
return matrix[index];
}

template <class T>
pvector<T> & pmatrix<T>::operator [] (int index)
{
return matrix[index];
}

pstack

template <class T>
class pstack
{

public:
pstack(); //default constructor
pstack(const pstack<T> &); //copy constructor
virtual ~pstack(); //destructor

void push(T storage); //push data onto stack
void pop(T & storage); //pop data off stack and store in parameter
const T pop(); //pop data off stack and return
const T top() const; //returns top value without popping

void makeEmpty(); //empty the stack

inline bool isEmpty() const; //returns true if stack is empty
inline int length() const; //returns number of elements on stack

const pstack<T> & operator = (const pstack<T> &); //assignment operator

protected:
struct node
{
T data;
node *next;
node() :next(0) {}
node(const T & a) :next(0), data(a) {}
} *sp;
int size;

};

template <class T>
pstack<T>::pstack() :sp(0), size(0)
{}

template <class T>
pstack<T>::pstack(const pstack<T> ©) :sp(0), size(0)
{
*this = copy;
}

template <class T>
pstack<T>::~pstack()
{
makeEmpty();
}

//push a value onto the stack
template <class T>
void pstack<T>::push(T storage)
{
//create new data
node *newnode = new node;

newnode->next=sp;
newnode->data=storage;
sp = newnode;
++size;
}

//pop a value off of stack
template <class T>
void pstack<T>::pop(T & storage)
{
if(isEmpty())
{
cerr << "\nError: accessing empty stack through method pstack::pop\n";
exit(1);
}

//store data
storage = sp->data;

//delete node and move stack pointer back one
node *temp = sp;
sp = sp->next;
delete temp;
--size;
}

//pop a value off of stack and return it
template <class T>
const T pstack<T>::pop()
{
T val;
pop(val);
return val;
}

template <class T>
const T pstack<T>::top() const
{
if(isEmpty())
{
cerr << "\nError: accessing empty stack through method pstack::top\n";
exit(1);
}

return sp->data;
}

template <class T>
int pstack<T>::length() const
{
return size;
}

template <class T>
void pstack<T>::makeEmpty()
{
node *temp;
//iterate through list, deleting each elements
while(sp!=0)
{
temp = sp;
sp = sp->next;
delete temp;
}
size = 0;
}

template <class T>
bool pstack<T>::isEmpty() const
{
return size == 0;
}

template <class T>
const pstack<T> & pstack<T>::operator = (const pstack<T> & copy)
{
makeEmpty();
if(copy.isEmpty())
return *this;

sp = new node(copy.sp->data);
node *newnode,*end = sp;
for(newnode = copy.sp->next; newnode; newnode = newnode->next)
{
end->next = new node(newnode->data);
end = end->next;
}
size = copy.size;
return *this;
}

pqueue

template <class T>
class pqueue
{

public:
pqueue(); //default constructor
pqueue(const pqueue<T> &); //copy constructor
virtual ~pqueue(); //destructor

void enqueue(const T &data); //enqueue data to queue
void dequeue(T &storage); //storage holds the data that is dequeued
const T dequeue(); //dequeue to return value
const T & front() const; //returns top value without dequeueing

void makeEmpty(); //empty the queue

inline bool isEmpty() const; //returns true if queue is empty
inline int length() const; //find out the number of queued items

const pqueue<T> & operator = (const pqueue<T> &); //assignment operator

protected:
struct node
{
T data;
node *next;
node() :next(0) {}
node(const T &a) :next(0), data(a) {}
} *head, *tail;
int size;

};

template <class T>
pqueue<T>::pqueue() :head(0), tail(0), size(0)
{}

template <class T>
pqueue<T>::pqueue(const pqueue<T> ©) :head(0), tail(0), size(0)
{
*this = copy;
}

template <class T>
pqueue<T>::~pqueue()
{
makeEmpty();
}

template <class T>
void pqueue<T>::enqueue(const T &data)
{
node *newnode = new node(data); //end of queue

if(size==0) //make sure queue exists
{
head = newnode;
tail = head;
}
else
{
tail->next = newnode;
tail = newnode;
}
++size;
}

template <class T>
void pqueue<T>::dequeue(T &storage)
{
if(head==0)
{
cerr << "\nError: accessing empty queue through method pqueue::dequeue\n";
exit(1);
}

storage = head->data; //save to var
node *temp = head; //make a new node
head = head->next; //iterate
delete temp; //delete the node
--size; //decrement size
}

template <class T>
const T pqueue<T>::dequeue()
{
T val; //store to temporary variable
dequeue(val); //dequeue
return val;
}

template <class T>
const T & pqueue<T>::front() const
{
if(head==0)
{
cerr << "\nError: accessing empty queue through method pqueue::front\n";
exit(1);
}
return head->data;
}

template <class T>
void pqueue<T>::makeEmpty()
{
node *temp;
while(head)
{
temp = head;
head = head->next;
delete temp;
}
size = 0;
}

template <class T>
const pqueue<T> & pqueue<T>::operator = (const pqueue<T> & copy)
{
makeEmpty();
if(copy.isEmpty())
return *this;

head = new node(copy.head->data);
tail = head;
node *newnode;
for(newnode = copy.head->next; newnode; newnode = newnode->next)
{
tail->next = new node(newnode->data);
tail = tail->next;
}
size = copy.size;
return *this;
}

template <class T>
int pqueue<T>::length() const
{
return size;
}

template <class T>
bool pqueue<T>::isEmpty() const
{
return size == 0;
}