DEFINITION MODULE BTree;


CONST  Order = 42; 
       (* Mit dieser Ordnung erh„lt man TSIZE(PageType) von 512 k *)
       nn = Order;
       n = (nn DIV 2);
       Empty= -1D;
       TreeRoot=0D;


TYPE (* TYPEn f�r den Bayer Baum *)


     FileType = ( TheData, NumIndex, GerIndex, PorIndex );  
     (* Unterscheidung zwischen Daten und IndexFiles             *)
     (* und den verschiedenen IndexArten. Dieser Aufz„hlungsTyp  *)
     (* wird vor allem f�r die Querverweisliste bei multiplen    *)
     (* Schl�sseln gebraucht (-> BaseType) => FileType so ordnen *)
     (* daž bei Next : ARRAY [FileType] keine unn”tigen Eintr„ge *)
     (* entstehen, d.h. zuerst alle IndexTypen die keine doppelten *)
     (* Schl�ssel zulassen und dann die anderen (oder so ... ) *)
     

     KeyType = LONGCARD; (* Um diesen Typ zu „ndern sind auch Anpassungen *)
       			 (* im  IMPLEMENTATION MODULE n”tig !!! *)

     EntryType = ARRAY [0..43] OF CHAR;
     
     DataType = RECORD
		   Inhalt : ARRAY[0..4] OF EntryType;
		   Flags  : ARRAY [0..5] OF CHAR; 
		(* 0..3 werden verwendet, 4,5 sind nur F�llBytes *)
		(* um auf TSIZE(PageType) von 256 Bytes zu kommen *)
		END(*RECORD*);

     DataPtr = LONGINT; (* Zeigt auf die Lage der Daten im File *)
     
                        (* Wenn man DataPtr bzw. PagePtr auf INTEGER *)
                        (* „ndern m”chte sind einige Žnderungen im  *)
                        (* IMPLEMENTATION MODULE notwendig! *)
                        
     PagePtr = LONGINT; (* Position einer Seite im File *)

     KeyArray =  ARRAY [NumIndex..PorIndex] OF KeyType;
     
     BaseType = RECORD
		  Flag : BOOLEAN;
		  Next : ARRAY [GerIndex..PorIndex] OF DataPtr;
		  (* Querverweisliste (doppelt verkettet) f�r die Verwendung *)
		  (* von mehreren Eintr„gen pro Schl�ssel *)
		  Prev : ARRAY [GerIndex..PorIndex] OF DataPtr;
		  Key  : KeyArray;
		  (*Key  : ARRAY [NumIndex..PorIndex] OF KeyType;*)
		  (* In diesem Feld werden s„mtliche Schl�ssel untergebracht *)
		  Data : DataType;
		END(*RECORD*);

     ItemType = RECORD
		   Key	    : KeyType;
		   RecordNr : DataPtr;
		   Ptr	    : PagePtr;
		END(*RECORD*);

     PageType = RECORD
		   Flag : BOOLEAN;
		   Anz	: CARDINAL;
		   Ptr0 : PagePtr;
		   Item : ARRAY [1..nn] OF ItemType;
		END(*RECORD*);


     FileOf = RECORD 
(* Dieser Typ schleppt so ziemlich alles mit sich rum *)
(* was f�r die Verwaltung der Datei interressant ist *)
		 Name : ARRAY [0..127] OF CHAR; 
		 (* Datei-Name *)
		 Handle : INTEGER; 
		 (* GEMDOS- Filehandle *)
		 CASE Type : FileType OF 
		 (* Je Nachdem ob es sich um ein Daten oder IndexFile *)
		 (* handelt Pointer auf unterschiedliche Typen        *)
		 (* Aužerdem werden durch den Eintrag im TAG-Feld die *)
		 (* verschiedenen Querverweislisten verwaltet         *)
				    TheData : RecordPtr : POINTER TO BaseType;
				    ELSE     RecordPtr1 : POINTER TO PageType;
			       END(*CASE*);
		 RecordSize : LONGINT; (* LONG(TSIZE(Inhalt)) *) 
		 (* L„nge eines Records *)
		 Current : LONGINT; 
		 Last : LONGINT; (* PagePtr bzw DataPtr *) 
		 (* Letzter Eintrag in der Datei                  *) 
		 (* gibt gleichzeitig die Dateigr”že in Records an *)
                 MultipleKeys : BOOLEAN; 
                 (* Flag ob mehrere Eintr„ge unter einem Schl�ssel erlaubt sind *)
	     END(*RECORD*);

	PrintDataProc = PROCEDURE( DataType);     

(* for internal use only :   *)

PROCEDURE Get( VAR File : FileOf; Pos : LONGINT);
PROCEDURE Put( VAR File : FileOf; Pos : LONGINT);
(*
PROCEDURE FileLength(FileName : ARRAY OF CHAR; length : LONGINT) :BOOLEAN;
  *)
  
  

PROCEDURE Create(VAR File : FileOf); (* Eine neue Datei anlegen. Ist eine Datei dieses Namens schon vorhanden wird sie gel”scht *)
PROCEDURE Start(VAR File : FileOf); (* Datei ™fnen. Die Datei muž vorhanden sein !!! *)
PROCEDURE Close(VAR File: FileOf);  (* Datei Schliežen. Wichtig sonst gehen alle Daten verloren !!*)

PROCEDURE PutData(VAR DataBase : FileOf; Data : DataType;  Reference : DataPtr);
PROCEDURE GetData(VAR DataBase : FileOf; VAR Data : DataType; VAR Keys : KeyArray; Reference :DataPtr);

PROCEDURE AddKey(VAR Index, DataBase : FileOf; NewKey : KeyType; Reference : DataPtr): BOOLEAN;
PROCEDURE AddData( VAR DataBase : FileOf; NewData : DataType) : DataPtr;

PROCEDURE Delete(VAR Index, DataBase : FileOf; Key : KeyType; VAR DataPointer : DataPtr): BOOLEAN;

PROCEDURE SearchPtr(VAR Index, DataBase : FileOf; Page : PagePtr; Key : KeyType; VAR found : BOOLEAN) : DataPtr;

PROCEDURE SearchFirst(VAR Index, DataBase : FileOf; Key : KeyType; VAR Data : DataType; VAR Keys : KeyArray): BOOLEAN;

PROCEDURE SearchNext(VAR Index, DataBase : FileOf; VAR Data : DataType; VAR Keys : KeyArray) : BOOLEAN;
PROCEDURE SearchPrevious(VAR Index, DataBase : FileOf; VAR Data : DataType;VAR Keys : KeyArray) : BOOLEAN;
(*   Suche bei Schl�sselgleichheit  *)

PROCEDURE First(VAR Index, DataBase : FileOf; VAR Key : KeyType; VAR Data : DataType; VAR Keys : KeyArray);
PROCEDURE Last (VAR Index, DataBase : FileOf; VAR Key : KeyType; VAR Data : DataType; VAR Keys : KeyArray);

PROCEDURE Next(VAR Index, DataBase : FileOf; Key : KeyType; VAR NextKey : KeyType; VAR NextData: DataType; VAR Keys : KeyArray) : BOOLEAN;
PROCEDURE Previous(VAR Index, DataBase : FileOf;  Key : KeyType; VAR NextKey : KeyType; VAR NextData: DataType; VAR Keys : KeyArray) : BOOLEAN;

PROCEDURE PrintTree(VAR Index, DataBase : FileOf; Tree : PagePtr; Tiefe : CARDINAL; OutProc : PrintDataProc);

END BTree.