//
// this is an example of linked lists using an iterator class.
// the test data is from the poem Jabberwocky by Lewis Carroll.
//
// Written by Maxwell Sayles, 2001, for CPSC331, University of Calgary.
//

#include <iostream>
using namespace std;

//
// class/structure declarations
//
struct Node;
class Iterator;
class List;


//
// class/structure definitions and member declarations
//

// linked list nodes
struct Node
{
	char* data; // pointer to an ASCIZ string
	Node* next;
};

// list iterator
// this iterator keeps track of the current and previous node, to allow for deleting of the current node
class Iterator
{
public:
	Iterator (List* list);
	bool HasMore();
	char* Item();
	void Next();
	void Insert (char* string);
	void Delete();
	
private:
	List* list;
	Node* currentNode;
	Node* previousNode;
};

// list class
class List
{
friend Iterator;
public:
	List();
	~List();

	void Prepend (char* string);
	Iterator Iterate();
	
private:
	Node* firstNode;
};



//
// create an iterator from a list
//
Iterator::Iterator (List* list)
{
	this->list = list;
	this->currentNode = list->firstNode;
	this->previousNode = 0;
}


//
// return true if there are more items in the list to iterate through
//
bool Iterator::HasMore()
{
	return (this->currentNode != 0);
}


//
// return the item the iterator currently points to
//
char* Iterator::Item()
{
	return this->currentNode->data;
}


//
// move the iterator to the next item
//
void Iterator::Next()
{
	this->previousNode = this->currentNode;
	this->currentNode = this->currentNode->next;
}


//
// creates a new node
// inserts the node into the list immediately before current node
// set the current node to the new node
//
void Iterator::Insert (char* string)
{
	Node* newNode = new Node;
	newNode->data = string;
	newNode->next = this->currentNode; // link the new node to this->current
	
	// are we inserting at the beginning of the list?
	if (this->currentNode == this->list->firstNode)
	{	// link first node of list to newNode
		this->list->firstNode = newNode;
	}
	
	else
	{	// link previous node to newNode
		this->previousNode->next = newNode;
	}	
	
	this->currentNode = newNode;
}


//
// delete the node currently pointed to
// point to the next node in the list
//
void Iterator::Delete()
{
	// does the currentNode point to the firstNode in the list?
	if (this->currentNode == this->list->firstNode)
	{	// link first node in list to next node
		this->list->firstNode = this->currentNode->next;
	}
	else
	{	// link previous node to next node
		this->previousNode->next = this->currentNode->next;
	}
	
	Node* nextNode = this->currentNode->next;
	delete this->currentNode;
	this->currentNode = nextNode;
}


//
// construct an empty list
//
List::List()
{
	this->firstNode = 0;
}

//
// go through each node and delete it
//
List::~List()
{
	Node* n = this->firstNode;
	while (n != 0)
	{
		Node* next = n->next;
		delete n;
		n = next;
	}
}

//
// prepend a string onto the beginning of the list
//
void List::Prepend (char* string)
{
	Node* newNode = new Node;
	newNode->data = string;
	newNode->next = this->firstNode;
	this->firstNode = newNode;
}

//
// create a list iterator
//
Iterator List::Iterate()
{
	return Iterator (this);
}


//
// print the list
//
void PrintList (List& list)
{
	Iterator iter = list.Iterate();
	while (iter.HasMore())
	{
		cout << iter.Item() << endl;
		iter.Next();
	}
	cout << endl;
}


//
// program entry
//
int main()
{
	List list;
	
	// prepend lines of Jaberwocky into the list
	// the lines are prepended in reverse order, because each new line is put on the front of the list
	list.Prepend ("  And the mome raths outgrabe.");
	list.Prepend ("All flimsy were the borogoves,");
	list.Prepend ("  Did gyre and gimble in the wabe:");
	list.Prepend ("'Twas brillig, and the slithy toves");
	
	PrintList (list);
	
	// the third line has a typo ('flimsy' should be 'mimsy'), so we need to delete it
	Iterator iter = list.Iterate();	// iter points to first line
	iter.Next();					// iter points to second line
	iter.Next();					// iter points to third line
	iter.Delete();					// delete the third line
	iter.Insert ("All mimsy were the borogoves,");		// insert the correct line
	
	PrintList (list);

	return 0;
}