template<class dataType> cllist::cllist() { init();}
template<class dataType> cllist::cllist(unsigned long n) { init(n);}
template<class dataType> cllist::cllist(unsigned long n, dataType defVal){ init(n,defVal);}
template<class dataType> cllist::~cllist(){ flush();}

// template linked list class by chris stones.
// a class to hold a variable array / stack of any type.
// maximum size of array = 4,294,967,296 (unsigned long).
// the Arrays performance does NOT decreace with size when used in a sequential mannor. 

// a single link in the list
template <class dataType>
struct clink {
	clink<dataType> *left;
	clink<dataType> *right;
	dataType	 data;
};

// floater. a marker that points to the item in the list that was last accessed in the hope that the next
// link that needs finding will probably lie next to it.
template <class dataType>
struct cfloater {
	unsigned long currentIndex;
	clink<dataType> *currentAddress;
};

// an exception to throw
class TLLIST_OUT_OF_BOUNDS{};

// where all the magick happens.
template <class dataType>
class cllist {
private:
	clink<dataType> first,last;
	cfloater<dataType> floater;
	unsigned long size;
	
	void init();
	void init(unsigned long, dataType);
	void init(unsigned long);
	
	clink<dataType> *access(unsigned long);

public:
	~cllist();
	cllist();					// default constructor, sets up an emptly list.
	cllist(unsigned long);				// single parameter constructor, sets up an array of the specified size.
	cllist(unsigned long,dataType);			// same as above, but with initiated to match parameter 2.
	
	dataType pop(unsigned long);			// remove a single item from anywhere in the list.
	dataType popLeft();				// remove the first (left) item from the fist.
	dataType popRight();				// remove the last (right) item from the list.
	
	void push(unsigned long, dataType);		// insert an item anywhere on the list.
	void pushLeft(dataType);			// add an item onto the beggining (Left) of the list
	void pushRight(dataType);			// add an item onto the end (right) of the list
	
	void flush();					// empty the list.
	unsigned long getSize();			// return the size of the list.
	
	dataType& operator [](double);			// overloaded [] for array like access to the list.
};

// constructors + destructors
template<class dataType> cllist::cllist() { init();}
template<class dataType> cllist::cllist(unsigned long n) { init(n);}
template<class dataType> cllist::cllist(unsigned long n, dataType defVal){ init(n,defVal);}
template<class dataType> cllist::~cllist(){ flush();}

// smaller function boddies
template<class dataType> void cllist::init(unsigned long n, dataType defVal) { while(size != n) { push(defVal);}}
template<class dataType> void cllist::init(unsigned long n) { init(); init(n,dataType());}
template<class dataType> dataType cllist::popLeft() { return pop(0);}
template<class dataType> dataType cllist::popRight() { return pop(size-1);}
template<class dataType> void cllist::pushLeft(dataType data) { push(0,data);}
template<class dataType> void cllist::pushRight(dataType data) { push(size, data);}
template<class dataType> dataType& cllist::operator [](double n) { return access(n)->data;}
template<class dataType> void cllist::flush() { while(size != 0){ pop(0);}}
template<class dataType> unsigned long cllist::getSize() { return size;}

template<class dataType> void cllist::init(){
	// basic initilisation
	size			= 0;
	first.left		= 0;
	first.right		= &last;
	last.right		= 0;
	last.left		= &first;
	floater.currentIndex	= 0;
	floater.currentAddress	= 0;
}

