[Devmaster-cvs] engine/include t_list.h,NONE,1.1

[<ce...@us...>]

Update of /cvsroot/devmaster/engine/include
In directory sc8-pr-cvs1:/tmp/cvs-serv28591/include

Added Files:
	t_list.h 
Log Message:
oops forgot about this one =)

--- NEW FILE: t_list.h ---
//////////////////////////////////////////////////
// created by robert beatty : bertobot at cox dot net
// copyright 2003
// use freely - if you change anything, ANYTHING, email me and let me know
//
//////////////////////////////////////////////////
// t_list.h
#ifndef __t_list_h_
#define __t_list_h_

#include "t_node.h"
/////////////////////////////////////////////////
/*
	t_list exception class
*/
class t_list_exception
{
public:
	t_list_exception()
	{
		printf("t_list.h, t_list::get(): accessing NULL object\n");
	}

	t_list_exception(unsigned int index)
	{
		printf("t_list.h t_list::operator[]: index out of range (index: %d)\n", index);
	}
};
//////////////////////////////////////////////////
/*
	class: t_list
		class t_list is a templated linked list.
*/
template <class any>
class t_list {
protected:
	t_node<any>
		*head,
		*current,
		*tail;

	unsigned int size;

private:
	// internal funcs
	void head_remove(t_node<any> *&);
	void node_remove(t_node<any> *&, t_node<any> *);

public:
	t_list();
	t_list(const t_list<any>&);
	t_list<any> operator=(const t_list<any>&);
	any& operator[](unsigned int);
	bool operator == (const t_list<any>&);

	bool add(const any&);
	bool remove();
	bool remove(unsigned int);

	any& get_last();
	any& get_current();

	void clear();
	void advance();
	void reset();
	void reset_tail();

	bool empty() const;
	bool end() const;

	unsigned int length() const;
	any* search(const any&);
	void concatenate(const t_list<any>&);
	void reverse();

