(* tra04.h5.28-29.pohja.p SJ *)

program joukkopohja;

uses tra;

(* palauttaa joukon alkioiden lukumäärän *)
(* aikavaativuus O(|A|) *)
function DSET_SIZE(A : DSET) : integer;
        var		n : integer;
                i : DSET_ITERATOR;
                x : ELEMENT;
begin
        n := 0;
        x := DSET_ANY(A, i);
        while (DSET_ITERATING(A, i)) do begin
                n := n + 1;
                x := DSET_ANOTHER(A, i)
        end;
        DSET_SIZE := n;
end; (* DSET_SIZE() *)


(* Kirjoita algoritmi DSET_DSET_MIN, joka palauttaa parametrina
   saamansa joukkojen joukon pienimmän alkion (ts. joukon, jossa on vähiten
   alkioita). Käytä hyväksesi www-sivulta löytyvän pohjan
   DSET_SIZE-operaatiota. Aikavaativuus? *)

function DSET_DSET_MIN(S : DSET) : DSET;
begin
end;
		
(* Kirjoita algoritmi joka yhdistää joukkojen joukon k joukon joukoksi.
   Algoritmisi siis saa parametrinaan joukon S, jonka alkiot ovat joukkoja
   (joiden alkioiden tyyppi ei ole kiinnostava) sekä positiivisen kokonaisluvun
   k. Algoritmisi yhdistää joukkoja pareittain kunnes joukossa S on tasan k
   joukkoa. Alkuperäisiä joukkoja ei siis pureta.  Pyrkimyksenä on, että
   jäljellejääneet k joukkoa olisivat mahdollisimman tasakokoisia. Käytä
   edellisen tehtävän SIZE ja MIN operaatioita.  Aikavaativuus? Algoritmisi ei
   tarvitse välttämättä palauttaa aivan optimaalista yhdistelmää, mieti
   kuitenkin optimaalisenkin ratkaisun periaatteita. *)

procedure yhdistele_pareittain(var S : DSET; k : integer);
begin
end; (* yhdistele_pareittain *)


procedure DSET_DSET_PRINT(S : DSET);
	var X : DSET;
        i : DSET_ITERATOR;
begin
	X := VOIDPTR_DSET_ANY(S, i);
	while (DSET_ITERATING(S, i)) do begin
		DSET_PRINT(X);
		X := VOIDPTR_DSET_ANOTHER(S, i);
	end;
end; (* DSET_DSET_PRINT() *)


(* pääohjelma *)

const	N = 10;
		K = 5;
		JM = 20;
		M = 100;

var i, j, r : integer;
	S, X : DSET;

begin

	VOIDPTR_DSET_CREATE(S);

	for i := 1 to N do begin

		INT_DSET_CREATE(X);
		r := random(JM)+1;

		for j := 1 to r do
			INT_DSET_INSERT(X, random(M));
		
		VOIDPTR_DSET_INSERT(S, X);

	end; (* for *)

	writeln('alkuperäiset:');

	DSET_DSET_PRINT(S);

	yhdistele_pareittain(S, K);

	writeln;
	writeln('uudet:');

	DSET_DSET_PRINT(S);

	while (not DSET_EMPTY(S)) do begin
		X := DSET_DSET_MIN(S);
		VOIDPTR_DSET_DELETE(S, X);
		DSET_FREE(X);
    end;

	DSET_FREE(S);

end.