package hjelpeklasser;
import java.util.*;
public class LenketHashTabell<T> implements Beholder<T>
{
private static final class Node<T>
{
private final T verdi;
private final int hashverdi;
private Node<T> neste;
private Node(T verdi, int hashverdi, Node<T> neste)
{
this.verdi = verdi;
this.hashverdi = hashverdi;
this.neste = neste;
}
}
private Node<T>[] hash;
private final float tetthet;
private int grense;
private int antall;
private int endringer;
@SuppressWarnings({"rawtypes","unchecked"})
public LenketHashTabell(int dimensjon)
{
hash = new Node[dimensjon];
antall = 0;
endringer = 0;
tetthet = 0.75f;
grense = (int)(tetthet * hash.length);
}
public LenketHashTabell()
{
this(13);
}
private void utvid()
{
@SuppressWarnings({"rawtypes","unchecked"})
Node<T>[] nyhash = new Node[2*hash.length + 1];
for (int i = 0; i < hash.length; i++)
{
Node<T> p = hash[i];
while (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);
}
@Override
public boolean leggInn(T verdi)
{
Objects.requireNonNull(verdi, "verdi er null!");
if (antall >= grense) utvid();
int hashverdi = verdi.hashCode();
int indeks = hashverdi % hash.length;
hash[indeks] = new Node<>(verdi, hashverdi, hash[indeks]);
antall++;
endringer++;
return true;
}
@Override
public int antall()
{
return antall;
}
@Override
public boolean tom()
{
return antall == 0;
}
@Override
public String toString()
{
StringJoiner sj = new StringJoiner(", ", "[", "]");
for (Node<T> p : hash)
{
while (p != null)
{
sj.add(p.verdi.toString());
p = p.neste;
}
}
return sj.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;
endringer++;
antall--;
return true;
}
@Override
public void nullstill()
{
if (antall > 0)
{
antall = 0;
for (int i = 0; i < hash.length; i++) hash[i] = null;
}
endringer++;
}
@Override
public Iterator<T> iterator()
{
return new HashTabellIterator();
}
private class HashTabellIterator implements Iterator<T>
{
private int indeks = 0;
private Node<T> p = null;
private boolean fjernOK = false;
private int iteratorendringer = 0;
private HashTabellIterator()
{
endringer = iteratorendringer;
if (!tom())
{
while (hash[indeks] == null) indeks++;
p = hash[indeks];
}
}
@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;
if (p.neste != null)
{
p = p.neste;
}
else
{
while (++indeks < hash.length && hash[indeks] == null);
p = indeks < hash.length ? hash[indeks] : null;
}
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 fjernindeks = indeks;
if (fjernindeks == hash.length || p == hash[fjernindeks])
{
while (hash[--fjernindeks] == null);
Node<T> q = hash[fjernindeks];
if (q.neste == null) hash[fjernindeks] = null;
else
{
Node<T> f = q;
while (q.neste != null) q = (f = q).neste;
f.neste = null;
}
}
else
{
if (hash[fjernindeks].neste == p) hash[fjernindeks] = p;
else
{
Node<T> q = hash[fjernindeks];
while (q.neste.neste != p) q = q.neste;
q.neste = p;
}
}
endringer++;
iteratorendringer++;
antall--;
}
}
}