////////////////// class LenketHashTabell //////////////////////////////

package hjelpeklasser;

import java.util.*;

public class LenketHashTabell<T> implements Beholder<T>
{
  private static final class Node<T>      // en indre nodeklasse
  {
    private final T verdi;          // nodens verdi
    private final int hashverdi;    // lagrer hashverdien
    private Node<T> neste;          // peker til neste node

    private Node(T verdi, int hashverdi, Node<T> neste)  // konstruktør
    {
      this.verdi = verdi;
      this.hashverdi = hashverdi;
      this.neste = neste;
    }
  } // class Node

  private Node<T>[] hash;           // en nodetabell
  private final float tetthet;      // eng: loadfactor
  private int grense;               // eng: threshold (norsk: terskel)
  private int antall;               // antall verdier
  private int endringer;            // antall endringer

  @SuppressWarnings({"rawtypes","unchecked"})
  public LenketHashTabell(int dimensjon)  // konstruktør 
  {
    hash = new Node[dimensjon];
    antall = 0;
    endringer = 0;
    tetthet = 0.75f;
    grense = (int)(tetthet * hash.length);
  }

  public LenketHashTabell()  // standardkonstruktør
  {
    this(13);  // velger 13 som startdimensjon
  }

  private void utvid()
  {
    @SuppressWarnings({"rawtypes","unchecked"})      // bruker raw type
    Node<T>[] nyhash = new Node[2*hash.length + 1];  // dobling + 1

    for (int i = 0; i < hash.length; i++)            // den gamle tabellen
    {
      Node<T> p = hash[i];                           // listen til hash[i]

      while (p != null)                              // går nedover
      {
        Node<T> q = p.neste;                         // hjelpevariabel
        int nyindeks = p.hashverdi % nyhash.length;  // indeks i ny tabell

        p.neste = nyhash[nyindeks];                  // p skal legges først

        nyhash[nyindeks] = p;
        p = q;                                       // flytter p til den neste
      }

      hash[i] = null;                                // nuller i den gamle
    }

    hash = nyhash;                                   // bytter tabell
    grense = (int)(tetthet * hash.length);           // ny grense    
  }

  @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;                // ingen nuller i tabellen
    int hashverdi = verdi.hashCode() & 0x7fffffff;  // "fjerner" fortegn

    Node<T> p = hash[hashverdi % hash.length];      // går til rett indeks

    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;                  // ingen nuller i tabellen
    int hashverdi = verdi.hashCode() & 0x7fffffff;    // "fjerner" fortegn
    int indeks = hashverdi % hash.length;             // finner indeksen 

    Node<T> p = hash[indeks], q = null;               // går til indeks

    while (p != null)                                 // går nedover
    {
      if (verdi.equals(p.verdi)) break;               // verdi ligger i p
      p = (q = p).neste;                              // flytter p og q
    }

    if (p == null) return false;                      // fant ikke verdi
    else
      if (p == hash[indeks]) hash[indeks] = p.neste;  // verdi ligger først
    else q.neste = p.neste;                           // p blir borte

    endringer++;                                      // fjerning er en endring
    antall--;                                         // en mindre
    return true;                                      // vellykket fjerning
  }

  @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;                  // tar vare på verdien

      if (p.neste != null)
      {
        p = p.neste;   // hvis p ikke er den siste
      }
      else  // må gå til neste indeks der hash[indeks] er ulik null
      {
        while (++indeks < hash.length && hash[indeks] == null);
        p = indeks < hash.length ? hash[indeks] : null;
      }

      fjernOK = true;                     // nå kan remove() kalles
      return verdi;                       // returnerer verdien
    }

    @Override
    public void remove()
    {
      if (iteratorendringer != endringer)
          throw new ConcurrentModificationException("Tabellen er endret!");

      if (!fjernOK) throw new IllegalStateException("Ulovlig tilstand!");

      fjernOK = false;            // remove() kan nå ikke kalles på nytt
      int fjernindeks = indeks;   // for å kunne gå tilbake i tabellen

      if (fjernindeks == hash.length || p == hash[fjernindeks])
      {
        while (hash[--fjernindeks] == null);  // går mot venstre

        Node<T> q = hash[fjernindeks];  // den siste i denne listen skal fjernes

        if (q.neste == null) hash[fjernindeks] = null;  // kun en node i listen
        else
        {
          Node<T> f = q;                                // f er forrige til q
          while (q.neste != null) q = (f = q).neste;    // q går til den siste
          f.neste = null;                               // q fjernes
        }
      }
      else  // den forrige til p skal fjernes
      {
        if (hash[fjernindeks].neste == p) hash[fjernindeks] = p;  // p er nr 2
        else
        {
          Node<T> q = hash[fjernindeks];
          while (q.neste.neste != p) q = q.neste;       // leter etter p
          q.neste = p;                                  // p sin forrige fjernes
        }
      }

      endringer++;           // en global endring
      iteratorendringer++;   // en lokal endring
      antall--;              // en verdi er fjernet
    }
  } // class HashTabellIterator   

}  // class LenketHashTabell