////////////////// class SBinTre //////////////////////////////

package hjelpeklasser;

import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class SBinTre<T>  implements Beholder<T>
{
  private static final class Node<T> // en indre nodeklasse
  {
    private T verdi;                 // nodens verdi
    private Node<T> venstre, høyre;  // venstre og høyre barn

    private Node(T verdi, Node<T> v, Node<T> h)  // konstruktør
    {
      this.verdi = verdi; venstre = v; høyre = h;
    }

    private Node(T verdi)  // konstruktør
    {
      this(verdi, null, null);
    }
  } // class Node

  private Node<T> rot;                       // peker til rotnoden
  private int antall;                        // antall noder
  private final Comparator<? super T> comp;  // komparator
  private int endringer;                     // antall endringer

  public SBinTre(Comparator<? super T> c)    // konstruktør
  {
    rot = null;
    antall = 0;
    comp = c;
    endringer = 0;
  }

  public static <T extends Comparable<? super T>> SBinTre<T> lagTre()
  {
    return new SBinTre<>(Komparator.<T>naturlig());
  }

  public static <T> SBinTre<T> lagTre(Comparator<? super T> c)
  {
    return new SBinTre<>(c);
  }

  @Override
  public int antall()        // antall verdier i treet
  {
    return antall;
  }

  @Override
  public boolean tom()       // er treet tomt?
  {
    return antall == 0;
  }

  @Override
  public void nullstill()
  {
    rot = null;
    antall = 0;
    endringer++;
  }

  @Override
  public boolean leggInn(T verdi)    // skal ligge i class SBinTre
  {
    if (verdi == null) throw new NullPointerException("Ulovlig nullverdi!");

    Node<T> p = rot, q = null;               // p starter i roten
    int cmp = 0;                             // hjelpevariabel

    while (p != null)       // fortsetter til p er ute av treet
    {
      q = p;                                 // q er forelder til p
      cmp = comp.compare(verdi,p.verdi);     // bruker komparatoren
      p = cmp < 0 ? p.venstre : p.høyre;     // flytter p
    }

    // p er nå null, dvs. ute av treet, q er den siste vi passerte

    p = new Node<>(verdi);                   // oppretter en ny node

    if (q == null) rot = p;                  // p blir rotnode
    else if (cmp < 0) q.venstre = p;         // venstre barn til q
    else q.høyre = p;                        // høyre barn til q

    endringer++;         // det er gjort en endring i treet
    antall++;                                // én verdi mer i treet
    return true;                             // vellykket innlegging
  }

  public static <T> SBinTre<T> lagTre(T[] a, Comparator<? super T> c)
  {
    SBinTre<T> tre = lagTre(c);                 // komparatoren c
    for (T verdi : a) tre.leggInn(verdi);       // bygger opp treet
    return tre;                                 // treet returneres
  }

  public static <T extends Comparable<? super T>> SBinTre<T> lagTre(T[] a)
  {
    return lagTre(a,Komparator.<T>naturlig());  // naturlig ordning
  }

  private static int høyde(Node<?> p)       // ? betyr vilkårlig type
  {
    if (p == null) return -1;        // et tomt tre har høyde -1
    return 1 + Math.max(høyde(p.venstre), høyde(p.høyre));
  }

  public int høyde()
  {
    return høyde(rot);  // kaller den private metoden
  }

  @Override
  public String toString()                   // hører til SBinTre
  {
    StringBuilder s = new StringBuilder();   // StringBuilder
    s.append('[');                           // starter med [
    if (!tom()) toString(rot,s);             // den rekursive metoden
    s.append(']');                           // avslutter med ]
    return s.toString();                     // returnerer
  }

  private static <T> void toString(Node<T> p, StringBuilder s)
  {
    if (p.venstre != null)                   // p har et venstre subtre
    {
      toString(p.venstre, s);                // komma og mellomrom etter
      s.append(',').append(' ');             // den siste i det venstre
    }                                        // subtreet til p

    s.append(p.verdi);                       // verdien i p

    if (p.høyre != null)                     // p har et høyre subtre
    {
      s.append(',').append(' ');             // komma og mellomrom etter
      toString(p.høyre, s);                  // p siden p ikke er den
    }                                        // siste noden i inorden
  }

  private static <T> Node<T>
  balansert(T[] a, int v, int h, Comparator<? super T> c)
  {
    if (v > h) return null;                               // et tomt tre
    else if (v == h) return new Node<>(a[v]);             // en bladnode

    int m = (v + h)/2;                                    // midten
    T verdi = a[m];                                       // midtverdien

    while (v < m && c.compare(verdi, a[m-1]) == 0) m--;   // til venstre

    Node<T> p = balansert(a, v, m - 1, c);                // venstre subtre
    Node<T> q = balansert(a, m + 1, h, c);                // høyre subtre

    return new Node<>(verdi, p, q);                       // rotnoden
  }

  public static <T extends Comparable<? super T>>
  SBinTre<T> lagBalansertTre(T[] a)
  {
    SBinTre<T> tre = lagTre();
    tre.rot = balansert(a, 0, a.length - 1, tre.comp);
    tre.antall = a.length;
    return tre;
  }

  public static <T>
  SBinTre<T> lagBalansertTre(T[] a, Comparator<? super T> c)
  {
    SBinTre<T> tre = lagTre(c);
    tre.rot = balansert(a, 0, a.length - 1, tre.comp);
    tre.antall = a.length;
    return tre;
  }

  @Override
  public boolean inneholder(T verdi)     // skal ligge i klassen SBinTre
  {
    if (verdi == null) return false;            // treet har ikke nullverdier

    Node<T> p = rot;                            // starter i roten
    while (p != null)                           // sjekker p
    {
      int cmp = comp.compare(verdi,p.verdi);    // sammenligner
      if (cmp < 0) p = p.venstre;               // går til venstre
      else if (cmp > 0) p = p.høyre;            // går til høyre
      else return true;                         // cmp == 0, funnet
    }
    return false;                               // ikke funnet
  }

  public T min()                 // skal returnere treets minste verdi
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");

    Node<T> p = rot;                            // starter i roten
    while (p.venstre != null) p = p.venstre;    // går mot venstre
    return p.verdi;                             // den minste verdien
  }

  public T maks()               // skal returnere treets største verdi
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");

    Node<T> p = rot;                            // starter i roten
    while (p.høyre != null) p = p.høyre;        // går mot høyre
    return p.verdi;                             // den største verdien
  }

  public T gulv(T verdi)
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");
    if (verdi == null) throw new NullPointerException("Ulovlig nullverdi!");

    Node<T> p = rot; T gulv = null;

    while (p != null)
    {
      int cmp = comp.compare(verdi, p.verdi);

      if (cmp < 0) p = p.venstre;  // gulvet ligger til venstre
      else if (cmp > 0)
      {
        gulv = p.verdi;            // nodeverdien er en kandidat
        p = p.høyre;
      }
      else return p.verdi;         // verdi ligger i treet
    }
    return gulv;
  }

  public T tak(T verdi)
  {
    if (tom())
    {
      throw new NoSuchElementException("Treet er tomt!");
    }

    Node<T> p = rot;
    T tak = null;

    while (p != null)
    {
      int cmp = comp.compare(verdi, p.verdi);

      if (cmp < 0)
      {
        tak = p.verdi;
        p = p.venstre;
      }
      else if (cmp > 0)
      {
        p = p.høyre;
      }
      else
      {
        return p.verdi;
      }
    }

    return tak;
  }

  public T større(T verdi)
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");
    if (verdi == null) throw new NullPointerException("Ulovlig nullverdi!");

    Node<T> p = rot;
    T større = null;

    while (p != null)
    {
      int cmp = comp.compare(verdi, p.verdi);

      if (cmp < 0)
      {
        større = p.verdi;  // en kandidat
        p = p.venstre;
      }
      else                 // den må ligge til høyre
      {
        p = p.høyre;
      }
    }

    return større;
  }

  public T mindre(T verdi)
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");

    Node<T> p = rot;
    T mindre = null;

    while (p != null)
    {
      int cmp = comp.compare(verdi, p.verdi);

      if (cmp <= 0)
      {
        p = p.venstre;
      }
      else
      {
        mindre = p.verdi;
        p = p.høyre;
      }
    }

    return mindre;
  }

  @Override
  public boolean fjern(T verdi)  // hører til klassen SBinTre
  {
    if (verdi == null) return false;  // treet har ingen nullverdier

    Node<T> p = rot, q = null;   // q skal være forelder til p

    while (p != null)            // leter etter verdi
    {
      int cmp = comp.compare(verdi,p.verdi);      // sammenligner
      if (cmp < 0) { q = p; p = p.venstre; }      // går til venstre
      else if (cmp > 0) { q = p; p = p.høyre; }   // går til høyre
      else break;    // den søkte verdien ligger i p
    }
    if (p == null) return false;   // finner ikke verdi

    if (p.venstre == null || p.høyre == null)  // Tilfelle 1) og 2)
    {
      Node<T> b = p.venstre != null ? p.venstre : p.høyre;  // b for barn
      if (p == rot) rot = b;
      else if (p == q.venstre) q.venstre = b;
      else q.høyre = b;
    }
    else  // Tilfelle 3)
    {
      Node<T> s = p, r = p.høyre;   // finner neste i inorden
      while (r.venstre != null)
      {
        s = r;    // s er forelder til r
        r = r.venstre;
      }

      p.verdi = r.verdi;   // kopierer verdien i r til p

      if (s != p) s.venstre = r.høyre;
      else s.høyre = r.høyre;
    }

    endringer++;   // det er gjort en endring i treet
    antall--;      // det er nå én node mindre i treet
    return  true;
  }

  public void fjernMin()  // hører til klassen SBinTre
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");

    if (rot.venstre == null) rot = rot.høyre;  // rotverdien er minst
    else
    {
      Node<T> p = rot.venstre, q = rot;
      while (p.venstre != null)
      {
        q = p;  // q er forelder til p
        p = p.venstre;
      }
      // p er noden med minst verdi
      q.venstre = p.høyre;
    }
    endringer++;   // det er gjort en endring i treet
    antall--;      // det er nå én node mindre i treet
  }

  private class InordenIterator implements Iterator<T>
  {
    private Stakk<Node<T>> s = new TabellStakk<>();  // for traversering
    private Node<T> p = null;                        // nodepeker
    private Node<T> q = null;                        // nodepeker
    private int iteratorendringer;                   // iteratorendringer

    private Node<T> først(Node<T> q)   // en hjelpemetode
    {
      while (q.venstre != null)        // starter i q
      {
        s.leggInn(q);                  // legger q på stakken
        q = q.venstre;                 // går videre mot venstre
      }
      return q;                        // q er lengst ned til venstre
    }

    public InordenIterator()  // konstruktør
    {
      if (rot == null) return;         // treet er tomt
      p = først(rot);                  // bruker hjelpemetoden
      iteratorendringer = endringer;   // setter treets endringer
    }

    @Override
    public T next()
    {
      if (!hasNext()) throw new NoSuchElementException();

      if (iteratorendringer != endringer)
                   throw new ConcurrentModificationException();

      T verdi = p.verdi;               // tar vare på verdien i noden p
      q = p;                           // q oppdateres før p flyttes

      if (p.høyre != null) p = først(p.høyre);  // p har høyre subtre
      else if (!s.tom()) p = s.taUt();          // p har ikke høyre subtre
      else p = null;                            // stakken er tom

      return verdi;                    // returnerer verdien
    }

    @Override
    public boolean hasNext()
    {
      return p != null;
    }

    @Override
    public void remove()
    {
      if (q == null)
      {
        throw new IllegalStateException();
      }

      if (iteratorendringer != endringer)
      {
        throw new ConcurrentModificationException();
      }

      if (q.høyre == null)  // Tilfelle 1
      {
        if (p == null)  // Tilfelle 1A, q er den siste i inorden
        {
          if (q == rot)
          {
            rot = q.venstre;  // q fjernes
          } else
          {
            Node<T> f = rot;  // må finne forelder til q
            while (f.høyre != q)
            {
              f = f.høyre;
            }
            f.høyre = q.venstre;   // q fjernes
          }
        }
        else  // Tilfelle 1B, q ligger i det venstre subtreet til p
        {
          if (q == p.venstre)
          {
            p.venstre = q.venstre;  // q fjernes
          } else  // q != p.venstre
          {
            Node<T> f = p.venstre;  // må finne forelder til q
            while (f.høyre != q)
            {
              f = f.høyre;
            }
            f.høyre = q.venstre;    // q fjernes
          }
        }
      }
      else  // Tilfelle 2
      {
        q.verdi = p.verdi;  // kopierer
        if (q.høyre == p)
        {
          q.høyre = p.høyre;  // fjerner p
        } else  // forelder til p ligger på stakken
        {
          Node<T> f = s.taUt();  // p sin forelder
          f.venstre = p.høyre;   // fjerner p
          while (f != q.høyre)
          {
            f = s.taUt();  // fjerner fra stakken
          }
        }
        p = q;  // setter p tilbake til q
      }

      q = null;               // for å hindre to remove() på rad
      iteratorendringer++;    // en endring i treet via iteratoren
      endringer++;            // det er gjort en endring i treet
      antall--;               // en verdi mindre i treet
    }

  } // InordenIterator

  @Override
  public Iterator<T> iterator()  // returnerer en iterator
  {
    return new InordenIterator();
  }

} // SBinTre