tpu/u_shashi.pas

{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION

 TDA-Diccionario (Inserta, Suprime, Miembro, Anula e Imprime)
 con dispersi\'on abierta, para enteros.
 keywords: conjunto, tabla de dispersion

FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $Id: u_shashi.pas 2003/06/12 13:57 mstorti Exp jdelia   $ }
unit u_shashi;
interface
uses u_listpi;
const
  B = 100; {numero de cubetas}
type
  tipo_elemento = integer;
  sethashi = object
  private
    A : array [1..b] of listpi;
    function H_FUN (x : tipo_elemento) : integer;
  public
    procedure ANULA;
    procedure INSERTA (x : tipo_elemento);
    function  MIEMBRO (x : tipo_elemento): boolean;
    procedure SUPRIME (x : tipo_elemento);
    procedure IMPRIME (s :string);
  end;

implementation

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function sethashi.H_FUN (x : tipo_elemento) : integer;
begin
   H_FUN := x mod b + 1;
   { Esta funcion de dispersion puede servir}
   { para reales entre 0 y 1. N debe ser mayor}
   { que B, por ejemplo 1000 }
   { H_FUN := trunc ( (x*N) * (x*N) div N);}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure sethashi.ANULA;
var
  j : integer;
begin  {Anula las listas de todas las cubetas}
  for j := 1 to B do A [j].ANULA;
end; { ANULA }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure sethashi.INSERTA (x : tipo_elemento);
var
  cubeta : integer;
  L      : listpi;
  p      : posicion;
begin
  cubeta := ( H_FUN (x) mod B ) + 1;
 {writeln ('poniendo ',x,' en la cubeta ',cubeta);}
  L := A [cubeta];
  p := L.FIN;
  if ( L.LOCALIZA (x) = p) then L.INSERTA (x, p);
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function sethashi.MIEMBRO (x: tipo_elemento): boolean;
var
  cubeta : integer;
  L      : listpi;
begin
 {ubica la cubeta}
  cubeta := ( H_FUN (x) mod B ) + 1;
 {busca en la lista correspondiente}
  L := A [cubeta];
  MIEMBRO := ( L.LOCALIZA (x) <> L.FIN );
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure sethashi.SUPRIME (x: tipo_elemento);
var
  cubeta : integer;
  p : posicion;
  L : listpi;
begin
 {ubica la cubeta}
  cubeta := ( H_FUN (x) mod B ) + 1;
 {busca en la lista correspondiente}
  L := A [cubeta];
  p := L.LOCALIZA (x);
  if (p <> L.FIN) then L.SUPRIME (p);
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure sethashi.IMPRIME (s: string);
var
  j : integer;
begin
  if length (s) > 0 then writeln (s);
  for j:=1 to B do A [j].IMPRIME (' ');
end;

end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}