Riešte nasledujúce úlohy. Vo všetkých úlohách môžete do tried dodefinovať pomocné metódy (nie nové položky). Nepoužívajte žiadne globálne premenné ani nedefinujte žiadne globálne podprogramy.

1. Cyklický jednosmerný spájaný zoznam je zadefinovaný takto:

type
  TVrchol = class
    info:string;
    next:TVrchol;
    ...
  end;
  filter = ...       // procedurálny typ
  TZoznam = class
    k:TVrchol;       // koniec zoznamu
    ...
    function daj(f:filter):string;
  end;

Napíšte metódu daj, ktorá v jednom reťazci vráti všetky vrcholy (v poradí od prvého po posledný), ktoré spĺňajú podmienku filtra. Výsledný reťazec bude obsahovať info-položky všetkých takýchto vrcholov oddelených znakom bodkočiarka. Tiež zadefinujte typ filter ako procedurálny typ - mala by to byť logická funkcia s jedným parametrom.

2. Binárny vyhľadávací strom si v každom vrchole okrem informačnej položky (info) pamätá aj počet výskytov pri zaraďovaní hodnoty do stromu (položka pocet). Strom je definovaný takto:

type
  TVrchol = class
    info,pocet:integer;
    l,p:TVrchol;
    ...
  end;
  TPole = array of TVrchol;
  TBVStrom = class
    koren:TVrchol;
    procedure vloz(i:integer);
    function viac(poc:integer):TPole;
  end;

Napíšte metódu vloz, ktorá vloží novú hodnotu do binárneho vyhľadávacieho stromu - ak takáto hodnota v strome už bola, tak len zvýši príslušné počítadlo výskytov. Nepoužite rekurzívny algoritmus. Ďalej zadefinujte metódu viac (môže byť rekurzívna), ktorá v dynamickom poli vráti všetky tie vrcholy stromu, ktorých počet výskytov bol aspoň poc.

3. Lexikografický strom obsahuje nejaký anglicko-slovenský slovník: ak sa nejaké slovo v strome nachádza, tak info príslušného vrcholu obsahuje slovenský preklad tohoto slova. (Hovoríme, že sa nejaké slovo v strome nachádza, ak existuje cesta od koreňa, ktorá prechádza po hranách stromu podľa príslušných písmen slova).

type
  TVrchol = class
    info:string;
    a:array['a'..'z'] of TVrchol;
    ...
  end;
  TLexStrom = class
    s:TVrchol;
    function preloz(w:string):string;
  end;

Napíšte funkciu, ktorá preloží slovenské slovo na anglické, t.j. nájde vrchol s info-položkou s daným reťazcom a vráti cestu - postupnosť písmen k tomuto vrcholu. Ak takéto slovenské slovo v strome nie je, funkcia vráti prázdny reťazec.

4. Orientovaný graf je popísaný týmito triedami:

type
  TVrchol = class
    info:integer;
    sused:array of TVrchol;
    ...
  end;
  TGraf = class
    vrchol:array of TVrchol;
    constructor Create(stream:Tstream);
    function zisti:boolean;     // či je párny počet vrcholov párneho stupňa
    ...
  end;

 Zadefinujte konštruktor, ktorý vytvorí daný graf z otvoreného údajového prúdu (stream). Súbor má takúto štruktúru:

• každý vrchol je zapísaný v jednom bloku údajov
• blok začína hodnotou info-položky vrcholu (4 bajty), ktorá je pre každý vrchol jednoznačná
• nasleduje počet susedov vrcholu (4 bajty)
• ďalej je v bloku pre každého suseda jeho info-položka (4 bajty)

Predpokladajte, že súbor je korektný. Potom napíšte aj metódu zisti, ktorá vráti true, aký je v grafe počet vrcholov párneho stupňa párny.

// 1. príklad
type
  TVrchol = class
    info:string;
    next:TVrchol;
  end;
  filter = function(v:TVrchol):boolean;       // procedurálny typ
  TZoznam = class
    k:TVrchol;                                // koniec zoznamu
    function daj(f:filter):string;
  end;

