Programmer 7500/MAX_PROGRAMMERS.iso/PASCAL/MADTRB40.ZIP/MSTREES.PAS

Pascal/Delphi Source File | 1986-05-04 | 42.3 KB | 1,040 lines

{ *************************************************************************** }
{ *                                                                         * }
{ *                         MEDIAN SPLIT TREE PROGRAM                       * }
{ *                                                                         * }
{ *                               Class: CS 577                             * }
{ *                          Instructor: Manber                             * }
{ *                                                                         * }
{ *                          Written by Chris Maeder                        * }
{ *                  Edited and Compiled using Turbo Pascal                 * }
{ *                              on an IBM PC                               * }
{ *                                                                         * }
{ *************************************************************************** }



Const
  MAX_KEYS_PER_NODE=3;                 { maximum number of look-up keys for any given tree node,
                                         not including split key }
  MAX_KEY_SIZE=15;                     { maximum size of string used to store a key }



Type
  KeyString=String[MAX_KEY_SIZE];      { a string type used to store look-up keys }
  FrequencyType=0..MAXINT;             { allowable integer values that a key's frquency value can take on }

  NodeKeyElement=                      { a look-up key node element type }
    Record
      Key:KeyString;                   { look-up key string }
      Frequency:FrequencyType;         { frequency value }
    End; { NodeKeyElement record }

  KeyArray=                            { an array of look-up keys }
    Array[1..MAX_KEYS_PER_NODE] of NodeKeyElement;

  TreeNodePtr=^TreeNodeType;           { a pointer which points to the tree node type 'TreeNodeType' }
  TreeNodeType=                        { a n-MST node of }
    Record
      NodeKeys:KeyArray;               { an array of look-up keys }
      SplitKey:NodeKeyElement;         { a key that splits the left and right subtree keys }
      Left:TreeNodePtr;                { a pointer to tree node's left son }
      Right:TreeNodePtr;               { a pointer to tree node's right son }
    End; { TreeNodeType record }

  L_L_ElementPtr=^L_L_ElementType;     { a pointer to the doubly linked list element type 'L_L_ElementType' }
  L_L_ElementType=                     { a doubly linked list element }
    Record
      Key:KeyString;                   { look-up key }
      Frequency:FrequencyType;         { frequency value }
      Front:L_L_ElementPtr;            { a pointer to the forward element }
      Back:L_L_ElementPtr;             { a pointer to the rearward element }
    End; { L_L_ElementType record }



Var
  L_L_HeadPtr:L_L_ElementPtr;          { a pointer to the head of the doubly linked list }
  L_L_TailPtr:L_L_ElementPtr;          { a pointer to the tail of the doubly linked list }
  MST_RootPtr:TreeNodePtr;             { a pointer to the root node of the MST }
  HoldPtr:Integer;                     { a pointer used to temporarily store console screen output vector }



Procedure InitProgram;

{ This procedure initializes all the global variables and pointers used in this
  program. }

Begin   { InitProgram }
  L_L_HeadPtr:=Nil;
  L_L_TailPtr:=Nil;
  HoldPtr:=ConOutPtr;
End;    { InitProgram }



Procedure HardCopy(    On:Boolean);

{ This procedure reroutes the output from the screen to the printer. }

Begin   { HardCopy }
  If On Then
    Begin
      HoldPtr:=ConOutPtr;
      ConOutPtr:=LstOutPtr;
    End { If On }
  Else
    Begin
      ConOutPtr:=HoldPtr;
    End; { Else }
End;    { HardCopy }



Procedure ReadInputFileModule;

{ *************************************************************************** }
{ *                                                                         * }
{ *                         READ INPUT FILE MODULE                          * }
{ *                                                                         * }
{ *     This module reads the file entries out of the declared input        * }
{ *     file.  Each file entry contains a look-up key and a value           * }
{ *     corresponding to its frequency count.                               * }
{ *                                                                         * }
{ *     The file entries are assumed to already be in sorted order          * }
{ *     according to the look-up keys lexical value.  These entries are     * }
{ *     then placed in a doubly linked list, maintaining their sorted       * }
{ *     lexical order.                                                      * }
{ *                                                                         * }
{ *************************************************************************** }

Const
  MAX_FILE_ENTRY_SIZE=50;              { maximum size of the file entry string }
  FILE_NAME='KeyData1.Dat';            { name of the input data file }

Type
  FileEntryString=String[MAX_FILE_ENTRY_SIZE]; { a string type used to store file entries }

Var
  DataFile:Text;                       { text file }
  FileEntry:FileEntryString;           { variable used in reading entries out of input data file }



  Procedure RemoveFirstEntryFromString(Var Text:FileEntryString);

  { This procedure removes the first text entry from the passed text string and
    returns the new truncated text string.  The text entries in the passed text
    string are assumed to be delinated by one space.  See the following
    example.

                Passed:     Entry1 Entry2 Entry3
                Returned:   Entry2 Entry3                                  }

  Begin   { RemoveFirstEntryFromString }
    If Pos(' ',Text)<>0 Then
      Text:=Copy(Text,(Pos(' ',Text)+1),(Length(Text)-Pos(' ',Text)));
  End;    { RemoveFirstEntryFromString }



  Procedure ReturnFirstEntryFromString(Var Text:FileEntryString);

  { This procedure removes the first text entry from the passed text string and
    returns the first text entry.  The text entries in the passed text string
    are assumed to be delinated by one space.  See the following example.

                Passed:     Entry1 Entry2 Entry3
                Returned:   Entry1                                         }

  Begin   { ReturnFirstEntryFromString }
    If Pos(' ',Text)<>0 Then
      Text:=Copy(Text,1,(Pos(' ',Text)-1));
  End;    { ReturnFirstEntryFromString }



  Function DetermineKeyFromFileEntry(    Entry:FileEntryString):KeyString;

  { This function is passed a file entry which contains a look-up key as the
    first entry.  This function picks off the look-up key from the file entry
    and passes the look-up key back. }

  Begin   { DetermineKeyFromFileEntry }
    ReturnFirstEntryFromString(Entry);
    DetermineKeyFromFileEntry:=Entry;
  End;    { DetermineKeyFromFileEntry }



  Function DetermineFrequencyFromFileEntry(    Entry:FileEntryString):FrequencyType;

  { This function is passed a file entry which contains a frequency count for a
    look-up key as the second entry.  This function picks off the frequency
    count from the file entry and passes the frequency count back. }

  Var
    Frequency:Integer;                 { a temporary variable used in conversion of string to real }
    ErrorCode:Integer;                 { a variable used in checking for error in conversion }

  Begin   { DetermineFrquencyFromFileEntry }
    RemoveFirstEntryFromString(Entry);
    ReturnFirstEntryFromString(Entry);
    Val(Entry,Frequency,ErrorCode);
    DetermineFrequencyFromFileEntry:=Frequency;
  End;    { DetermineFrquencyFromFileEntry }



  Procedure AddKeyToLinkedList(Var HeadPtr,
                                   TailPtr:  L_L_ElementPtr;
                                   FileEntry:FileEntryString);

  { This procedure places the passed file entry onto the end of the doubly
    linked list.  By adding the passed file entry to the end of the doubly
    linked list maintains the assumed lexical ordering of the keys. }

  Var
    New_L_L_Element:L_L_ElementPtr;    { a pointer to a new doubly linked list element which will be added to the tail
                                         of the passed linked list }

  Begin   { AddKeyToLinkedList }
    New(New_L_L_Element);              { create a new queue element to add to the end of the passed linked list }
    With New_L_L_Element^ Do
      Begin                            { routine to enter information into new linked list element }
        Key:=DetermineKeyFromFileEntry(FileEntry);
        Frequency:=DetermineFrequencyFromFileEntry(FileEntry);
        Front:=Nil;                    { set forward pointer to Nil }
        Back:=Nil;                     { set backward pointer to Nil }
      End; { With New_L_L_Element }
    If HeadPtr=Nil Then
      Begin                            { Special Case One - linked list not yet in existance }
        HeadPtr:=New_L_L_Element;      { set passed linked list head pointer to point to first element in the linked list }
        TailPtr:=New_L_L_Element;      { set passed linked list tail pointer to point to first element in the linked list }
      End { If HeadPtr }
    Else
      Begin                            { Special Case Two - linked list in existance }
        TailPtr^.Back:=New_L_L_Element;  { link new element to end of linked list }
        New_L_L_Element^.Front:=TailPtr; { link new element to end of linked list }
        TailPtr:=New_L_L_Element;        { increment tail pointer }
      End; { Else }
  End;    { AddKeyToLinkedList }



Begin   { ReadInputFileModule }
  Assign(DataFile,FILE_NAME);          { assign to a disk file }
  Reset(DataFile);                     { open the file for reading }
  Repeat                               { read in the file entries }
    ReadLn(DataFile,FileEntry);
    AddKeyToLinkedList(L_L_HeadPtr,L_L_TailPtr,FileEntry);
  Until Eof(DataFile);                 { read until end of file found }
  Close(DataFile);                     { close the disk file }
End;    { ReadInputFileModule }



Procedure PrintLinkedList(    L_L_HeadPtr,
                              L_L_TailPtr:L_L_ElementPtr);

{ This procedure prints out the the doubly linked list containing the look-up
  keys. }

Var
  L_L_NodePtr:L_L_ElementPtr;          { a pointer used to traverse the doubly linked list }

Begin   { PrintLinkedList }
  WriteLn;
  WriteLn;
  WriteLn('LINKED  LIST  OF LOOK-UP KEYS AND');
  WriteLn('CORRESPONDING FREQUENCIES FOLLOWS:');
  WriteLn('----------------------------------');
  WriteLn;
  WriteLn;
  If L_L_HeadPtr<>Nil Then
    Begin
      L_L_NodePtr:=L_L_HeadPtr;
      WriteLn(L_L_NodePtr^.Key,' ',L_L_NodePtr^.Frequency);
      While L_L_NodePtr<>L_L_TailPtr Do
        Begin
          L_L_NodePtr:=L_L_NodePtr^.Back;
          WriteLn(L_L_NodePtr^.Key,' ',L_L_NodePtr^.Frequency);
        End; { While L_L_NodePtr }
    End { If L_L_HeadPtr }
  Else
    WriteLn('No elements in linked list');
End;    { PrintLinkedList }



Procedure Build_MST_Module;

{ *************************************************************************** }
{ *                                                                         * }
{ *                     BUILD MEDIAN SPLIT TREE MODULE                      * }
{ *                                                                         * }
{ *     This module controls the building of the n-MST (median split        * }
{ *     tree).  There are n entries per node where the n-1 most frequently  * }
{ *     accessed keys in the subtree and the median of the rest of the      * }
{ *     keys in the subtree.                                                * }
{ *                                                                         * }
{ *     Observe that n=1 produces a balanced binary search tree, n=2        * }
{ *     produces a conventional median split tree, and n=total number of    * }
{ *     look-up keys produces a sequential search.                          * }
{ *                                                                         * }
{ *************************************************************************** }

Type
  ChildType=(LEFT,RIGHT,ROOT);         { an enumerated data type used to determine how to link child
                                         node with parent node }



  Procedure SortKeyArray(Var SetOfKeys:KeyArray);

  { This procedure controls the quicksort on the passed array of look-up keys
    so that they are sorted in ascending order according to their lexical ( or
    alphabetical) order. }



    Procedure QuickSort(    LowElement,
                            HighElement:Integer;
                        Var SetOfKeys:  KeyArray);

    { This is a recursive procedure that sorts the passed array of look-up keys
      by first determining a pivotal element and then partitions the remaining
      elements (between LowElement and HighElement of the passed SetOfKeys)
      according to that pivotal element. }

    Var
      LowIndex:Integer;                  { an incremented index starting at the low element in the passed set of keys }
      HighIndex:Integer;                 { an incremented index starting at the high element in the passed set of keys }
      PivotalKey:KeyString;              { a look-up key which acts as a pivotal element }
      TemporaryNodeElement:NodeKeyElement; { a node key element used in transposing elements in the set of keys }

    Begin   { QuickSort }
      LowIndex:=LowElement;
      HighIndex:=HighElement;
      PivotalKey:=SetOfKeys[(LowElement+HighElement) Div 2].Key;
      Repeat
        While SetOfKeys[LowIndex].Key<PivotalKey Do
          LowIndex:=LowIndex+1;
        While PivotalKey<SetOfKeys[HighIndex].Key Do
          HighIndex:=HighIndex-1;
        If LowIndex<=HighIndex Then
          Begin { transpose elements in key array }
            TemporaryNodeElement:=SetOfKeys[LowIndex];
            SetOfKeys[LowIndex]:=SetOfKeys[HighIndex];
            SetOfKeys[HighIndex]:=TemporaryNodeElement;
            LowIndex:=LowIndex+1;
            HighIndex:=HighIndex-1;
          End; { If LowIndex }
      Until LowIndex>HighIndex;
      If LowElement<HighIndex Then
        QuickSort(LowElement,
                  HighIndex,
                  SetOfKeys);
      If LowElement<HighElement Then
        QuickSort(LowIndex,
                  HighElement,
                  SetOfKeys);
    End;    { QuickSort }



  Begin   { SortKeyArray }
    QuickSort(1,
              MAX_KEYS_PER_NODE,
              SetOfKeys);
  End;    { SortKeyArray }



  Function EmptyLinkedList(    L_L_HeadPtr:L_L_ElementPtr):Boolean;

  { This function is used to check if the passed linked list is empty.  If the
    linked list is empty, this function returns as true, else it returns as
    false. }

  Begin   { EmptyLinkedList }
    If L_L_HeadPtr=Nil Then
      EmptyLinkedList:=True
    Else
      EmptyLinkedList:=False;
  End;    { EmptyLinkedList }



  Function SplitValue(    NumberOf_L_L_Elements:Integer):Integer;

  { This function determines the index to the key that should be used as the
    split key value for the passed number of elements remaining in the doubly
    linked list.

    Observe that instead of selecting the median as the split value, a more
    balanced MST can be formed by selecting the key whose index in the lexical
    order is maximized where the split value is given by

            SplitValue=((MAX_KEYS_PER_NODE+1)*IntegerMultiplier)+1

    closest to median value for the passed number of linked list elements.

    This algorithm produces an unbalanced, but complete tree in which all but
    at most one node are completely filled with look-up keys including split
    keys, in which the overflow tends toward the left most son. }

  Var
    IntegerMultiplier:Integer;         { an incremented integer used as an exponent }
    MedianValue:Integer;               { an integer variable used to temporaily store the median value }
    PossibleSplitValue:Integer;        { an integer variable used in determining the split value }

  Begin   { SplitValue }
    IntegerMultiplier:=1;              { initialized incremented integer }
    MedianValue:=(NumberOf_L_L_Elements Div 2);
    PossibleSplitValue:=1;             { initialize split value }
    While (Abs((IntegerMultiplier*(MAX_KEYS_PER_NODE+1))+1)-MedianValue<=
          Abs(PossibleSplitValue-MedianValue)) Do
      Begin
        PossibleSplitValue:=(IntegerMultiplier*(MAX_KEYS_PER_NODE+1))+1;
        IntegerMultiplier:=IntegerMultiplier+1;
      End; { While Abs }
    SplitValue:=PossibleSplitValue;
  End;    { SplitValue }



  Procedure DetermineSplitKey(Var L_L_HeadPtr,
                                  L_L_TailPtr,
                                  L_L_SplitKey,
                                  Left_L_L_HeadPtr,
                                  Left_L_L_TailPtr,
                                  Right_L_L_HeadPtr,
                                  Right_L_L_TailPtr:L_L_ElementPtr);

  { This procedure from the linked list returns the median split key element
    and the newly split linked list (at the split key element) to the calling
    routine. }

  Var
    Count:Integer;                     { a variable used to determine number of elements in the passed linked list }
    L_L_Element:L_L_ElementPtr;        { a pointer used in traversing the passed linked list }
    L_L_Index:Integer;                 { a variable used to traverse the linked list }

  Begin   { DetermineSplitKey }
    If Not EmptyLinkedList(L_L_HeadPtr) Then
      Begin
        { determine number of elements in passed linked list }
        Count:=1;                      { initialize counter }
        L_L_Element:=L_L_HeadPtr;      { initialize traversal element }
        While L_L_Element<>L_L_TailPtr Do
          Begin
            Count:=Count+1;            { increment counter }
            L_L_Element:=L_L_Element^.Back; { increment pointer }
          End; { While L_L_Element }
        { locate split key element }
        L_L_Element:=L_L_HeadPtr;      { initialize traversal element }
        For L_L_Index:=2 To SplitValue(Count) Do
          L_L_Element:=L_L_Element^.Back;
        { split key has been found }
        L_L_SplitKey:=L_L_Element;
        { now split current linked list about split key }
        { split left half of linked list }
        If L_L_SplitKey<>L_L_HeadPtr Then
          Begin
            Left_L_L_HeadPtr:=L_L_HeadPtr;
            Left_L_L_TailPtr:=L_L_SplitKey^.Front;
            Left_L_L_TailPtr^.Back:=Nil;
          End { If L_L_SplitKey }
        Else
          Begin
            Left_L_L_HeadPtr:=Nil;
            Left_L_L_TailPtr:=Nil;
          End; { Else }
        { split right half of linked list }
        If L_L_SplitKey<>L_L_TailPtr Then
          Begin
            Right_L_L_HeadPtr:=L_L_SplitKey^.Back;
            Right_L_L_HeadPtr^.Front:=Nil;
            Right_L_L_TailPtr:=L_L_TailPtr;
          End { If L_L_SplitKey }
        Else
          Begin
            Right_L_L_HeadPtr:=Nil;
            Right_L_L_TailPtr:=Nil;
          End { Else }
      End { If Not EmptyLinkedList }
    Else
      Begin
        Left_L_L_HeadPtr:=Nil;
        Left_L_L_TailPtr:=Nil;
        Right_L_L_HeadPtr:=Nil;
        Right_L_L_TailPtr:=Nil;
        L_L_SplitKey^.Key:='';
        L_L_SplitKey^.Frequency:=0;
      End; { Else }
    L_L_SplitKey^.Front:=Nil;          { disconnect link }
    L_L_SplitKey^.Back:=Nil;           { disconnect link }
  End;    { DetermineSplitKey }



  Procedure RemoveElementFromLinkedList(Var L_L_HeadPtr,
                                            L_L_TailPtr,
                                            RemoveElement:L_L_ElementPtr);

  { This procedure removes the passed element from the passed doubly linked
    list.

    Example Linked List:

                               ______
                __       __   |  __  |   __       __       __
        Nil<---|__|<--->|__|<-- |__| -->|__|<--->|__|<--->|__|--->Nil

        HeadPtr--^                ^--RemoveElement          ^--TailPtr


    Note that there are four special cases when deleting an element from the
    passed linked list:

        1. Delete last remaining element from linked list.
        2. Delete element from front of linked list.
        3. Delete element from end of linked list.
        4. Delete element from middle of linked list.           }

  Begin   { RemoveElementFromLinkedList }
    { Special Case One - Check if deleting last remaining element from linked list }
    If L_L_HeadPtr=L_L_TailPtr Then
      Begin { delete last remaining element from linked list }
        L_L_HeadPtr:=Nil;
        L_L_TailPtr:=Nil;
      End { If L_L_HeadPtr }
    Else
      { Special Case Two - Check if deleting element from front of linked list }
      If L_L_HeadPtr=RemoveElement Then
        Begin { delete element from front of linked list }
          RemoveElement^.Back^.Front:=Nil; { release link with list }
          L_L_HeadPtr:=RemoveElement^.Back; { increment head pointer }
        End { If L_L_HeadPtr }
      Else
        { Special Case Three - Check if deleting element from rear of linked list }
        If L_L_TailPtr=RemoveElement Then
          Begin { delete element from end of linked list }
            RemoveElement^.Front^.Back:=Nil; { release link with list }
            L_L_TailPtr:=RemoveElement^.Front; { decrement tail pointer }
          End { If L_L_TailPtr }
        Else
          { Special Case Four - Deleting element from middle of linked list }
          Begin
            RemoveElement^.Front^.Back:=RemoveElement^.Back; { re-link list }
            RemoveElement^.Back^.Front:=RemoveElement^.Front; { re-link list }
          End; { Else }
  End;    { RemoveElementFromLinkedList }



  Procedure DetermineMostFrequentKey(Var L_L_HeadPtr,
                                         L_L_TailPtr,
                                         FrequentKey:L_L_ElementPtr);

  { This procedure determines the most frequent occurring look-up key in the
    passed linked list of look-up keys, using their corresponding frequency
    values.

    This procedure then returns this most frequently occurring key to the
    calling routine, while also removing the key from the passed linked list.

    Observe that this procedure uses a sequential search to find the most
    frequently occurring key.  This algorithm is slow and clearly could be
    improved by keeping the keys sorted both in lexical and frequency order.
    Since the median split tree is normally only built once and then used, it
    was decided to keep this implementation simple. }

  Var
    L_L_Element:L_L_ElementPtr;         { a pointer used in traversing the passed linked list }

  Begin   { DetermineMostFrequentKey }
    If Not EmptyLinkedList(L_L_HeadPtr) Then
      Begin { determine most frequent key in linked list }
        FrequentKey:=L_L_HeadPtr;      { initialize the most frequent key pointer }
        L_L_Element:=L_L_HeadPtr;      { initialize linked list traversing pointer }
        While L_L_Element<>L_L_TailPtr Do
          Begin
            L_L_Element:=L_L_Element^.Back; { increment the traversing pointer }
            If L_L_Element^.Frequency>FrequentKey^.Frequency Then
              FrequentKey:=L_L_Element;
          End; { While L_L_Element }
        RemoveElementFromLinkedList(L_L_HeadPtr,
                                    L_L_TailPtr,
                                    FrequentKey);
        FrequentKey^.Front:=Nil;
        FrequentKey^.Back:=Nil;
      End { If Not EmptyLinkedList }
    Else
      With FrequentKey^ Do
        Begin { linked list is empty, hence return an empty entry }
          Key:='';
          Frequency:=0;
          Front:=Nil;
          Back:=Nil;
        End; { With FrequentKey }
  End;    { DetermineMostFrequentKey }



  Procedure Fill_MST_Node(Var L_L_HeadPtr,
                              L_L_TailPtr:      L_L_ElementPtr;
                          Var TreeNode:         TreeNodePtr;
                          Var Left_L_L_HeadPtr,
                              Left_L_L_TailPtr,
                              Right_L_L_HeadPtr,
                              Right_L_L_TailPtr:L_L_ElementPtr);

  { This procedure takes the passed linked list of look-up keys, takes the n
    most frequently occurring keys from the linked list, places them into the
    passed key array, sorts the keys according to their lexical order,
    determines the split key and then splits the linked list accordingly, and
    finally returns the passed tree node and the split linked list back to the
    calling routine. }

  Var
    ArrayIndex:Integer;                { an index counter used in filling the look-up key array }
    L_L_Element:L_L_ElementPtr;        { a pointer to a removed linked list element }

  Begin   { Fill_MST_Node }
    { fill the node's key array }
    For ArrayIndex:=1 To MAX_KEYS_PER_NODE Do
      Begin
        DetermineMostFrequentKey(L_L_HeadPtr,
                                 L_L_TailPtr,
                                 L_L_Element);
        With TreeNode^ Do
          Begin
            NodeKeys[ArrayIndex].Key:=L_L_Element^.Key;
            NodeKeys[ArrayIndex].Frequency:=L_L_Element^.Frequency;
          End; { With TreeNode }
      End; { For ArrayElement }
    SortKeyArray(TreeNode^.NodeKeys);  { sort the keys according to their lexical order }
    { determine split key and split linked list }
    DetermineSplitKey(L_L_HeadPtr,
                      L_L_TailPtr,
                      L_L_Element,
                      Left_L_L_HeadPtr,
                      Left_L_L_TailPtr,
                      Right_L_L_HeadPtr,
                      Right_L_L_TailPtr);
    With TreeNode^ Do
      Begin
        SplitKey.Key:=L_L_Element^.Key;
        SplitKey.Frequency:=L_L_Element^.Frequency;
        Left:=Nil;                     { set left child ptr to Nil }
        Right:=Nil;                    { set right child ptr to Nil }
      End; { With TreeNode^ }
  End;    { Fill_MST_Node }



  Procedure Build_MST_Node(Var L_L_HeadPtr,
                               L_L_TailPtr:   L_L_ElementPtr;
                           Var ParentTreeNode:TreeNodePtr;
                               ParentBranch:  ChildType);

  { This recursive procedure does the actual building of the n degree median
    split tree. }

  Var
    CurrentTreeNode:TreeNodePtr;       { a MST node pointer used in adding new nodes to the MST }
    Left_L_L_HeadPtr:L_L_ElementPtr;   { pointer to the newly split linked list of look-up keys }
    Left_L_L_TailPtr:L_L_ElementPtr;   { pointer to the newly split linked list of look-up keys }
    Right_L_L_HeadPtr:L_L_ElementPtr;  { pointer to the newly split linked list of look-up keys }
    Right_L_L_TailPtr:L_L_ElementPtr;  { pointer to the newly split linked list of look-up keys }

  Begin   { Build_MST_Node }
    If Not EmptyLinkedList(L_L_HeadPtr) Then
      Begin
        { build current node }
        New(CurrentTreeNode);          { allocate an MST node }
        Fill_MST_Node(L_L_HeadPtr,     { fill the MST node with keys from the linked list }
                      L_L_TailPtr,
                      CurrentTreeNode,
                      Left_L_L_HeadPtr,
                      Left_L_L_TailPtr,
                      Right_L_L_HeadPtr,
                      Right_L_L_TailPtr);
        { connect current tree node to parent tree node according to passed parent branch ( or child type ) }
        Case ParentBranch Of
          ROOT  : MST_RootPtr:=CurrentTreeNode;
          LEFT  : ParentTreeNode^.Left:=CurrentTreeNode;
          RIGHT : ParentTreeNode^.Right:=CurrentTreeNode;
        End; { Case ParentBranch }
        { build left son }
        Build_MST_Node(Left_L_L_HeadPtr,
                       Left_L_L_TailPtr,
                       CurrentTreeNode,
                       LEFT);
        { build right son }
        Build_MST_Node(Right_L_L_HeadPtr,
                       Right_L_L_TailPtr,
                       CurrentTreeNode,
                       RIGHT);
      End; { If Not EmptyLinkedList }
  End;    { Build_MST_Node }




Begin   { Build_MST_Module }
  Build_MST_Node(L_L_HeadPtr,
                 L_L_TailPtr,
                 MST_RootPtr,
                 ROOT);
End;    { Build_MST_Module }



Procedure Print_MST_Module;

{ *************************************************************************** }
{ *                                                                         * }
{ *                     PRINT MEDIAN SPLIT TREE MODULE                      * }
{ *                                                                         * }
{ *    This module prints out the median split tree node data in a form     * }
{ *    representing the tree structure that it is stored in.  It calls a    * }
{ *    recursive inorder traversal procedure 'PrintNodesInorder' that       * }
{ *    travels down the right most subtree first.                           * }
{ *                                                                         * }
{ *************************************************************************** }

Const
  Offset:Integer=15;                   { column offset used in printing of each tree level }

Type
  ChildType=(LEFT,RIGHT,ROOT);         { an enumerated data type used in printing out the proper branch for each child node }



  Procedure Print_MST_Node(   Node:  TreeNodePtr;
                              Level: Integer;
                              Branch:ChildType);

  { This procedure prints out the MST node with the proper branch attached. }

  Var
    NodeElement:Integer;               { a index counter to an array element }

  Begin   { Print_MST_Node }
    If Node=Nil Then
      Case Branch Of
        ROOT  : Begin
                  WriteLn(' ':Level*Offset,'Nil');    { write out split value }
                  WriteLn(' ':Level*Offset,'^ Split Key');
                  For NodeElement:=MAX_KEYS_PER_NODE DownTo ((MAX_KEYS_PER_NODE Div 2)+2) Do
                    WriteLn(' ':Level*Offset,'Nil'); { write out right elements }
                  WriteLn('-':Level*Offset,'Nil');   { write out center element }
                  For NodeElement:=(MAX_KEYS_PER_NODE Div 2) DownTo 1 Do
                    WriteLn(' ':Level*Offset,'Nil');  { write out left elements }
                End;
        RIGHT : Begin
                  WriteLn(' ':Level*Offset,'Nil');    { write out split value }
                  WriteLn(' ':Level*Offset,'^ Split Key');
                  For NodeElement:=MAX_KEYS_PER_NODE DownTo 2 Do
                    WriteLn(' ':Level*Offset,'Nil'); { write out elements }
                  WriteLn('/':Level*Offset,'Nil');   { write out left most element }
                End;
        LEFT  : Begin
                  WriteLn(' ':Level*Offset,'Nil');    { write out split value }
                  WriteLn(' ':Level*Offset,'^ Split Key');
                  WriteLn('\':Level*Offset,'Nil');   { write out right most element }
                  For NodeElement:=MAX_KEYS_PER_NODE-1 Downto 1 Do
                    WriteLn(' ':Level*Offset,'Nil'); { write out elements }
                End;
      End { Case Branch }
    Else { not a Nil node }
      With Node^ Do
        Case Branch Of
          ROOT  : Begin
                    If Length(SplitKey.Key)<>0 Then
                      WriteLn(' ':Level*Offset,SplitKey.Key,
                              ' ',SplitKey.Frequency)
                    Else
                      WriteLn(' ':Level*Offset,'Nil');
                    WriteLn(' ':Level*Offset,'^ Split Key');
                    For NodeElement:=MAX_KEYS_PER_NODE DownTo ((MAX_KEYS_PER_NODE Div 2)+2) Do
                      If Length(NodeKeys[NodeElement].Key)<>0 Then
                        WriteLn(' ':Level*Offset,NodeKeys[NodeElement].Key,
                                ' ',NodeKeys[NodeElement].Frequency)
                      Else
                        WriteLn(' ':Level*Offset,'Nil');
                    If Length(NodeKeys[(MAX_KEYS_PER_NODE Div 2)+1].Key)<>0 Then
                      WriteLn('-':Level*Offset,NodeKeys[(MAX_KEYS_PER_NODE Div 2)+1].Key,
                              ' ',NodeKeys[(MAX_KEYS_PER_NODE Div 2)+1].Frequency)
                    Else
                      WriteLn('-':Level*Offset,'Nil');
                    For NodeElement:=(MAX_KEYS_PER_NODE Div 2) DownTo 1 Do
                      If Length(NodeKeys[NodeElement].Key)<>0 Then
                        WriteLn(' ':Level*Offset,NodeKeys[NodeElement].Key,
                                ' ',NodeKeys[NodeElement].Frequency)
                      Else
                        WriteLn(' ':Level*Offset,'Nil');
                  End;
          RIGHT : Begin
                    If Length(SplitKey.Key)<>0 Then
                      WriteLn(' ':Level*Offset,SplitKey.Key,
                              ' ',SplitKey.Frequency)
                    Else
                      WriteLn(' ':Level*Offset,'Nil');
                    WriteLn(' ':Level*Offset,'^ Split Key');
                    For NodeElement:=MAX_KEYS_PER_NODE DownTo 2 Do
                      If Length(NodeKeys[NodeElement].Key)<>0 Then
                        WriteLn(' ':Level*Offset,NodeKeys[NodeElement].Key,
                                ' ',NodeKeys[NodeElement].Frequency)
                      Else
                        WriteLn(' ':Level*Offset,'Nil');
                    If Length(NodeKeys[1].Key)<>0 Then
                      WriteLn('/':Level*Offset,NodeKeys[1].Key,
                              ' ',NodeKeys[1].Frequency)
                    Else
                      WriteLn('/':Level*Offset,'Nil');
                  End;
          LEFT  : Begin
                    If Length(SplitKey.Key)<>0 Then
                      WriteLn(' ':Level*Offset,SplitKey.Key,
                              ' ',SplitKey.Frequency)
                    Else
                      WriteLn(' ':Level*Offset,'Nil');
                    WriteLn(' ':Level*Offset,'^ Split Key');
                    If Length(NodeKeys[MAX_KEYS_PER_NODE].Key)<>0 Then
                      WriteLn('\':Level*Offset,NodeKeys[MAX_KEYS_PER_NODE].Key,
                              ' ',NodeKeys[MAX_KEYS_PER_NODE].Frequency)
                    Else
                      WriteLn('\':Level*Offset,'Nil');
                    For NodeElement:=MAX_KEYS_PER_NODE-1 DownTo 1 Do
                      If Length(NodeKeys[NodeElement].Key)<>0 Then
                        WriteLn(' ':Level*Offset,NodeKeys[NodeElement].Key,
                                ' ',NodeKeys[NodeElement].Frequency)
                      Else
                        WriteLn(' ':Level*Offset,'Nil');
                  End;
        End; { Case Branch }
  End;    { Print_MST_Node }



  Procedure PrintNodesInorder(    Node:  TreeNodePtr;
                                  Level: Integer;
                                  Branch:ChildType);

  { This recursive procedure is used to print the nodes of the median split
    tree.  It traverses the tree using an inorder traversal that goes to the
    right most subtree first. }

  Begin    { PrintNodesInorder }
    If Node=Nil Then                   { Nil child node }
      Print_MST_Node(Node,level,Branch)
    Else
      Begin
        PrintNodesInorder(Node^.Right,Level+1,RIGHT); { traverse right subtree }
        Print_MST_Node(Node,Level,Branch);
        PrintNodesInorder(Node^.Left,Level+1,LEFT); { traverse left subtree }
      End; { Else }
  End;     { PrintNodesInorder }



Begin   { Print_MST_Module }
  WriteLn;
  WriteLn;
  WriteLn('MEDIAN SPLIT TREE FOLLOWS:');
  WriteLn('--------------------------');
  WriteLn;
  WriteLn;
  PrintNodesInorder(MST_RootPtr,0,ROOT);
End;    { Print_MST_Module }



Procedure PrintQueryHeading;

{ This procedure prints out a heading for the search for matching look-up keys
  for the file of queries. }

Begin   { PrintQueryHeading }
  WriteLn;
  WriteLn;
  WriteLn('QUERY SEARCH FOLLOWS:');
  WriteLn('---------------------');
  WriteLn;
  WriteLn;
End;    { PrintQueryHeading }



Procedure Search_MST_Module(    Query:              KeyString;
                            Var Found:              Boolean;
                            Var NumberOfComparisons:Integer);

{ *************************************************************************** }
{ *                                                                         * }
{ *                     SEARCH MEDIAN SPLIT TREE MODULE                     * }
{ *                                                                         * }
{ *    This module controls the looking up of the passed quiery with the    * }
{ *    entries in the median split tree.                                    * }
{ *                                                                         * }
{ *************************************************************************** }



  Procedure InitModule;

  { This procedure initializes the variables used in this module. }

  Begin   { InitModule }
    Found:=False;
    NumberOfComparisons:=0;
  End;    { InitModule }



  Procedure Search_MST_Node(    ArrayOfKeys:        KeyArray;
                                Query:              KeyString;
                            Var Found:              Boolean;
                            Var NumberOfComparisons:Integer);

  { This procedure performs a binary search on the passed array of look-up keys
    to try to find a match with the passed query.  If a match is found then the
    Found boolean is returned as true.  The NumberOfComparisons is also
    returned. }

  Var
    LowElement:Integer;                { an index to a low element in the passed array }
    MidElement:Integer;                { an index to a middle element in the passed array }
    HighElement:Integer;               { an index to a high element in the passed array }

  Begin   { Search_MST_Node }
    { initialize the index variables }
    LowElement:=1;
    HighElement:=MAX_KEYS_PER_NODE;
    While (LowElement<=HighElement) And ( Not Found) Do
      Begin
        NumberOfComparisons:=NumberOfComparisons+1; { increment counter }
        MidElement:=(LowElement+HighElement) Div 2; { determine mid point }
        If Query<ArrayOfKeys[MidElement].Key Then
          HighElement:=MidElement-1
        Else
          If Query>ArrayOfKeys[MidElement].Key Then
            LowElement:=MidElement+1
          Else
            Found:=True;
      End; { While LowElement }
  End;    { Search_MST_Node }



  Procedure  Search_MST(    CurrentTreeNode:    TreeNodePtr;
                            Query:              KeyString;
                        Var Found:              Boolean;
                        Var NumberOfComparisons:Integer);

  Begin   { Search_MST }
    If CurrentTreeNode<>Nil Then
      Begin
        Search_MST_Node(CurrentTreeNode^.NodeKeys,
                        Query,
                        Found,
                        NumberOfComparisons);
        If (Not Found) And (CurrentTreeNode^.SplitKey.Key<>'') Then
          Begin
            NumberOfComparisons:=NumberOfComparisons+1; { increment counter }
            If Query=CurrentTreeNode^.SplitKey.Key Then
              Found:=True
            Else { continue search }
              Begin
                If Query<CurrentTreeNode^.SplitKey.Key Then
                  CurrentTreeNode:=CurrentTreeNode^.Left { point to left subtree }
                Else
                  CurrentTreeNode:=CurrentTreeNode^.Right; { point to right subtree }
                Search_MST(CurrentTreeNode,
                           Query,
                           Found,
                           NumberOfComparisons);
              End; { Else }
          End; { If Not Found }
      End; { If CurrentTreeNode }
  End;    { Search_MST }



Begin   { Search_MST_Module }
  InitModule;
  Search_MST(MST_RootPtr,
             Query,
             Found,
             NumberOfComparisons);
End;    { Search_MST_Module }



Procedure PrintSearchResults(    Query:              KeyString;
                                 Found:              Boolean;
                                 NumberOfComparisons:Integer);

{ This procedure prints out the result from the look-up key search. }

Begin   { PrintSearchResults }
  If Not Found Then
    WriteLn('The query ',Query,' was not found to exist in the median split tree.')
  Else
    WriteLn('The query ',Query,' was found in ',NumberOfComparisons,' comparisons.');
End;    { PrintSearchResults }



Procedure ReadQueryFile;

{ This procedure reads queries from a query file, passes the query to a look-up
  module to see idf the query exists in the MST and finally passes the result
  of the search to a procedure to print the results of the search. }

Const
  FILE_NAME='Query1.Dat';              { name of the query data file }

Type
  FileEntryString=String[MAX_KEY_SIZE]; { a string type used to store file entries }

Var
  QueryFile:Text;                      { text file }
  FileEntry:FileEntryString;           { variable used in reading the queries in teh query file }
  Found:Boolean;                       { a boolean flag used to determine if a query is in the MST }
  NumberOfComparisons:Integer;         { a counter used to determine the number of comparisons required
                                         to find a particular query in the MST }

Begin   { ReadQueryFile }
  Assign(QueryFile,FILE_NAME);         { assign to a disk file }
  Reset(QueryFile);                    { open the file for reading }
  Repeat
    ReadLn(QueryFile,FileEntry);        { read in the file entry }
    Search_MST_Module(FileEntry,
                      Found,
                      NumberOfComparisons);
    PrintSearchResults(FileEntry,
                       Found,
                       NumberOfComparisons);
  Until Eof(QueryFile);                { read until end of file found }
  Close(QueryFile);                    { close the disk file }
End;    { ReadQueryFile }



Begin   { Main Program }
  InitProgram;
  HardCopy(False);
  ReadInputFileModule;
  PrintLinkedList(L_L_HeadPtr,L_L_TailPtr);
  Build_MST_Module;
  Print_MST_Module;
  PrintQueryHeading;
  ReadQueryFile;
End.    { Main Program }