template<class dataType> clink<dataType>* cllist::access(unsigned long index) {
			
	// a quick check...
	if(index >= size) { throw TLLIST_OUT_OF_BOUNDS(); }
		
	// which is closer to the desired link ? (first, last or floater)
	unsigned long distanceFirst   = index + 1;
	unsigned long distanceLast    = (size + 1) - index;
	unsigned long distanceFloater;
		
	// the first time access() is called, floater is not inside the actual array,
	// and because index is an unsigned variable (not able to be -1) its index is incorrect to its position,
	// ignore floater the first time the closest point is calculated.
	if (floater.currentAddress != &first) {
		if (index >= floater.currentIndex) { distanceFloater = index - floater.currentIndex; }
		else				   { distanceFloater = floater.currentIndex - index; }
	}
	else { distanceFloater = size; } // make it impossibly big, so one of the others is selected as closer.
		
	// is the required index point to the right, or left of the closest known index point ?
	bool loopRight = true;
		
	// default, first is closest
	clink<dataType> *thisLink = &first;
	unsigned long distance = distanceFirst;
		
	// maybe last is closer ??
	if (distanceLast    < distance) { 
		distance = distanceLast; 
		thisLink = &last; 
		loopRight = false;
	}
		
	// or maybe the floater ??
	if (distanceFloater < distance) { 
		distance = distanceFloater; 
		thisLink = floater.currentAddress; 
		if (floater.currentIndex > index) { loopRight = false; }
		else				  { loopRight = true; }	
	}
		
	// now loop to the required access index.
	while(distance != 0) {
		distance--;
		if (loopRight) { thisLink = thisLink->right; }
		else	       { thisLink = thisLink->left;  }
	}
		
	// set floater to this link UNLESS accessing the first of last link (remembed by first and last local variable)
	if(index != 0 && index != size-1) {
		floater.currentIndex = index;
		floater.currentAddress = thisLink;
	}
		
	//return result
	return thisLink;
}

template<class dataType> dataType cllist::pop(unsigned long n) {
	
	clink<dataType> *popLink = access(n);
	dataType forReturn = popLink->data;
		
	// correct pointers on either side of the link to be poped
	popLink->left->right = popLink->right;
	popLink->right->left = popLink->left;
		
	// correct size parameter
	size--;
		
	// are we about to delete the object that the floater points to ?
	if(popLink == floater.currentAddress) {
		// move the floater to the right, (index remains correct)
		floater.currentAddress = popLink->right;
	}
	else {
		// the object floater points to will not be deleted.
		// however, if we deleted an object on the left of floater, then floaters
		// index needs to be decremented.
		if(n < floater.currentIndex) { floater.currentIndex--; }
	}
	// delete the poped link
	delete popLink;
		
	// return the data
	return forReturn;
}

template<class dataType> void cllist::push(unsigned long index, dataType value) {
	
	// to push to position n is to add a link with the index of n. pushing the last index n to index n+1.
	clink<dataType> *rightLink;
	clink<dataType> *leftLink;
	
	// create a new link.
	clink<dataType> *newLink = new clink<dataType>;
	newLink->data = value;
		
	// get the link which will be to the right of the new link
	// special case.. PUSHING to the very end of the list. will throw an out of bounds if we call accessLink()
	if (index == size) { rightLink = &last; }
	else               { rightLink = access(index); }
		
	// get the link which will be to the left of the new link
	leftLink = rightLink->left;
		
	// insert the new link
	newLink->right = rightLink;
	newLink->left  = leftLink;
	rightLink->left = newLink;
	leftLink->right = newLink;
		
	// fix the size variable
	size++;
		
	// fix the floater....
	// dont move the floater if we are pushing to the very right, or left of the list
	if(index != size-1 && index != 0) {
		floater.currentIndex = index;
		floater.currentAddress = newLink;
	}
	else {
		// if we just pushed to the left of the floater, then floaters index needs to be incrememnted
		if(index <= floater.currentIndex) {
			floater.currentIndex++;
		}
	}
}

// linked list tester by chris stones.

#include<iostream>
using namespace std;

#include"tllist.h"

// tests...
//	add 100 items to the list
//	remove link from random place
//	add link to random place
//	output entire list (with array interface)
//	output entire list by popping.

// exception tests...
//	Out of bounds

int main() {

	cllist<int> stack;
	int n;
	
	cout << "pushing 20 numbers to the right" << endl;
	for (n=0; n<20; n++) { stack.pushRight(n); }
	
	cout << "output entire list" << endl;
	for (n=0; n<20; n++) { cout << stack[n] << '|'; }
	
	cout << "output intex 10" << endl;
	cout << stack[10] << endl;
	
	cout << "output index 15" << endl;
	cout << stack[15] << endl;
	
	cout << "insert 99 into index 10" << endl;
	stack.push(10,99);
	
	cout << "remove index 1 = ";
	cout << stack.pop(1) << endl;
	
	cout << "pop all items off list" << endl;
	while(stack.getSize != 0) {
		cout << stack.popLeft() << '|';
	}
	
	cout << "cause out of bounds error" << endl;
	stack.popRight();

	return 0;
}

template<class dataType> cllist<dataType>::cllist() { init();}