program test19;
(* 						       19 lipiec 1988
 
      ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»
      º       m o d u l  o b s l u g i     º
      º            r e l a c j i           º
      º                                    º
      ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ
 
  zadaniem modulu jest zrealizowanie systemu wspolpracy z
 relacjami i krotkami: modul opisuje te pojecia i definiuje
 operacje na nich: insert, delete, make etc.*)
 
 
   (***************************************************)
   (*                                                 *)
   (*        Assumptions on file system               *)
   (*                                                 *)
   (* The module handling relations assumes a file    *)
   (* system of random access files. The signature    *)
   (* of file system consists of four sorts:          *)
   (*  P - files,                                     *)
   (*  R - records,                                   *)
   (*  S - file's names,                              *)
   (*  N - nonnegative integers                       *)
   (* and several operations and predicates,          *)
   (*   makefile : S x N -> P                         *)
   (*   openfile : S x N -> P                         *)
   (*   closefile : P -> P                            *)
   (*   isopen?  : P -> B0                            *)
   (*   frewind   : P -> P                            *)
   (*   feof      : P -> B0                           *)
   (*   fput      : P x R -> P                        *)
   (*   fget      : P -> R                            *)
   (*   fseek     : P x N -> P                        *)
   (*   position : P -> N                             *)
   (*   filelen  : P -> N                             *)
   (*                                                 *)
   (* which satisfy  the following properties         *)
   (*                                                 *)
   (* isopen?(makefile(s,n))                          *)
   (* position(makefile(s,n)) = 1                     *)
   (* feof(p) <=> (position(p) = filelen(p))          *)
   (* ªisopen?(closefile(p))                          *)
   (* position(frewind(p)) = 1                        *)
   (* k<filelen(p) => position(fseek(p,k)) = k        *)
   (*                                                 *)
   (* isopen?(p) => (p':=fput(p,r))(k:=position(p'))  *)
   (*  (p":=fseek(p',k-1)) (r':=fget(p")) (r =r')     *)
   (* 						      *)
   (*  isopen?(p) => (p':=frewind(p))                 *)
   (*   (while ªfeof(p') do  r:= fget(p') od) true    *)
   (*                                                 *)
   (*  position(p) ó filelen(p)                       *)
   (*                                                 *)
   (*** * * * * * * * * * * * * * * * * * * * * * * ***)
 
unit FileSystem: class;
  (* system plikow bezposredniego dostepu *)
 
 
  (************************************************************)
  (*            T Y P Y     D A N Y C H                       *)
  (************************************************************)
 
  unit Rfile: class;
    (* plik jest ciagiem ponumerowanych rekordow
       jednakowej dlugosci *)
 
       var name: arrayof char (* nazwa zewnetrzna *),
           opened: boolean (* czy otwarty *),
	   reclen (* dlugosc rekordu - w slowach *),
	          (* rozmiar slowa odpowiada rozmiarowi
		     liczby typu integer *)
           position (* numer biezacego rekordu *),
	   length: integer (* dlugosc pliku -
	                      numer pozycji nastepnej po
	                      ostatniej zajetej *),
	   plik: file (* plik bezposredniego dostepu *),
	   next, prev: Rfile (* wszystkie pliki w systemie
	                        sa powiazane w liste
				dwukierunkowa *)
    end Rfile;
 
 
  var system: Rfile; (* dowiazanie do straznika listy plikow *)
 
 
 
	
 
(******************************************************************)
(******************************************************************)
 
 
  	   		
  (*****************************************************************)
  (*          P R O C E D U R Y   I   F U N K C J E                *)
  (*          S Y S T E M U    P L I K O W                         *)
  (*****************************************************************)
 
 
 
                           (******************************)
                           (*     A U X I L I A R Y      *)
                           (******************************)
 
 
			   			
			   unit FindInSystem: function
			        ( name:arrayof char): Rfile ;
				
				unit equalstring: function
				     (s1, s2: arrayof char): boolean;
				   var i1, i2, len, i: integer;
				begin
				 if s1 = none then
         		         writeln(" 1st parameter in equalstring=none");
				 call endrun fi;
				 if s2 = none then
				 writeln(" 2nd parameter in equalstring=none");
				 call endrun fi;
				   i1 := lower(s1); i2 := lower(s2);
				   len := upper(s1) - i1 + 1;
				   if len =/= upper(s2) - i2 + 1
				     then return fi;
				   for i := 1 to len
				    do if s1(i1)  =/= s2(i2)
				         then return fi;
				       i1 := i1 + 1;
				       i2 := i2 + 1;
				    od;
				   result := true
          	                end equalstring;
				
			      var p: Rfile;
			   begin system.name := name;
			         p := system.next;
				 while not equalstring( name, p.name )
				   do p := p.next od;
				 if (p = system) then result := none
				                 else result := p fi;
			  end FindInSystem;
 
	                 (*********************************)
			
			 unit AddToSystem: function
			      (name: arrayof char): Rfile;
			   begin
			     result := new Rfile;
			     result.name := name;
			     result.next := system.next;
			     result.prev := system;
			     system.next.prev := result;
			     system.next := result;
			   end AddToSystem;
			
			 (*********************************)
			
			 unit DeleteFromSystem: procedure
			      (p:Rfile);
			   begin
			     if p = system then return fi;
			     p.next.prev := p.prev;
			     p.prev.next := p.next
			   end DeleteFromSystem;
			
			  (********************************)
			
			  unit FindFileLength: function
			        (p: file, recl:integer): integer;
				
         	         (* odtwarza dlugosc istniejacego pliku,
			    recl - dlugosc rekord w slowach *)
			
			    var record: arrayof integer, i:integer;
			    begin
			      if p = none then
			         write(" FS - FindFileLength - ");
				 writeln("file object does not exist");
				 return;
			      fi;	
			      result := 1;
			      call reset(p);
			      array record dim (1:recl);
			      i := recl*intsize;
			      do
			        getrec(p,record,i);
				if i =/= recl*intsize then exit fi;
				result := result + 1;
			      od;
			    end FindFileLength;  	
 
 
		
		
 
			
(*****************************************************************)
 
(*   M A K E F I L E   *)
	   	
	(* utworzenie i dolaczenie do systemu nowego pliku
	   o zadanej nazwie i dlugosci rekordu *)
 
 
	
    unit makefile: function
         ( name: arrayof char (* nazwa zewnetrzna pliku *),
           reclen: integer (* dlugosc rekordu pliku *) ): Rfile;
	
      begin
        if FindInSystem(name) =/= none
	   (* istnieje w systemie plik o tej nazwie *)
	then
	   writeln(" FS - makefile - file name duplicated");
	fi;
	if reclen <= 0
	then
	  writeln(" FS - makefile - record length should be possitive");
	fi;
	result := AddToSystem(name);    	   		
        result.opened := true;
        result .reclen := reclen;
	result.position := 1;
	result.length := 1;
	open (result.plik, direct, name);
	call rewrite(result.plik);
     end makefile;	
 
 
(***************************************************************)
 
(*   O P E N F I L E    *)
 
       (* otwarcie i ewentualne dolaczenie do systemu
          pliku o zadanej nazwie zewnetrznej i rozmiarze
	  rekordu *)
 
 
 
   unit openfile: function
        (name: arrayof char (* nazwa zewnetrzna pliku *),
         reclen: integer (* dlugosc rekordu pliku *) ): Rfile;
	 			
     begin
       if reclen <= 0
       then
         writeln(" FS - openfile - record length should be possitive");
       fi;
       result := FindInSystem(name);
       if result = none then result := AddToSystem(name) fi;
       result.opened := true;
       result.reclen := reclen;
       result.position := 1;
       open(result.plik, direct, name);
       result.length := FindFileLength(result.plik,reclen);
       if result.length = 1 then call rewrite(result.plik)
          else call reset(result.plik) fi;
    end openfile;
 
 
(***************************************************************)
 
(*   C L O S E F I L E    *)
 
    (* zamkniecie pliku z usunieciem obiektu pliku ;
       obiekt typu Rfile pozostaje w systemie z odpowiednia
       adnotacja *)
 
 
   unit closefile: procedure (p:Rfile);
     begin
       if p = none
       then
         writeln(" FS - closefile - closing nonexisting file");
       fi;
       if not p.opened
       then
        writeln(" FS - closefile - closing not opened file");
       fi;
       p. opened := false;
       kill(p.plik)
    end closefile;
 
 
 
(****************************************************************)
 
(*   I S O P E N    *)
 
    (* sprawdzenie, czy plik jest otwarty *)
 
 
   unit isopen: function( p:Rfile): boolean;
     begin
       if p = none
       then
         writeln(" FS - isopen - testing nonexisting file");
       fi;
       result := p.opened
     end isopen;
 
 
(****************************************************************)
 
(*   F R E W I N D   *)
 
      (* przewiniecie pliku do poczatku *)
 
 
   unit frewind: procedure( p:Rfile);
     begin
       if p = none
       then
        writeln(" FS - frewind - rewinding nonexisting file");
       fi;
       if not p.opened
       then
          writeln(" FS - frewind - rewinding net opened file");
       fi;
       p.position := 1;
       call reset(p.plik)
     end frewind;
 
 
(**************************************************************)
 
(*   F E O F    *)
 
     (* test, czy koniec pliku *)
 
 
   unit feof: function(p: Rfile): boolean;
     begin
       if p = none
       then
          writeln(" FS - feof - testing nonexisting file");
       fi;
       if not p.opened
       then
         writeln(" FS - feof - testing not opened file");
       fi;
       result := ( p.position >= p.length )
     end feof;
 
 
(**************************************************************)
 
(*   F P U T   *)
 
     (* wlozenie rekordu na plik w miejsce wskazane przez
        atrybut position *)
	
	
 
   unit fput: procedure( p: Rfile, Record: arrayof integer);
 
     var ile, i : integer;
     begin
       if p = none
       then
         writeln(" FS - fput - file does not exist"); i:= inchar;
       fi;
       if not p.opened
       then
         writeln(" FS - fput - file not opened");
       fi;
       if p.position > p.length
       then
        writeln(" FS - fput - try to access after file length");
       fi;
       if Record = none
       then
          writeln(" FS - fput - record does not exist");
       fi;
       ile := upper(Record) - lower(Record) + 1;
       if ile =/= p.reclen
       then
          writeln(" FS - fput - wrong record length");
       fi;
       i := ile * intsize;
       putrec(p.plik, Record, i);
       if i =/= ile * intsize
       then
         writeln(" FS - fput - error during writing ");
       fi;
       p.position := p.position + 1;
       if p.position > p.length then p.length := p.position fi;
     end fput;
 
 
(**************************************************************)
 
(*   F G E T   *)
 
    (* odczytanie rekordu z pliku z miejsca wskazywanego
       przez atrybut position *)
 
 
   unit fget: function( p: Rfile): arrayof integer;
     var Record: arrayof integer,
         ile, i : integer;
      begin
        if p = none
	then
	   writeln(" FS - fget - file does not exist ");
	fi;
	if not p.opened
	then
	   writeln(" FS - fget - file not opened");
	fi;
	if p.position >= p.length
	then
	   writeln(" FS - fget - try to read past eof");
	fi;
	ile := p.reclen;
	array Record dim (1:ile);
        i := ile * intsize;
	getrec(p.plik, Record, i);
	if i =/= ile * intsize
	then
	   writeln(" FS - fget - error during reading");
	fi;
	p.position := p.position + 1;
	result := Record;
     end fget;
 
 
 
(*************************************************************)
 
(*   F S E E K   *)
 
       (* wyszukanie w pliku rekordu o zadanym numerze -
          ustawienie atrybutu position *)
	
 
 
   unit fseek: procedure( p: Rfile, nrrec: integer);
 
     var offset: integer;
      begin
        if p = none
	then
	   writeln(" FS - fseek - file does not exist");
	fi;
	if not p.opened
	then
	  writeln(" FS - fseek - file not opened");
	fi;
	if nrrec <= 0
	then
	 writeln(" FS - fseek - record number should be positive");
	fi;
	if nrrec > p.length
	then
	  writeln(" FS - fseek - try to access after file length");
	fi;
        p.position := nrrec;
	offset := (nrrec - 1) * p.reclen * intsize;
	call seek(p.plik, offset, 0)
     end fseek;
 
 
 
(************************************************************)
 
(*   P O S I T I O N   *)
 
    (* answeres the current position of file pointer *)
 
 
   unit position: function( p: Rfile): integer;
     begin
       if p = none
       then
         writeln(" FS - position - checking nonexisting file");
       fi;
       if not p.opened
       then
         writeln(" FS - position - checking not opened file");
       fi;
       result := p.position
     end position;
 
 
(************************************************************)
 
(*   F I L E L E N   *)
 
    (* gives the file length - the number of position
       immediately after the last one *)
 
 
  unit filelen: function( p: Rfile): integer;
    begin
      if p = none
      then
        writeln(" FS - filelen - checking nonexisting file");
      fi;
      if not p.opened
      then
        writeln(" FS - filelen - checking not opened file");
      fi;
      result := p.length
    end filelen;
 
 
(**************************************************************)
(**************************************************************)
 
 
 
 
	
 
 
 
  begin (* of FileSystem *)
     system := new Rfile;
     system.next, system.prev := system;
  end FileSystem;
 
(***************************************************************)
(*  Pakiet Grafiki Blokowej                                    *)
(*                                                             *)
(*                                                             *)
(*                                                             *)
(*                                                             *)
(***************************************************************)
  unit Bold : procedure;
  begin
    write( chr(27), "[1m")
  end Bold;
 
  unit Blink : procedure;
  begin
    write( chr(27), "[5m")
  end Blink;
 
  unit Reverse : procedure;
  begin
    write( chr(27), "[7m")
  end Reverse;
 
  unit Normal : procedure;
  begin
    write( chr(27), "[0m")
  end Normal;
 
  unit Underscore : procedure;
  begin
    write( chr(27), "[4m")
  end Underscore;
 
 
 
  unit inchar : IIuwgraph function : integer;
    (*podaj nr znaku przeslanego z klawiatury *)
    var i : integer;
  begin
    do
      i := inkey;
      if i <> 0 then exit fi;
    od;
    result := i;
  end inchar;
 
  unit NewPage : procedure;
  begin
    write( chr(27), "[2J")
  end NewPage;
 
  unit  SetCursor : procedure(row, column : integer);
    var c,d,e,f  : char,
        i,j : integer;
  begin
    i := row div 10;
    j := row mod 10;
    c := chr(48+i);
    d := chr(48+j);
    i := column div 10;
    j := column mod 10;
    e := chr(48+i);
    f := chr(48+j);
    write( chr(27), "[", c, d, ";", e, f, "H")
  end SetCursor;
h(***************************************************************)
(*  koniec Grafiki                                             *)
(***************************************************************)
 
unit HandlerOfRelations : FileSystem class(PageSize: integer,
             TreeHeight: integer,
				HalfPageSize : integer) ;
  signal signal8,      (*przekroczono wysokosc TreeHeight   *)
         signal14,     (*dwa identyczne klucze o jednakowych ref*)
         Signal13;       (*sygnal usuwania nieobecnego rekordu*)
 signal Signal11,  (*nie ma poprzednika w PrevKey*)
        Signal12;  (*nie ma nastepnika w NextKey*)
 
 
  unit Node : class;
     (*klasa prefiksujaca wszystkie klasy wykorzystywane w
     interpreterze*)
    var Gender:integer
  begin
  end Node;
 
(*  unit ObjectToRec : function (n : Node) : arrayof integer;
  end ObjectToRec;
 
  unit RecToObject : function(a: arrayof integer) : Node;
  end RecToObject;*)
 
(*struktura logiczna
 
                     DataFile
                   /     |      \
           Atrybut               \             .
                     | Relation   \            |
                     |             \           |
                     |                         |
                     |           |IndexFile  | |
                     |           |           | |
                     | _______________________ |      *)
 
 
 
       (********************************************
        *                                          *
        *        DataFile                          *
        *                                          *
        *    Reset                                 *
        *    AddRec                                *
        *    DelRec                                *
        *    FindRec                               *
        *    FreePlace                             *
        *                                          *
        *                                          *
        ********************************************)
 
  unit DataFile : Node class;
      (*typ DataFile jest wspolnym prefiksem dla Atrybut i
Relation i IndexFile. Ten typ umo*liwia operacje
      Wstaw Rekord, UsunRekord etc. *)
    var plik : Rfile;
    var FreePlace : integer; (* pozycja wolnego miejsca
                                w pliku*)
 
 
    unit Reset : procedure ;
    begin
       call fseek(plik,1);
    end Reset;
 
    unit AddRec : procedure (input Record:arrayof integer;
                           output RefRec:integer);
      (*Procedura wstawia rekord Record do DataFile i zwraca
jego pozycje w pliku wykorzystujac przy tym informacje o
wolnych miejscach zapamietana na stosie FreePlace*)
 
      var AuxRec: arrayof integer;
    begin
       array AuxRec dim(lower(Record):upper(Record));
       if FreePlace=0
       then
          RefRec:=FileLen(plik);
          (*jesli nie bylo usunietych rekordow, to Record
           zapiszemy na koncu pliku*)
       else
          RefRec:=FreePlace;
          call fseek(plik,RefRec);
          AuxRec:=fget(plik);(*odczytanie pozycji poprzed
                            niego wolnego miejsca, ktore
                  bedzie teraz aktualnym wolnym miejscem*)
          FreePlace:=AuxRec(1);
       fi;
       call fseek(plik,RefRec);
       call fput(plik,Record)
   end AddRec;
 
     unit DelRec: procedure(input DataRef: integer);
       (*Procedura usuwa rekord wskazany przez DataRef i wpisuje
na jego miejsce referencje do ostatniego wolnego miejsca.
Pozycja usunietego rekordu jest zapamietana na stosie
FreePlace *)
 
       var AuxRec: arrayof integer;
     begin
        call fseek(plik,DataRef);
        array AuxRec dim (1 : plik.reclen);
        AuxRec(1):=FreePlace;
        call fput(plik,AuxRec);
        FreePlace:=DataRef;
     end DelRec;
 
     unit FindRec:procedure(input Record:arrayof integer;
                           output RefRec : integer);
(*Procedura FindRec odszukuje rekord wskazany przez Record
i zwraca jego pozycje w pliku*)
       var equal :boolean,
           i,  Place: integer,
           AuxRec: arrayof integer;
     begin
        array AuxRec dim(lower(Record): upper(Record));
        call Reset;
        equal:=false;
        while (not feof(plik) and not equal)
        do
          RefRec := position(plik);
          AuxRec:= fget(plik);
          for i:=lower(AuxRec) to upper(AuxRec)
          do
            equal:= AuxRec(i)=Record(i);
            if not equal then exit fi
          od (*koniec porownywania rekordow*);
          (* czy znaleziony jest usunietym wczesniej rekordem? *)
          if (equal and FreePlace <> 0)
          then
             Place:=FreePlace;
             while not Place=0
             do
                if RefRec = Place
                then
                   equal:=false;
                   exit (*if equal*)
                else
                   call fseek(plik,Place);
                   AuxRec:=fget(plik);
                   Place:=AuxRec(1)
                fi;
             od;
            call fseek(plik,RefRec+plik.reclen);
          fi (*if equal*);
        od (*eof plik*);
        if not equal
        then
            RefRec:=-1(*nie znalezlismy rekordu*)
         fi;
     end FindRec;
 
  begin (*DataFile*)
 
      FreePlace:=0
  end DataFile;
 
(*
        ********************************************
        *              Relation                    *
        *                                          *
        *    insert                                *
        *    delete                                *
        *    retrieve                              *
        *    member                                *
        *    close                                 *
        *    open                                  *
        *    allocate                              *
        *    deallocate                            *
        *                                          *
        ********************************************
*)
unit Relation : DataFile class ;
   var Index :arrayof IndexFile;
 
   unit Tuple : Node class;
     (*element relacji*)
   end Tuple;
 
   unit virtual TupleToRec : function (t : Tuple): arrayof
							   integer;
   end TupleToRec ;
 
   unit virtual RecToTuple : function(a : arrayof integer):
							Tuple;
   end RecToTuple;
 
 
 
  unit Insert:  procedure (t: Tuple);
    var i,PageRef,DataRef:integer;
    var AuxRec : arrayof integer;
  begin
 AuxRec:=TupleToRec(t);
 call AddRec(AuxRec, DataRef);
 if  Index <> none
 then
 for i:=1 to upper(Index)
 do
   if Index(i)<>none
   then
      call Index(i).AddKey(Index(i).KeyOf(t),DataRef)
   fi
      od;
      fi;
  end Insert;
 
  unit Delete : procedure (t: Tuple);
   var i,DataRef :integer,
      AuxRec : arrayof integer;
  begin
   if Index =/= none
   then (*najpierw szukamy w indeksach i usuwamy tam*)
     for i:=1 to upper(Index)
     do
       if none <> Index(i)
       then
          DataRef := Index(i).FindKey(Index(i).KeyOf(t));
          call  Index(i).DelKey(Index(i).KeyOf(t),DataRef);
         (*
DelKey dziala? *)
       fi;
     od
   else (*brak indeksu*)
     AuxRec := TupleToRec(t);
     call FindRec(AuxRec, DataRef);
   fi;
   if DataRef = -1
   then
     raise Signal13   (*proba usuniecia rekordu ktorego nie ma*)
   else
     call DelRec(DataRef) ;  (*wstawic  na liste usuniec*)
   fi
 end Delete;
 
 
     (*  ********************************************
        *          IndexFile                       *
        *                                          *
        *  Key                                     *
        *  Order                                   *
        *  Item                                    *
        *  Page                                    *
        *  Addkey                                  *
        *  DelKey                                  *
        *  NextKey                                 *
        *  FindKey                                 *
        *  SearchKey                               *
        *  PrevKey                                 *
        *  MinKey                                  *
        *  MaxKey                                  *
        *  Path                                    *
        *  CloseIndex                              *
        ********************************************
*)
 
unit IndexFile : DataFile coroutine;
 
 
  unit SearchStep: class;
    var PageRef,RefOnPage : integer,
        updated : boolean;
  end SearchStep;
 
  unit Item : class ;
    var ky: key, PageRef: integer, DataRef: integer;
      (* item jest jednostka ( rekordem) przechowywana w
      indeksie na stronie tzn.Page
      zawiera:
        ky - klucz,
        PageRef - informacje o stronie na ktorej znajduje sie
 korzen poddrzewa z kluczami wiekszymi od klucza kl,
           a mniejszymi od kluczy podporzadkowanych sasiadowi z
 lewej,
        DataRef - informacja w ktorym rekordzie zapisano
 krotke odpowiadajaca naszemu kluczowi ky*)
  end Item;
 
  unit Page: class;
    var ItemsOnPage,     (*ilu synow ma ta strona +1*)
        LessPageRef: integer;  (*wskaznik do poddrzewa elementow
mniejszych od pierwszego klucza na tej stronie*)
    var ItemsArray: arrayof Item;
  begin
    array ItemsArray dim (1:PageSize)
  end Page;
 
  var KeySize: integer;
 
  unit key : Node class ;
    (*definicja klucza zgodnie z zyczeniem uzytkownika*)
  end key;
 
 
  var StackOfPages: arrayof Page;
  var Finger: integer;   (*zmienne StackOfPages i Finger
 implementuja stos stron*)
  var Path: arrayof SearchStep; (*zmienne Path i Finger
 				  implementuja sciezke*)
 
(* axiom: nr strony wskazanej przez Finger w StackOfPages jest
 identyczny z numerem strony wskazanym przez Finger w Path*)
 
  unit virtual KeyOf : function (t : Tuple) : key;
    (*KeyOf tworzy z dowolnej krotki klucz zaleznie od
     rozwazanego indeksu*)
  end KeyOf;
 
  unit virtual Leq: function (k1,k2 : key):Boolean;
      (* Leq sprawdza czy krotki k1,k2 sa w relacji
      obowiazujacej w rozwazanym indeksie
      zakladamy, ze jest to relacja antysymetryczna*)
  end Leq;
 
 
  unit AddKey : procedure (input ky:key,DataRef:integer);
    (*wstawienie klucza ky i referencji DataRef do indexu w odpowiednie
                                                      miejsce w B-drzewie
     DataRef jest adresem rekordu ktory odpowiada kluczowi
     w pliku relacji*)
    var depth,       (*aktualna glebokosc stosu stron*)
        PageRef,
        i : integer,
        AddItem, AuxItem, itm2 : Item,
        IncreaseHeight : boolean,
        NewRoot : Page,
        AuxRec : arrayof integer;
 
    unit Search : procedure (input itm1 : Item, PageRef :
							 integer;
					   output include : boolean, itm2 :
								  Item);
		(*szukaj poczawszy od strony PageRef, miejsca dla itm1;
		 jezeli nie znajdzie miejsca na tej stronie to
rekurencyjnie szuka na nastepnej odpowiedniej az do
liscia;
		 jezeli include to WSTAWIA obiekt itm2*)
 
      var NextPageRef,
          ItemRef :  integer,
          inclde  :  boolean,
          item2   :  Item,
          AuxPage :  Page;
 
      unit Insert : procedure;
		  (*wstawia obiekt itm2 na strone PageRef w miejscu ItemRef*)
		  var OldPage, RightPage : Page,
			    AuxRec : arrayof integer,
     		         AuxItmArr ,
			AuxItmArr2 : arrayof Item,
                       RightPageRef,
         			 i : integer;
      begin (*Insert*)
                OldPage := StackOfPages(Finger);
		if OldPage.ItemsOnPage < PageSize
		then (*jest miejsce na tej stronie *)
  		  call UpdatePage (item2, ItemRef, OldPage);
                  Path(Finger).RefOnPage := ItemRef + 1;
	          include := false;
		else (*strona jest pelna dokonujemy podzialu *)
                  include := true;
		  OldPage.ItemsOnPage := HalfPageSize;
                  Path(Finger).updated := true;
		  RightPage := new Page;
		  RightPage.ItemsOnPage := HalfPageSize;
                  array RightPage.ItemsArray dim (1:PageSize);
		  AuxItmArr := OldPage.ItemsArray;
		  AuxItmArr2 := RightPage.ItemsArray;
		  if ItemRef = HalfPageSize
		  then (*obiekt itm2=item2 idzie do gory*)
  		    for i := 1  to  HalfPageSize
		    do
			   AuxItmArr2(i):=AuxItmArr(i+HalfPageSize)
		    od;
		    itm2:= item2;
		  else (*to nie item2 idzie do gory  *)
  		      if ItemRef < HalfPageSize
		      then (*wstawiamy do lewej strony*)
  			   for i := 1  to HalfPageSize
			   do
				AuxItmArr2(i) :=
						AuxItmArr(i+HalfPageSize)
			   od;
			   itm2 := AuxItmArr(HalfPageSize);
			   for i := HalfPageSize-1 downto ItemRef+1
			   do
				AuxItmArr(i+1) :=
						AuxItmArr(i)
			   od;
                          AuxItmArr(ItemRef+1) := item2;
			 else (*ItemRef>HalfPageSize *)
			   itm2 := AuxItmArr(HalfPageSize+1);
  			   for i := HalfPageSize+2  to ItemRef
			   do
				AuxItmArr2(i-HalfPageSize-1) :=
								AuxItmArr(i)
			   od;
			   AuxItmArr2(ItemRef-HalfPageSize)
							:= item2;
 
			   for i := ItemRef+1  to PageSize
			   do
				AuxItmArr2(i-HalfPageSize) :=
						AuxItmArr(i)
			   od;
			 fi (*ItemRef < HalfPageSize *)
	         fi (*ItemRef = HalfPagSize *);
(*****)		 (*   StackOfPages(finger) := OldPage; *)
		    call fseek(plik,Path(Finger).PageRef);
           call fput(plik,PageToRec(StackOfPages(Finger)));
		    RightPage.LessPageRef := itm2.PageRef;
		      AuxRec :=PageToRec(RightPage);
		    call AddRec(AuxRec,RightPageRef);
		    itm2.PageRef :=RightPageRef;
		fi (* *)
      end Insert;
 
 
    begin (*Search*)
 
      if PageRef = -1
      then (*poprzednia strona jest lisciem, nalezy do niej
             wstawic itm1 ale z PageRef = -1*)
        include := true;
        itm2 := itm1;
        itm2.PageRef := -1;
      else (*przeszukaj te strone*)
        Finger, depth := Finger+1;
        call GetPage (PageRef);
        AuxPage := StackOfPages (Finger);
        call SearchPage (AuxPage, itm1, NextPageRef, ItemRef);
        call Search(itm1, NextPageRef, include, item2);
        if include
        then (*wstawic obiekt item2 na strone PageRef w miejsce
              ItemRef; jezeli na tej stronie wystarczy miejsca
              na nowy obiekt to wstawic go i zgasic include;
              jezeli brakuje miejsca to strone dzielimy i
              include pozostawiamy zapalone, nowy item itm2 ma
              byc wstawiony na wyzszej stronie  *)
  	   call Insert;
        fi (*include*);
        Finger := Finger -1;
      fi (*PageRef=-1*);
    end Search;
 
 
  begin (*AddKey*)
    (*szukaj w korzeniu i powtarzaj rekurencyjnie w odp.
     poddrzewach, gdy znajdziesz to sygnal blad
     w przeciwnym przypadku*)
    Path(1).updated := true;
    AuxItem := new Item;
    AuxItem.ky := ky;
    AuxItem.DataRef := DataRef;
    AuxItem.PageRef := -1;
    Finger := 0;
    call Search(AuxItem, Path(1).PageRef,
				 IncreaseHeight, AddItem);
    if IncreaseHeight
    then (*korzen podzielony, dodajemy nowy korzen*)
      NewRoot := new Page;
      NewRoot.ItemsOnPage := 1;
      NewRoot.LessPageRef := Path(1).PageRef;
      			(*adres prawej czesci starego korzenia*)
      array NewRoot.ItemsArray dim (1:PageSize);
      NewRoot.ItemsArray(1) := AddItem;
      if depth+1 > TreeHeight
	   then (*przekroczono dopuszczalna wysokosc drzewa*)
        raise Signal8
	   fi;
      for i := 1 to depth
	   do
             StackOfPages(i+1) := StackOfPages(i);
	     Path(i+1) := Path(i);
	   od;
	   StackOfPages(1) := NewRoot;
	   Path(1) := new SearchStep;
      Path(1).RefOnPage := 1;
      Path(1).updated := true;
		      AuxRec :=PageToRec(NewRoot);
	   call AddRec(AuxRec, PageRef);
	   Path(1).PageRef := PageRef (*adres nowego korzenia*) ;
      Finger := depth+1;
    else
      Finger := depth;
	 fi (*IncreaseHeight*);
 
  end AddKey;
 
 
 
 
(*AXIOM  po wykonaniu dowolnej operacji zmieniajacej Finger
 Finger i Path pokazuja na sciezce jakis item w ktorym jest
 klucz tzn. item dla ktorego RefOnPage =/= 0*)
 
  unit PrevKey : procedure (output ky:key, DataRef:integer);
    (*ky jest bezposrednim poprzednikiem klucza biezacego
wskazanego przez Path. DataRef wskazuje referencje do
krotki odpowiadajacej ky w pliku danych*)
    var AuxPage : Page,
        AuxRec : arrayof integer,
        PageRef, nextPageRef,
        RefOnPage : integer;
  begin (*Zakladamy, ze biezacy klucz jest wskazany przez
						Path(Finger)*)
    RefOnPage := Path(Finger).RefOnPage;
    PageRef:=Path(Finger).PageRef;
    AuxPage:=StackOfPages(Finger);
    if AuxPage.LessPageRef = -1
    then (*jestesmy w lisciu*)
	    if RefOnPage <> 1
	    then (*poprzednikiem jest sasiad z lewej*)
		 RefOnPage := RefOnPage -1;
		 Path(Finger).RefOnPage := RefOnPage
	    else (*RefOnPage = 1*)
		 if Finger =1
		 then (*to jest korzen*)
	           ky:=AuxPage.ItemsArray(RefOnPage).ky;
                   DataRef:=AuxPage.ItemsArray(RefOnPage).DataRef;
		   raise signal11; (*nie ma poprzednika*)
		   return;
		 else
		   RefOnPage := 0;
                   while Finger <> 1 and RefOnPage = 0
 		   do
			Finger := Finger-1;
			Auxpage := StackOfPages(Finger);
			RefOnPage := Path(Finger).RefOnPage
		   od;
		   if Finger = 1 and RefOnPage = 0
		   then
		        ky:=AuxPage.ItemsArray(1).ky;
                        DataRef:=AuxPage.ItemsArray(1).DataRef;
			raise signal11; (*nie ma poprzednika*)
			return;
        	   fi;
		 fi (* Finger = 1 *);
	    fi (* RefOnPage <> 1 *);
	 else (*to nie jest lisc*)
		if RefOnPage = 1
		then
		  nextPageRef := AuxPage.LessPageRef;
		  Path(Finger).RefOnPage := 0
		else
		  RefOnPage := RefOnPage -1;
		  nextPageRef := AuxPage.ItemsArray(RefOnPage).PageRef;
		  Path(Finger).RefOnPage := RefOnPage
		fi;
		while nextPageRef <> -1      (*szukamy najwiekszego syna*)
 		do
		  Finger := Finger +1;
		  PageRef := nextPageRef;
		  call GetPage(PageRef);
		  AuxPage := StackOfPages(Finger);
		  RefOnPage, Path(Finger).RefOnPage :=
                                             Auxpage.ItemsOnPage;
		  nextPageRef := AuxPage.ItemsArray(RefOnPage).PageRef
 		od;
	 fi;
    ky:=AuxPage.ItemsArray(RefOnPage).ky;
    DataRef:=AuxPage.ItemsArray(RefOnPage).DataRef
  end PrevKey;
 
 
  unit MinKey : procedure (output k:Key, DataRef : integer);
    (*ustawia Pointer do indexu i Path tak by pokazywaly
najmniejszy klucz. k - jest najmniejszym kluczem w
rozwazanym indeksie, DataRef jest odpowiadajaca mu
referencja do rekordu w pliku glownym relacji*)
 
    var PageRef : integer,
        AuxPage : Page,
        AuxItem : Item;
 
  begin
    Finger :=1;
     do
      AuxPage := StackOfPages(Finger);
      PageRef := AuxPage.LessPageRef;
      Path(Finger).RefOnPage := 0;
      if PageRef = -1 then exit fi;
      Finger := Finger +1;
      call GetPage(PageRef);
     od;
     AuxItem := AuxPage.ItemsArray(1);
     k := AuxItem.ky;
     DataRef := AuxItem.DataRef;
     Path(Finger).RefOnPage := 1;
 
  end MinKey;
 
  unit MaxKey : procedure( output k:Key, DataRef: integer);
(*ustawia Pointer do indexu i Path tak by pokazywaly
najwiekszy klucz*)
    var PageRef, n : integer,
           AuxPage : Page;
 
  begin
    Finger :=1;
     do
      AuxPage := StackOfPages(Finger);
      Path(Finger).RefOnPage, n :=
				AuxPage.ItemsOnPage ;
      PageRef := AuxPage.ItemsArray(n).PageRef;
      if PageRef = -1 then exit fi;
      Finger := Finger+1;
      call GetPage(PageRef);
     od;
     k := AuxPage.ItemsArray(n).Ky;
     DataRef := AuxPage.ItemsArray(n).DataRef;
 
  end MaxKey;
 
 
 
(*************************************************************************)
 
 
  unit NextKey: procedure (output ky:key,DataRef:integer);
(*referencja DataRef do bezposredniego nastepnika biezacej
 pozycji
     ky jest bezposrednim nastepnikiem klucza biezacego
 wskazanego przez Path. DataRef wskazuje referencje do
 krotki odpowiadajacej ky w pliku danych*)
     var AuxPage : Page,
         AuxItem : Item,
        PageRef,nextPageRef,
        RefOnPage : integer;
  begin (*Zakladamy, ze biezacy klucz jest wskazany przez
  						Path(Finger) *)
    RefOnPage := Path(Finger).RefOnPage;
    PageRef := Path(Finger).PageRef;
    AuxPage:=StackOfPages(Finger);
 
    if AuxPage.LessPageRef = -1
    then (*jestesmy w lisciu*)
       while Finger <> 1 and RefOnPage = AuxPage.ItemsOnPage
       do
	 Finger := Finger - 1;
         AuxPage := StackOfPages(Finger);
	 RefOnPage := Path(Finger).refOnPage
       od;
       if  RefOnPage = AuxPage.ItemsOnPage
       then
           AuxItem := AuxPage.ItemsArray(RefOnPage);
           DataRef := AuxItem.DataRef;
           ky := AuxItem.ky;
          raise signal12; (*nie ma nastepnika*)
	  return;
       else
         RefOnPage := RefOnPage+1;
         Path(Finger).RefOnPage := RefOnPage
       fi;
    else (*to nie jest lisc*)
      nextPageRef := AuxPage.ItemsArray(RefOnPage).PageRef;
      while nextPageRef <> -1
 	   do
		Finger := Finger+1;
                PageRef := NextPageRef;
                call GetPage(PageRef);
		AuxPage := StackOfPages(Finger);
 		Path(Finger).refOnPage := 0;
		NextPageRef := AuxPage.LesspageRef
	   od;
      RefOnPage := 1;
      Path(Finger).RefOnPage := 1
    fi;
    AuxItem := AuxPage.ItemsArray(RefOnPage);
    DataRef := AuxItem.DataRef;
    ky := AuxItem.ky
  end NextKey;
 
 
  unit DelKey : procedure (input ky:key,DataRef:integer);
    (*usuwanie klucza ky, o referencji do pliku glownego
    dataref, z indeksu, jezeli takiego klucza nie ma to
    sygnal*)
    var DataRef1: integer,
        k: key,
        underflw:boolean;  (*true if underflow occurred*)
 
     unit remove : procedure(output underflw:boolean);
      var AuxPage,AuxPage1 :Page,
          i,ItemsOnPage,RefOnPage,nextPageRef :integer;
      begin
        AuxPage:=StackOfPages(Finger);
	i:=Finger;
        Path(Finger).updated:=true;
        RefOnPage := Path(Finger).RefOnPage;
 
        if  AuxPage.LessPageRef <> -1
        then (*to nie jest lisc*)
          NextPageRef :=
                    AuxPage.ItemsArray(RefOnPage).PageRef;
          while NextPageRef <> -1
          do
            Finger := Finger+1;
            call GetPage(NextPageRef);
            AuxPage1 := StackOfPages(Finger);
            Path(Finger).RefOnPage := 0;
            NextPageRef := AuxPage1.LessPageRef
          od;
          Path(Finger).updated:=true;
          Path(Finger).RefOnPage := 1;
          AuxPage.ItemsArray(RefOnPage).ky:=
	                        AuxPage1.ItemsArray(1).ky;
	  AuxPage.ItemsArray(RefOnPage).DataRef:=
	                   AuxPage1.ItemsArray(1).DataRef;
	  StackOfPages(i):=AuxPage;(*wymienilam usuniety element*)
          AuxPage:= AuxPage1;
          RefOnPage:=1;
        fi;(*jestesmy w lisciu*)
 
          ItemsOnPage:= AuxPage.ItemsOnPage -1;
	
          for i:=RefOnPage to ItemsOnPage
          do
            AuxPage.ItemsArray(i):=AuxPage.ItemsArray(i+1)
          od;
          AuxPage.ItemsOnPage:= ItemsOnPage;
	  StackOfPages(Finger):=AuxPage;
          if ItemsOnPage<HalfPageSize
          then (*trzeba wywolac underflow*)
          underflw:=true
	fi
    end remove;
 
unit underflow: procedure(inout underflw:boolean);
     (* Finger wskazuje strone A na ktorej jest niedomiar *)
    var Itm:Item,
        AuxPage,AuxPage1, AuxPage2:Page,
        i,k,n,pb,lb,PageRef,RefOnPage: integer,
        AuxRec: arrayof integer;
    begin
      call SetCursor(7,1);     (*****************************)
      writeln("underflow",Finger);
      underflw:=false;
      if Finger<>1 then
      AuxPage:=StackOfPages(Finger);(*strona z niedomiarem*)
 
      Path(Finger).updated:=true ;
      Path(Finger-1).updated:=true ;
      AuxPage1:=StackOfPages(Finger-1); (*strona ojca*)
      RefOnPage:=Path(Finger-1).RefOnPage;
      if RefOnPage< AuxPage1.ItemsOnPage
      then (*istnieje prawy stryj*)
         k:=RefOnPage+1;
         Itm:=AuxPage1.ItemsArray(k);
         PageRef:=Itm.PageRef;
         (*wczytanie strony-brata prawego na AuxPage2*)
         call fseek(plik,PageRef);
         AuxRec:=fget(plik);
         AuxPage2:=RecToPage(AuxRec);
 
         Itm.PageRef:=AuxPage2.LessPageRef;
         AuxPage.ItemsArray(AuxPage.ItemsOnPage+1):=Itm;
         (*stryj schodzi do AuxPage*)
         n:=AuxPage2.ItemsOnPage-HalfPageSize;
 
         if  n>0
         then
	   n:=entier((n-1)/2);(* przelewamy n elementow *)
           Itm:=AuxPage2.ItemsArray(n+1);
           Itm.PageRef:=PageRef;
           AuxPage1.ItemsArray(k):=Itm;
           for i:=1 to n
           do
             AuxPage.ItemsArray(HalfPageSize+i):=
                                   AuxPage2.ItemsArray(i)
           od;
           AuxPage.ItemsOnPage:=HalfPageSize+n;
           StackOfPages(Finger):=AuxPage;
           StackOfPages(Finger-1):=AuxPage1;
           k:=AuxPage2.ItemsOnPage-(n+1);
 
           for i:=1 to k
           do
              AuxPage2.ItemsArray(i):=
                                 AuxPage2.ItemsArray(n+1+i)
           od;
           AuxPage2.ItemsOnPage:=k;
           AuxRec:=PageToRec(AuxPage2);(*zapamiet. AuxPage2*)
           call fseek(plik,PageRef);
           call fput(plik,AuxRec);
         else
            (*AuxPage2.ItemsOnPage=HalfPageSize tzn. n=0*)
            for i:=1 to HalfPageSize
            do
              AuxPage.ItemsArray(HalfPageSize+i):=
                                   AuxPage2.ItemsArray(i)
            od;
            AuxPage.ItemsOnPage:=PageSize;
            for i:=RefOnPage+2 to AuxPage1.ItemsOnPage
            do
              AuxPage1.ItemsArray(i-1):=
                                   AuxPage1.ItemsArray(i)
            od;
 
            AuxPage1.ItemsOnPage:=AuxPage1.ItemsOnPage-1;
            StackOfPages(Finger-1):=AuxPage1;
            StackOfPages(Finger):=AuxPage;
            call DelRec(PageRef);
            if AuxPage1.ItemsOnPage<HalfPageSize
            then
               Finger:=Finger-1;
               underflw:=true;
               (*niedomiar na stronie ojca*)
            fi ;
          fi (*n>0*)
 
        else (*nie ma prawego stryja, wez z lewej*)
          if  RefOnPage>1
          then
            Itm:=AuxPage1.ItemsArray(RefOnPage-1);
            PageRef:=Itm.PageRef;
          else
            PageRef:=AuxPage1.LessPageRef;
          fi;
          (*wczytanie strony-brata lewego na AuxPage2*)
          call fseek(plik,PageRef);
          AuxRec:=fget(plik);
          AuxPage2:=RecToPage(AuxRec);  (*str-brat lewy*)
 
          Itm:=AuxPage1.ItemsArray(RefOnPage);
          Itm.PageRef:=AuxPage.LessPageRef;
          n:=AuxPage2.ItemsOnPage-HalfPageSize;
          if n>0
          then
	    n:=entier((n-1)/2);
            (*przesun o n+1 w prawo elem na str.AuxPage*)
             k:=AuxPage.ItemsOnPage;
             for i:=1 to n+1
             do
               AuxPage.ItemsArray(k+n+2-i):=
                               AuxPage.ItemsArray(k+1-i)
             od;
 
             AuxPage.ItemsArray(n+1):=Itm;
             (*ojciec do AuxPage*)
             AuxPage.ItemsOnPage:=k+n+1;
             Itm:=AuxPage2.ItemsArray(HalfPageSize+n+1);
             Itm.PageRef:=PageRef; (*referencja do AuxPage*)
             AuxPage1.ItemsArray(RefOnPage):=Itm;
             for i:=1 to n
             do
               AuxPage.ItemsArray(i):=
                   AuxPage2.ItemsArray(HalfPageSize+1+i+n)
             od;
             AuxPage.ItemsOnPage:=HalfPageSize+n;
             AuxPage2.ItemsOnPage:= HalfPageSize+n;
 
             (*wyslac strony i zapisac sciezke i stos*)
             StackOfPages(Finger-1):=AuxPage1;
             StackOfPages(Finger):=AuxPage;
             (*zapamietanie strony AuxPage2*)
             AuxRec:=PageToRec(AuxPage2);
             call fseek(plik,PageRef);
             call fput(plik,AuxRec);
 
          else
            (*n=o tzn.AuxPage2.ItemsOnPage=HalfPageSize*)
 
            AuxPage2.ItemsArray(HalfPageSize+1):=Itm;
            for i:=1 to HalfPageSize-1
            do
              AuxPage2.ItemsArray(HalfPageSize+1+i):=
                                   AuxPage.ItemsArray(i)
            od;
            AuxPage1.ItemsOnPage:=AuxPage1.ItemsOnPage-1;
	    AuxPage2.ItemsOnPage:=PageSize;
            StackOfPages(Finger-1):=AuxPage1;
            StackOfPages(Finger):=AuxPage2;
            Path(Finger-1).RefOnPage:=RefOnPage-1;
            call DelRec(Path(Finger).PageRef);
            (*wyrzucono str AuxPage*)
            Path(Finger).PageRef:=PageRef;
 
            if AuxPage1.ItemsOnPage<HalfPageSize
            then
               Finger:=Finger-1;
               underflw:=true (*niedomiar na stronie ojca*)
            fi;
          fi (*n>0*)
 
     fi(*lewy istnieje*)
 
 
    else (*niedomiar jest w korzeniu*)
      AuxPage:=StackOfPages(1);
      if AuxPage.ItemsOnPage=0
      then
        call DelRec(Path(1).PageRef);
        if AuxPage.LessPageRef<>-1
        then
             i:=2;
             while Path(i)<>none
             do
                Path(i-1):=Path(i);
                StackOfPages(i-1):=StackOfPages(i);
                i:=i+1
             od
        else
          writeln("drzewo znika ");
        fi;
     fi
    fi (*Finger<>1*);
  end underflow;
 
  begin (*DelKey*)
      k:=ky;
      DataRef1:=FindKey(k);
      do
      if k=ky and DataRef=DataRef1
      then
         (*znalezlismy wlasciwy klucz *)
         call remove(underflw);
         while underflw
         do
            call underflow(underflw)
         od;
         return
      else
        if k<>ky or DataRef1= -1
        then
          writeln("* nie ma takiego klucza *")
        else
          call NextKey(k,DataRef1)
        fi
      fi
    od
  end DelKey;
 
 
  unit FindKey:function (k : key): integer;
    (*wynikiem poszukiwania klucza k jest referencja do
     datafile wskazujaca na krotke o danym kluczu. Gdy
     nie znaleziono, wartoscia funkcji jest -1 *)
     var PageRef,
     i : integer,
     AuxPage : Page,
     Itms : arrayof Item,
     k1 : Key;
   begin
     Finger := 1;
     PageRef := Path(Finger).PageRef;
     do
       call GetPage( PageRef );
       (*przeszukujemy strone o adresie Pageref*)
       AuxPage := StackOfPages(Finger);
       Itms := AuxPage.ItemsArray;
       for i := AuxPage.ItemsOnPage downto 1
       do
  	  k1 := Itms(i).ky;
	  if leq(k1, k)
          then
	      Path(Finger).RefOnPage := i;
	      if leq(k, k1)
       	      then (*znaleziony*)
	          result := Itms(i).DataRef;
	          return
	      fi;
              PageRef := Itms(i).PageRef;
              exit;
            else
	      if i =1
	      then (*klucz k jest mniejszy od wszystkich kluczy
				na rozwazanej stronie*)
  	         PageRef := AuxPage.LessPageRef;
		 Path(Finger).RefOnPage := 0;
	      fi;
	  fi;
       od;
 
       if PageRef = -1
       then (*jestesmy w lisciu, nie ma poszukiwanego klucza*)
          if Path(Finger).RefOnPage = 0
	  then
	      Path(Finger).RefOnPage :=1
	  fi;
	  result := -1;
	  exit (*FindKey*)
       else
          Finger := Finger+1
       fi;
    od;
 end FindKey;
 
unit SearchKey: procedure(input k:key;
                            output DataRef : integer);
(*referencja do klucza, ktory jest >=k *)
begin
   DataRef:=FindKey(k);
   if DataRef=-1
   then
     call NextKey(k,DataRef)
   fi
end SearchKey;
 
 
 
  unit GetPage  :  procedure(PageRef : integer);
  (* wczytanie do stosu stron strony o adresie  PageRef,
    chyba, ze strona o tej referencji jest juz w stosie.
    Poprawienie sciezki i ew. przeslanie do pliku strony
    wskazanej przez Path(Finger).PageRef o ile byla zmieniana jej tresc *)
 
    var AuxRec : arrayof integer;
  begin
 
    if Path(Finger) = none
    then
      Path(Finger) := new SearchStep;
      Path(Finger).Updated := false;
      Path(Finger).PageRef := PageRef-1; (*chce by byla roznica ponizej *)
    fi;
(*!   if Path(Finger).PageRef <> PageRef
    then   *)   (*zmiana strony *)
      if Path(Finger).Updated
      then (*wyslanie strony na plik, poniewaz byla zmieniana *)
        AuxRec := PageToRec(StackOfPages(Finger));
        call fseek(plik, Path(Finger).PageRef);
        call fput(plik,AuxRec);
      fi (*updated*);
      (*wczytanie potrzebnej strony*)
      call fseek(plik, PageRef);
      AuxRec := fget(plik);
      StackOfPages(Finger) := RecToPage(AuxRec);
      Path(Finger) := new SearchStep;
      Path(Finger).PageRef := PageRef;
      Path(Finger).updated := false;
(*!    fi  *)
 
  end GetPage  ;
 
  unit UpdatePage  :  procedure (input AuxItem : Item,
                                    ItemRef : integer,
							AuxPage : Page);
  (* wstaw AuxItem na wskazanej stronie, w miejscu ItemRef +1 *)
    var  AuxItmArr : arrayof Item,
         n,i: integer;
  begin
    AuxPage.ItemsOnPage, n := AuxPage.ItemsOnPage +1;
    for i := n  downto ItemRef +2
    do
      AuxItmArr :=   AuxPage.ItemsArray;
      AuxItmArr(i) := AuxItmArr(i-1)
    od;
    AuxPage.ItemsArray(ItemRef+1) := AuxItem;
    Path(Finger).Updated := true;
  end UpdatePage  ;
 
  unit order : function (i1, i2 : Item) : boolean;
  (*ropzszerzenie porzadku LessOrEqual Leq o badanie DataRef w
przypadku gdy klucze sa rowne   *)
 
    var k1,k2 :key,
        n : integer;
 
  begin
    k1 := i1.ky;
    k2 := i2.ky;
    if Leq(k2,k1)
    then (* k2ók1 *)
      if Leq(k1, k2)
      then (* k1=k2 *)
 
        (* DORADZAMY zbadaj czy k1 = k2? *************************)
	(* potrzebna inna funkcja EQ? booleowska *****************)
	(* o odp. wlasnosciach: zwrotnsc,przechodniosc, symetria *)
	
        n := i1.DataRef - i2.DataRef;
        if n=0
        then (*dwa identyczne klucze o jednakowych referencjach*)
          raise Signal14
        fi;
        result := n<0;
      else (* k1>k2 *)
        result := false
      fi
    else (*k1<k2 ?*)
      if not Leq(k1, k2)
      then
(* 16.08.87 ********************************************)
        (* raise RelacjaNieSpojna *)
      else	
        result := true
      fi	
    fi
  end order;
 
  unit SearchPage  : procedure (input P : Page, it : Item;
				 output NextPageRef, ItemRef : integer);
  (* szukamy miejsca dla obiektu it na stronie P, NextPageRef
jest adresem strony na ktorej mozemy kontynuowac
poszukiwania; ItemRef jest numerem obiektu mniejszego od it
lub jest rowne 0 gdy nasz obiekt it jest mniejszy
od wszystkich obiektow na stronie*)
 
     var Itms : arrayof Item,
         it1 : Item;
 
  begin
    Itms :=P.ItemsArray;
    for ItemRef  := P.ItemsOnPage  downto  1
    do
      it1 := Itms(ItemRef);
      if order (it1, it)
      then (*it1<it *)
        NextPageRef := it1.PageRef;
        return
      fi
    od;
    (*obiekt it jest mniejszy od wszystkich obiektow na tej
stronie*)
    ItemRef := 0;
    NextPageRef := P.LessPageRef;
  end SearchPage ;
 
 
 
  unit RecToPage  :  function(A: arrayof integer): Page;
    (*Ta funkcja odczytuje tablice liczb calkowitych i zmienia
ja w strone Page. Wykorzystuje sie virtualna funkcje
RecToKey.   *)
    var P: Page,
        i,j : integer,
        It : Item;
  begin
    P:=new Page;
    P.ItemsOnPage,j := A(1);
    P.LessPageRef := A(2);
    array P.ItemsArray dim (1:PageSize);
    for i := 1 to  j  (*P.ItemsOnPage*)
    do
      It := new Item;
      It.ky := RecToKey(A, 3+(i-1)*(KeySize+2) ) ;
      It.PageRef := A(i*(KeySize+2)+1);
      It.DataRef := A(i*(KeySize+2)+2);
      P.ItemsArray(i) := It;
    od(*itemsOnPage*);
    result :=P
  end RecToPage ;
 
  unit PageToRec : function (P: Page): arrayof integer;
    (*Funkcja odwrotna do poprzedniej*)
    var A :  arrayof integer,
        It:  Item,
        i :  integer;
  begin
    array A dim(1:(2+PageSize*(KeySize+2)));
    A(1) :=P.ItemsOnPage;
    A(2) := P.LessPageRef;
    for i := 1  to P.ItemsOnPage
    do
      It:=P.ItemsArray(i);
    (*  if It = none then writeln(" It w PageToRec jest none");
                        writeln("ItemsOnPage= ",P.ItemsOnPage,"i= ",i)
      fi; *)
      call KeyToRec(It.ky, A, 3+(i-1)*(KeySize+2) );
       (*O KeyToRec zakladam, ze jest to procedura virtualna,
ktora przepisuje klucz ky do tablicy A poczynajac od
danego miejsca A(j) do kolejnych KeySize komorek tej
tablicy. *)
      A(i*(KeySize+2)+1) := It.PageRef;
      A(i*(KeySize+2)+2) := It.DataRef;
    od;
    result := A
  end PageToRec ;
 
  unit virtual KeyToRec  :  procedure(ky:Key, A: arrayof integer, j: integer);
    (*procedura virtualna, ktora przepisuje klucz ky do tablicy
A poczynajac od danego miejsca A(j) do kolejnych KeySize
komorek tej tablicy. *)
 
  begin
 
  end KeyToRec ;
 
  unit virtual RecToKey : function(A: arrayof integer, 	
							j:integer): Key;
    (*Funkcja odczytuje KeySize kolejnych komorek z tablicy A
poczynajac od A(j) i tworzy z nich klucz   *)
 
  begin
 
  end RecToKey ;
 
  var AuxRec : arrayof integer,
      akey   :  Key,
      PageRef : integer;
 
begin (*IndexFile*)
  (*ustawic wskazowke do IndexFile *)
  (*zainicjowac Path i StackOfPages*)
  Finger :=1;
  array StackOfPages dim(1:TreeHeight);
  array Path dim (1:TreeHeight);
  StackOfPages(1) := new Page;
  StackOfPages(1).ItemsOnPage := 0;
  StackOfPages(1).LessPageRef := -1;
  array StackOfPages(1).ItemsArray dim (1: PageSize);
  Path(1):= new SearchStep;
  Path(1).PageRef := 1;
  Path(1).RefOnPage := 0;
 
 
end IndexFile;
 
 
 
 
begin (*Relation*)
 
   end Relation;
 
 
 
 
begin (*obsluga relacji*)
 
end HandlerOfRelations;
 
 
begin (*to begin odpowiada zewnetrznym : program i end*)
 
pref HandlerOfRelations(4,8,2) block
 
unit Bibliografia   : Relation  class;
  (*nasza przykladowa relacja *)
  const autleng=25, tytleng=50, wydleng=15;
 
  unit Krotka : Tuple class ;
    var autor,
        tytul,
        wydawca : arrayof char,
        rok,
        pozycja : integer;
  begin
    array autor dim(1 : autleng);
    array tytul dim (1 : tytleng);
    array wydawca dim (1 :wydleng);
  end Krotka;
 
  var ak : Krotka;    (*aktualna krotka*)
 
  unit virtual TupleToRec : function (k : Krotka): arrayof
            						   integer;
  var Aux : arrayof integer,
        AIC : arrayof char,
        i : integer;
 
  begin
    array Aux dim (1:95);
    AIC := k.autor;
    for i := 1 to autleng
    do
      Aux(i) := ord(AIC(i));
      if ord(AIC(i)) = 13
      then (*Enter  *)
         exit
      fi;
    od;
    for i := 1 to tytleng
    do
       Aux(autleng+i) := ord(k.tytul(i));
       if ord(k.tytul(i)) = 13
       then (*Enter *)
          exit
       fi;
    od;
    for i := 1 to wydleng
    do
       Aux(75+i) := ord(k.wydawca(i));
       if ord(k.wydawca(i)) = 13
       then (*Enter *)
          exit
       fi;
    od;
    Aux(91) := k.rok;
    Aux(92) := k.pozycja;
    result := Aux;
  end TupleToRec;
 
unit virtual RecToTuple : function (a: arrayof integer)
							 :Krotka;
    (*   *)
   var k:krotka,
       i:integer;
begin
   k:=new krotka;
   for i:=1 to autleng
   do
      k.autor(i):=chr(a(i));
      if a(i) = 13
      then (*koniec tekstu *)
         exit
      fi;
   od;
   for i:=1 to tytleng
   do
      k.tytul(i):=chr(a(autleng+i));
      if a(autleng+i) = 13
      then (*koniec tekstu *)
         exit
      fi;
   od;
   for  i := 1  to wydleng
   do
      k.wydawca(i):=chr(a(75+i));
      if a(75+i) = 13
      then (*koniec tekstu *)
         exit
      fi;
   od;
   k.rok:=a(91);
   k.pozycja:=a(92);
   result := k
end RecToTuple  ;
 
unit DrukujKrotke :  procedure;
  (*drukuj aktualna krotke *)
begin
  call SetCursor(4,1);
  writeln("                                        ");
  writeln("                                        ");
  writeln("                                        ");
  writeln("                                        ");
  call SetCursor(10,1);
  write("      autor:                              ");
  call SetCursor(10,14);
  call Drukuj(ak.autor); writeln;
  write("      tytul:                              ");
  call SetCursor(11,14);
  call Drukuj(ak.tytul); writeln;
  write("    wydawca:                              ");
  call SetCursor(12,14);
  call Drukuj(ak.wydawca); writeln;
  writeln("rok wydania: ",ak.rok);
  writeln(" pozycja nr: ",ak.pozycja);
end DrukujKrotke ;
 
unit WczytajKrotke :  procedure;
  (*Czytaj aktualna krotke *)
begin
  call SetCursor(25,1);
  write("edit tuple, pressing PgDn finishes ");
 
  do
    call SetCursor(4,1);
    writeln; call Reverse;
    write("      autor: "); call Normal;
    call Czytaj(ak.autor); call Reverse;
    write("      tytul: "); call Normal;
    call Czytaj(ak.tytul); call Reverse;
    write("    wydawca: "); call Normal;
    call Czytaj(ak.wydawca); call Reverse;
    write("rok wydania: "); call Normal;
    read(ak.rok); call Reverse;
    write(" pozycja nr: "); call Normal;
    readln(ak.pozycja);
    if inchar = -81 then exit fi;
  od;
end WczytajKrotke ;
 
unit IndeksAutorow : IndexFile class ;
  (*   *)
  unit klucz : Key class ;
    var autor : arrayof char;
  begin
    array autor dim (1: autleng );
 
  end klucz;
 
  unit virtual KeyOf  :  function (k :Krotka) : klucz;
    (*tworzenie klucza z krotki *)
  begin
    result := new klucz;
    result.autor := copy (k.autor)
  end KeyOf ;
 
  unit virtual Leq : function (k1,k2 : klucz) : boolean;
    (*porownanie dwu kluczy *)
    var i: integer;
  begin
    result := true;
 
 
 
    for i := 1 to autleng
    do
      if ord(k1.autor(i)) =13
      then
        exit
      else
        if ord(k2.autor(i)) = 13	
	then
	  result := false;
	  exit
	else
	
	fi;
      fi;
      if ord(k1.autor(i)) = ord(k2.autor(i))
      then (*rowne*)
      else
        if ord(k1.autor(i)) < ord(k2.autor(i))
	then
	  result := true ;
	else
	  result := false;
	fi;
	exit;
      fi;
    od;
  end Leq ;
 
    unit virtual KeyToRec :  procedure(ky:klucz, A: arrayof integer,
                                                               j: integer);
       (*procedura virtualna, ktora przepisuje klucz ky do tablicy
       A poczynajac od danego miejsca A(j) do kolejnych KeySize
       komorek tej tablicy. *)
 
     var i : integer;
     begin
       for i := 1 to autleng
       do
         A(j+i-1) := ord(ky.autor(i))
       od;
     end KeyToRec ;
 
     unit virtual RecToKey : function(A: arrayof integer, 	
						j:integer): klucz;
       (*Funkcja odczytuje KeySize kolejnych komorek z tablicy A
       poczynajac od A(j) i tworzy z nich klucz   *)
 
     var k : klucz;
     begin
       k := new klucz;
       for i := 1 to autleng
       do
          k.autor(i) := chr(A(j+i-1))
       od;
       result := k
     end RecToKey ;
 
     unit DrukujStrone : procedure (PageRef: integer);
     var P : Page,
         j,
         i : integer,
	 l : klucz,
         c : char,
         AuxRec : arrayof integer;
  begin
    if PageRef = -1 then  return fi;
       for i := 1 to TreeHeight
       do
        if Path(i) = none then exit fi;
        if Path(i).updated
        then
          call fseek(plik,Path(i).PageRef);
	  call fput(plik,PageToRec(StackOfPages(i)));
	  Path(i).updated := false;
        fi;
       od;
       (*wczytaj strone*)
       call fseek(plik, PageRef);
       AuxRec := fget(plik);
       P := RecToPage(AuxRec);
       (*drukuj*)
 
       writeln("stronaRefNr=",PageRef:4,"  itemow =", P.ItemsOnPage:3);
       write(" klucze                ");
       for i := 1 to P.ItemsOnPage
       do
          l := P.ItemsArray(i).ky;
          for j := 1 to 12
	 do
	   c := l.autor(j);
	   if ord(c) = 13
	   then
	     write(' ')
           else
	     write(c)
	   fi;
	 od;
       od;
       writeln;
       write(" PgRfs",P.LessPageRef:5);
       for i := 1 to P.ItemsOnPage
       do
          write(P.ItemsArray(i).PageRef:12);
       od;
       writeln;
       call DrukujStrone(P.LessPageRef);
       for i := 1 to P.ItemsOnPage
       do
          call DrukujStrone(P.ItemsArray(i).PageRef);
       od;
       kill(AuxRec);
  end DrukujStrone;
 
  var akl : klucz;
 
  begin (*indeksAutorow*)
     KeySize := autleng;
     akl, akey := new klucz;
     (*  dlugosc rekordu-klucza = 2+(PageSize * (KeySize + 2)); *)
     if otworz
     then
        plik := openfile(unpack("autor.idx"),2+(PageSize * (KeySize + 2)) );
        (* odczytac strony do StackOfPages *)
        Path(1).PageRef := INFO(1);
        Path(1).RefOnPage := 1;
        call fseek(plik,Path(1).PageRef);
        AuxRec := fget(plik);
        StackOfPages(1) := RecToPage(AuxRec);
        kill(AuxRec);
     else
        plik := makefile(unpack("autor.idx"),2+(PageSize * (KeySize + 2)) );
     fi;
     return;
       (* ZAMYKANIE indeksu *)
       (* strony zmienione ze sciezki sa zapisywane na pliku *)
     for i := 1 to TreeHeight
     do
        if Path(i) = none then exit fi;
        if Path(i).updated
        then
           call fseek(plik,Path(i).PageRef);
  	   call fput(plik,PageToRec(StackOfPages(i)));
	   Path(i).updated := false;
         fi;
       od;
       (* ZAPISAC nr rekordu - korzenia *)
       INFO(1) := Path(1).PageRef;
       call closefile(plik);
     end IndeksAutorow ;
 
     var IA :IndeksAutorow ;
 
     unit IndeksPoz : IndexFile class ;
  (*   *)
     unit klucz : Key class ;
     var poz : integer;
     begin
 
     end klucz;
 
     unit virtual KeyOf  :  function (k :Krotka) : klucz;
        (*tworzenie klucza z krotki *)
     begin
       result := new klucz;
       result.poz := k.pozycja
     end KeyOf ;
 
     unit virtual Leq : function (k1,k2 : klucz) : boolean;
        (*porownanie dwu kluczy *)
     begin
       result := not (k1.poz > k2.poz)
     end Leq ;
 
     unit virtual KeyToRec :  procedure(ky:klucz, A: arrayof integer,
                                                                j: integer);
      (*procedura virtualna, ktora przepisuje klucz ky do tablicy
       A poczynajac od danego miejsca A(j) do kolejnych KeySize
       komorek tej tablicy. *)
 
    (*   *)
     var i : integer;
     begin
        A(j) := ky.poz;
     end KeyToRec ;
 
     unit virtual RecToKey : function(A: arrayof integer, 	
						j:integer): klucz;
       (*Funkcja odczytuje KeySize kolejnych komorek z tablicy A
         poczynajac od A(j) i tworzy z nich klucz   *)
    (*    *)
     var k : klucz;
     begin
        k := new klucz;
        k.poz := A(j);
        result := k
     end RecToKey ;
 
     unit DrukujStrone : procedure (PageRef: integer);
     var P : Page,
         i : integer,
         AuxRec : arrayof integer;
     begin
       if PageRef = -1 then  return fi;
       for i := 1 to TreeHeight
       do
         if Path(i) = none then exit fi;
         if Path(i).updated
         then
            call fseek(plik,Path(i).PageRef);
            call fput(plik,PageToRec(StackOfPages(i)));
            Path(i).updated := false;
         fi;
       od;
       (*wczytaj strone*)
       call fseek(plik, PageRef);
       AuxRec := fget(plik);
       P := RecToPage(AuxRec);
       (*drukuj*)
 
       writeln("stronaRefNr=",PageRef:4,"  itemow =", P.ItemsOnPage:3);
       write(" klucze    ");
       for i := 1 to P.ItemsOnPage
       do
          write(P.ItemsArray(i).ky qua klucz.poz:12);
       od;
(* 16.08.87 *******************************************************)
       writeln;
       write(" PgRfs",P.LessPageRef:5);
       for i := 1 to P.ItemsOnPage
       do
         write(P.ItemsArray(i).PageRef:12);
       od;
       writeln;
       call DrukujStrone(P.LessPageRef);
       for i := 1 to P.ItemsOnPage
       do
         call DrukujStrone(P.ItemsArray(i).PageRef);
       od;
       kill(AuxRec);
  end DrukujStrone;
 
 
  var akl : klucz;
 
  begin (*indeksPozycji*)
     KeySize := 1;
     akl, akey := new klucz;
     (*  plik.reclength := 2+(PageSize * (KeySize + 2)); *)
     if otworz
     then
       plik := openfile(unpack("nrpzycji.idx"),2+(PageSize * (KeySize + 2)));
       (* odczytac strone-korzen do StackOfPages *)
 
       Path(1).PageRef := INFO(2);
       Path(1).RefOnPage := 1;
       call fseek(plik,Path(1).PageRef);
       AuxRec := fget(plik);
       StackOfPages(1) := RecToPage(AuxRec);
       kill(AuxRec);
     else
       plik := makefile(unpack("nrpzycji.idx"),2+(PageSize * (KeySize + 2)) );
     fi;
     return;
      (* ZAMYKANIE indexu *)
       for i := 1 to TreeHeight
       do
         if Path(i) = none then exit fi;
         if Path(i).updated
         then
            call fseek(plik,Path(i).PageRef);
            call fput(plik,PageToRec(StackOfPages(i)));
            Path(i).updated := false;
         fi;
       od;
              (* ZAPISAC nr rekordu - korzenia *)
              INFO(2) := Path(1).PageRef;
              call closefile(plik);
end IndeksPoz ;
 
var IB :IndeksPoz ;
 
begin (*bibliografia*)
 
if otworz
then
  plik:= openfile(unpack("bibliog.dta"), 95);
else
  plik:= makefile(unpack("bibliog.dta"), 95);
fi;
  ak := new Krotka;
 (* call IncreaseIndex( new IndeksAutorow); *)
  array Index dim(1 : 2);
  Index(1), IA := new IndeksAutorow;
  Index(2), IB := new IndeksPoz;
end Bibliografia ;
 
 
    (*deklaracje pomocnicze programu glownego*)
     var cha : char,
         otworz,                (* otwieramy *)
         otwarta : boolean,  (*czy baza bibliograficzna juz jest otwarta?*)
         R : Bibliografia,
         i,j : integer,
         Rec : arrayof integer;
 
  unit Czytaj  :  procedure(a: arrayof char);
  (*czytaj tablice znakow *)
  var i,j : integer,
      cha1: char;
  begin
    for i  := 1 to upper(a)
    do
      j := inchar;
      a(i) := chr(j);
      write(a(i));
      if j = 13
      then (*wczytano Enter *)
        writeln;
        exit
      fi;
    od;
    if i < upper(a)
    then
      a(i+1) := chr(13)
    else
      a(upper(a)) := chr(13)
    fi
  end Czytaj ;
 
  unit Drukuj : procedure (a : arrayof char);
    (*drukuj tablice znakow jako linijke tekstu *)
  var i : integer;
  begin
    for i := 1 to upper(a)
    do
      write(a(i));
      if ord(a(i)) =13
      then (*wydrukowano Enter *)
          exit
      fi
    od;
  end Drukuj ;
 
var INFO : arrayof integer,
    j1,j2: integer,
    extrem : boolean,
    infoplik : Rfile;
 
    handlers
 
       when Signal13 :
          call SetCursor(5,1);
          writeln("Trying to delete an already absent record");
          return;
	
       when Signal11 :
           call SetCursor(5,1);
	   writeln("osiagnieto element minimalny");
	   extrem := true;
           return;
	
       when Signal12 :
           call SetCursor(5,1);
           writeln("osiagnieto element maksymalny");
	   extrem := true;
           return;	
    end handlers;
 
 
begin (*program glowny prefiksowany przez HandlerOfRelations*)
  (*dane bibliograficzne*)
  (*wyswietl powitanie*)
 
   array INFO dim (1:3);
   call Reverse;
   call NewPage;
   call SetCursor(13,10);
   (*call Normal;*)
   (*call Bold;*)
   write("TOOLBOX dla baz danych");
   call SetCursor(15,10);
   write("test 19v.4");
   call SetCursor(21,10);
   (*call Normal;*)
   write("G.Mirkowska, A.Salwicki - Lipiec 1988");
   call SetCursor(22,10);
   write("klase FileSystem napisala J.Warpechowska");
   call SetCursor(23,68);
   write("press a key");
   i := inchar;
   call Normal;
   call NewPage;
   writeln; writeln; writeln;
   write(
   "Do you wish to use the previously prepared bibliography files?(y/n)?");
   i := inchar;
   call Bold;
   write(chr(i));
   if i =121
   then
     otworz := true;
     infoplik := openfile(unpack("bibliog.bas"),3);
     INFO := fget(infoplik);
   else
     otworz := false;
     infoplik := makefile(unpack("bibliog.bas"),3);
   fi;
 
    R :=new Bibliografia;
    R.FreePlace := Info(3);
    call NewPage;
    call Reverse;
    writeln(
 "i-INSERT  d-DELETE  s-SEARCH  m-MINMAX  t-TYPE  n-NEXT  p-PREVIOUS q-QUIT");
 
    writeln(
 "ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ");
    writeln;
    call SetCursor(23,1);
    call Normal;
    writeln(
 "ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ");
    writeln(
 "                                                                          ");
    call Blink;
    write(
 "                                                         make a choice    ");
    call Normal;
    call Bold;
    call SetCursor(1,76);
    cha := chr(inchar);
    writeln(cha);
    call SetCursor(25,1);
    write(
 "                                                                        ");
    call SetCursor(5,1);
  do
    case cha
 
      when 'q' : (* quit*)
        call Blink;
	call SetCursor(24,7);
        writeln("end of program test19-4,  CLOSING FILES");
	call Normal;
	call SetCursor(5,1);
	call closefile(R.plik);
	attach(R.IA);
	attach(R.IB);
	INFO(3) := R.FreePlace;
        call frewind(infoplik);
	call fput(infoplik,INFO);
	call closefile(infoplik);
	call NewPage;
        call endrun;
	(* end quit *)
	
      when 'i': (*read a tuple and INSERT*)
        call R.WczytajKrotke;
	call SetCursor(24,7);
	call Blink;
	call Reverse;
	write("inserting the tuple");
        call R.Insert(R.ak);
        j1,j2 := 1;
        call Normal;
	call SetCursor(24,7);
	write("                                                      ");
	
      when 't' : (*type*)
        call Normal;
	call Reverse;
	call SetCursor(3,38);
	write("print: r-RELATION or b-BTREE ");
        cha := chr(inchar);
	call Normal;
	writeln(cha);
        if cha = 'r'
        then (*printing relation*)
          call SetCursor(24,4);
	  write(" press SPACEBAR for next record");
	  call SetCursor(5,1);
	  call fseek(R.plik,1);
          while not feof(R.plik)
          do
            Rec := fget(R.plik);
            R.ak := R.RecToTuple(Rec);
            call R.DrukujKrotke;
	    call SetCursor(24,19);
	    i:=inchar;
          od;
        else (*printing Btree*)
          call SetCursor(4,30);
	  call Reverse;
	  write("select index: a-AUTHORS or p-POSITIONS ");
          call Normal;
	  cha := chr(inchar);
  	  writeln(cha);
	  call SetCursor(5,1);
         if cha = 'p'
         then
           call R.IB.DrukujStrone(R.IB.Path(1).PageRef);
         else
           call R.IA.DrukujStrone(R.IA.Path(1).PageRef);
         fi;
 
       fi (*koniec drukuj*);
 
   when 's': (*search for a tuple*)
     call SetCursor(3,19);
     call Reverse;
     write(" searching tuple (t)? or key (k)? ");
     cha := chr(inchar);
     	writeln(cha);
	call Normal;
     if cha = 't'
     then (*give a tuple *)
       call SetCursor(5,1);
       call R.WczytajKrotke;
       Rec := R.TupleToRec(R.ak);
       	call SetCursor(24,7);
	call Blink;
	call Reverse;
	write("searching the tuple");
 
       call R.FindRec(Rec, i);
 
        call Normal;
	call SetCursor(24,7);
	write("                                             ");
       if i = -1
       then (*  *)
           writeln(" the tuple not found");
       else (*  *)
           writeln(" position of the tuple in the datafile = ",i);
           (* call fseek(R.plik, i);
           Rec := fget(R.plik);
           R.ak := R.RecToTuple(rec);
           call R.DrukujKrotke; *)
      fi;
     else (*'k'  *)
       if cha ='k'
       then (*searching in the authors or position index*)
         call SetCursor(4,19);
	 call Reverse;
	 write("which index: authors(a)? or positions(p)?  ");
         cha := chr(inchar);
	 writeln(cha);
	 call Normal;	
         if cha = 'a'
         then
           i := 1;
	   call SetCursor(5,1);
           write(" autor:  ");
           call Czytaj(R.IA.akl.autor);
	
           j1 := R.IA.Findkey(R.IA.akl);
           if j1<> -1
           then (*znaleziono  *)
  	     call SetCursor(24,7);
	     writeln("tuple found on position = ",j1);
             call fseek(R.plik, j1);
             Rec := fget(R.plik);
             R.ak := R.RecToTuple(Rec);
             call R.DrukujKrotke;
	   else (*nie znaleziono *)
	     call SetCursor(24,7);
             writeln(" tuple not found");
	   fi
         else (*zakladamy cha ='p'*)
           i := 2;
	   call SetCursor(5,1);
           write(" position nr:  ");
           read(R.IB.akl.poz);
           j2 := R.Index(i).Findkey(R.IB.akl);
           if j2<> -1
	   then (*znaleziono  *)
  	     call SetCursor(24,7);
	     write("tuple found on position = ",j2);
             call fseek(R.plik, j2);
             Rec := fget(R.plik);
             R.ak := R.RecToTuple(rec);
	     call SetCursor(6,1);
             call R.DrukujKrotke;
	   else (*nie znaleziono *)
	     call SetCursor(24,7);
             writeln(" tuple not found");
      	   fi ;
         fi (*wyboru klucza*);
       fi (*cha ='c'*)
     fi (*when 's'*);
 
 
 
   when 'p': (*show the previous tuple*)
 
         call SetCursor(4,19);
	 call Reverse;
	 write("which index: authors(a)? or positions(p)?  ");
         cha := chr(inchar);
	 	writeln(cha);
	 call Normal;	
         if cha = 'a'
         then
	    if j1>0
            then (*aktualna krotka jest okreslona *)
              call R.Index(1).PrevKey(R.IA.akl,j1);
	      if extrem
	      then
	        extrem := false;
		j1 :=0;
		R.IA.akl := R.IA.new klucz;
	      else
	        call SetCursor(24,7);
                write("tuple found on position = ",j1);
                call fseek(R.plik, j1);
                Rec := fget(R.plik);
                R.ak := R.RecToTuple(Rec);
		call SetCursor(6,1);
                call R.DrukujKrotke;
	      fi;
           else (*  *)
	     call SetCursor(24,7);
             write("no key has been located yet");
           fi;
	 else
	    if j2>0
            then (*aktualna krotka jest okreslona *)
              call R.Index(2).PrevKey(R.IB.akl,j2);
	      if extrem
	      then
	        extrem := false;
	      else
	        call SetCursor(24,7);
                write("tuple found on position = ",j2);
                call fseek(R.plik, j2);
                Rec := fget(R.plik);
                R.ak := R.RecToTuple(Rec);
		call SetCursor(6,1);
                call R.DrukujKrotke;
	      fi;
           else (*  *)
	     call SetCursor(24,7);
             writeln("no key has been located yet");
           fi;
        fi (* prev *);
 
 
   when 'm': (*min or max*)
     call Reverse;
     call SetCursor(3,25);
     write("searching index of: authors(a)? or positions(p)?");
     cha := chr(inchar);
	 	call Normal;
		writeln(cha);
     if cha ='a'
     then
       call Reverse;
       call SetCursor(4,25);
       write("searching index of authors: min(i)? or max(x)?");
       cha := chr(inchar);
           call Normal;
           writeln(cha);
	call SetCursor(5,1);
        if cha = 'i'
        then
            call R.IA.MinKey(R.IA.akl, j1);
            call SetCursor(24,7);
            writeln(" min key found on position = ",j1);
            call fseek(R.plik, j1);
            Rec := fget(R.plik);
            R.ak := R.RecToTuple(Rec);
	    call SetCursor(6,1);
            call R.DrukujKrotke;
          else
            call R.IA.MaxKey(R.IA.akl, j1);
	    call SetCursor(24,7);
            writeln("max key found on position = ",j1);
            call fseek(R.plik, j1);
            Rec := fget(R.plik);
            R.ak := R.RecToTuple(Rec);
	    call SetCursor(6,1);
            call R.DrukujKrotke;
       fi;
     else (*wg pozycji*)
       call Reverse;
       call SetCursor(4,25);
       write("searching index of positions: min(i)? or max(x)?");
       cha := chr(inchar);
       call Normal;
       writeln(cha);
       call SetCursor(24,7);
       if cha = 'i'
       then
            call R.IB.MinKey(R.IB.akl, j2);
            writeln("tuple found on position = ",j2);
            call fseek(R.plik, j2);
            Rec := fget(R.plik);
            R.ak := R.RecToTuple(Rec);
	    call SetCursor(6,1);
            call R.DrukujKrotke;
          else
            call R.IB.MaxKey(R.IB.akl, j2);
            writeln("tuple found on position = ",j2);
            call fseek(R.plik, j2);
            Rec := fget(R.plik);
            R.ak := R.RecToTuple(Rec);
	    call SetCursor(6,1);
            call R.DrukujKrotke;
      fi;
     fi;  (* end of minmax utility *)
 
 
   when 'n': (*show the next tuple*)
         call SetCursor(4,19);
	 call Reverse;
	 write("which index: authors(a)? or positions(p)?  ");
         cha := chr(inchar);
	 writeln(cha);
	 call Normal;	
	 call SetCursor(24,7);
         if cha = 'a'
         then
	    if j1>0
            then (*aktualna krotka jest okreslona *)
              call R.Index(1).NextKey(R.IA.akl,j1);
	      if extrem
	      then
	        extrem := false;
	      else
                writeln("tuple found on position = ",j1);
                call fseek(R.plik, j1);
                Rec := fget(R.plik);
                R.ak := R.RecToTuple(Rec);
		call SetCursor(6,1);
                call R.DrukujKrotke;
	      fi;
           else (*  *)
             writeln("no key has been located yet");
           fi;
	 else
	    if j2>0
            then (*aktualna krotka jest okreslona *)
              call R.Index(2).NextKey(R.IB.akl,j2);
	      if extrem
	      then
	        extrem := false;
	      else
                writeln("tuple found on position = ",j2);
                call fseek(R.plik, j2);
                Rec := fget(R.plik);
                R.ak := R.RecToTuple(Rec);
		call SetCursor(6,1);
                call R.DrukujKrotke;
	      fi;
           else (*  *)
             writeln("no key has been located yet");
           fi;
        fi (*Next*);
 
   when 'd': (*delete the actual tuple*)
     call Reverse;
     call SetCursor(3,25);
     write("from index of: authors(a)? or positions(p)?");
     cha := chr(inchar);
     call Normal;
     writeln(cha);
 
     if cha ='a'
     then (* ustawic aktualna krotke*)
 
     else
 
     fi;
 
     call SetCursor(25,4);
     call Blink;
     call Reverse;
     write("DELETING the actual tuple");
     call R.Delete(R.ak);
 
 
   otherwise
      call SetCursor(25,4);
      write("REPEAT")
   esac;
 
    call Normal;
    call SetCursor(25,1);
    write("                                           ");
    call Blink;
    call Reverse;
    call SetCursor(25,60);
    write("press a key");
    call Normal;
    call Bold;
    call SetCursor(1,76);
    write(chr(32));
    i:=inchar;
    call Normal;	
    call SetCursor(3,1);
    writeln(
 "                                                                         ");
    writeln(
 "                                                                         ");
    writeln(
 "                                                                         ");
    writeln(
 "                                                                         ");
    writeln(
 "                                                                         ");
    writeln(
 "                                                                         ");
    writeln(
 "                                                                         ");
    writeln(
 "                                                                         ");
    writeln(
 "                                                                         ");
    writeln(
 "                                                                         ");
    writeln(
 "                                                                         ");
    writeln(
 "                                                                         ");
    call SetCursor(24,1);
    writeln(
 "                                                                         ");
    write(
 "                                                                         ");
 
    call Normal;
    call Blink;
    call Reverse;
    call SetCursor(25,60);
    write("make your choice");
    call Normal;
    call Bold;
    call SetCursor(1,76);
    write(chr(32));
    i := inchar;
    cha := chr(i);
    call SetCursor(1,76);
    writeln(chr(i));
    call SetCursor(25,60);
    write("                    ");
    call SetCursor(5,1);
  od
 end
end Test19;