program HashingEnderecamentoAberto;

const VAZIO    = '!!!!!!!!!!';
      RETIRADO = '**********';
      M        = 7;
      N        = 10; { Tamanho da chave }
      TAMALFABETO = 256; { Usado na funcao h de Zobrist }
   
type TipoApontador  = integer;
     TipoChave      = packed array [1..N] of char;
     TipoItem       = record 
                        Chave: TipoChave
                        { outros componentes }
                      end;
     TipoIndice     = 0..M - 1;
     TipoDicionario = array [TipoIndice] of TipoItem;
{    TipoPesos      = array [1..N] of integer; }
     TipoPesos      = array[1..N, 1..TAMALFABETO] of integer; { Zobrist}
var 
  Tabela  : TipoDicionario;
  p       : TipoPesos;
  Elemento: TipoItem;
  arq     : text;
  j, i    : integer;

{
procedure GeraPesos (var p: TipoPesos);
var i: integer;
begin
  randomize;
  for i:= 1 to N do p[i] := trunc (1000000 * random + 1);
end;} {GeraPesos}

procedure GeraPesos (var p: TipoPesos);
var i, j: integer;
begin
  randomize;
  for i:= 1 to N do 
    for j := 1 to TAMALFABETO do
      p[i, j] := trunc(1000000 * random + 1);
end; {GeraPesos}

{
function h (Chave: TipoChave; p: TipoPesos): TipoIndice;
var i, Soma: integer;
begin
  Soma := 0;
  for i := 1 to N do Soma := Soma + ord (Chave[i]) * p[i];
  h := Soma mod M;
end;
}

function h (Chave: TipoChave; p: TipoPesos): TipoIndice;
var i, Soma: integer; { Funcao h do Zobrist}
begin
  Soma := 0;
  for i := 1 to N do Soma := Soma + p[i, ord(Chave[i])];
  h := Soma mod M;
end; 

procedure Inicializa (var T: TipoDicionario);
var i: integer;
begin
  for i := 0 to M - 1 do T[i].Chave := VAZIO
end; { Inicializa }

function Pesquisa (Ch: TipoChave; var p: TipoPesos; 
                   var T: TipoDicionario): TipoApontador;
var i, Inicial: integer;
begin
  Inicial := h (Ch, p);
  i := 0;
  while (T[(Inicial + i) mod M].Chave <> VAZIO) and
        (T[(Inicial + i) mod M].Chave <> Ch) and
        (i < M) do i := i + 1;
  if T[(Inicial + i) mod M].Chave = Ch 
  then Pesquisa := (Inicial + i) mod M
  else Pesquisa := M { Pesquisa sem sucesso }
end; { Pesquisa }

procedure Insere (x: TipoItem; var p: TipoPesos; 
                  var T: TipoDicionario);
var i, Inicial: integer;
begin
  if Pesquisa (x.Chave, p, T) < M
  then writeln ('Elemento ja esta presente')
  else begin
       Inicial := h (x.Chave, p);
       i := 0;
       while ((T[(Inicial + i) mod M].Chave <> VAZIO) and
          (T[(Inicial + i) mod M].Chave <> RETIRADO)) and
          (i < M) do i := i + 1;
       if i < M 
       then T[(Inicial + i) mod M] := x
       else writeln (' Tabela cheia')
       end;
end; { Insere }

procedure Retira (Ch: TipoChave; var p: TipoPesos; 
                  var T: TipoDicionario);
var i: integer;
begin
  i := Pesquisa (Ch, p, T);
  if i < M 
  then T[i].Chave := RETIRADO
  else writeln ('Registro nao esta presente')
end; { Retira }

procedure imprime (var tabela: TipoDicionario);
var i, j: integer;
begin
  for i := 0 to M - 1 do 
    begin
    write (i: 3, '  ');
    for j := 1 to n do write (tabela[i].Chave[j]);
    writeln
    end
end; { imprime }

begin
  inicializa (Tabela);
{
  assign (arq, 'hash.dat');
  reset (arq);
}
  GeraPesos (p);
  readln (Elemento.Chave);
  while Elemento.Chave <> 'aaaaaaaaaa' do 
    begin
    insere (Elemento, p, Tabela);
    readln (Elemento.Chave);
    end;
{
  close (arq);
}
  writeln ('Tabela apos insercao:');
  imprime (Tabela);
{
  reset (arq);
}

  write ('Pesquisar :  ');
  readln (Elemento.Chave);
  while elemento.chave <> 'aaaaaaaaaa' do 
    begin
    i := pesquisa (Elemento.Chave, p, Tabela);
    if i < M 
    then writeln ('sucesso na posicao ', i: 3, ' ')
    else writeln ('pesquisa sem sucesso ');
    write ('Pesquisar :  ');
    readln (Elemento.Chave);
  end;
{
  close (arq);
  reset (arq);
}
  writeln ('Retirar seguintes chaves:');
  readln (Elemento.Chave);
  while elemento.chave <> 'aaaaaaaaaa' do 
    begin
    Retira (Elemento.Chave, p, Tabela);
    readln (Elemento.Chave);
    end;
{
  close (arq);
}
  writeln ('Tabela apos retiradas:');
  imprime (tabela);
{
  reset (arq);
} 
  writeln ('Inserir de novo os elementos seguintes:');
  readln (Elemento.Chave);
  while elemento.chave <> 'aaaaaaaaaa' do 
    begin
    Insere (Elemento, p, Tabela);
    readln (Elemento.Chave);
    end;
{
  close (arq);
}
  writeln ('Tabela apos novas insercoes:');
  Imprime (Tabela);
end. { hashing_by_open_addressing }