/*#########################################################
HEADER FILE "linked_list.h":
###########################################################*/
 
/* Joe Pea - Linked List */
 
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
 
#include <cstdlib>  // Provides size_t
#include "node.h"  // Provides node class
 
namespace CISP430_A5
{
    template <class Item>
    class linked_list
	/*TODO: * Optimize so that we don't have to iterate through each address to reach a desired position.
			  Make a "position" field for each Node object or something?
			  Or create a "last_position" variable in this class so we can iterate forward
			  or backward from the last position instead of from the beginning each time?
			* Add post and pre conditions for all the new functions above.
	*/
	/**
			The /*REMOVED*//*, /*STAYS THE SAME*//*, and /*ADDED*//* comments show the 
			differences in converting from the sequence class to the linked_list class.
	*/
    {
		public:
		/* TYPEDEFS and MEMBER CONSTANTS: */
			typedef Item value_type;
			typedef size_t size_type;
 
 
 
		/* CONSTRUCTORS and DESTRUCTOR: */
			linked_list( );
			linked_list(const linked_list& source);
			~linked_list( );
 
 
 
		/* MODIFICATION MEMBER FUNCTIONS */
			/*ADDED:*/
				value_type get(int position); // get item at position x
				void set(int position, const value_type& entry); // set item at position x, if past boundaries, just modify at beginning or at end.
				void add(const value_type& entry); // add to the end of list
				void insert(int position, const value_type& entry); // set item at position x, if past boundaries, just insert at beginning or attach at end.
				void attach(int position, const value_type& entry); // set item at position x, if past boundaries, just insert at beginning or attach at end.
				void remove(int position);
 
			/*REMOVED:*/
				/*void remove_current( );*/
				/*void start( );*/
				/*void advance( );*/
				/*void insert(const value_type& entry);*/
				/*void attach(const value_type& entry);*/
 
			/*STAYS THE SAME:*/
				void operator=(const linked_list& source);
 
 
 
		/* CONSTANT MEMBER FUNCTIONS */
			/*STAYS THE SAME:*/
				value_type current( ) const;
				size_type size( ) const { return many_nodes; }
				bool is_item( ) const { return (cursor != NULL); }
 
 
 
		private:
		/*PRIVATE HELPER FUNCTIONS*/
			/*ADDED:*/
				void remove_current( );
				void start( );
				void advance( );
				void insert_here(const value_type& entry); // same as insert() from sequence. insert at current position.
				void attach_here(const value_type& entry); // same as attach() from sequence. attach at current position.
 
 
 
		/*PRIVATE VARIABLES*/	
			/*STAYS THE SAME:*/
				node<Item> *cursor;
				node<Item> *precursor;
				node<Item> *head_ptr;
				node<Item> *tail_ptr;
				size_type many_nodes;
    };
}
 
 
 
 
 
/* Sample usage:
int main(void) {
 
	linked_list items = new linked_list;
	items.attach(10);
	items.insert(30);
	items.attach(20);
	items.insert(40);
 
	// for each item in the list:
	for (int i=0; i<items.size(); ++i) {
		cout << items.get(i) << endl;
	}
 
	items.set(2, 50);
	// item at position 2 is now 50.
}
*/
 
 
 
 
// The implementation of a template class must be included in its header file:
#include "linked_list.template"
#endif
 
/*#########################################################
TEMPLATE FILE "linked_list.template":
###########################################################*/
 
 
/* Joe Pea - CISP430 Assignment 5 */
 
namespace CISP430_A5 {
/*I've marked lines/blocks as REMOVED or ADDED in order to tell what I changed
	from the sequence class to create my ideal linked_list class*/
/*TODO: Add previous field to Node class and remove usage of precursor.*/
 
	/* CONSTRUCTORS and DESTRUCTOR */
 
	template <class Item>
	linked_list<Item>::linked_list() {
		head_ptr = NULL;
		tail_ptr = NULL;
		cursor = NULL;
		precursor = NULL; // no need for this if Node objects have a "previous" link field.
		many_nodes = 0;
	}
 
