package hjelpeklasser;
import java.util.*;
public class KvadratiskHashTabell<T> implements Beholder<T>
{
private static final int[] PRIM = {1,3,7,11,19,31,59,107,211,419,827,1627,3251,
6491,12979,25951,51899,103787,207563,415111,830191,1660367,3320699,6641387,6641387,
13282747,26565491,53130971,106261931,212523859,425047703,850095391,1700190707};
private static final class HashObjekt<T>
{
private final T verdi;
private final int hashverdi;
private HashObjekt(T verdi, int hashverdi)
{
this.verdi = verdi;
this.hashverdi = hashverdi;
}
}
private final HashObjekt<T> x
= new HashObjekt<>(null, 0);
private boolean ledig(int indeks)
{
HashObjekt<T> o = hash[indeks];
return o == null || o == x;
}
private HashObjekt<T>[] hash;
private final float tetthet;
private int grense;
private int antall;
private int endringer;
private int iprim;
@SuppressWarnings({"rawtypes","unchecked"})
private void utvid()
{
if (iprim == PRIM.length - 1) return;
HashObjekt<T>[] gammelhash = hash;
hash = new HashObjekt[PRIM[++iprim]];
int dim = hash.length;
for (int i = 0; i < gammelhash.length; i++)
{
HashObjekt<T> o = gammelhash[i];
if (o == x) gammelhash[i] = null;
else if (o != null) leggInn(o, o.hashverdi % dim);
}
grense = (int)(tetthet * hash.length);
}
@SuppressWarnings({"rawtypes","unchecked"})
public KvadratiskHashTabell(int dim)
{
if (dim < 0) throw new IllegalArgumentException("Ulovlig dimensjon!");
for (; iprim < PRIM.length; iprim++)
{
if (dim <= PRIM[iprim]) break;
}
dim = iprim < PRIM.length ? PRIM[iprim] : PRIM[iprim - 1];
hash = new HashObjekt[dim];
tetthet = 0.75f;
grense = (int)(tetthet * hash.length);
antall = 0;
endringer = 0;
}
public KvadratiskHashTabell()
{
this(11);
}
@Override
public int antall()
{
return antall;
}
@Override
public boolean tom()
{
return antall == 0;
}
private void leggInn(HashObjekt<T> o, int h)
{
HashObjekt<T>[] hash1 = hash;
int dim = hash1.length;
if (ledig(h)) hash1[h] = o;
else
{
for (int hopplengde = 1, v = h; ; hopplengde += 2)
{
if ((h += hopplengde) >= dim) h -= dim;
if (ledig(h)) { hash1[h] = o; return; }
if ((v -= hopplengde) < 0) v += dim;
if (ledig(v)) { hash1[v] = o; return; }
}
}
}
@Override
public boolean leggInn(T verdi)
{
Objects.requireNonNull(verdi, "verdi er null!");
if (antall >= grense) utvid();
int hverdi = verdi.hashCode() & 0x7fffffff;
int dim = hash.length;
int h = hverdi % hash.length;
HashObjekt<T> o = new HashObjekt<>(verdi, hverdi);
leggInn(o, h);
antall++;
endringer++;
return true;
}
@Override
public String toString()
{
StringJoiner s = new StringJoiner(", ", "[", "]");
for (HashObjekt<T> o : hash)
{
if (o != null && o != x) s.add(o.verdi.toString());
}
return s.toString();
}
@Override
public boolean inneholder(T verdi)
{
if (verdi == null) return false;
HashObjekt<T>[] hash1 = hash;
int dim = hash1.length;
int hashverdi = verdi.hashCode() & 0x7fffffff;
int h = hashverdi % dim;
HashObjekt<T> o = hash1[h];
if (o == null) return false;
else if (verdi.equals(o.verdi)) return true;
else
{
for (int hopplengde = 1, v = h; ; hopplengde += 2)
{
if ((h += hopplengde) >= dim) h -= dim;
o = hash1[h];
if (o == null) return false;
else if (verdi.equals(o.verdi)) return true;
if ((v -= hopplengde) < 0) v += dim;
o = hash1[v];
if (o == null) return false;
else if (verdi.equals(o.verdi)) return true;
}
}
}
@Override
public boolean fjern(T verdi)
{
if (verdi == null) return false;
HashObjekt<T>[] hash1 = hash;
int dim = hash.length;
int hashverdi = verdi.hashCode() & 0x7fffffff;
int h = hashverdi % dim;
HashObjekt<T> o = hash1[h];
if (o == null) return false;
else if (verdi.equals(o.verdi)) hash1[h] = x;
else
{
for (int hopplengde = 1, v = h; ; hopplengde += 2)
{
if ((h += hopplengde) >= dim) h -= dim;
o = hash1[h];
if (o == null) return false;
else if (verdi.equals(o.verdi)) { hash1[h] = x; break; }
if ((v -= hopplengde) < 0) v += dim;
o = hash1[v];
if (o == null) return false;
else if (verdi.equals(o.verdi)) { hash1[v] = x; break; }
}
}
endringer++;
antall--;
return true;
}
@Override
public void nullstill()
{
Arrays.fill(hash, null);
endringer++;
antall = 0;
}
@Override
public Iterator<T> iterator()
{
return new KvadratiskHashTabellIterator();
}
private class KvadratiskHashTabellIterator implements Iterator<T>
{
private int i;
private boolean fjernOK = false;
private int iteratorendringer = endringer;
private KvadratiskHashTabellIterator()
{
while (i < hash.length && (hash[i] == null || hash[i] == x)) i++;
}
@Override
public boolean hasNext()
{
return i < hash.length;
}
@Override
public T next()
{
if (iteratorendringer != endringer)
throw new ConcurrentModificationException("Tabellen er endret!");
if (!hasNext())
throw new NoSuchElementException("Ingen flere verdier");
T verdi = hash[i].verdi;
while (++i < hash.length && (hash[i] == null || hash[i] == x));
fjernOK = true;
return verdi;
}
@Override
public void remove()
{
if (iteratorendringer != endringer)
throw new ConcurrentModificationException("Tabellen er endret!");
if (!fjernOK) throw new IllegalStateException("Ulovlig tilstand!");
fjernOK = false;
int j = i - 1;
while (hash[j] == null || hash[j] == x) j--;
hash[j] = x;
endringer++;
iteratorendringer++;
antall--;
}
}
}