unit lignes;
(* Gestionnaire	de lignes. *)

(* Les lignes d'un programme sont stock‚s sous la forme d'une liste chain‚e
 * dont la racine est la variable globale programme.  Mais les lignes sont
 * aussi dans une table de hashage pour faciliter les recherches.  En effet,
 * la structure RECORD_LIGNE contient deux pointeurs vers deux autres
 * structures de type LIGNE.  Le premier, prochain, est vers la prochaine
 * ligne du programme, et ce pour profiter, lors de l'execution, de la nature
 * "lin‚aire" d'un programme Basic.  L'autre pointeur, lien, sert … chainer
 * la table de hashage.  Cette derniŠre permet de trouver une ligne
 * rapidement lors d'un branchement.  De plus, il y a une variable globale
 * priv‚e ligne_precedente pour faciliter la cr‚ation de ligne, en effet on
 * ‚crit en g‚n‚ral s‚quentiellement son programme, cela permet d'ins‚rer
 * rapidement la ligne dans la liste chain‚e.  Par contre pour la destruction
 * d'une ligne, on est oblig‚e de faire une recherche lin‚aire sur tout le
 * programme, mais cela arrive moins souvent.
 *)

interface

type	LIGNE	= ^RECORD_LIGNE;

	RECORD_LIGNE = 	record
				numero_ligne	: word;
				chaine		: string;
				prochain	: LIGNE;
				lien		: LIGNE;
			end;

var	programme	: LIGNE;

procedure 	initialise_gestionnaire_lignes;
procedure	termine_gestionnaire_lignes;

function 	cree_ligne (numero_ligne : word; chaine	: string) : LIGNE;
function	cherche_ligne (numero_ligne : word) : LIGNE;
procedure 	detruit_ligne (l : LIGNE);

implementation

uses interpreteur;

const 	VALEUR_HASHAGE 	= 89;

var     initialise 		: boolean;
	table_hashage		: array	[0 .. VALEUR_HASHAGE - 1] of LIGNE;
	ligne_precedente	: LIGNE;

procedure initialise_gestionnaire_lignes;
(* Initialise le gestionnaire de lignes	en mettant … nil les listes chain‚es,
 * et en initialisant programme et ligne_precedente … nil.
 *)

var	i 	: integer;

begin
	programme := nil;
	initialise := true;
	for i := 0 to VALEUR_HASHAGE - 1 do
		table_hashage[i] := nil;
	ligne_precedente := nil;
end;

procedure termine_gestionnaire_lignes;
(* Termine le gestionnaire de lignes en d‚truisant toutes les lignes, cela
 * en utilisant la liste chain‚e programme, et initialise la table de hashage
 * … nil.
 *)

var	l               : LIGNE;
	prochain	: LIGNE;
	i		: integer;

begin
	if not initialise then begin
		writeln('Erreur Interne: ',
			'Gestionnaire de lignes non initialis‚!');
		halt;
	end else begin
		l := programme;
		while l <> nil do begin
			prochain := l^.prochain;
			dispose(l);
			l := prochain;
		end;
		programme := nil;
		initialise := false;
		for i := 0 to VALEUR_HASHAGE - 1 do
			table_hashage[i] := nil;
		ligne_precedente := nil;
	end;
end;

function hash (numero_ligne : word) : word;
(* La fonction de hashage est numero_ligne modulo VALEUR_HASHAGE. *)

begin
	hash :=	numero_ligne mod VALEUR_HASHAGE;
end;

function cree_ligne (numero_ligne : word; chaine : string) : LIGNE;
(* Cr‚e	une ligne, l'insŠre dans la liste chain‚e programme et dans la table
 * de hashage, et renvoie un pointeur sur sa structure de controle, qui est
 * nil s'il n'y a pas assez de m‚moire.  Aucune v‚rification n'est faite pour
 * savoir si cette ligne est d‚j… dans la table	de hashage.
 *)

procedure insere_dans_programme (numero_ligne : word; l : LIGNE);
(* InsŠre l dans la liste chain‚e programme. *)

