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;
(***************************************************************)
(*  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;