|
From: <ce...@us...> - 2003-06-19 17:47:35
|
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
|