	~t_list();

};
/////////////////////////////////////////////////
/*
	t_list constructor
*/
template <class any>
t_list<any>::t_list()
{
	head = tail = current = NULL;
	size = 0;
}
/////////////////////////////////////////////////
/*
	t_list copy constructor
*/
template <class any>
t_list<any>::t_list(const t_list<any>& rhs)
{
	head = tail = current = NULL;
	size = 0;

	t_node<any>* temp = rhs.head;
	while (temp != NULL)
	{
		add (temp->element);
		temp = temp->next;
	}
	reset();
}
/////////////////////////////////////////////////
/*
	t_list assignment operator
*/
template <class any>
t_list<any> t_list<any>::operator=(const t_list<any>& rhs)
{
	if (this == &rhs)
		return *this;

	clear();

	t_node<any>* temp = rhs.head;
	while (temp != NULL)
	{
		add (temp->element);
		temp = temp->next;
	}
	reset();

	return *this;
}
/////////////////////////////////////////////////
/*
	t_list index operator []
*/
template <class any>
any& t_list<any>::operator[](unsigned int index)
{
	if ( (index < 0) || (index >= size) )
		throw t_list_exception(index);

	t_node<any> *ptr = head;
	for (unsigned int i = 0; ( (i < index) && (ptr != NULL) ); i++)
		ptr = ptr->next;

	return ptr->element;
}
/////////////////////////////////////////////////
/*
	t_list equivalency operator
*/
template <class any>
bool t_list<any>::operator == (const t_list<any>& rhs)
{
	bool result = false;

	// primary checks
	if (length() != rhs.length())
		return false;

	t_node<any>
		*compare1 = head,
		*compare2 = rhs.head;

	// check if they're different
	while (compare1 != NULL && compare2 != NULL)
	{
		if (compare1 != compare1)
			return false;
		compare1 = compare1->next;
		compare2 = compare2->next;
	}

	// i guess they match =)
	return true;
}
/////////////////////////////////////////////////
/*
	t_list::add(any newElement)
		add's new element to linked list
		to the end of the list.  very
		queue-like.
*/
template <class any>
bool t_list<any>::add(const any& newElement)
{

	// physical node
	t_node<any> *newNode = new t_node<any>(newElement);

	if (head == NULL)
	{
		head = newNode;
		tail = head;
	}

	else
	{
		tail->next = newNode;
		tail = tail->next;
	}

	size++;
	return true;
}
/////////////////////////////////////////////////
/*
	t_list::remove()
		removes current's element.  if
		current is null, returns false.
		otherwise, true.
*/
template <class any>
bool t_list<any>::remove()
{
	if (current != NULL)
	{
		node_remove(head, current);
		return true;
	}
	return false;
}
/////////////////////////////////////////////////
/*
	t_list::remove(index)
		remove element with index number
		_index_.  returns true if index
		is in bound, false if out-of-bounds
*/
template <class any>
bool t_list<any>::remove(unsigned int index)
{
	// check bounds
	if ( (index < 0) || (index >= size) )
		return false;

	t_node<any>
		*t = head;

	for (unsigned int i = 0; i < index; i++)
		t = t->next;

	node_remove(head, t);
	return true;
}
/////////////////////////////////////////////////
/*
	t_list::get()
		return's the last added element.
*/
template <class any>
any& t_list<any>::get_last()
{
	if (tail != NULL)
		return tail->element;
	throw t_list_exception();
}
/////////////////////////////////////////////////
/*
	t_list::get_current()
		return current's element
*/
template <class any>
any& t_list<any>::get_current()
{
	if (current != NULL)
		return current->element;
	throw t_list_exception();
}
/////////////////////////////////////////////////
/*
	t_list::clear()
		remove all nodes in list
*/
template <class any>
void t_list<any>::clear()
{
	while (head != NULL)
	{
		head_remove(head);
	}

	size = 0;
	head = tail = current = NULL;
}
/////////////////////////////////////////////////
/*
	t_list::advance()
		steps current down the list
*/
template <class any>
void t_list<any>::advance()
{
	if (current != NULL)
		current = current->next;
}
/////////////////////////////////////////////////
/*
	t_list::reset()
		set current to head node
*/
template <class any>
void t_list<any>::reset()
{
	current = head;
}
/////////////////////////////////////////////////
/*
	t_list::reset_tail()
		resets the tail.  called by
		head_remove if tail is being
		removed.
*/
template <class any>
void t_list<any>::reset_tail()
{
	t_node<any> *t = head;
	while (t != NULL)
	{
		tail = t;
		t = t->next;
	}
}
/////////////////////////////////////////////////
/*
	t_list::empty()
		see if the list is empty
		(head is null).
*/
template <class any>
bool t_list<any>::empty() const
{
	return (head == NULL);
}
/////////////////////////////////////////////////
/*
	t_list::end()
		see if current has reached the
		end of the list (current is NULL).
*/
template <class any>
bool t_list<any>::end() const
{
	return (current == NULL);
}
/////////////////////////////////////////////////
/*
	t_list::length()
		return size (number of elements) in list
*/
template <class any>
unsigned int t_list<any>::length() const
{
	return size;
}
/////////////////////////////////////////////////
/*
	t_list::search(any s)
		search list for element s
*/
template <class any>
any* t_list<any>::search(const any& s)
{
	t_node<any> *temp = head;
	while (temp != NULL)
	{
		if (temp->element == s)
			return &(temp->element);
		temp = temp->next;
	}
	return NULL;
}
/////////////////////////////////////////////////
/*
	t_list::concatenate(t_list)
		concatenates list to this
*/
template <class any>
void t_list<any>::concatenate(const t_list<any>& rhs)
{
	t_node<any> *temp = rhs.head;
	while (temp != NULL)
	{
		add(temp->element);
		temp = temp->next;
	}
}
/////////////////////////////////////////////////
/*
	t_list::head_remove(head)
		remove sublist/subtree _head_
*/
template <class any>
void t_list<any>::head_remove(t_node<any> *&head)
{
	bool retail = false;
	if (head != NULL)
	{
		if (head == tail)
			retail = true;

		t_node<any> *t = head->next;
		delete head;
		head = t;
		size--;

		if (retail)
			reset_tail();
	}
}
/////////////////////////////////////////////////
/*
	t_list::node_remove(t_node head, t_node d)
		remove d from head; look for node d
		and if found, remove it
*/
template <class any>
void t_list<any>::node_remove(t_node<any> *&head, t_node<any> *d)
{
	if (head != NULL && d != NULL)
	{
		if (d == head)
			head_remove(head);
		else
			node_remove(head->next, d);
	}
}
/////////////////////////////////////////////////
template <class any>
void t_list<any>::reverse()
{
	if (size > 1)
	{
		t_list<any> newl;

		while (!empty())
		{
			newl.add(get_last());
			remove(length() - 1);
		}

		*this = newl;
	}
}
/////////////////////////////////////////////////
/*
	t_list deconstructor
*/
template <class any>
t_list<any>::~t_list()
{
	clear();
}
/////////////////////////////////////////////////
#endif