////////////////// class SFBinTre //////////////////////////////

package hjelpeklasser;

import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.stream.Stream;

public class SFBinTre<T> implements Beholder<T>
{
  private static final class Node<T>
  {
    private T verdi;             // nodens verdi
    private Node<T> venstre;     // venstre barn
    private Node<T> høyre;       // høyre barn
    private Node<T> forelder;    // nodens forelder

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

    private Node(T verdi, Node<T> forelder)
    {
      this(verdi,null,null,forelder);
    }

  } // class Node  

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

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

  public static <T extends Comparable<? super T>> SFBinTre<T> sfbintre()
  {
    return new SFBinTre<>(Comparator.naturalOrder());
  }

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

  public static <T extends Comparable<? super T>> SFBinTre<T> sfbintre(Stream<T> s)
  {
    SFBinTre<T> tre = sfbintre();
    s.forEach(tre::leggInn);
    return tre;
  }

  public static <T> SFBinTre<T> sfbintre(Stream<T> s, Comparator<? super T> c)
  {
    SFBinTre<T> tre = SFBinTre.sfbintre(c);
    s.forEach(tre::leggInn);
    return tre;
  }

  @Override
  public boolean leggInn(T verdi)
  {
    // må lages spesielt for dennne klassen
    throw new UnsupportedOperationException("Not supported yet.");
  }

  @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 inneholder(T verdi)     // skal ligge i klassen SBinTre
  {
    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
  }

  @Override
  public boolean fjern(T verdi)
  {
    // må lages spesielt for dennne klassen
    throw new UnsupportedOperationException("Not supported yet.");
  }

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

  /////////// class InordenIterator //////////////

  private class InordenIterator implements Iterator<T>
  {
    private Node<T> p;
    private int iteratorendringer;

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

    public InordenIterator()  // konstruktør
    {
      p = null;
      if (rot != null) p = først(rot);    // bruker hjelpemetoden
      iteratorendringer = endringer;
    }

    @Override
    public T next()
    {
      // må lages spesielt for dennne klassen
      throw new UnsupportedOperationException("Not supported yet.");
    }

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

  } // class InordenIterator

  @Override
  public String toString()
  {
    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
  }

} // class SFBinTre