function TZoznam.daj(f:filter):string;
var
  p:TVrchol;
begin
  Result:=''; if k=nil then exit;
  p:=k;
  repeat
    p:=p.next;
    if f(p) then
      if Result='' then Result:=p.info
      else Result:=Result+';'+p.info;
  until p=k;
end;

// 2. príklad
type
  TVrchol = class
    info,pocet:integer;
    l,p:TVrchol;
  end;
  TPole = array of TVrchol;
  TBVStrom = class
    koren:TVrchol;
    procedure vloz(i:integer);
    function viac(poc:integer):TPole;
  end;

procedure TBVStrom.vloz(i:integer);
var
  pred,s:TVrchol;
begin
  s:=koren; pred:=nil;
  while (s<>nil) and (s.info<>i) do begin
    pred:=s;
    if s.info>i then s:=s.l
    else s:=s.p;
  end;
  if s=nil then begin
    s:=TVrchol.Create; s.info:=i; s.pocet:=1;
    if pred=nil then koren:=s
    else if pred.info>i then pred.l:=s
    else pred.p:=s;
  end
  else inc(s.pocet)
end;

function TBVStrom.viac(poc:integer):TPole;
  procedure viac1(s:TVrchol);
  begin
    if s<>nil then begin
      if s.pocet>=poc then begin
        setlength(Result,length(Result)+1);
        Result[high(Result)]:=s;
      end;
      viac1(s.l);
      viac1(s.p);
    end;
  end;
begin
  Result:=nil;
  viac1(koren);
end;

// 3. príklad
type
  TVrchol = class
    info:string;
    a:array['a'..'z'] of TVrchol;
    function preloz1(w1,w2:string):string;
  end;
  TLexStrom = class
    s:TVrchol;
    function preloz(w:string):string;
  end;

function TVrchol.preloz1(w1,w2:string):string;
var
  c:char;
begin
  Result:='';
  if w1=info then Result:=w2
  else
    for c:='a' to 'z' do
      if a[c]<>nil then begin
        Result:=a[c].preloz1(w1,w2+c);
        if Result<>'' then exit;
      end;
end;

function TLexStrom.preloz(w:string):string;
begin
  if s=nil then Result:=''
  else Result:=s.preloz1(w,'');
end;

// 4. príklad
type
  TVrchol = class
    info:integer;
    sused:array of TVrchol;
    procedure pridajSuseda(v:TVrchol);
  end;

  TGraf = class
    vrchol:array of TVrchol;
    constructor Create(stream:TStream);
    function hladajVrchol(info:integer):TVrchol;
    function zisti:boolean;
  end;

procedure TVrchol.pridajSuseda(v:TVrchol);
begin
  if v=nil then exit;
  setlength(sused,length(sused)+1);
  sused[high(sused)]:=v;
end;

constructor TGraf.Create(stream:TStream);
var
  i,j,k:integer;
begin
  stream.position:=0;
  while stream.position<stream.size do begin
    setlength(vrchol,length(vrchol)+1);
    vrchol[high(vrchol)]:=TVrchol.Create;
    stream.read(vrchol[high(vrchol)].info,4);
    stream.read(i,4);
    stream.position:=stream.position+4*i;
  end;
  stream.position:=0; i:=0;
  while stream.position<stream.size do begin
    stream.read(j,4);
    stream.read(j,4);
    while j>0 do begin
      stream.read(k,4);
      vrchol[i].pridajSuseda(hladajVrchol(k));
      dec(j);
    end;
    inc(i);
  end;
end;

function TGraf.hladajVrchol(info:integer):TVrchol;
var
  i:integer;
begin
  for i:=0 to high(vrchol) do
    if vrchol[i].info=info then begin
      Result:=vrchol[i]; exit;
    end;
  Result:=nil;
end;

function TGraf.zisti:boolean;
var
  i:integer;
begin
  Result:=true;
  for i:=0 to high(vrchol) do
    if not odd(length(vrchol[i].sused)) then
      Result:=not Result;
end;