program hachage;

	const
		N = 71; {nombre de valeurs pour la fonction de hachage}
		N_1 = N - 1;
		M = 100;{taille du tableau}
		M_1 = M - 1;

	type
		chaine = string[20];
		element = record
				nom: chaine;
				suiv: integer;
			end;
		tableau = array[0..M_1] of element;

	var
		f: text;
		s: chaine;
		t: tableau;
		Nbnoms: integer; {nombre de noms courants, initialise a 0}
		Nc: integer;{nombre de collisions, initialise a 0}


{-----------------------partie hachage-----------------------------------------------}


	function h (s: chaine): integer;
{h(s) est compris entre 0 et N-1}
		var
			i, r: integer;
	begin
		r := 0;
		for i := 1 to length(s) do
			r := ((r * (256 mod N)) mod N + ord(s[i])) mod N;
		h := r;
	end;

	procedure insertion (s: chaine);
{lors d'une insertion, une collision est visualisee}
		var
			z, i: integer;
	begin
		if Nc + N >= M then
			writeln('debordement de table', N + Nc)
		else
			begin
				i := h(s);
				if t[i].nom = '' then
					begin
						t[i].nom := s;
					end
				else
					begin
						Nc := Nc + 1;
						z := N_1 + Nc;
						t[z].nom := s;
						t[z].suiv := t[i].suiv;
						t[i].suiv := z;
						writeln(i, ' ', t[i].nom, ' -->', s); {permet de visualiser une collision lors de l'insertion}
					end;
				Nbnoms := Nbnoms + 1;
			end;
	end;

	function recherche (s: chaine): boolean;
{lors d'un appel a recherche, le chemin de recherche est affiche}
		var
			i: integer;
	begin
		i := h(s);
		while (t[i].nom <> s) and (t[i].suiv <> -1) do
			begin
				writeln(i, ' ', t[i].nom);
				i := t[i].suiv;
			end;
		writeln(i, ' ', t[i].nom);
		writeln('fin recherche');
		if (s = t[i].nom) then
			recherche := true
		else
			recherche := false;
	end;

	procedure suppression (s: chaine);
{supprime un element de la table}
		var
			i, p: integer;
			x: chaine;
	begin
		i := h(s);
		p := -1; {valeur de p lorsque la boucle qui suit n'est pas executee}
		while (t[i].nom <> s) and (t[i].suiv <> -1) do
			begin
				p := i;
				i := t[i].suiv;
			end;
		if (s = t[i].nom) then
			begin
				if p <> -1 then {suppression en milieu de liste}
					begin
						t[p].suiv := t[i].suiv;
						t[i].suiv := -1;
						t[i].nom := '';
					end
				else {suppression en tete de liste}
					begin
						if t[i].suiv = -1 then {il n' y a qu' un element dans la liste}
							t[i].nom := ''
						else {la liste comporte au moins deux elements}
							begin
								x := t[t[i].suiv].nom;
								suppression(x); {on supprime le deuxieme element et on remplace la tete de liste}
								t[i].nom := x;
							end;
					end;
				Nbnoms := Nbnoms - 1;
			end
		else {element ne figurant pas dans la liste}
			writeln('pas dans la liste');
	end;

{-----------------------partie transfert fichier--> table de hachage-----------------------}

	procedure initialisation (n: integer);
		var
			i: integer;
	begin
		for i := 0 to n do
			begin
				t[i].nom := '';
				t[i].suiv := -1;
			end;
		Nc := 0;
		Nbnoms := 0;
	end;

	procedure recopie (var f: text);
{Insere les cles du fichier dans la table de hachage}
	begin
		showtext;
		while not eof(f) do
			begin
				readln(f, s);
				insertion(s);
			end;
	end;

{------------------------partie menu-------------------------------------------------}
	procedure menu;
	begin
		writeln('taper m (menu), c (chercher), s (supprimer) , i (inserer) ou q (quitter) ');
		writeln('puis un blanc et le nom a chercher si le choix n''est pas q ou m');
	end;

	procedure action;
		var
			i: integer;
			x: chaine;
			c: char;
	begin
		menu;
		repeat
			readln(x);
			c := x[1];
			if (c <> 'q') or (c <> 'm') then
				x := omit(x, 1, 2);
			case c of
				'q': 
					;
				'm': 
					menu;
				'c': 
					if recherche(x) then
						writeln(x, ' trouve')
					else
						writeln(x, ' non trouve');
				'i': 
					if recherche(x) then
						writeln(x, ' est deja dans la table')
					else
						insertion(x);
				's': 
					suppression(x);
			end;
		until c = 'q';
	end;


begin {principal}
	reset(f, 'Noms');
	initialisation(M_1);
	writeln('VISUALISATION DES COLLISIONS');
	recopie(f);
	writeln('Nbnoms=', Nbnoms : 2, '  Nc=', Nc : 2, '  N=', N : 2);
	action;
end. {principal}