(* tra04.h10.58-59.p SJ *)

program kasalajittelu;

(* tyypit *)

const MAX = 10;
type element = string[20];
     taulu = array[1..MAX] of element;
     BTREE = taulu;
     PRIQUEUE = BTREE;
     BTREE_NODE = integer;

(* haku BTREEsta, hieman tarpeeton *)
function RETRIEVE(var T : BTREE; n : BTREE_NODE) : element;
begin
	RETRIEVE := T[n]
end;

(* käänteinen precedes merkkijonoille *)
function precedes(a, b : element) : boolean;
begin
	precedes := a > b
end;

(* tehtävä 58 *)

function ROOT(var T : BTREE) : BTREE_NODE;
begin
end;

function PARENT(var T : BTREE; n : BTREE_NODE) : BTREE_NODE;
begin
end;

function LEFT_CHILD(var T : BTREE; n : BTREE_NODE) : BTREE_NODE;
begin
end;

function RIGHT_CHILD(var T : BTREE; n : BTREE_NODE) : BTREE_NODE;
begin
end;

procedure SWAP(var T : BTREE; a, b : BTREE_NODE);
begin
end;

(* tehtävä 59 *)

procedure jarjestaalas(var T : BTREE; maara : integer);
begin
end;


procedure jarjestaylos(var T : BTREE; maara : integer);
begin
end;


procedure PRIQ_INSERT(var T : PRIQUEUE; var maara : integer; a : element);
begin
	maara := maara + 1;
	T[maara] := a;
	jarjestaylos(T, maara)
end;

function PRIQ_DELETEMAX(var T : PRIQUEUE; var maara : integer) : element;
begin
	SWAP(T, ROOT(T), maara);
	maara := maara - 1;
	jarjestaalas(T, maara);
	PRIQ_DELETEMAX := RETRIEVE(T, maara+1);
end;
	

procedure kasalajittelu(var A : taulu; koko : integer);
var i, maara : integer;
begin
	maara := 0;
	for i := 1 to koko do
		PRIQ_INSERT(A, maara, A[i]);
		(* vaihtoehtoisesti:
		jarjestaylos(A, i); *)
		
	for i := koko downto 1 do
		A[i] := PRIQ_DELETEMAX(A, maara);
		(* vaihtoehtoisesti :
		SWAP(1, i, A);
		jarjestaylos(A, i); *)

end; (* kasalajittelu *)


(* pääohjelma kokeilua varten *)
var alkiot : taulu;
    i, j, N : integer;
	a : element;

begin (* pääohjelma *)

	N := MAX;

	for i := 1 to N do begin
		a := '';
		for j := 1 to 5 do
			a := a + chr(ord('a') + random(20));
		alkiot[i] := a;
	end;
	
	for i := 1 to N do
		write(alkiot[i], ' ');
	writeln;
	
	kasalajittelu(alkiot, N);

	for i := 1 to N do
		write(alkiot[i], ' ');
	writeln;

end.