////////////////// class DobbeltlenketHashTabell //////////////////////////////

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>      // 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> etter;          // peker til den som legges inn senere

    private Node(T verdi, int hashverdi, Node<T> neste)  // konstruktør
    {
      this.verdi = verdi;
      this.hashverdi = hashverdi;
      this.neste = neste;
      this.etter = null;
    }
  } // 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 iprim;                // indeks i tabellen PRIM
  private int endringer;            // antall endringer
  private Node<T> hode, hale;       // kjede for innleggingsrekkefølge

  private void utvid()                               // hører til HashTabell
  {
    if (iprim == PRIM.length - 1) return;            // ingen utvidelse

    @SuppressWarnings({"rawtypes","unchecked"})      // bruker raw type
    Node<T>[] nyhash = new Node[PRIM[++iprim]];      // ca. dobling

    for (int i = 0; i < hash.length; i++)            // den gamle tabellen
    {
      for (Node<T> p = hash[i]; p != null; )         // pekerkjeden til hash[i]    
      {
        Node<T> q = p.neste;                         // hjelpepeker
        int nyindeks = p.hashverdi % nyhash.length;  // indeks i ny tabell

        p.neste = nyhash[nyindeks];                  // p legges først i kjeden
        nyhash[nyindeks] = p;                        // til nyhash[indeks]

        p = q;                                       // flytter p til den neste
      }
      hash[i] = null;                                // nuller i den gamle
    }

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

  @SuppressWarnings({"rawtypes","unchecked"})        // en annotasjon
  public DobbeltlenketHashTabell(int dimensjon)      // konstruktør 
  {
    if (dimensjon < 0) throw new IllegalArgumentException("Negativ dimensjon!");

    iprim = 0;  // en instansvariabel
    for (; iprim < PRIM.length; iprim++) if (dimensjon <= PRIM[iprim]) break;
    dimensjon = iprim < PRIM.length ? PRIM[iprim] : PRIM[iprim - 1];

    hash = new Node[dimensjon];                // bruker raw type
    tetthet = 0.75f;                           // maksimalt 75% full
    grense = (int)(tetthet * hash.length);     // gjør om til int

    hode = hale = null;                        // foreløpig tom liste
    antall = 0;                                // foreløpig ingen verdier
    endringer = 0;                             // foreløpig ingen endringer
  }

  public DobbeltlenketHashTabell()             // standardkonstruktør
  {
    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;  // fjerner fortegn
    int indeks = hashverdi % hash.length;           // finner indeksen

    // legger inn først i listen som hører til indeks
    hash[indeks] = new Node<>(verdi, hashverdi, hash[indeks]);  // lagrer hashverdi

    if (tom()) hode = hale = hash[indeks];  // hode og hale går til samme node
    else hale = hale.etter = hash[indeks];  // hale går til den nyeste noden  

    endringer++;     // en endring
    antall++;        // en ny verdi
    return true;     // vellykket innlegging
  }

  @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;                // 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                                              // noden p skal fjernes
    {
      if (p == hash[indeks]) hash[indeks] = p.neste;  // verdi ligger først
      else q.neste = p.neste;                         // p blir borte

      // må fjerne noden p fra hode/hale-listen
      if (antall == 1) hode = hale = null;            // kun en node
      else if (p == hode) hode = hode.etter;          // p lå først
      else
      {
        Node<T> r = hode;
        while (r.etter != p) r = r.etter;
        r.etter = p.etter;
        if (p == hale) hale = r;
      }
    }
    endringer++;                                      // en endring
    antall--;                                         // en mindre
    return true;                                      // vellykket fjerning
  }

  @Override
  public void nullstill()
  {
    if (!tom())
    {
      endringer++;     // en endring
      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;              // tar vare på verdien
      p = p.etter;                    // flytter p i hode/hale-listen

      return verdi;                   // returnerer verdien
    }

    /*
    Metoden remove() er ikke kodet. Den er komplisert å kode i dette 
    opplegget. Den skal fjerne den forrige noden til p både fra
    hode/hale-listen og fra selve hashtabellen. Vi kan finne den
    i hode/hale-listen, men siden duplikater er tillatt er det 
    problematisk å finne den i selve hashtabellen. Dette er ikke umulig,
    men det blir ineffektivt.
    */

  } // class HashTabellIterator   

}  // class DobbeltlenketHashTabell