// genericlist.cc
//
//	Generic Data Structures
//		Lists and Ordered Lists, Stacks and Queues, Sets
//	Written by Tim Budd
//	Oregon State University
//		June 1991
//
//
//	copyrighted but can be freely redistributed as long as notice
//	of authorship is retained.

# include "genericlist.h"

// *********************************************************
//  generic Linked Lists
// *********************************************************

class genericLink {
public:
	void * element;
	genericLink * next;

	genericLink (void *, genericLink * n = 0);
	~genericLink();

	void addToFront(void *);
	void addToEnd(void *);
	genericLink * remove(void *);
};

inline genericLink::genericLink(void *v, genericLink * n) {	
	element = v; 
	next = n; 
}

genericLink::~genericLink() {
	//	delete the sequence of link fields
	if (next)
		delete next;
}

void genericLink::addToFront(void * v) {
	next = new genericLink(v, next);
}

void genericLink::addToEnd(void * v) {
	if (next)
		next->addToEnd(v);
	else
		next = new genericLink(v);
}

genericLink * genericLink::remove(void * v) {
	if (this == v)
		return next;
	if (next)
		next = next->remove(v);
	return this;
}

genericList::~genericList() {
	//	get rid of the links
	if (data)
		delete data;
}

void genericList::addToFront(void *v) {
	data = new genericLink(v, data);
}

void genericList::addToEnd(void * v) {
	if (data)
		data->addToEnd(v);
	else
		data = new genericLink(v);
}

void * genericList::current() {	
	if (crnt) 
		return crnt->element; 
	return 0; 
}

int genericList::includes(void * v) {
	for (first(); current(); next())
		if (match(current(), v))
			return 1;
	return 0;
}

int genericList::match(void * x, void * y) {
	return x == y;
}

void genericList::removeCurrent() {
	if (data == crnt) 	// its the first element
		data = crnt->next;
	else
		data = data->remove(crnt);

	//	now delete the link structure
	//	parent class is responsible for deleting 
	//	value portion

	crnt->next = 0;
	delete crnt;
	crnt = 0;
}

void * genericList::remove(void * v) {
	for (first(); current(); next())
		if (match(current(), v)) {
			//	we return the element we found
			//	which may not be same as arg
			void * fv = current();
			removeCurrent();
			return fv;
			}
	return 0;
}

void genericList::next() {	
	crnt = crnt->next; 
}

// *********************************************************
//  List Iterators
// *********************************************************

void genericListIterator::next()
{	ptr = ptr->next; }

void * genericListIterator::current() {	
	if (ptr)
		return ptr->element;
	return 0;
}

// *********************************************************
//  generic Ordered Lists
// *********************************************************

int genericOrderedList::compare(void * a, void * b) {
	// return equal
	return 0;
}

int genericOrderedList::match(void * a, void * b) {
	return 0 == compare(a, b);
}

void genericOrderedList::add(void * v) {
	// manipulate the list entirely through links
	first();

	// case 1, no elements or first element 
	if ((! current()) || (compare(v, current()) < 0))
		addToFront(v);

	// case 2, somewhere in list
	else {
		genericLink * p = currentValue();
		for (next(); current(); next()) {
			if (compare(v, current()) < 0) {
				p->addToFront(v);
				break;
				}
			p = currentValue();
			}

		// case 3, add to end of list
		if (! current())
			p->addToFront(v);
		}
}

// *********************************************************
//  generic Stacks and Queues
// *********************************************************

//	
//	the following all operate by positioning the current pointer
//	then manipulating the current element
//

void * genericStack::top() {
	first();
	return current();
}

void genericStack::pop() {
	first();
	if (current())
		removeCurrent();
}

void * genericQueue::top() {
	first();
	return current();
}

void genericQueue::pop() {
	first();
	if (current())
		removeCurrent();
}

// *********************************************************
//  Sets 
// *********************************************************

void genericSet::add(void * v) {	
	if (! includes(v))
		genericList::addToFront(v); 
}