// FILE: SlistT.cpp
// Ed Smith
// R England, Rhodes College
// CS 142, Spring 2003
//
//		Implementation: singly linked list Template
//
//		Class invariants:
//			- head, tail, and cursor are nonzero
//			- head points at empty head node
//			- tail points at last node
//			- last node has zero next pointer
//			- all fn's maintain length var

#include	"SlistT.h"

#include	<iostream>
using namespace std;




//////// public member functions ////////

//// constructor, destructor
template <class Type>
SlistT<Type>::SlistT (void) {
	tail = cursor = head = new Node;
	listLength = 0;
}

template <class Type>
SlistT<Type>::~SlistT (void) {
	clean ();
	delete head;
}

//// mutators

// insert
//		insert newItem after cursor node
template <class Type>
void SlistT<Type>::insert (const Type& newItem) {
	Node *pNewNode = new Node (newItem);
	if (!(pNewNode -> next = cursor -> next))
		tail = pNewNode;
	cursor -> next = pNewNode;
	listLength++;
}

// remove
//		delete node following cursor node
template <class Type>
bool SlistT<Type>::remove (void) {
	Node *temp;
	temp = cursor -> next;
	if (temp) {
		if (temp == tail)
			tail = cursor;
		cursor -> next = cursor -> next -> next;
		delete temp;
		listLength--;
		return true;
	}
	return false;
}





// clean
//		delete all nodes
template <class Type>
void SlistT<Type>::clean (void) {
	reset ();
	while (remove ())
		;
}

// append
//		add copies of nodes from another list to end of this list
template <class Type>
bool SlistT<Type>::append(const SlistT& other){
	Node *temp;
	temp = other.head -> next;

	if ((other.empty()) || (equal(other)))
		return false;

	while (temp){
		moveToEnd();
		insert(temp -> dataItem);
		temp = temp -> next;
	}
	return true;
}

// prepend
//		add copies of nodes from another list to beginning of this list
template <class Type>
bool SlistT<Type>::prepend(const SlistT& other){
	Node *temp;
	temp = other.head -> next;

	Node *tempCursor;
	tempCursor = head;

	if ((other.empty()) || (equal(other)))
		return false;
	reset ();
	while (temp){
		insert(temp -> dataItem);
		temp = temp -> next;
		cursor = cursor -> next;
	}
	return true;
}

// rotateLeft
//		rotate nodes to the left n places
template <class Type>
bool SlistT<Type>::rotateLeft (unsigned n){
	Node *ptr1;
	ptr1 = head;
	if ((empty()) || (!(n % listLength)))
		return false;
	
	for (unsigned i = 0; i < (n % listLength); i++){
		ptr1 = ptr1 -> next;
	}
	tail -> next = head -> next;
	head -> next = ptr1 -> next;
	ptr1 -> next = 0;
	tail = ptr1;
	return true;
}

// rotateRight
//		rotate nodes to the right n places
template <class Type>
bool SlistT<Type>::rotateRight (unsigned n){
	unsigned temp;
	if ((empty()) || (!(n % listLength)))
		return false;
	temp = listLength - (n % listLength);
	rotateLeft (temp);
	return true;
}

// move
//		move cursor to next node
template <class Type>
bool SlistT<Type>::move (void) {
	if (cursor -> next) {
		cursor = cursor -> next;
		return true;
	}
	return false;
}

// moveToEnd
//		set cursor to point to tail node
template <class Type>
void SlistT<Type>::moveToEnd (void) {
	 cursor = tail; 
}

// reset
//		set cursor to point to empty head node
template <class Type>
void SlistT<Type>::reset (void) {
	 cursor = head; 
}



//// accessors

// empty
//		return true if list is empty; false otherwise
template <class Type>
bool SlistT<Type>::empty (void) const { 
	return (head == tail); 
}

// get
//		retrieve data item in node after cursor node
template <class Type>
bool SlistT<Type>::get (Type& item) const {
	if (cursor -> next) {
		item = cursor -> next -> dataItem;
		return true;
	}
	return false;
}

// length
//		return the length of the list
template <class Type>
unsigned SlistT<Type>::length () const{return listLength;}

// equal
//		determine wether 2 lists are one and the same
template <class Type>
bool SlistT<Type>::equal (const SlistT& other) const{
	return ((this) == (&other));
}

// printDEBUG
//		print all items of the list
//		[DEBUGGING fn --- application would normally control all output!]
template <class Type>
void SlistT<Type>::printDEBUG (void) const {
	printDEBUG (head -> next);
}



//////// private member function ////////

// printDEBUG
//		print data item stored in thisNode and beyond
template <class Type>
void SlistT<Type>::printDEBUG (const Node *thisNode) const {
	if (thisNode) {
		cout << thisNode -> dataItem << ' ';
		printDEBUG (thisNode -> next);
	}
	
}