{  ==============                                                              }
{  KSP 15. rocnik    1511: O recidivistoch            Copyright (c) Jan Mojzis }
{  ==============                                                              }
{  Zadanie:                                                                    }
{  Nepokoje v nasich vazniciach narastaju do neusosnych medzi. A to nielen preto,}
{  ze su preplnene, ale aj preto, ze recidivistom su vzdy pridelene nove cisla a }
{  nie tie ich, na kt. si uz zvykli. Vo vazniciach, kde sa vsetci oslovuju     }
{  cislami, je tento fakt velmi nevytany.                                      }
{  Vsetko vyriesil novy projekt Alcatraz II. Ak pride do tejto vaznice dalsi   }
{  vazen, dozorcovia zadaju do pocitaca jeho meno a priezvisko a program vypise}
{  NOVY, ak tu este predtym vazneny nebol, alebo RECIDIVISTA, ak neprisiel po  }
{  prvy raz. Program tiez vypise cislo vazna. Novemu vaznovi moze program      }
{  priradit lubovolne cislo, ktore avsak nema iny vazen, no recidivistovi musi }
{  priradit cislo z jeho predchadzajuceho pobytu. Mozno predpokladat ze cisla su}
{  priradovane iba uvedenym programom.                                         }
{  ULOHA:                                                                      }
{      Vytvorte horeuvedeny program tak, aby fungoval co najrychlejsie a pre   }
{  co najvacsie mnozstva vaznov. Program bude uvedeny do prevadzky zaroven s   }
{  otvorenim vaznice, takze vaznica je na zaciatku prazdna. Kedze Alcatraz II  }
{  nikdy neprestane fungovat, mal by aj vas program fungovat v nekonecnej slucke.}
{  Mena vaznov su zlozene z velkych pismen abecedy a z medzier.                }
{      Priklad vstupu a vystupu:                                               }
{              ? LEX LUTHOR                                                    }
{                NOVY 3560                                                     }
{              ? JAMES BOND                                                    }
{              NOVY 007                                                        }
{              ? LEX LUTHOR                                                    }
{              RECIDIVISTA 3560                                                }
{              ? LOIS LANE                                                     }
{              NOVY 806070                                                     }
{              ? JAMES BOND                                                    }
{              RECIDIVISTA 007                                                 }
{                                                                              }
{                                                                              }
{      ----------------------------------------------------------------------  }
{    Lexikograficky strom pre rychle vyhladavanie.                             }
{    Ovladanie je ESC pre exit a ? klavesa pre vyhladavanie. Program si vie    }
{    aj zapamatat novopecenych recidivistov, ktorych si hned poznamena do      }
{    stromu, tabulky aj do suboru cez append.                                  }
{    Subor je obycajny textovy. Da sa premazat, ale nechal som dva prve riadky }
{    pre hlavicku Alcatraz II. Preto by mali byt vzdy 2 riadky zhora (program  }
{    automaticky preskakuje 2 riadky).                                         }
{    Program pouziva binarny strom, a sice dva. Jeden sluzi pre evidovanie     }
{    vaznov, ten je lexikograficky s vetvami nazvov 'a'..'z' a velke pismena sa}
{    osetruju hned na zaciatku ansilowercase-om. Druhy je strom cisielkovy, je }
{    naprosto rovnaky, len s mensim poctom vetiev. Podstatna je len platna cesta.}
{                                                                              }
{    STROM Vaznov (napriklad):                Strom Cisiel vaznov (napriklad): }
{    * * / *            * \ *  *                 * * /  *           * \*       }
{    *[a] = -1          *[c] = 7                 * [0] = nil?*      * [7]=nil?*}
{    (neexistuje)*        (1 index v tab)*          *  * *             * ***   }
{    Spolu 26 vetiev v kazdom uzle                   tu je vetiev 10           }
{                                                                              }
{    Tabulka cisiel vaznov:                                                    }
{    [0] 313                                                                   }
{    [7] 007                                                                   }
{    ...                                                                       }
{    Pri vkladani do cisloveho stromu sa len vytvaraju nove vetvy s nil podvetvami.}
{    Je to pre rychle vyhladavanie.                                            }
{    Pri vkladani do pismenkoveho stromu sa vytvaraju nove vetvy takisto, ale kazda }
{    novovytvorena vetva sa nastavi na -1 pre cislo indexu. Okrem poslednej vetvy,  }
{    kde uz sa vklada priamo cislo.                                            }
{                                                                              }
{    Toto cislo indexu je velmi dolezite, lebo "Karol Koubek" je recidivista.  }
{    Dozorca chce zistit, ci novoprijaty Karol Koube je uz v databaze. V beznom}
{    pripade ak by sme neskumali korektnost pomocou -1, by sme presli vetvami az po }
{    ..ek a zistime ze cesta je platna, vazen teda existuje. To je chyba.       }
{    Pre istotu som aj do cisloveho stromu dal -1 validator. Keby sa cesta skoncila }
{    predcasne a cislo by nemalo existovat. Napriklad pri generovani noveho cisla   }
{    pre noveho recidivistu, stary je zapisany ako 666, vytvori sa nahodou 666.     }
{    Toto sa uz nestane.                                                       }
{                                                                              }
{    Nesmu byt dvaja rovnaki recidivisti a dve rovnake cisla.                  }
{                                                                              }
{    Dolezite je este spomenut ze pre tabulku skutocnych cisiel vaznov, pouzivam}
{    hlavny index velkost_pola_recidivistov, ktory sluzi jednak ako posledna   }
{    aktualna velkost, a zaroven ako hodnota, ktora sa uklada do stromu vaznov.}
{                                                                              }
{    Pohyb v pismenkovom strome prebieha tak, ze sa retazec rozdeli na znaky, a}
{    zistuje sa len to, ci existuje vetva oznacena ako znak[z].                }
{    Pohyb v cisielkovom strome je rovnaky, pouziva vetvy oznacene ako 'a'..'z'.}
{    Mal som aj lepsie riesenie:                                               }
{    z ciselka berieme poslednu cifierku najpr, teda z 1567 si zoberieme       }
{    7 pomocou 1567 mod 10. Potom cisielko este zmensime div 10. Vysledok zapiseme }
{    a nastavime novu vetvu. Ale nesplnalo to kriteria pre 007.                }
{                                                                              }
{    Sofistikovane je prevedene zlucenie stromu cisielok a stromu vaznov. A to tak, }
{    ze vo vetve vaznov sa okrem mena eviduje cislo, ale nie konkretne instantne }
{    cislo, ale len poradove cislo indexu na lokalnej tabulke vaznov. Potom      }
{    konkretne cislo vazna dostaneme, ked pouzieme toto "cislo" v indexe tabulky,}
{    a tym ho spravne rozlustime. Pole je array of string, a je dynamicke, pre   }
{    rozny pocet vaznov a pre setrenie pamate. Jediny sposob ktory mi napadol pre}
{    okamzite zistenie ci novy vazen sa nekryje s inym vaznom (ciselne).         }
{                                                                                }
{    Z cisielkoveho stromu je jedno ci cislo berieme v strome od predu alebo od  }
{    zadu. Podstatne je len to, aby sme vzdy zvolili rovnaky postup.             }
{                                                                                }
{    V zadani som si vsimol aj cislo 007. Rozhodol som sa  teda, pre zjednodusenie }
{    vetvy urcit ako typ char.                                                   }
{                                                                                }
{    - Ostatne veci su uz prijemne, zlozitost programu je O^n, priamo umerna poctu }
{    pismeniek a cisielok.                                                       }
{                                                                                }
{    POZNAMKA:                                                                   }
{           CRT_EFD nie je sucastou tohto riesenia. Kniznicu CRT_EFD pre pracu s }
{           konzolovymi vypismi mozete stiahnut napriklad na:                    }
{           http://www.stano.wz.sk/index.php?id=8                                }
{                                                                                }
{                                                                              }
{  Author: (c) 2007 Jan Mojzis                                                 }
{  Date  : 06.07.2008                                     http://www.trsek.com }

program lexikograficky_strom;

{Program na simulovanie lexikografickeho stromu. Jeho vytvaranie a pouzitie.}

const subor = 'recidivisti.dat';
{------------ HLAVNY STROM VAZNOV --------------}
type m_basisti=^atom_b;
     atom_b=record
      cislo : integer; { recidivistovo cislo; }
      znak:array['a'..'z'] of m_basisti
     end;
{--------- HLAVNY STROM PRE CISLA --------------}
type c_basisti = ^atom_bc;
      atom_bc = record
      valid : integer;
       ch : array['0'..'9'] of c_basisti
      end;

var BASISTI:m_basisti;
    BAS_CISLA : c_basisti;
    j:integer;
    file_append : text;
    nove_cislo : integer = -1;
    recidivista:string  = '';
    cislo:integer = 0;
    cislarecidivistov : array of string;
    velkost_pola_recidivistov : integer = 0;
    volby : char = #0;
    prazdny : boolean = false;

procedure inicializuj(var s:m_basisti);
{Vytvorime si novy uzol a nastavime vsetky vetvy na prazdontu NIL}
var z:'a'..'z';
begin
 new(s);
 for z:='a' to 'z' do s^.znak[z]:=nil;
 s^.cislo:=-1;
end;

procedure inicializuj_strom_cisel(var rec_n:c_basisti);
{To iste pre cisielkovy strom}
var z:'0'..'9';
begin
 new(rec_n);
 for z:='0' to '9' do rec_n^.ch[z]:=nil;
 rec_n^.valid:=-1;
end;

procedure VlozBasistu(var s:m_basisti;slovo:string;cislo:integer);
{To ci vazen v databaze uz nahodou je, je nam nepotrebne, lebo to zistuje f. HladajBasistu}
var i:integer;
    z:'a'..'z';
    p:m_basisti;
begin
 slovo := AnsiLowerCase(slovo);
 p:=s;
 for i:=1 to length(slovo) do
 begin
  if(p^.znak[slovo[i]]=nil) then
  begin
   new(p^.znak[slovo[i]]);
   p:=p^.znak[slovo[i]];
   for z:='a' to 'z' do p^.znak[z]:=nil;
   p^.cislo:=-1;
  end
  else  p:=p^.znak[slovo[i]]
 end;
 p^.cislo:=cislo;
end;
procedure VlozCislo(var s:c_basisti;cislo:string);
var i:integer;
    z:'0'..'9';
    p:c_basisti;
    konci : boolean;
begin
 p:=s;
konci := false;
i:=0;
 for i:=1 to length(cislo) do
 begin
  if(p^.ch[cislo[i]]=nil) then
 begin
   new(p^.ch[cislo[i]]);
   p:=p^.ch[cislo[i]];
   for z:='0' to '9' do p^.ch[z]:=nil;
   p^.valid:=-1;
  end
  else  p:=p^.ch[cislo[i]];
 end;
p^.valid := 1;
end;


procedure HladajBasistu(var s:m_basisti;slovo:string; var cislo:integer);
var p:m_basisti;
    i:integer;
    stav:boolean;
begin
 stav:=true;
 p:=s;
 i:=1;
 slovo := AnsiLowerCase(slovo);
 if(slovo[1]=' ') then stav:=false
 else
  if(p=nil) then stav:=false
  else
   repeat
    if p^.znak[slovo[i]]<>nil then
    begin
     p:=p^.znak[slovo[i]];
     inc(i)
    end
    else  stav:=false;
   until (stav=false)or(i=length(slovo)+1);               { overenie identity }
  if (stav=false)and(p^.cislo=-1) then cislo:=-1
  else if (stav=true)and(p^.cislo<>-1) then cislo:=p^.cislo
   else cislo:=-1;
end;
function HladajCislo(var s:c_basisti; cislo:string) : integer;
var p:c_basisti;
    i:integer;
    stav:boolean;
    konci : boolean;
begin
 stav:=true;
 p:=s;
 i:=1;
 if(cislo[1]=' ') then stav:=false
 else
  if(p=nil) then stav:=false
  else
   repeat
    if p^.ch[cislo[i]]<>nil then
    begin
     p:=p^.ch[cislo[i]];
     inc(i)
    end
    else  stav:=false;
   until (stav=false)or(i=length(cislo)+1);                 { overovacie podmienky }
  if (stav=false)and(p^.valid=-1) then result:=-1           { antiduplicitne cisla }
  else if (stav=true)and(p^.valid<>-1) then result:=p^.valid
   else result:=-1;end;


procedure napln_mena(var s:m_basisti; slovnik:string);
var f:text;
    recidivista:string;
    i:byte;
    cislo : string;
    rez : integer;
begin
cislo:='';
rez:=-1;
 assign(f,subor);
 {I$-}
 reset(f);
 if ioresult<>0 then begin
                      writeln('Chyba subor obsahujuci slovnik!');
                      halt(1)
                     end;
 {I$+}
 velkost_pola_recidivistov:=0;
 readln(f);
 readln(f);
 if seekeof(f) then prazdny:=true
 else
 while not eof(f) do
 begin
 readln(f, cislo);
 rez:=AnsiPos(' ', cislo);
 inc(rez);
 recidivista:=Copy(cislo,rez,maxint);
 dec(rez);
 Delete(cislo,rez,maxint);

 setlength(cislarecidivistov,velkost_pola_recidivistov+1);
 cislarecidivistov[velkost_pola_recidivistov]:=cislo;
  VlozBasistu(s,recidivista, velkost_pola_recidivistov);
 inc(velkost_pola_recidivistov);
 end;
 close(f);
end;

procedure napln_cisla(var s:c_basisti; sub:string);
var f:text;
    i:byte;
    cislo : string;
    retazec : string;
    rez : integer;
begin
cislo:='';
 assign(f,sub);
 {I$-}
 reset(f);
 if ioresult<>0 then begin
                      writeln('Chyba subor obsahujuci slovnik!');
                      halt(1)
                     end;
 {I$+}
 readln(f);
 readln(f);
 while not eof(f) do
 begin
 readln(f, cislo);

 rez:=AnsiPos(' ', cislo);

 inc(rez);
 recidivista:=Copy(cislo,rez,maxint);
 dec(rez);
 Delete(cislo,rez,maxint);
 VlozCislo(s,cislo );
 end;
 close(f);
end;

procedure test(var s:m_basisti; slovnik:string);
var f:text;
    recidivista:string;
    i:byte;
    cislo : string;
    rez : integer;
    vratcislo: integer;
begin
vratcislo:=-1;
 assign(f,'recidivisti.dat');
 {I$-}
 reset(f);
 if ioresult<>0 then begin
                      writeln('Chyba subor obsahujuci slovnik!');
                      halt(1)
                     end;
 {I$+}
 velkost_pola_recidivistov:=0;
 readln(f);
 readln(f);
 while not eof(f) do
 begin
 readln(f, cislo);
 rez:=AnsiPos(' ', cislo);
 inc(rez);
 recidivista:=Copy(cislo,rez,maxint);
 dec(rez);
 Delete(cislo,rez,maxint);

 setlength(cislarecidivistov,velkost_pola_recidivistov+1);
 cislarecidivistov[velkost_pola_recidivistov]:=cislo;
 HladajBasistu(s,recidivista,vratcislo);
  inc(velkost_pola_recidivistov);
 end;
 close(f);
end;

procedure OdstranAtom(p:m_basisti);
var z:'a'..'z';
begin
 for z:='a' to 'z' do
  if (p^.znak[z]<>nil) then OdstranAtom(p^.znak[z]);
  if (p^.cislo<>-1)then begin
   write(p^.cislo);
   inc(j);
   write(' ',j);
   readln;
  end;
 dispose(p); p:=nil;
end;

procedure OdstranStrom(var s:m_basisti);
var p:m_basisti;
begin
 j:=0;
 p:=s;
 OdstranAtom(p);
 s:=nil;
end;

begin
 randomize;
 inicializuj(BASISTI);
 inicializuj_strom_cisel(BAS_CISLA);
 napln_mena(BASISTI, subor);
 if not prazdny then begin
 napln_cisla(BAS_CISLA, subor);
 test(BASISTI,subor);
  write('Zoznam recidivistov nacitany  ');
 end
 else write('Zoznam Alcatraz II je prazdny  ');
 writeln('volby [ESC] = koniec, [?] = hladat');
  repeat
          volby := ReadKey;
          if volby = '?' then begin
                write('? ');
                readln(recidivista);
                HladajBasistu(BASISTI,recidivista,cislo);
                if cislo <> -1 then
                  writeln(recidivista, ' - RECIDIVISTA c.', cislarecidivistov[cislo])
                else begin
                  write('NOVY ');
                     repeat
                      nove_cislo:=random(maxint);
{  test duplicity}       nove_cislo:=66;
                      j:=HladajCislo(BAS_CISLA, inttostr(nove_cislo));
                    until j <> 1;
                 writeln('c. ', nove_cislo);
                 VlozCislo(BAS_CISLA,inttostr(nove_cislo));

                 setlength(cislarecidivistov,velkost_pola_recidivistov+1);
                 cislarecidivistov[velkost_pola_recidivistov]:=inttostr(nove_cislo);
                 VlozBasistu(BASISTI,recidivista, velkost_pola_recidivistov);
                 inc(velkost_pola_recidivistov);

                 assignfile(file_append, 'recidivisti.dat');
                 append(file_append);
                 write(file_append,#13#10,nove_cislo, ' ', recidivista);
                 closefile(file_append);

                end;
          end;
  until volby = #27;
end.