procedure methode_brute (numero_ligne : word; l : LIGNE);
(* M‚thode brute d'insertion de l dans la liste chain‚e programme. *)

var	precedent	: LIGNE;
	courant		: LIGNE;

begin
	if numero_ligne < programme^.numero_ligne then begin
		l^.prochain := programme;
		programme := l;
	end else begin
		precedent := programme;
		courant	:= programme^.prochain;
		while (courant <> nil)
		and (numero_ligne < courant^.numero_ligne ) do begin
			precedent := courant;
			courant	:= courant^.prochain;
		end;
		if courant = nil then begin
			precedent^.prochain := l;
			l^.prochain := nil;
		end else begin
			l^.prochain := precedent^.prochain;
			precedent^.prochain := l;
		end;
	end;
	ligne_precedente := l;
end;

var	numero 	: word;

begin
	if programme = nil then begin
		l^.prochain := nil;
		programme := l;
		ligne_precedente := l;
	end else begin
		if numero_ligne < ligne_precedente^.numero_ligne then
			methode_brute(numero_ligne, l)
		else if ligne_precedente^.prochain = nil then begin
			ligne_precedente^.prochain := l;
			l^.prochain := nil;
			ligne_precedente := l;
		end else begin
			numero := ligne_precedente^.prochain^.numero_ligne;
			if numero_ligne > numero then
				methode_brute(numero_ligne, l)
			else begin
				l^.prochain := ligne_precedente^.prochain;
				ligne_precedente^.prochain := l;
				ligne_precedente := l;
			end;
		end;
	end;
end;

var	l	: LIGNE;
	h	: word;

begin
	if maxavail < sizeof(RECORD_LIGNE) then	begin
		erreur_interpreteur := PAS_ASSEZ_MEMOIRE;
		cree_ligne := nil
	end else begin
		new(l);
		l^.numero_ligne	:= numero_ligne;
		l^.chaine := chaine;
		insere_dans_programme (numero_ligne, l);
		h := hash(numero_ligne);
		l^.lien	:= table_hashage[h];
		table_hashage[h] := l;
		cree_ligne := l;
	end;
end;

function cherche_ligne (numero_ligne : word) : LIGNE;
(* Cherche si la ligne numero_ligne est dans la table de hashage, renvoie un
 * pointeur sur	sa structure de	controle si oui, ou nil	sinon.
 *)

var	l	: LIGNE;

begin
	l := table_hashage[hash(numero_ligne)];
	while (l <> nil) and (l^.numero_ligne <> numero_ligne) do
		l := l^.lien;
	cherche_ligne := l;
end;

procedure detruit_ligne	(l : LIGNE);
(* Detruit la ligne l, c'est … dire l'enlŠve de la liste chain‚e programme,
 * l'enlŠve de la table de hashage, et d‚salloue la m‚moire.  Les pr‚cautions
 * sont prises pour les cas o— l est nil, o— la ligne en question n'est pas
 * dans le programme, et o— elle n'est pas dans la table de hashage.  Le
 * temps d'execution est proportionnel … la taille du programme, mais mˆme
 * pour un programme relativement gros (10000 lignes par exemple), le temps
 * de r‚ponse devrait ˆtre acceptable.
 *)

procedure enleve_de_programme (l : LIGNE);
(* EnlŠve l de la liste chain‚e programme si n‚cessaire. *)

var     precedent	: LIGNE;
	courant		: LIGNE;

begin
	if programme <> nil then begin
		if programme = l then
			programme := programme^.prochain
		else begin
			precedent := programme;
			courant	:= programme^.prochain;
			while (courant <> nil) and (courant <> l) do begin
				precedent := courant;
				courant	:= courant^.prochain;
			end;
			if courant <> nil then
				precedent^.prochain := l^.prochain;
		end;
	end;
end;

procedure enleve_de_table_hashage (l : LIGNE);
(* EnlŠve l de la table de hashage si n‚cessaire. *)

var     h 		: word;
	precedent	: LIGNE;
	courant		: LIGNE;

begin
	h := hash(l^.numero_ligne);
	if table_hashage[h] <> nil then begin
		if table_hashage[h] = l then
			table_hashage[h] := l^.lien
		else begin
			precedent := table_hashage[h];
			courant	:= table_hashage[h]^.lien;
			while (courant <> nil) and (courant <> l) do begin
				precedent := courant;
				courant	:= courant^.lien;
			end;
			if courant <> nil then
				precedent^.lien := l^.lien;
		end;
	end;
end;

begin
	if l <> nil then begin
		enleve_de_programme(l);
		enleve_de_table_hashage(l);
		dispose(l);
	end;
end;

begin
	initialise := false;
end.