#include <stdio.h>
#include <stdlib.h>
#include "config.h"
#include "BHeap.h"
#include "FHeap.h"
#include "PLList.h"

char N[] = {
	5, 9, 10, 29, 6, 1, 15, 18, 25, 11,
	2, 14, 23, 16, 17, 3, 8, 24, 20, 13,
	30, 21, 26, 4, 7, 28, 12, 27, 19, 22,
};

void exception(int e, char *msg)
{
	fprintf(stderr, "%s\n", msg);
	exit(-1);
}

PriorityList *newlist(void)
{
	return new FHeap;
}

void DoCombTest(int number)
{
	int i, n;
	Key_t K, oK;
	Datas_t Datas;
	PriorityList *T;

	cerr << _("Creation of a priority list and adding ") << number <<
		_(" random entrie(s)...");
	T = newlist();
	for (i = 1; i <= number; i++) {
		T->Insert(rand() % P_INFINITY, NULL);
	}
	cerr << _("Ok.\nDeleting the list...");
	oK = P_INFINITY;
	for (i = number; i >= 1; i--) {
		T->Dump(cerr);
		if (T->n() != i) {
			cerr << _("List has ") << T->
				n() << _(" keys. Expecting ") << i << endl;
			exception(1, _("List corrupted."));
		}
		if ((n = T->rn()) != i) {
			cerr << _("List has ") << T->
				rn() << _(" keys (real count). Expecting ") <<
				i << endl;
			exception(1, _("List corrupted."));
		}
		K = T->Extract_Min(Datas);
		if (oK < K)
			exception(1, _("Incorrect order."));
	}
	delete T;

	cerr << "Ok.\n";
}

void FullTest(void)
{
	PriorityList *T;
	Datas_t Datas;
	char msg[10240];
	Cell C1, C2;
	Key_t K;
	int i;

	cerr << _("Size of a PriorityList cell: ") << sizeof(PriorityList) <<
		endl;
	cerr << _("Size of a BHeap cell       : ") << sizeof(BHeap) << endl;
	cerr << _("Size of a FHeap cell       : ") << sizeof(FHeap) << endl;
	cerr << _("Size of a PList header     : ") << sizeof(PLList) << endl;
	cerr << _("Size of a CList cell       : ") << sizeof(CList) << endl;
	cerr << _("Size of a SList cell       : ") << sizeof(SList) << endl;

	DoCombTest(0);
	DoCombTest(10);
	DoCombTest(70);
//  DoCombTest(1000);
//  DoCombTest(10000);
#ifdef BT
	DoCombTest(100000);
#ifdef VBT
	DoCombTest(1000000);
#endif
#endif

	cerr << _("Creating a priority list and adding keys:\n");
	T = newlist();
	for (i = 0; i < 30; i++) {
		fprintf(stderr, "%i ", N[i]);
		T->Insert(N[i], NULL);
	}

	fprintf(stderr, "59 54 -10\n");
	C1 = T->Insert(59, NULL);
	C2 = T->Insert(54, NULL);
	T->Insert(-10, NULL);

	cerr << _("Ok.\nList browsing...\n");
	T->Dump(cerr);
	cerr << _("Ok.\nExtract_Min + List browsing...\n");
	cerr << T->Extract_Min(Datas) << endl;
	T->Dump(cerr);
	cerr << _("Ok.\nLower_Key(-12) over 59...\n");
	T->Lower_Key(C1, -12);
	cerr << _("Ok.\nList browsing...\n");
	T->Dump(cerr);
	cerr << _("Ok.\nDelete over 54...\n");
	T->Delete(Datas, C2);
	cerr << _("Ok.\nList browsing...\n");
	T->Dump(cerr);
	cerr << "Ok.\nExtract_Min...\n";
	cerr << T->Extract_Min(Datas) << endl;
	cerr << _("Ok.\nExtracting datas...\n");
	for (i = 1; i <= 30; i++) {
		cerr << _("Minimum #") << i << " = " << (K =
							 (T->
							  Extract_Min(Datas)))
			<< endl;
		if (K != i)
			exception(1, _("Incorrect order."));
	}

	cerr << _("Ok.\n\nAll the tests were successfull\n");
	return;
}

int main(int argc, char **argv)
{
	FullTest();
}