-- AUTOR: Elvira Mayordomo Cámara
-- PROYECTO: módulo de implementación del
-- TAD tablas hash por recolocación
-- cuadrática
-- FICHERO: tablasrecolocacion.adb
-- FECHA: 14-12-02

package body tablasrecolocacion is

function localizar(t:tabla;c:tpClave) return integer is
-- recordad que 2n<= max y max primo. Si no no
-- se puede garantizar el funcionamiento
-- correcto de localizar

-- Está función devuelve la posición de c en la tabla t.
-- Si c no está, devuelve la posición donde se colocaría c por 
-- recolocación cuadrática.
-- Reaprovecha las posiciones borradas.

-- coste en tiempo O(1) en media
inicial,pos,i,libre:integer;
hayborradas:boolean;
 
begin
    inicial:=h(c,max);
    pos:=inicial;
    hayborradas:=false;
    i:=0;
-- El coste de todas las operaciones depende de este while
    while (((not t(pos).vacio) and t(pos).laclave/=c) 
    or t(pos).borrado) loop
        if t(pos).borrado then 
            hayborradas:=true;
            libre:=pos; 
        end if;
        i:= i+1;
        pos:=(inicial + i*i) mod max;
    end loop;
    
    -- Si no ha encontrado c, aprovecha las posiciones borradas 
    if (t(pos).laclave/=c or t(pos).vacio) and hayborradas then
        pos:=libre;
    end if; 
    return pos;
end localizar;
 
procedure tablavacia(t:out tabla) is
-- Post: t=crearVacía
-- coste en tiempo O(max)
begin
    for i in 0..max-1 loop
        t(i).vacio:=true;
        t(i).borrado:=false;
    end loop;
end tablavacia;

 
function esta(t:tabla; c:tpClave) return boolean is
-- Post: esta(t,c)=está(t,c)
-- coste en tiempo O(1) en media
pos: integer;
begin
    pos:=localizar(t,c);
    return (t(pos).laclave=c and (NOT t(pos).vacio));
end esta;
        
 
procedure modificar(t:in out tabla; c:in tpClave; v: in tpValor) is
-- Pre: t=t0
-- Post: t=añadir(t0,c,v)
-- coste en tiempo O(1) en media
pos: integer;
begin
    pos:=localizar(t,c);
    if  t(pos).vacio then
        -- añado un dato nuevo
        t(pos):=(c,v,false,false);          
    -- si ya estaba c modifico v
    elsif t(pos).laclave=c then 
            t(pos).elvalor:=v; 
    end if;
end modificar;

 
function consultar(t:tabla; c:tpClave) return tpValor is
-- Pre: está(t,c)
-- Post: consulta(t,c)=elValor(t,c)
-- coste en tiempo O(1) en media
pos: integer;
begin
    pos:=localizar(t,c);
    return t(pos).elvalor;
end consultar;

 
procedure borrar(t:in out tabla; c:in tpClave) is
-- Pre: t=t0
-- Post: t=borrar(t0,c,v)
-- coste en tiempo O(1) en media
pos: integer;
begin
    if esta(t,c) then 
        pos:=localizar(t,c);
        t(pos).borrado:=true;
        t(pos).vacio:=true;
    end if;
end borrar;



end tablasrecolocacion;