////////////////// class KvadratiskHashTabell //////////////////////////////

package hjelpeklasser;

import java.util.*;

public class KvadratiskHashTabell<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 verdi, int hashverdi)   // konstruktør
    {
      this.verdi = verdi;
      this.hashverdi = hashverdi;
    }
  }

  private final HashObjekt<T> x                  // et fast objekt
    = new HashObjekt<>(null, 0);                 // 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 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

  @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 KvadratiskHashTabell(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
  }

  public KvadratiskHashTabell()                // 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);  // nytt objekt
    leggInn(o, h);                                      // legger inn

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

  @Override
  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

    if (o == null) return false;                    // verdi ukjent
    else if (verdi.equals(o.verdi)) hash1[h] = x;   // fjerner verdi
    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)) { hash1[h] = x; break; } // fjerner

        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)) { hash1[v] = x; break; } // fjerner
      }
    }

    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 KvadratiskHashTabellIterator();
  }

  private class KvadratiskHashTabellIterator implements Iterator<T>
  {
    private int i;                          // tabellindeks starter i 0
    private boolean fjernOK = false;        // brukes i next() og remove()
    private int iteratorendringer = endringer;

    private KvadratiskHashTabellIterator()  // konstruktør
    {
      while (i < hash.length && (hash[i] == null || hash[i] == x)) i++;
    }

    @Override
    public boolean hasNext()
    {
      return i < hash.length;               // er indeks i inne i tabellen?      
    }

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

      if (!hasNext())
        throw new NoSuchElementException("Ingen flere verdier");

      T verdi = hash[i].verdi;

      // flytter tabellindeksen i videre - hopper over null og x
      while (++i < hash.length && (hash[i] == null || hash[i] == x));

      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 j = i - 1;              // hjelpevariabel for kunne gå bakover
      while (hash[j] == null || hash[j] == x) j--;

      hash[j] = x;                // fjerner

      endringer++;                // en global endring
      iteratorendringer++;        // en lokal endring
      antall--;                   // reduserer antallet
    }

  }  // KvadratiskHashTabellIterator

} // KvadratiskHashTabell