{ Hashing - DEMO fuer Datenstrukturen Vorlesung, SS03-Benn }
{ Autor: Dipl.-Ing. Thomas Speiser                         }
{ Source from: http://Codes.TurboTools.de                  }

program hashing;
uses Crt;
const m = 32;     { Groesse des Hashing Feldes }
      p = 97;     { eine Primzahl als oberste Grenze der Platzanzahl }
      free = 0;

type index = 1..p;
     memory = array[index] of integer;   { Speicherfeld }

var s: string;
    i,x,y: integer;
    direkt, kolli: integer; { Anzahl Kollisionen und direkte Zuweisungen }

    mem: memory;
    overflow: boolean;

{ Vorlesungs - Proceduren }
{ Lineares Sondieren      }
procedure place(var mem: memory; key: integer);
var hk, h, g: index;
    found: boolean;
begin
{ z.B. 3 mod 97 = 3 => UNSINN!!! (fuer einen Key welcher kleiner als P ist) }

 hk:=key mod 5;
 found:=false;
 overflow:=false;
 h:=hk; g:=1;
      repeat

 x:=whereX; y:=whereY;
 gotoxy(1,3); write('H: ',h,' G: ',g);
{ delay(1);}
 gotoxy(x,y);

       if mem[h] = free then
        begin
         inc(direkt);
         found:=true;
         mem[h]:=key;
{
  if ((key >= 1) and (key <= 9)) or (mem[h] = free) then write('0');
  write(mem[h],' ');
  if i mod 5 = 0 then writeLN;
}
        end
       else
        begin
        inc(kolli);
        g:=succ(g);
{ Zur Verminderung von unnoetigen Kollisionen "key" mit in h() eingefuegt }
        h:=key + hk + g;

 x:=whereX; y:=whereY;
 gotoxy(1,3); write('H: ',h,' G: ',g,'     ');
 delay(1);
 gotoxy(x,y);

         if h >= p then h:=h-p;
         if g = p then
          begin
           writeLN('Speicherfeld ueberfuellt');
           overflow:=true;
          end;
        end;
      until found or overflow;
end;

function hoch(r,n: longint): longint;
var i,t: longint;
begin
t:=r;
if n <> 0 then for i:=1 to n-1 do t:=r*t else t:=1;
hoch:=t;
end;

{ Hash - Funktionen aus Segdewick, Algorithmen }

function hashfunc(s: string): longint;
var i,i2,a: longint;
begin
i2:=0;
a:=length(s);
i:=0;
repeat
inc(i);
i2:=i2+(ord(s[i])-64)*hoch(m,a-1);
dec(a);
until i = length(s);
hashfunc:=i2;
end;

function hashfunc2(s: string): longint;
var h: longint;
    j: integer;
begin
h:=ord(s[1])-64;
for j:=2 to length(s) do h:=((h*32)+ord(s[j])-64) mod m;
hashfunc2:=h;
end;

begin
TextMode(CO80 xor Lo(LastMode)+Font8x8 xor LASTMODE);
kolli:=0;
direkt:=0;
ClrScr;
writeLN('H A S H I N G - D E M O!');
writeLN;
writeLN;
for i:=1 to p-1 do place(mem,i);
writeLN;
for i:=1 to p-1 do begin
{ show memory }
  if ((mem[i] >= 1) and (mem[i] <= 9)) or (mem[i] = free) then write('0');
  write(mem[i],' ');
  if i mod 5 = 0 then writeLN;
{ show memory }
end;
writeLN;
writeLN('Direkte Zuweisungen: ',direkt);
writeLN('Kollisionen        : ',Kolli);

writeLN('SCHLUESSEL eingeben! ');        readLN(s);
writeLN('Zahl      : ',hashfunc(s));
writeLN('mod m     : ',hashfunc(s) mod m);
writeLN('mod 101   : ',hashfunc(s) mod 101);
writeLN('Zahl      : ',hashfunc2(s));
writeLN('mod m     : ',hashfunc2(s) mod m);
writeLN('mod 101   : ',hashfunc2(s) mod 101);
writeLN;

writeLN('< TASTE DRUECKEN >');
readLN;
end.