path: root/src/test.cc

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <termios.h>
#include <string.h>
#include "config.h"
#include "BHeap.h"
#include "FHeap.h"
#include "BinHeap.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,
};

int method = -1;
FILE *input;
struct termios initial_settings, new_settings;

char *method_names[] = {
	N_("0 - Binary Heap"),
	N_("1 - Binomial Heap"),
	N_("2 - Fibonacci Heap"),
	N_("3 - Sorted chained list"),
	NULL
};

char *menu[] = {
	N_("a - Add a key into the priority list"),
	N_("c - Change priority list type"),
	N_("d - Delete a Key from the priority list"),
	N_("e - Extract Min onto the priority list"),
	N_("l - Lower Key onto a key of the priority list"),
	N_("p - Print the current priority list on the screen"),
	N_("r - Remove the whole priority list"),
	N_("t - Test the priority list algorithms"),
	N_("q - Quit"),
	NULL
};

void exception(int e, char *msg)
{
	fprintf(stderr, "%s\n", msg);
	tcsetattr(fileno(input), TCSANOW, &initial_settings);
	exit(-1);
}

PriorityList *newlist(int method)
{
	switch (method) {
	case 0:
		return new BinHeap;
		break;
	case 1:
		return new BHeap;
		break;
	case 2:
		return new FHeap;
		break;
	case 3:
		return new PLList;
		break;
	default:
		cerr << _("Unknow priority list type: ") << method << endl;
		exception(1, "Exitting");
		return NULL;
	}
}

