package hjelpeklasser;
import java.util.*;
public class DobbeltlenketHashTabell<T> implements Beholder<T>
{
private static final int[] PRIM = {0,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 class Node<T>
{
private final T verdi;
private final int hashverdi;
private Node<T> neste;
private Node<T> etter;
private Node(T verdi, int hashverdi, Node<T> neste)
{
this.verdi = verdi;
this.hashverdi = hashverdi;
this.neste = neste;
this.etter = null;
}
}
private Node<T>[] hash;
private final float tetthet;
private int grense;
private int antall;
private int iprim;
private int endringer;
private Node<T> hode, hale;
private void utvid()
{
if (iprim == PRIM.length - 1) return;
@SuppressWarnings({"rawtypes","unchecked"})
Node<T>[] nyhash = new Node[PRIM[++iprim]];
for (int i = 0; i < hash.length; i++)
{
for (Node<T> p = hash[i]; p != null; )
{
Node<T> q = p.neste;
int nyindeks = p.hashverdi % nyhash.length;
p.neste = nyhash[nyindeks];
nyhash[nyindeks] = p;
p = q;
}
hash[i] = null;
}
hash = nyhash;
grense = (int)(tetthet * hash.length);
}
@SuppressWarnings({"rawtypes","unchecked"})
public DobbeltlenketHashTabell(int dimensjon)
{
if (dimensjon < 0) throw new IllegalArgumentException("Negativ dimensjon!");
iprim = 0;
for (; iprim < PRIM.length; iprim++) if (dimensjon <= PRIM[iprim]) break;
dimensjon = iprim < PRIM.length ? PRIM[iprim] : PRIM[iprim - 1];
hash = new Node[dimensjon];
tetthet = 0.75f;
grense = (int)(tetthet * hash.length);
hode = hale = null;
antall = 0;
endringer = 0;
}
public DobbeltlenketHashTabell()
{
this(11);
}
@Override
public int antall()
{
return antall;
}
@Override
public boolean tom()
{
return antall == 0;
}
@Override
public boolean leggInn(T verdi)
{
Objects.requireNonNull(verdi, "verdi er null!");
if (antall >= grense)
{
utvid();
}
int hashverdi = verdi.hashCode() & 0x7fffffff;
int indeks = hashverdi % hash.length;
hash[indeks] = new Node<>(verdi, hashverdi, hash[indeks]);
if (tom()) hode = hale = hash[indeks];
else hale = hale.etter = hash[indeks];
endringer++;
antall++;
return true;
}
@Override
public String toString()
{
StringJoiner s = new StringJoiner(", ", "[", "]");
Node<T> p = hode;
while (p != null)
{
s.add(p.verdi.toString());
p = p.etter;
}
return s.toString();
}
@Override
public boolean inneholder(T verdi)
{
if (verdi == null) return false;
int hashverdi = verdi.hashCode() & 0x7fffffff;
Node<T> p = hash[hashverdi % hash.length];
while (p != null)
{
if (verdi.equals(p.verdi)) return true;
p = p.neste;
}
return false;
}
@Override
public boolean fjern(T verdi)
{
if (verdi == null) return false;
int hashverdi = verdi.hashCode() & 0x7fffffff;
int indeks = hashverdi % hash.length;
Node<T> p = hash[indeks], q = null;
while (p != null)
{
if (verdi.equals(p.verdi)) break;
p = (q = p).neste;
}
if (p == null) return false;
else
{
if (p == hash[indeks]) hash[indeks] = p.neste;
else q.neste = p.neste;
if (antall == 1) hode = hale = null;
else if (p == hode) hode = hode.etter;
else
{
Node<T> r = hode;
while (r.etter != p) r = r.etter;
r.etter = p.etter;
if (p == hale) hale = r;
}
}
endringer++;
antall--;
return true;
}
@Override
public void nullstill()
{
if (!tom())
{
endringer++;
antall = 0;
for (int i = 0; i < hash.length; i++) hash[i] = null;
Node<T> p = hode, q;
while (p != null)
{
q = p.neste;
p.neste = null;
p = q;
}
hode = hale = null;
}
}
@Override
public Iterator<T> iterator()
{
return new HashTabellIterator();
}
private class HashTabellIterator implements Iterator<T>
{
private Node<T> p = null;
private final int iteratorendringer = endringer;
private HashTabellIterator()
{
p = hode;
}
@Override
public boolean hasNext()
{
return p != null;
}
@Override
public T next()
{
if (iteratorendringer != endringer)
throw new ConcurrentModificationException("Tabellen er endret!");
if (!hasNext())
throw new NoSuchElementException("Ingen flere verdier");
T verdi = p.verdi;
p = p.etter;
return verdi;
}
}
}