Program HashTests (Input,Output);

Const
   MaxTableSize = 2000;
   Empty = -1;   {Hash table element not used}

   m = 100000000; { random number generator }     
   b = 31415821;
   m1 = 10000;
 
Type
   HashTable = Array[0..MaxTableSize-1] of Integer;

   NodePointer = ^Node;
   Node = Record
           Key  : Integer;
           Next : NodePointer;
          End;
   PointerArray = Array[0..MaxTableSize-1] of NodePointer;


Var
   Table : HashTable;

   Answer : Char;

   ListHead : PointerArray;

   RandNum : Integer4;
  



{*******************************************}
FUNCTION Mult (p, q :Integer4) : Integer4;
Var 
   p1 , p0, q1, q0 : Integer4;
Begin
   p1 := p DIV m1;
   p0 := p MOD m1;
   q1 := q DIV m1;
   q0 := q MOD m1;
   Mult := (((p0*q1 + p1*q0) MOD m1) * m1 + p0*q0) MOD m;
End;




{Generate a pseudo-random number between 0 and 1.
RandNum should be seeded at start of each program. }

FUNCTION Random : Real;

Begin
   RandNum := (Mult(RandNum,b) + 1) MOD m;
   Random := RandNum / m;
End;






{***********************************************}
Procedure InsertTable (Var Table : HashTable; 
                       TableSize : Integer;
                       Key : Integer);
Var
   ProbeNumber, Hashindex : Integer;

Begin
   ProbeNumber := 1;
   Hashindex := Key MOD TableSize;  { hash function }
   While (Table[Hashindex] <> Empty) and  { not empty }
         (Table[Hashindex] <> Key) and  { occupied }
         (ProbeNumber <= TableSize) Do  { full table }
    Begin
      { linear probe next index in hash table }
      Hashindex := (Hashindex + 1) MOD TableSize;
      ProbeNumber := ProbeNumber + 1;
    End;

   { insert key in hash table }
   If Table[Hashindex] = Empty Then
      Table[Hashindex] := Key;

End;


 
{***********************************************}
Procedure FindTablePlace (Var Table : HashTable;
                         TableSize : Integer; 
                         Key : Integer;
                         Var Count : Integer);
Var
   ProbeNumber, Hashindex : Integer;

Begin
   ProbeNumber := 1;
   Hashindex := Key MOD TableSize;    { hash function }
   Count := 1;
   While (Table[Hashindex] <> Empty) and
         (Table[Hashindex] <> Key) and
         (ProbeNumber <= TableSize) Do
    Begin
      { linear probe next index }
      Hashindex := (Hashindex + 1) MOD TableSize;
      ProbeNumber := ProbeNumber + 1;
      Count := Count + 1;
    End;
   
End;




{************************************************}
Procedure DisplayTable (Var Table : HashTable;
                        TableSize : Integer);
Var
   i, j : Integer;

Begin
   i := 0;
   Repeat
      For j := 0 to 9 Do
        If i+j <= TableSize-1 Then
           Write(Table[i+j]:6);
      Writeln;
      i := i + 10;
   Until i > TableSize-1;
End;






{********************************************************}
Procedure InsertList (Var ListHead : PointerArray; 
                      TableSize : Integer;
                      Key : Integer);

Var
   Current, Previous, NewNodePtr : NodePointer;
   Hashindex : Integer;
   Found : Boolean;

Begin
 
   Hashindex := Key MOD TableSize;  { hash function }

   Current := ListHead[Hashindex];

   Found := False;  
   While Not Found and (Current <> Nil) Do
    Begin
      If Key <= Current^.Key Then   { insert here }
         Found := True    { quit search }
      Else
       Begin     { move pointers to next node }
         Previous := Current;
         Current := Current^.Next;
       End;
    End;

   New(NewNodePtr);      { create new node }
   NewNodePtr^.Key := Key;  { load it with data }
   NewNodePtr^.Next := Current; { new node points to current }
   If Current = ListHead[Hashindex] Then   { empty list }
      ListHead[Hashindex] := NewNodePtr { first node in list}
   Else
      Previous^.Next := NewNodePtr;  

End;  { InsertList }





{********************************************************}
Procedure FindListPlace (Var ListHead : PointerArray; 
                         TableSize : Integer;
                         Key : Integer;
                         Var Count : Integer);

Var
   Current : NodePointer;
   Found : Boolean;

