[Devmaster-cvs] engine/include/core t_list.h,NONE,1.1 t_node.h,NONE,1.1 t_queue.h,NONE,1.1 t_stack.h,NONE,1.1

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

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

Added Files:
	t_list.h t_node.h t_queue.h t_stack.h 
Log Message:


--- 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


--- NEW FILE: t_node.h ---
// t_node.h
#ifndef __t_node_h_
#define __t_node_h_

#include <iostream>
/////////////////////////////////////////////////
/*
	class: t_node

	this class is a TEMPLATED node class that is
	used for linked list *t_list*
*/
/////////////////////////////////////////////////
template <class node>
class t_node
{
public:
	node element;
	t_node<node>* next;

	t_node()
	{
		element = node();
		next = NULL;
	}

	t_node(const node& ne)
	{
		element = ne;
		next = NULL;
	}
};
/////////////////////////////////////////////////
#endif

--- NEW FILE: t_queue.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
//
//////////////////////////////////////////////////
#ifndef __t_queue_h_
#define __t_queue_h_
//////////////////////////////////////////////////
#include "t_node.h"
/////////////////////////////////////////////////
class t_queue_exception
{
public:
	t_queue_exception()
	{
		printf("t_queue.h, t_queue::get(): accessing NULL object\n");
	}

	t_queue_exception(unsigned int index)
	{
		printf("t_queue.h t_queue::operator[]: index out of range (index: %d)\n", index);
	}
};
//////////////////////////////////////////////////
template <class any>
class t_queue
{
protected:
	t_node<any>
		*head,
		*tail;

	unsigned int size;

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

	bool enque(const any&);
	bool deque(any&);
	bool deque();
	any& get();
	void clear();
	bool empty() const;
	unsigned int length() const;
	virtual ~t_queue();
};
//////////////////////////////////////////////////
//////////////////////////////////////////////////
template <class any>
t_queue<any>::t_queue()
{
	head = tail = NULL;
	size = 0;
}
//////////////////////////////////////////////////
template <class any>
t_queue<any>::t_queue(const t_queue<any>& rhs)
{
	t_node<any> *t = rhs.head;
	while (t)
	{
		enque(t->element);
	}
}
//////////////////////////////////////////////////
template <class any>
t_queue<any> t_queue<any>::operator = (const t_queue<any>& rhs)
{
	// check for self assignement
	if (this == &rhs)
		return *this;

	// clear everything
	clear();

	// copy
	t_node<any> *t = rhs.head;
	while (t)
	{
		enque(t->element);
	}

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

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

	return t->element;
}
//////////////////////////////////////////////////
template <class any>
bool t_queue<any>::enque(const any& e)
{
	t_node<any> *t = new t_node<any>(e);
	// check if assertion succeeded.  if fail, return false

	// if no head, head insert
	if (!head)
		tail = head = t;

	// otherwise, tail insert
	else
	{
		tail->next = t;
		tail = t;
	}

	size++;
	return true;
}
//////////////////////////////////////////////////
template <class any>
bool t_queue<any>::deque(any& e)
{
	if (!empty())
	{
		e = tail->element;
		return deque();
	}
	return false;
}
//////////////////////////////////////////////////
template <class any>
bool t_queue<any>::deque()
{
	if (!empty())
	{
		t_node<any> *t = head;

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

		else
		{
			// find tail successor
			while (t && t->next && t->next->next)
				t = t->next;

			delete tail;
			t->next = NULL;
			tail = t;
		}

		size--;
		return true;
	}
	return false;
}
//////////////////////////////////////////////////
template <class any>
any& t_queue<any>::get()
{
	if (!empty())
		return tail->element;

	throw t_queue_exception();
}
//////////////////////////////////////////////////
template <class any>
void t_queue<any>::clear()
{
	while (!empty())
		deque();
}
//////////////////////////////////////////////////
template <class any>
bool t_queue<any>::empty() const
{
	return (head == NULL);
}
//////////////////////////////////////////////////
template <class any>
unsigned int t_queue<any>::length() const
{
	return size;
}
//////////////////////////////////////////////////
template <class any>
t_queue<any>::~t_queue()
{
	clear();
}
//////////////////////////////////////////////////
//////////////////////////////////////////////////
#endif

--- NEW FILE: t_stack.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
//
//////////////////////////////////////////////////
#ifndef __t_stack_h_
#define __t_stack_h_
//////////////////////////////////////////////////
#include "t_node.h"
/////////////////////////////////////////////////
class t_stack_exception
{
public:
	t_stack_exception()
	{
		printf("t_stack.h, t_stack::get(): accessing NULL object\n");
	}

	t_stack_exception(unsigned int index)
	{
		printf("t_stack.h t_stack::operator[]: index out of range (index: %d)\n", index);
	}
};
//////////////////////////////////////////////////
template <class any>
class t_stack
{
protected:
	t_node<any> *head;
	unsigned int size;

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

	bool push(const any&);
	bool pop(any&);
	bool pop();
	any& get();
	void clear();
	bool empty() const;
	unsigned int length() const;

	virtual ~t_stack();

};
//////////////////////////////////////////////////
//////////////////////////////////////////////////
template <class any>
t_stack<any>::t_stack()
{
	head = NULL;
	size = 0;
}
//////////////////////////////////////////////////
template <class any>
t_stack<any>::t_stack(const t_stack<any>& rhs)
{
	t_node<any> *t = rhs.head;
	while (t)
	{
		push(t->element);
	}
}
//////////////////////////////////////////////////
template <class any>
t_stack<any> t_stack<any>::operator = (const t_stack<any>& rhs)
{
	// check for self assignement
	if (this == &rhs)
		return *this;

	// clear everything
	clear();

	// copy
	t_node<any> *t = rhs.head;
	while (t)
	{
		push(t->element);
	}

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

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

	return t->element;
}
//////////////////////////////////////////////////
template <class any>
bool t_stack<any>::push(const any& e)
{
	t_node<any> *t = new t_node<any>(e);
	// check if assertion succeeded.  if fail, return false

	// head insert
	t->next = head;
	head = t;
	size++;
	return true;
}
//////////////////////////////////////////////////
template <class any>
bool t_stack<any>::pop(any& e)
{
	if (!empty())
	{
		e = head->element;
		return pop();
	}
	return false;
}
//////////////////////////////////////////////////
template <class any>
bool t_stack<any>::pop()
{
	if (!empty())
	{
		t_node<any> *t = head->next;
		delete head;
		head = t;
		size--;
		return true;
	}
	return false;
}
//////////////////////////////////////////////////
template <class any>
any& t_stack<any>::get()
{
	if (!empty())
		return head->element;

	throw t_stack_exception();
}
//////////////////////////////////////////////////
template <class any>
void t_stack<any>::clear()
{
	while (!empty())
		pop();
}
//////////////////////////////////////////////////
template <class any>
bool t_stack<any>::empty() const
{
	return (head == NULL);
}
//////////////////////////////////////////////////
template <class any>
unsigned int t_stack<any>::length() const
{
	return size;
}
//////////////////////////////////////////////////
template <class any>
t_stack<any>::~t_stack()
{
	clear();
}
//////////////////////////////////////////////////
//////////////////////////////////////////////////
#endif