////////////////// class Hashtabell //////////////////////////////

package hjelpeklasser;

import java.util.*;

public class Hashtabell<T> implements Beholder<T>  // lukket adressering
{
  private final float tetthet;        // eng: loadfactor
  private int terskel;                // eng: threshold
  private int antall;                 // antall verdier

  private Beholder<T>[] hash;         // en tabell av beholdere

  private int indeks(T verdi)
  {
    return (verdi.hashCode() & 0x7fffffff) % hash.length;
  }

  @SuppressWarnings("unchecked")
  private void rehash()
  {
    Beholder<T>[] gammel = hash;
    hash = new Beholder[2*gammel.length + 1];

    terskel = (int)(tetthet * hash.length);  // ny terskel

    for (int i = 0; i < hash.length; i++)
    {
      hash[i] = new EnkeltLenketListe<>();     // oppretter tomme lister
    }

    for (Beholder<T> beholder : gammel)
    {
      if (!beholder.tom())
      {
        for (T t : beholder) leggInn(t);
      }
    }
  }

  @SuppressWarnings("unchecked")
  public Hashtabell(int dimensjon)   // konstruktør med parameter
  {
    if (dimensjon < 1) throw
      new IllegalArgumentException("Ulovig dimensjon!");

    hash = new Beholder[dimensjon];  // bruker raw type

    for (int i = 0; i < dimensjon; i++)
    {
      hash[i] = new EnkeltLenketListe<>();  // oppretter tomme lister
    }

    tetthet = 0.75f;  // tabellen skal være maksimalt 75% full
    terskel = (int)(tetthet*dimensjon);
    antall = 0;
  }

  public Hashtabell()  // standardkonstruktør
  {
    this(13);
  }

  @Override
  public int antall() { return antall; }

  @Override
  public boolean tom() { return antall == 0; }

  @Override
  public boolean leggInn(T verdi)
  {
   if (verdi == null)
      throw new IllegalArgumentException("verdi er null!");

   if (antall >= terskel) rehash();

    antall++;
    return hash[indeks(verdi)].leggInn(verdi);
  }

  @Override
  public boolean inneholder(T verdi)
  {
    if (verdi == null) return false;
    else return hash[indeks(verdi)].inneholder(verdi);
  }

  @Override
  public boolean fjern(T verdi)
  {
    if (verdi == null) return false;

    antall--;
    return hash[indeks(verdi)].fjern(verdi);
  }

  @Override
  public void nullstill()
  {
    for (Beholder<T> beholder : hash) beholder.nullstill();
    antall = 0;
  }

  @Override
  public String toString()
  {
    if (tom()) return "[]";

    StringBuilder s = new StringBuilder("[");

    for (Beholder<T> beholder : hash)
    {
      if (!beholder.tom())
      {
        for (T t : beholder)  // bruker iteratoren i liste
          s.append(t).append(',').append(' ');
      }
    }

    s.delete(s.length() - 2, s.length());  // fjerner ", " bakerst
    s.append(']');

    return s.toString();
  }

  private class HashIterator implements Iterator<T>
  {
    private int indeks = 0;
    private Iterator<T> i;

    private HashIterator()
    {
      while (indeks < hash.length && hash[indeks].tom()) indeks++;
      if (indeks < hash.length) i = hash[indeks].iterator();
      else i = hash[0].iterator();
    }

    @Override
    public boolean hasNext()
    {
      return i.hasNext();
    }

    @Override
    public T next()
    {
      if (!hasNext())
        throw new NoSuchElementException("Ingen flere verdier");

      T temp = i.next();

      if (!i.hasNext())
      {
        indeks++;
        while (indeks < hash.length && hash[indeks].tom()) indeks++;
        if (indeks < hash.length) i = hash[indeks].iterator();
      }
      return temp;
    }

    @Override
    public void remove()
    {
      throw new UnsupportedOperationException();
    }
  }

  @Override
  public Iterator<T> iterator()
  {
    return new HashIterator();
  }

}  // class Hashtabell