/* Holy shit this file * Is fucking ugly! * What the fuck was this * guy thinking?! Like -- * indent man indent!!! * remind me to clean this * shit up! --Dunk */ /* ----------------------------------------------------------------------// file: list.h // purpose: defines a node structure and a linked list template class // author: Chris Dickey - 2/1/96 // // ----------------------------------------------------------------------// */ #ifndef _list_h_ #define _list_h_ #include <assert.h> #include <iostream> using namespace std; #define ADD(a) Add(a, __FILE__, __LINE__) #if !defined(FALSE) #define FALSE 0 #endif #if !defined(TRUE) #define TRUE (!FALSE) #endif template <class T> struct nodeStruct { T data; nodeStruct<T> *next; }; //==========================listClass class===============================// template <class T> class listClass { public: // constructors and destructors listClass() : num_items(0), head(NULL) {} listClass(const listClass<T>& L); virtual ~listClass(); int NumItems() { return num_items; } // AddItem adds an item after the node bool AddItem(nodeStruct<T> *node, T item); // RemoveItem the item in the list and removes it, however, a // function to find the item should be defined in a child class bool RemoveItem(nodeStruct<T> *node); nodeStruct<T> *FindItem(T item); nodeStruct<T> *Head() { return head; } private: int num_items; protected: nodeStruct<T> *head; }; //-------------------------------------------------------------------------// // member functions for the classes follow // //-------------------------------------------------------------------------// template <class T> listClass<T>::listClass(const listClass<T> & L) { num_items = L.num_items; /* if the head of the old list is empty (NULL), then just set the new head to NULL and we're done */ if (L.head == NULL) head = NULL; // if not, we have to run through the list and allocate needed memory else { /* we'll just exit if we can't allocate a nodeStruct, and we can improve if we need to manage our own memory */ assert((head = new nodeStruct<T>) != NULL); // copy the data over head->data = L.head->data; // now we loop through the list and allocate and create the new one nodeStruct<T> *temp, *newlist; for (temp = L.head->next, newlist = head; temp; temp = temp->next) { assert((newlist->next = new nodeStruct<T>) != NULL); newlist = newlist->next; newlist->data = temp->data; } // finally, make the last 'next' point to NULL to indicate end of list newlist->next = NULL; } // end else } template <class T> listClass<T>::~listClass() { // to delete, we just remove and deallocate each item register nodeStruct<T> *temp = head; while (temp) { head = head->next; delete temp; temp = head; } } /* this assumes that even if item is a pointer to some type, it's been allocated already */ template <class T> bool listClass<T>::AddItem(nodeStruct<T> *node, T item) { /* AddItem adds the item AFTER the node, if it's NULL it goes at the head */ nodeStruct<T> *NewNode = new nodeStruct<T>; assert(NewNode != NULL); if (node == NULL) { /* set the data to the parameter, then set the pointers straight and pop it onto the head of the list */ node = NewNode; node->data = item; node->next = head; head = node; } else { NewNode->next = node->next; NewNode->data = item; node->next = NewNode; } num_items++; // increment num_items since we added return TRUE; } template <class T> bool listClass<T>::RemoveItem(nodeStruct<T> *node) { // Remove item assumes you have alread found the node, so child classes // will have to define their own rules to find items based on data type nodeStruct<T> *found; // if its at the head of the list, removal is easy if (node == head) { // deallocate any memory found = head; head = found->next; delete found; num_items--; /* decrement number of items in list */ return TRUE; /* it's been found, so return TRUE */ } else { register nodeStruct<T> *temp = head; while (temp && (temp->next != node)) temp = temp->next; if (temp->next == node) { // ie, it was found found = temp->next; temp->next = found->next; if (found) delete found; num_items--; // decrement number of items in list return TRUE; // yay, we found it so we return TRUE } } // Could not find it, oddly enough, so we return false. return FALSE; } // this function runs through the list and compares data, returning the node // if it is found template <class T> nodeStruct<T> *listClass<T>::FindItem(T item) { register nodeStruct<T> *temp; for (temp = head; temp; temp = temp->next) if (temp->data == item) return temp; return NULL; } //==============================List class===============================// // List is a special list used for the mud which checks for duplicate items // if DEBUG is defined template <class T> class List : public listClass<T> { public: List() {} List(const List<T>& L) {} virtual ~List() {} bool Add(T item, const char *filename, int lineno); bool Remove(T item); // Traverse will travel the list calling func with the data of each node // void Traverse(void (*func)(T)); }; //============================List member functions=====================// template <class T> bool List<T>::Add(T item, const char *filename, int lineno) { #ifdef DEBUG if (FindItem(item)) { cerr << "SYSERR: Attempt to add duplicate item to list in file " << filename << ", line: " << lineno << endl; abort(); } #endif return AddItem(NULL, item); } template <class T> bool List<T>::Remove(T item) { return RemoveItem(FindItem(item)); } //template <class T> //void List<T>::Traverse(void (*func)(T)) //{ // for (nodeStruct<T> *temp = head; temp; temp = temp->next) // func(temp->data); //} /* If we get here we're really fucked! SIKE! */ #endif