/* This file contains the List class, a singly linked unordered
* templated list class. struct List_Link is the data structure for
* the list links.
*
* Copyright (c) 1994, 2014 by Aaron Bloomfield
* Released under a CC BY-SA license
*
* Revision history
* 05-01-94: Main code written
* 07-12-95: Bug updates
* 01-13-14: Modified to fit modern C++ compilers; reformatted
*
* The tail of the list, in this implementation, is where the elements
* are pushed (added) to and popped (removed) from. For example:
*
* head <-- element <-- element <-- element <-- element <-- tail
*
*
* Methods:
*
* List() Constructor, initilized an empty list
* ~List() Destructor, deletes the entire list
* void push(T item); Adds an item to the tail of the list
* T* pop(); Removes an item from the tail of the list
* int size(); Returns the size (length) of the list
* void display(); Displays the list
* int empty(); Returns 1 if the list is empty, 0 otherwise
* void clear(); Clears (removes all elements from) the list
* T* push_head(); Adds an item to the head of the list
* T* tail(); Returns the tail data
* T* head(); Returns the head data
* int element (T item); Returns 1 if T is in the list, 0 otherwise
* pop_head (T item); Removes an item from the head of the list
* int remove (T item) Removes item, returns 1 if sucessful, else 0
* T* getptr (T item) Returns the pointer to the parameter or NULL
* void save(FILE *fp) Saves the list- calls the objects methods
*
*
* The List class requires <iostream> to be included, as it uses
* cout's in the display method.
*
* In order to use the List class, the data type T must either be a
* standard type, or be a class with the '==' operator overloaded. To
* use the display method, the data type must also have the '<<'
* operator overloaded. Examples follow, using a Complex class with
* two attributes, real and imag (both ints). The operator overloads
* need to be functions outside the class declaration, and the
* attributes used need to be public.
*
* class Complex {
* public:
* int real, imag;
* Complex () { real = imag = 0; }
* Complex (int r, int i) { real = r; imag = i; }
* ~Complex () { }
* void set (int r, int i) { real = r; imag = i; }
* };
*
* int operator == (Complex c1, Complex c2) {
* return ( (c1.real == c2.real) && (c1.imag == c2.imag) );
* }
*
* int operator != (Complex c1, Complex c2) {
* return ( (c1.real != c2.real) || (c1.imag != c2.imag) );
* }
*
* ostream& operator << (ostream& out, Complex c) {
* return (out << c.real << " + " << c.imag << "i");
* }
*
*/
#include <iostream>
using namespace std;
template <class T>
struct List_Link {
T *data;
List_Link<T> *next;
};
template <class T>
class List {
friend class Fsm;
/* head <-- element <-- element <-- element <-- element <-- tail */
private:
List_Link<T> *_head, *_tail;
public:
List() {
_head = _tail = NULL;
} // cout << "List Constructor called.\n"; }
~List() {
clear();
}
void push(T item) {
// cout << "push(): called with element: " << item << endl;
if ( _head == NULL ) {
_head = _tail = new List_Link<T>;
_head->next = NULL;
} else {
List_Link<T> *temp;
temp = _tail;
_tail = new List_Link<T>;
_tail->next = temp;
}
_tail->data = new T;
*_tail->data = item;
}
T* pop() {
if ( _head == NULL )
return NULL;
else {
List_Link<T> *temp;
T *ret;
temp = _tail;
if ( _head == _tail )
_tail = _head = NULL;
else
_tail = _tail->next;
ret = temp->data;
delete temp;
return ret;
}
}
int size() {
if ( _tail == NULL )
return 0;
else {
int s = 0;
List_Link<T> *temp;
for ( temp = _tail; temp != NULL; temp = temp->next )
++s;
return s;
}
}
void save(FILE *fp) {
if ( _head == NULL ) {}
else {
List_Link<T> *temp;
for ( temp = _tail; temp != NULL; temp = temp->next )
temp->data->save(fp);
}
}
void display() {
if ( _head == NULL )
cout << "List is empty.\n";
else {
// cout << "display(): List is printed reverse: List is not empty.\n\t";
List_Link<T> *temp;
for ( temp = _tail; temp != NULL; temp = temp->next )
cout << *temp->data << " ";
cout << endl;
}
}
int empty() {
return ( _head == NULL );
}
T* tail() {
if ( _tail == NULL )
return NULL;
else
return _tail->data;
}
T* head() {
if ( _head == NULL )
return NULL;
else
return _head->data;
}
int element (T item) {
List_Link<T> *temp;
if ( _tail == NULL )
return 0;
for ( temp = _tail; temp != NULL; temp = temp->next )
if ( *temp->data == item )
return 1;
return 0;
}
T* getptr (T item) {
List_Link<T> *temp;
if ( _tail == NULL )
return NULL;
for ( temp = _tail; temp != NULL; temp = temp->next )
if ( *temp->data == item )
return temp->data;
return NULL;
}
void clear() {
while ( this->pop() != NULL ) { }
}
void push_head (T item) {
if ( _head == NULL ) {
_head = _tail = new List_Link<T>;
_head->next = NULL;
} else {
List_Link<T> *temp;
temp = _head;
_head = new List_Link<T>;
temp->next = _head;
_head->next = NULL;
}
_head->data = new T;
*_head->data = item;
}
T* pop_head() {
if ( _head == NULL )
return NULL;
else {
List_Link<T> *temp;
T *ret;
for ( temp = _tail; temp->next != _head; temp = temp->next ) { }
ret = _head->data;
_head = temp;
temp = temp->next;
delete temp;
_head->next = NULL;
return ret;
}
}
int remove (T item) {
if ( this->element(item) ) {
cout << "remove(): element '" << item << "' exists.\n";
if ( _head == _tail ) {
delete _head;
_head = _tail = NULL;
} else if ( *_tail->data == item ) {
List_Link<T> *temp;
temp = _tail;
_tail = _tail->next;
delete temp;
} else {
List_Link<T> *temp, *temp2;
for ( temp = _tail;
*temp->next->data != item;
temp = temp->next ) { }
temp2 = temp->next;
temp->next = temp->next->next;
delete temp2;
}
return 1;
} else {
cout << "remove(): element '" << item << "' does not exist.\n";
return 0;
}
}
};