	template <class Item>
	linked_list<Item>::linked_list( const linked_list& source ) { // copier
 
		int src_size = source.size(); // to replicate cursor position
		int many_til_end = 0; // to replicate cursor position
		int many_til_mid = 0; // to replicate cursor position
		node<Item> *src_cursor = source.cursor; // to replicate cursor position
 
		list_copy(source.head_ptr, head_ptr, tail_ptr);
 
		/*replicate the size value (before cursor position because functions used for that depend on many_nodes value*/
			many_nodes = source.many_nodes;
 
		/*replicate the cursor position*/
			if (src_cursor != NULL) {
				while (src_cursor != NULL) {
					++many_til_end;
					src_cursor = src_cursor->link();
				}
				many_til_mid = src_size - many_til_end; // this is how many to advance to replicate cursor position.
				start(); // put this.cursor at beginning. // DEPENDS ON VALUE OF many_nodes ABOVE
				for (int i=0; i<many_til_mid; ++i) {
					advance(); // DEPENDS ON VALUE OF many_nodes ABOVE
				}
				/* after the for loop, the new linked_list's cursor should be at the same position as the source's cursor was.*/
			}
			else {
				cursor = NULL;
				precursor = NULL;
			}
	}
 
	template <class Item>
	linked_list<Item>::~linked_list() { // Destructor
		list_clear(head_ptr);
		head_ptr = tail_ptr = cursor = precursor = NULL;
		many_nodes = 0;
	}
 
	/* MODIFICATION MEMBER FUNCTIONS */
 
	template <class Item>
	void linked_list<Item>::start() {
		if (many_nodes > 0) { // if at least one item exists
			cursor = head_ptr;
			precursor = NULL;
		}
	}
 
	template <class Item>
	void linked_list<Item>::advance() {
		if (is_item()) {
			precursor = cursor;
			cursor = cursor->link();
			if ( cursor == NULL ) {
				precursor = NULL;
			}
		}
	}
 
	/*
	ADDED [
	*/
		template <class Item>
		typename linked_list<Item>::value_type linked_list<Item>::get(int position) {
			for (int i=0; i<=position; ++i) { // advance the cursor to the position then return item
				if (i==0)
					start();
				else
					advance();
 
				if (i==position) {
					return current();
				}
			}
		}
 
		template <class Item>
		void linked_list<Item>::set(int position, const value_type& entry) {
			if (is_item()) { // only set at a valid position.
 
				insert(position, entry); // insert new item to list
 
				advance();
				remove_current(); // remove old item from list.
			}
		}
 
		template <class Item>
		void linked_list<Item>::add(const value_type& entry) {
			cursor = precursor = NULL; // remove cursor
			attach_here(entry); // <<-- attaches at end when no cursor.
		}
 
		template <class Item>
		void linked_list<Item>::remove(int position) {
			for (int i=0; i<=position; ++i) { // advance the cursor to the position then insert item
				if (i==0)
					start();
				else
					advance();
 
				if (i==position) {
					remove_current();
				}
			}
		}
 
		template <class Item>
		void linked_list<Item>::insert(int position, const value_type& entry) {
			for (int i=0; i<=position; ++i) { // advance the cursor to the position then insert item
				if (i==0)
					start();
				else
					advance();
 
				if (i==position) {
					insert_here(entry);
				}
			}
		}
	/*
	]
	*/
 
	template <class Item>
	void linked_list<Item>::insert_here(const value_type &entry) {
	/*REMOVED*/
		// void linked_list<Item>::insert(const value_type &entry) {
 
		/*if the list is empty*/
		if (!is_item() && !many_nodes) {
			cursor = new node<Item>(entry);
			head_ptr = cursor;
			tail_ptr = cursor;
		}
 
		/*if the list is not empty and cursor points to the first item*/
		else if (is_item() && cursor == head_ptr) {
			cursor = new node<Item>( entry );
			cursor->set_link( head_ptr );
			head_ptr = cursor;
		}
 
		/*if the list is not empty and there is no current item*/
		else if (!is_item() && many_nodes) {
			cursor = new node<Item>( entry );
			cursor->set_link( head_ptr );
			head_ptr = cursor;
		}
 
		/*if the list is not empty and the cursor points somewhere in 
			the middle(including last item)*/
		else if (is_item() && cursor != head_ptr) {
			cursor = new node<Item>( entry );
			cursor->set_link( precursor->link() );
			precursor->set_link( cursor );
		}
 
		++many_nodes; //increase the node count
	}
 
	/*ADDED*/
		template <class Item>
		void linked_list<Item>::attach(int position, const value_type& entry) {
			for (int i=0; i<=position; ++i) { // advance the cursor to the position then attach item
				if (i==0)
					start();
				else
					advance();
 
				if (i==position) {
					attach_here(entry);
				}
			}
		}
 
