#include <iostream>
#include <iomanip>
#include <vector>
#include "SortedList.h"

using namespace std;

class Integer {
  int value;
public:
  explicit Integer(int v=0) : value(v) {}
  int intValue() const { return value; }
  bool operator==(const Integer& i) const { return value==i.value; }
  bool operator<=(const Integer& i) const { return value<=i.value; }
  bool operator<(const Integer& i) const { return value<i.value; }
  bool operator>=(const Integer& i) const { return value>=i.value; }
  bool operator>(const Integer& i) const { return value>i.value; }
};

ostream& operator<<(ostream& os,const Integer &i)
{
  os <<i.intValue();
  return os;
}

typedef pair<SortedList<Integer> *,vector<int> > Pair;

void print(const Pair &P) {
  cout <<"Sorted List:";
	for (int i=1; i<=P.first->size(); i++)
		cout <<" "<<P.first->get(i);
	cout <<endl<<"Sorted array:";
	for (int i=0; i<P.second.size(); i++)
		cout <<" "<<P.second[i];
	cout <<endl;
}


template <typename T>
bool isSorted(const SortedList<T> &L) {
	for (int i=1; i<L.size(); i++)
		if (L.get(i) > L.get(i+1))
			return false;
    
	return true;
}

double compare(const Pair& P)
// return the number of points, max: 0.4
{
	print(P);
	SortedList<Integer> *L=P.first;;
	const vector<int> &A=P.second;
	double points=0.0;
	if (A.size()==L->size())
		points += 0.05;
	if (isSorted(*L))
		points += 0.05;
	int count=0;
	for (int i=0; i<A.size(); i++) {
		if (i+1 <= L->size() && A[i]==L->get(i+1).intValue())
			count++;
	}
	if (count>A.size()-3)
		points += 0.2-0.05*(A.size()-count);
	// test count()
	int idcount=1;
	count=0;
	int maxcount=0;
	for (int i=1; i<A.size(); i++) {
		if (A[i]==A[i-1]) {
			idcount++;
		} else {
			maxcount++;
			if (L->count(Integer(A[i-1]))==idcount)
				count++;
			idcount=1;
		}
	}
	maxcount++;
	if (L->count(Integer(A[A.size()-1]))==idcount)
		count++;
	if (count>maxcount-3)
		points += 0.1-0.025*(maxcount-count);
	return points;
}
  
Pair generate(int size,int minindex,int maxindex)
// for minindex and maxindex: non-positive values mean size()+1-index
{
	SortedList<Integer> *L=new SortedList<Integer>;
	vector<int> A(size);
	int mini,maxi;
	for (int i=0; i<size; i++) {
		if (maxindex<=0)
			maxi=L->size()+1-maxindex;
		else
			maxi=maxindex;
		if (minindex<=0)
			mini=L->size()+1-minindex;
		else
			mini=minindex;
    int item=rand()%20;
		L->add(rand()%(maxi-mini+1)+mini,Integer(item));
		A[i]=item;
	}
	sort(A.begin(),A.end());
	return Pair(L,A);
}

int main() {
	double points=0.0;
	double maxpoints=0.0;
  	
	srand(20062);

	// 5 tests, each 0.4 points:
    
	cout <<"Test 1."<<endl;
	// test adding at the beginning
	try {
		const Pair &P=generate(10,1,1);
		points += compare(P);
  	delete P.first;
	} 
	catch (exception e)
    {
      // no exception expected
      cout <<"Unexpected exception"<<e.what()<<endl;
    }
    
	cout <<"Test 2."<<endl;
	// test adding at the end
	try {
		const Pair &P=generate(20,0,0);
		points += compare(P);
		delete P.first;
	} 
	catch (exception e)
    {
      // no exception expected
      cout <<"Unexpected exception"<<e.what()<<endl;
    }
    
	cout <<"Test 3."<<endl;
	// test adding at random positions
	try {
		const Pair &P=generate(30,1,0);
		points += compare(P);
		delete P.first;
	} 
	catch (exception e)
    {
      // no exception expected
      cout <<"Unexpected exception"<<e.what()<<endl;
    }
    
	cout <<"Test 4."<<endl;
	// test remove at position
	try {
		Pair P=generate(30,1,-1);
		P.first->List<Integer>::remove(8);
		P.second.erase(P.second.begin()+7);
		points += compare(P)/2.0;
		P.first->List<Integer>::remove(20);
		P.second.erase(P.second.begin()+19);
		points += compare(P)/2.0;
		delete P.first;
	} 
	catch (exception e)
    {
      // no exception expected
      cout <<"Unexpected exception"<<e.what()<<endl;
    }
    
	cout <<"Test 5."<<endl;
	// test remove item
	try {
		Pair P=generate(30,1,-1);
		P.first->remove(Integer(11));
		P.second.erase(remove(P.second.begin(), P.second.end(), 11L), P.second.end());
		points += compare(P);
	} 
	catch (exception e)
    {
      // no exception expected
      cout <<"Unexpected exception"<<e.what()<<endl;
    }

	cout <<endl<<"Points="<<setprecision(2)<<points<<" out of 2"<<endl;

	system("PAUSE");
      	
  return 0;
}