void DoCombTest(int method, 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(method);
	for (i = 1; i <= number; i++) {
		T->Insert(rand() % 100, NULL);
	}
	cerr << _("Ok.\nDeleting the list...");
	oK = P_INFINITY;
	for (i = number; i >= 1; i--) {
		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(int method)
{
	PriorityList *T;
	Datas_t Datas;
	Cell C1, C2, C3 = NULL;
	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 PLList header    : ") << sizeof(PLList) << endl;
	cerr << _("Size of a CList cell       : ") << sizeof(CList) << endl;
	cerr << _("Size of a SList cell       : ") << sizeof(SList) << endl;
	cerr << _("Size of a BinHeap header   : ") << sizeof(BinHeap) << endl;
	cerr << _("Size of a BinHeap cell     : ") << sizeof(binheap_t) << endl;

	DoCombTest(method, 0);
	DoCombTest(method, 30);
	DoCombTest(method, 70);
	DoCombTest(method, 1000);

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

	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(0) over 59...\n");
	T->Lower_Key(C1, 0);
	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.\nLower_Key(-12) over 30...\n");
	T->Lower_Key(C3, -12);
	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 = 0; i <= 29; 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;
}

void Usage(void)
{
	cerr << _("Usage: testTas [type]\n");
	exit(-1);
}

int getchoice(char *greet, char *choices[], FILE * in)
{
	int chosen = 0;
	int selected;
	char **option;

	do {
		cerr << _("Choice: ") << greet << endl;
		option = choices;
		while (*option) {
			cerr << *(option++) << endl;
		}
		do {
			selected = fgetc(in);
		} while (selected == '\n' || selected == '\r');
		option = choices;
		while (*option) {
			if (selected == *option[0]) {
				chosen = 1;
				break;
			}
			option++;
		}
		if (!chosen) {
			cerr << _("Incorrect choice, select again\n");
		}
	} while (!chosen);
	return selected;
}

char **buildslots(PriorityList * T, Cell * Cells, char option)
{
	char **slots, **r, temp[BUFSIZ];
	int i;

	r = slots = (char **) malloc(12 * sizeof(char *));

	for (i = 0; i < 10; i++) {
		if (Cells[i] || option) {
			if (Cells[i]) {
				sprintf(temp, _("%i - Key: %i"), i, T->ReadKey(Cells[i]));
			} else {
				sprintf(temp, _("%i - Empty slot"), i);
			}
			*(slots++) = strdup(temp);
		}
	}

	if (option)
		*(slots++) = strdup(_("n - Don't store"));
	*(slots++) = strdup(_("c - Cancel"));

	*slots = NULL;

	return r;

}

void freeslots(char **slots)
{
	char **t;

	for (t = slots; *t; t++)
		free(*t);
	free(slots);
}

void initterm(FILE * in) {
	tcgetattr(fileno(input), &initial_settings);
	new_settings = initial_settings;
	new_settings.c_lflag &= ~ICANON;
	new_settings.c_lflag &= ~ECHO;
	new_settings.c_cc[VMIN] = 1;
	new_settings.c_cc[VTIME] = 0;
	new_settings.c_lflag &= ~ISIG;

	if (tcsetattr(fileno(input), TCSANOW, &new_settings) != 0) {
		cerr << _("could not set attributes\n");
		exit(-1);
	}

}

void clearterm(FILE * in) {
	tcsetattr(fileno(input), TCSANOW, &initial_settings);
}

int main(int argc, char **argv)
{
	char choice = 0, **slots;
	PriorityList *T, * Temp;
	Datas_t Datas;
	Cell Cells[10], M;
	int i;
	Key_t Key;

	/*
	   Lecture des arguments de la ligne de commande.
	 */

	while (--argc) {
		argv++;
		if ((strlen(*argv) != 1) || (((*argv)[0] < '0' || (*argv)[0] > '3'))) {
			cerr << _("Unknow priority list type: ") << *argv << endl;
			Usage();
		}
		if (method != -1) {
			cerr << _("Extra command: ") << *argv << endl;
			Usage();
		}
		method = (*argv)[0] - '0';
	}
	
	if (method == -1)
		method = 0;

	/*
	   Initialisation du terminal.
	 */

	if (!isatty(fileno(stdout))) {
		cerr << _("You are not a terminal, Ok.\n");
	}

	input = fopen("/dev/tty", "r");
	if (!input) {
		cerr << _("Unable to open /dev/tty\n");
		exit(1);
	}
	
	initterm(input);
	
	/*
	   Debut du programme de test.
	 */

	for (i = 0; i < 10; i++) {
		Cells[i] = NULL;
	}

	T = newlist(method);

	do {
		cerr << "\n\n\n\n";
		cerr << _("Priority list type: ") << method_names[method] << endl;
		choice = getchoice(_("Please select an action"), menu, input);
		cerr << _("You have chosen: ") << choice << "\n\n";
		switch (choice) {
		case 'a':	// Ajout d'une clef.
			slots = buildslots(T, Cells, 1);
			choice = getchoice(_("Please select a slot to save the cell"), slots, input);
			if (choice == 'c') {
				freeslots(slots);
				break;
			}
			if (choice == 'n') {
				choice = -1;
			} else {
				choice -= '0';
			}
			cerr << _("Please type in a key to add") << endl;
			clearterm(input);
			cin >> Key;
			initterm(input);
			if (choice == -1) {
				T->Insert(Key, NULL);
			} else {
				Cells[choice] = T->Insert(Key, NULL);
			}
			freeslots(slots);
			break;
		case 'c':	// Changement du type.
			Temp = T;
			cerr << "\n\n\n\n";
			method = getchoice(_("Please select a priority list type"), method_names, input) - '0';
			T = newlist(method);
			T->Union(Temp);
			delete Temp;
			for (i = 0; i < 10; i++) {
				Cells[i] = NULL;
			}
			break;
		case 'd':	// Effacement d'une clef.
			slots = buildslots(T, Cells, 0);
			choice = getchoice(_("Please select a key to delete"), slots, input);
			if (choice == 'c') {
				freeslots(slots);
				break;
			}
			choice -= '0';
			cerr << _("Delete result: ") << T->Delete(Datas, Cells[choice]);
			Cells[choice] = NULL;
			freeslots(slots);
			break;
		case 'e':	// Extract Min.
			M = T->Min();
			for (i = 0; i < 10; i++) {
				if (Cells[i] == M) {
					Cells[i] = NULL;
					break;
				}
			}
			cerr << _("Extract Min result: ") << T->Extract_Min(Datas);
			break;
		case 'l':	// Lower Key.
			slots = buildslots(T, Cells, 0);
			choice = getchoice(_("Please select a key to lower"), slots, input);
			if (choice == 'c') {
				freeslots(slots);
				break;
			}
			choice -= '0';
			cerr << _("Please type in the new key") << endl;
			clearterm(input);
			cin >> Key;
			initterm(input);
			cerr << _("Lower key result: ") << T->Lower_Key(Cells[choice], Key) ? _("True") : _("False");
			freeslots(slots);
			break;
		case 'p':	// Print
			T->Dump(cerr);
			break;
		case 'r':	// Delete
			delete T;
			T = newlist(method);
			break;
		case 't':	// Test
			FullTest(method);
			break;
		}
	} while (choice != 'q');

	clearterm(input);
	exit(0);
}