#include <iostream.h>
#include "Array.h"
#include "Strngs.h"
#include "SortArray.h"
#include "Stacks.h"

long calls = 0L;

#include "List.h"
#include "FastList.h"

#include "boolean.h"
#include "StopWatch.h"

#define List FastList

template <class T>  // recursive with value param
void writeList(List<T> t)
{	if(!t.empty())
	{	cout<<t.head()<<' ';
		writeList(t.tail());
	}
}

template <class T> // non recursive with value param
void swriteList(List<T> t)
{	while(!t.empty())
	{	cout<<t.head()<<' ';
		t = (t.tail());
	}
}

template <class T> //recursive with ref param.  
void WriteList(const List<T>& L)
{	if( ! L.empty() )
	{	cout << L.head() << ' ';
		WriteList(L.tail());
	}
}

template <class T>
void writeListReverse(const List<T>&t) // Write a list backwards. 
{	if(!t.empty())
	{	writeListReverse(t.tail());
		cout<<t.head()<<endl;
	}
}

template <class T>
T minList(const List<T>& t) // The minimum of t
{	if(t.empty())userERROR("Empty List");
	T x = t.head();
	if(t.tail().empty())return x;
	T y = minList(t.tail());	 
	if(x < y) return x; else return y;
}

template <class T>
List<T>  frontList(const List<T>& L)
{	if( L.empty()) return L;
	if( L.tail().empty()) return L.tail(); 
	return L.head() + frontList(L.tail());
}

template <class T> 
List<T> butMinList(const List<T>& L) // Everything in L but its minimum
{	if(L.empty())return L;
	if(L.tail().empty())return L.tail(); // empty list
	// L is not empty here. Neither is L.tail().
	T hd = L.head();
	List<T> tl = L.tail();	 
	T minTL = minList(tl);
	if(hd < minTL ) 
		return tl; 
	else 
		return hd + butMinList(tl);
}

template <class T>
List<T> SortList(const List<T>& t) // Selection sort
{	if(t.empty())return t;
	if(t.tail().empty())return t;
	T x = minList(t);
	List<T> L = butMinList(t);
	return x + SortList(L);
}

template <class T>
Boolean elementList(const T& e, const List<T>& t) // Is e an element of t?
{	if(t.empty())return false;
	if(e == t.head()) return true;
	return elementList(e, t.tail());
}

unsigned int fibonacci(unsigned int n)
{	if (n <= 1) return 1;
	return fibonacci(n-1) + fibonacci(n-2);
}

unsigned int FibonacciLoop(unsigned int n)
{	unsigned int last2 = 1, last1 = 1;
	unsigned int next;
	if(n <= 1) return 1;
	unsigned int i = 1;
	while( i++ < n)
	{	next = last1 + last2;
		last2 = last1;
		last1 = next;
	}
	return next;
}

unsigned int fastFibonacci
(	unsigned int last2,
	unsigned int last1,
	unsigned int i,
	unsigned int n
)	
{	if( i >= n ) return last1;
	return fastFibonacci(last1, last2 + last1, i+1,n);
}

unsigned int twoToThe(unsigned int n)
{	if (n == 0) return 1;
	return 2 * twoToThe(n-1);
}

 unsigned int ftwoToThe(unsigned int n)
{	if (n == 0) return 1;
	if ( n % 2 == 1)
		return 2 * twoToThe(n-1);
	else
	{	unsigned int temp = twoToThe(n / 2);
		return temp * temp;
	}
}


//SortableArray<String> L(4);
Array<String> inp(4);
StopWatch timer;

void main()
{	int i;
	inp[0] = "Zaphod Beeblebrox";
	inp[2] = "Hello";
	inp[1] = "Bye";
	inp[3] = "All's Well";
	for(i=0;i<4;i++)
		cout <<inp[i]<<endl;
	cout<<endl;
	
List<String> S;
S = inp[3] + S;
S = inp[2] + S;
S = inp[1] + S;
S = inp[0] + S;

List<String> T(S);
while(!T.empty())
{	cout<<T.head()<<endl;
	T = T.tail();
}
	cout<<endl;
writeListReverse(S);
	cout<<endl;

S = SortList(S);
writeList(S);
	cout<<endl;
	
//for(i = 0; i< 48; i++)
//cout << i<<' '<<twoToThe(i)<<' '<<ftwoToThe(i)<<endl;

List<int> IL;
for(i = 0; i< 50; i++)
	IL = i + IL;
// cout << "Length:       "<<IL.length()<<endl;
calls = 0L;
timer.start();
//swriteList(IL);
//cout<<endl;
swriteList(SortList(IL));
cout<<endl;
timer.mark();
cout << calls<<endl;
//swriteList(IL);
//cout<<endl;
//timer.mark();
//cout << calls<<endl;
timer.stop();

//if(elementList(String("bye"),S)) cout<<"true"; else cout<<"false";
//	SortableArray<String> L(inp);
//	L = inp;
//	L.quickSort(0,3);
//	for(i=0;i<4;i++)
//		cout << L[i]<<endl;
//	cout<<endl;
//	inp = L;
//	for(i=0;i<4;i++)
//		cout <<inp[i]<<endl;
//	cout<<endl;
	
{ // new scope
	Stack<int> SS;
	Array<int> DD = SS.asArray();
	cout << "array/stack"<<DD.length()<<endl;
}
}