tpu/u_shashi.pas

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

 TDA-Diccionario (Inserta, Suprime, Miembro, Anula)
 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 = 30; {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
  { La siguiente funcion de dispersion puede servir     }
  { para reales entre 0 y 1, en donde "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 ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
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.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}