	template <class Item>
	void linked_list<Item>::attach_here(const value_type& entry) {
	/*REMOVED*/
		// void linked_list<Item>::attach(const value_type& entry) {
 
		/*if the list is empty*/
		if (!is_item() && !many_nodes) {
			cursor = new node<Item>(entry);
			head_ptr = cursor;
			tail_ptr = cursor;
			precursor = NULL;
		}
 
		/*if the list is not empty and cursor points to the first item and there's only one item*/
		else if (is_item() && many_nodes == 1) {
			cursor = new node<Item>( entry );
			cursor->set_link( head_ptr->link() );
			head_ptr->set_link( cursor );
			precursor = head_ptr;
			tail_ptr = cursor;
		}
 
		/*if the list is not empty and cursor points to the first item and there's more than one item*/
		else if (is_item() && many_nodes > 1 && cursor == head_ptr ) {
			cursor = new node<Item>( entry );
			cursor->set_link( head_ptr->link() );
			head_ptr->set_link( cursor );
			precursor = head_ptr;
		}
 
		/*if the list is not empty and there is no current item*/
		else if (!is_item() && many_nodes) {
			cursor = new node<Item>( entry );
			tail_ptr->set_link( cursor );
			precursor = tail_ptr;
			tail_ptr = cursor;
		}
 
		/*if the list is not empty and the cursor points somewhere in 
			the middle(including last item)*/
		else if (is_item() && cursor != head_ptr) {
			if (cursor != tail_ptr) { // if cursor is not at last item
				cursor = new node<Item>( entry );
			}
			else if (cursor == tail_ptr) { // if cursor is at last item
				cursor = new node<Item>( entry );
				tail_ptr = cursor;
			}
			cursor->set_link( (precursor->link())->link() );
			(precursor->link())->set_link( cursor );
			precursor = precursor->link();
		}
 
		++many_nodes; // increase the node count
	}
 
	template <class Item>
	void linked_list<Item>::remove_current() {
		if ( is_item() ) {
 
			/*If the cursor points to an item in the middle of the list, not tail, not head:*/
			if (cursor != head_ptr && cursor != tail_ptr) {
				precursor->set_link( cursor->link() );
				delete cursor;
				cursor = precursor->link();
			}
 
			/*If the cursor points to the first item in the list and that is the only item:*/
			else if (many_nodes == 1) {
				delete cursor;
				cursor = head_ptr = tail_ptr = precursor = NULL;
			}
 
			/*If the cursor points to the first item in the list and there is more than one item:*/
			else if ( cursor == head_ptr && many_nodes > 1) {
				cursor = cursor->link();
				delete head_ptr;
				head_ptr = cursor;
			}
 
			/*If the cursor points to the last item in the list (and there is more than one item)*/
			else if ( cursor == tail_ptr && many_nodes > 1) {
				delete cursor;
				tail_ptr = precursor;
				/* #!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!# */
				tail_ptr->set_link(NULL);
				/* #!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!# */
				precursor = cursor = NULL;
			}
 
			--many_nodes;
		}
	}
 
	template <class Item>
	void linked_list<Item>::operator =(const linked_list& source) {
		if (this != &source) {
			list_clear(head_ptr);
			head_ptr = tail_ptr = cursor = precursor = NULL;
			many_nodes = 0;
 
			int src_size = source.size(); // to replicate cursor position
			int many_til_end = 0; // to replicate cursor position
			int many_til_mid = 0; // to replicate cursor position
			node<Item> *src_cursor = source.cursor; // to replicate cursor position
 
			list_copy(source.head_ptr, head_ptr, tail_ptr);
 
			/*replicate the size value (before cursor position because functions used for that depend on many_nodes value*/
				many_nodes = source.many_nodes;
 
			/*replicate the cursor position*/
				if (src_cursor != NULL) {
					while (src_cursor != NULL) {
						++many_til_end;
						src_cursor = src_cursor->link();
					}
					many_til_mid = src_size - many_til_end; // this is how many to advance to replicate cursor position.
					start(); // put this.cursor at beginning.
					for (int i=0; i<many_til_mid; ++i) {
						advance();
					}
					/* after the for loop, the new linked_list's cursor should be at the same position as the source's cursor was.*/
				}
				else {
					cursor = NULL;
					precursor = NULL;
				}
		}
	}
 
	/* CONSTANT MEMBER FUNCTIONS */
 
	template <class Item>
	typename linked_list<Item>::value_type linked_list<Item>::current() const {
		if ( is_item() ) {
			return cursor->data();
		}
	}
 
}