////////////////// class LenketKvadratiskHashTabell //////////////////////////////

package hjelpeklasser;

import java.util.*;

public class LenketKvadratiskHashTabell<T> implements Beholder<T>
{
  private static final int[] PRIM = {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 final class HashObjekt<T>       // en indre klasse
  {
    private final T verdi;                       // verdi av typen T
    private final int hashverdi;                 // hashverdien
    private HashObjekt<T> neste;                 // peker for lenking

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

  private final HashObjekt<T> x                  // et fast objekt
    = new HashObjekt<>(null, 0, null);           // kun null-verdier

  private boolean ledig(int indeks)              // ledig for innlegging
  {
    HashObjekt<T> o = hash[indeks];              // objektet på indeks 
    return o == null || o == x;
  }

  private boolean har(HashObjekt<T> o, T verdi)  // objektet o inneholder verdi
  {
    return o != x && o.verdi.equals(verdi);
  }

  private HashObjekt<T>[] hash;       // en tabell med hashobjekter
  private final float tetthet;        // eng: loadfactor
  private int grense;                 // eng: threshold, norsk: terskel
  private int antall;                 // antall verdier
  private int endringer;              // antall endringer
  private int iprim;                  // indeks i primtallstabellen
  private int antallFjernet;          // antall som er fjernet
  private HashObjekt<T> hode, hale;   // start og slutt på en pekerkjede

  @SuppressWarnings({"rawtypes","unchecked"})             // en annotasjon
  private void utvid()                                    // utvidelsesmetode
  {
    if (iprim == PRIM.length - 1) return;                 // ingen utvidelse

    HashObjekt<T>[] gammelhash = hash;                    // den gamle tabellen
    hash = new HashObjekt[PRIM[++iprim]];                 // en ny tabell
    int dim = hash.length;

    for (int i = 0; i < gammelhash.length; i++)           // den gamletabellen
    {
      HashObjekt<T> o = gammelhash[i];
      if (o == x) gammelhash[i] = null;                   // nuller
      else if (o != null) leggInn(o, o.hashverdi % dim);  // legger inn
    }

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

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

    for (; iprim < PRIM.length; iprim++)       // leter i tabellen prim
    {
      if (dim <= PRIM[iprim]) break;           // stopper her
    }

    dim = iprim < PRIM.length ? PRIM[iprim] : PRIM[iprim - 1];

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

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

  public LenketKvadratiskHashTabell()          // standardkonstruktør
  {
    this(11);
  }

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

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

  // privat hjelpemetode
  private void leggInn(HashObjekt<T> o, int h)            // h = hashindeks
  {
    HashObjekt<T>[] hash1 = hash;                         // hashtabellen
    int dim = hash1.length;                               // dimensjonen

    if (ledig(h)) hash1[h] = o;                            // legger inn
    else
    {
      for (int hopplengde = 1, v = h; ; hopplengde += 2)  // øker med 2
      {
        if ((h += hopplengde) >= dim) h -= dim;           // med klokken
        if (ledig(h)) { hash1[h] = o; return; }           // legger inn

        if ((v -= hopplengde) < 0) v += dim;              // mot klokken
        if (ledig(v)) { hash1[v] = o; return; }           // legger inn
      }
    } // else
  }

  @Override
  public boolean leggInn(T verdi)
  {
    Objects.requireNonNull(verdi, "verdi er null!");    // sjekker verdi
    if (antall >= grense) utvid();                      // utvider

    int hverdi = verdi.hashCode() & 0x7fffffff;         // fjerner fortegn
    int dim = hash.length;                              // tabellens dimensjon
    int h = hverdi % hash.length;                       // hashindeks

    HashObjekt<T> o =
      new HashObjekt<>(verdi, hverdi, null);            // nytt objekt

    leggInn(o, h);                                      // legger inn

    if (tom()) hode = hale = o;                         // første verdi
    else hale = hale.neste = o;                         // havner bakesrt

    antall++;                                           // øker antallet
    endringer++;                                        // en endring
    return true;                                        // vellykket innlegging
  }

  @Override
  public String toString()
  {
    StringJoiner s = new StringJoiner(", ", "[", "]");

    HashObjekt<T> p = hode;
    while (p != null)
    {
      s.add(p.verdi.toString());
      p = p.neste;
    }
    return s.toString();
  }
  /*
  public String toString()
  {
    StringJoiner s = new StringJoiner(", ", "[", "]");
    for (HashObjekt<T> o : hash)
    {
      if (o != null && o != x) s.add(o.verdi.toString());
    }
    return s.toString();
  }
  */

  @Override
  public boolean inneholder(T verdi)
  {
    if (verdi == null) return false;                  // har ikke null-verdier

    HashObjekt<T>[] hash1 = hash;                     // en lokal variabel
    int dim = hash1.length;                           // tabellens lengde

    int hashverdi = verdi.hashCode() & 0x7fffffff;    // fjerner fortegn
    int h = hashverdi % dim;                          // startindeks
    HashObjekt<T> o = hash1[h];                       // objektet på indeks h

    if (o == null) return false;                      // verdi finnes ikke
    else if (verdi.equals(o.verdi)) return true;      // her ligger verdi
    else                                              // leter videre
    {
      for (int hopplengde = 1, v = h; ; hopplengde += 2)  // øker med 2
      {
        if ((h += hopplengde) >= dim) h -= dim;       // med klokken
        o = hash1[h];                                 // objektet på indeks h
        if (o == null) return false;                  // verdi finnes ikke
        else if (verdi.equals(o.verdi)) return true;  // her ligger verdi     

        if ((v -= hopplengde) < 0) v += dim;          // mot klokken
        o = hash1[v];                                 // objektet på indeks v
        if (o == null) return false;                  // verdi finnes ikke
        else if (verdi.equals(o.verdi)) return true;  // her ligger verdi  
      }
    }
  }

  @Override
  public boolean fjern(T verdi)
  {
    if (verdi == null) return false;                // har ikke null-verdier

    HashObjekt<T>[] hash1 = hash;                   // en lokal variabel
    int dim = hash.length;                          // tabellens dimensjon

    int hashverdi = verdi.hashCode() & 0x7fffffff;  // fjerner fortegn
    int h = hashverdi % dim;                        // startindeks
    HashObjekt<T> o = hash1[h];                     // objektet på indeks h
    HashObjekt<T> p;                                // hjelpepeker

    if (o == null) return false;                    // verdi ukjent
    else if (verdi.equals(o.verdi))
    {
      p = hash1[h];
      hash1[h] = x;                                 // fjernet
    }
    else
    {
      for (int hopplengde = 1, v = h; ; hopplengde += 2)  // søker videre
      {
        if ((h += hopplengde) >= dim) h -= dim;     // med klokken
        o = hash1[h];                               // objektet på indeks h
        if (o == null) return false;                // verdi ukjent
        else if (verdi.equals(o.verdi))
        {
          p = hash1[h];
          hash1[h] = x;                             // fjernet
          break;
        }

        if ((v -= hopplengde) < 0) v += dim;        // mot klokken
        o = hash1[v];                               // objektet på indeks v
        if (o == null) return false;                // verdi ukjent
        else if (verdi.equals(o.verdi))
        {
          p = hash1[v];
          hash1[v] = x;                             // fjernet
          break;
        }
      }
    }

    // må fjerne noden p fra hode/hale-listen
    if (antall == 1) hode = hale = null;            // kun en node
    else if (p == hode) hode = hode.neste;          // p lå først
    else
    {
      HashObjekt<T> r = hode;
      while (r.neste != p) r = r.neste;
      r.neste = p.neste;
      if (p == hale) hale = r;
    }

    endringer++;       // en endring
    antall--;          // reduserer antallet

    return true;       // vellykket fjerning
  }

  @Override
  public void nullstill()
  {
    Arrays.fill(hash, null);  // nuller tabellen
    endringer++;              // en endring
    antall = 0;               // tabellen er tom
  }

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

  private class LenketKvadratiskHashTabellIterator implements Iterator<T>
  {
    private HashObjekt<T> p = hode;
    private final int iteratorendringer = endringer;

    @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.neste;

      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.
    */

  }  // LenketKvadratiskHashTabellIterator

} // LenketKvadratiskHashTabell