/*
 * Copyright (C) 1999,2000,2001 Frank Hale
 * frankhale@yahoo.com
 * http://sapphire.sourceforge.net/
 *
 * Updated: 3 Nov 2001
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */


#ifndef _LINKEDLIST_H_
#define _LINKEDLIST_H_

// Forward declaration. LinkedListIterator needs to be a friend of LinkedList.
class _LinkedListIterator;
class _LinkedList;

// Directions you can traverse the list
const int FORWARD  = 0;	
const int BACKWARD = 1;

// Element is an node in the list.
class Element
{
public: 

	// This is pretty nasty but I am using friend classed
	// to circumvent having to write get/set functions, but
	// I wanna make the next,prev, and data pointers private.
	// But I still need LinkedList and LinkedListIterator
	// to access those pointers.
	friend class _LinkedList;
	friend class _LinkedListIterator;

private: // Variables 
	
	Element *next; // Pointer to next element 
	Element *prev; // Pointer to previous element 
	void	*data; // The data that is stored in this element 

public: // Member functions 
	Element() 
	{ 
		next=NULL; 
		prev=NULL; 
		data=NULL; 
	}
};

// LinkedList is a list of elements.
class _LinkedList 
{
private: // Variables 
	Element *head, *tail, *iter;
	int elements;

	friend class _LinkedListIterator;

private: // Member functions 
	
	// Returns the next element
	Element* getNextElement() { return (iter != NULL) ? iter=iter->next : NULL; }
	
	// Returns the previous element 
	Element* getPrevElement() { return (iter != NULL) ? iter=iter->prev : NULL; } 

	// The next two functions set the direction of traversal 
	// This is for iterating purposes and functions with 
	// LinkedListIterator operator++ and operator--.
	void setForward()  { iter = head; }  
	void setBackward() { iter = tail; }

public: // Member functions
	_LinkedList();
	~_LinkedList();
	
	void* getHead() { return head->data; }
	void* getTail() { return tail->data; }
	
	void insert(void *data); // Inserts an element by data (NOT NODE) 
	void remove(void *data); // Removes an element based on its data  
	
	void removeAll();        // Remove all elements in this list. Note
				 // that the destructor will do clean up for
				 // you so you don't have to explicity call
			         // this function.
							 

	Element* find(void *data); // Finds an element by its data 

	// Returns the number of elements in this list 
	int getElementCount() const { return elements; }
	int count() const { return elements; }
};

// LinkedListIterator iterates a list so you can do something with each element.
class _LinkedListIterator 
{
private: // Variables 
	_LinkedList *list;
	Element *element;

public: // Member functions 
	
	_LinkedListIterator();
	
	// Constructor is passed a list and the desired direction of 
	// tranversal. The direction FORWARD is assumed.
	_LinkedListIterator(_LinkedList *l, int direction = FORWARD)  { setList(l, direction); }
	
	// The next two functions iterate the list either forward
	// or backward depending on the direction you specified.
	void operator++(int) { if(element) element = list->getNextElement(); }
	void operator--(int) { if(element) element = list->getPrevElement(); }

	// Reset interation to the beginning depending on the direction
	// you desire. 
	void reset(int direction = FORWARD);

	void setList(_LinkedList *l, int direction = FORWARD);

	void* current() { return ( (element) ? element->data : NULL); }
};

template <class T>
class LinkedList : public _LinkedList
{
public:
	LinkedList() : _LinkedList() { }
	
	T* first() { return (T*) _LinkedList::getHead(); }
	T* last()  { return (T*) _LinkedList::getTail(); }
	
	void insert(T *d) { _LinkedList::insert( (T*) d); }
	void remove(T *d) { _LinkedList::remove( (T*) d); }
};

template <class T>
class LinkedListIterator : public _LinkedListIterator
{
public:
	LinkedListIterator() : _LinkedListIterator() {}
	
	LinkedListIterator(_LinkedList *l, int direction = FORWARD) 
		: _LinkedListIterator(l, direction){}

	T* current() { return (T*) _LinkedListIterator::current(); }
};

#endif