// File: ScansioneQuadratica.pseudocpp

/* 
   Contiene lo pseudocodice delle fiunzione Inserisci, Cerca, Elimina
   nel caso di hashing aperto con scansione quadratica.

   Si noti che ogni posizione della tavola puo' essere
   in tre stati: 'vuota', 'liberata', 'occupata' 
   dove 'occupata' significa che non e' vuota e non e' liberata.

   Si noti inoltre che la funzione f(i) utilizzata nella scansione
   puo' non garantire la possibilita' di scandire tutte le posizioni
   della tavola Per questa ragione si introduce un controllo che il
   numero di scansioni effettuate non superi un certo numero di passi (qui
   pari alla dimTavola).
*/


// Inserisce l'oggetto nella prima posizione vuota o liberata.

void Inserisci(Chiave K, InsAttr I)
{
  if (tavola_piena) return; // oppure rehash

  int h = hash(K);
  int i = 0;
  int probe = h;
  while (tavola[probe].stato != 'occupata' && i < dimTavola) {
    probe = h + f(i); // f(i)= i^2, tipicamente
    i++;
  }
  tavola[probe] = (K,I);
}


// Considera la ricerca fallita se arriva ad una posizione 'vuota'.
// Nota per non bloccare la sequenza di scansione le posizioni liberate
// non vengono poste a 'vuota' ma nello stato speciale 'liberata'.

(bool,Chiave,InsAttr) Cerca(Chiave K, InsAttr I)
{
  int h = hash(K);
  int i = 0;
  int probe = h;
  while (tavola[probe].stato != 'vuota' && tavola[probe].key != K && 
	 i < dimTavola;) {
    probe = h + f(i);
    i++;
  }
 if (tavola[probe].stato != 'vuota') return (false,nil,nil);
 else return (true, tavola[probe].key, tavola[probe].insattr);
}


// Per non bloccare la sequenza di scansione le posizioni liberate
// non vengono poste a 'vuota' ma nello stato speciale 'liberata'.

void Elimina(Chiave K)
{
  int h = hash(K);
  int i = 0;
  int probe = h;
  while (tavola[probe].stato != 'vuota' && tavola[probe].key != K && 
	 i < dimTavola;) {
    probe = h + f(i);
    i++;
  }
  if (tavola[probe].key == K) tavola[probe] = 'liberata';
}