Begin
   Current := ListHead[Key MOD TableSize];  { hash function }

   Count := 1;
   Found := False;  
   While Not Found and (Current <> Nil) Do
    Begin
      Count := Count + 1;  { increment key comparisons count }
      If Key >= Current^.Key Then   { would be inserted here }
         Found := True    { quit search }
      Else
        { move pointer to next node }
         Current := Current^.Next;
    End;

End;  { FindListPlace }




{*********************************************************}
Procedure DisplayList (List : NodePointer);

Var
   Current : NodePointer;

Begin
   Current := List;
   While Current <> Nil Do
     Begin
       Write(Current^.Key:6);
       Current := Current^.Next;
     End;
   Writeln;
End;





{*********************************************************}
Procedure CleanupList (Var List : NodePointer);

Var
   Current, Previous : NodePointer;

Begin
   Current := List;
   List := Nil;
   While Current <> Nil Do
     Begin
       Previous := Current;
       Current := Current^.Next;
       Dispose(Previous);
     End;
End;




{***************************************************}
Procedure User (Var TableSize, Range, NumTables,
                Tests : Integer; Var Alpha : Real);
Begin 
   Writeln('Enter table size');
   Readln(TableSize);
   Writeln('Enter key range 1- ');
   Readln(Range);
   Writeln('Enter alpha (0<alpha<1)');
   Readln(Alpha);   { initial load factor }
   Writeln('Enter number of tables to generate');
   Readln(NumTables); 
   Writeln('Enter number of tests per table');
   Readln(Tests);
End;





{*********************************************}
Procedure LinearProbe;

Var
   TableSize : Integer;
   Alpha : Real;
   i, j, NumTables, Range, Tests, Count : Integer;
   TotalCount : Integer4;
   Continue : Boolean;
   Again : Char;

Begin   
   Continue := True;
   While Continue Do
    Begin
      User(TableSize,Range,NumTables,Tests,Alpha);
      TotalCount := 0;

      For j := 1 to NumTables Do
       Begin
         { clear table of previous keys }
         For i := 0 to TableSize-1 Do
            Table[i] := Empty;    
         { load initial table }
         For i := 1 to Trunc(TableSize * Alpha) Do
            InsertTable(Table,TableSize,Trunc(Random*Range));
       {  DisplayTable(Table,TableSize); }

         { simulate inserting }
         For i := 1 to Tests Do
          Begin
           
             FindTablePlace(Table,TableSize,
                       Trunc(Random*MaxInt),Count);
            TotalCount := TotalCount + Count;
          End;
       End; { for }

      Writeln('Average probes at load factor of ',
              Alpha:4:2,
              '   Table size ',TableSize:4,' is ',            
               TotalCount/(Tests*NumTables):6:2);

      Writeln('Again? (Y or N)');
      Readln(Again);
      If (Again <> 'Y') and (Again <> 'y') Then
         Continue := False;
    End;  { while }
End;




{*********************************************}
Procedure Chaining;

Var
   TableSize : Integer;
   Alpha : Real;
   i, j, NumTables, Range, Tests, Count : Integer;
   TotalCount : Integer4;
   Continue : Boolean;
   Again : Char;

Begin   
   Continue := True;
   While Continue Do
   Begin
      User(TableSize,Range,NumTables,Tests,Alpha);
      TotalCount := 0;

      For j := 1 to NumTables Do
       Begin
         { clear table of previous keys }
         For i := 0 to TableSize-1 Do
             CleanupList(ListHead[i]);
         { load initial table }
         For i := 1 to Trunc(TableSize * Alpha) Do            

           InsertList(ListHead,TableSize,
                      Trunc(Random*MaxInt));

       {  For i := 0 to TableSize-1 Do
            DisplayList(ListHead[i]); }

         { simulate inserting }
         For i := 1 to Tests Do
          Begin
            FindListPlace(ListHead,TableSize,
                          Trunc(Random*MaxInt),Count);
            TotalCount := TotalCount + Count;
          End;
       End; { for }

      Writeln('Average probes at load factor of ',
              Alpha:4:2,
              '   Table size ',TableSize:4,' is ',            
               TotalCount/(Tests*NumTables):6:2);

      Writeln('Again? (Y or N)');
      Readln(Again);
      If (Again <> 'Y') and (Again <> 'y') Then
         Continue := False;
    End;  { while }
End;





Begin
   Writeln('Seed random number generator');
   Readln(RandNum);

   Repeat
      Writeln('Linear Probing or Chaining? (P or C)');
      Readln(Answer);
      If (Answer = 'P') or (Answer = 'p') Then
         LinearProbe
      Else
         Chaining;    
   Until False;  
End.