////////////// class STBinTre ////////////////////////

package hjelpeklasser;

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


public class STBinTre<T> implements Beholder<T>
{
  private static final class Node<T>
  {
    private T verdi;                  // nodens verdi
    private Node<T> venstre;          // peker til venstre barn
    private Node<T> høyre;            // peker til høyre barn
    private boolean harHøyreBarn;     // hvor går høyre peker?

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

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

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

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

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

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

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

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

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

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

  @Override
  public boolean leggInn(T verdi)
  {
    Node<T> p = rot, q = null;               // pekere
    int cmp = 0;                             // hjelpevariabel

    while (p != null)
    {
      q = p;                                 // q er forelder til p
      cmp = comp.compare(verdi,p.verdi);     // sammenligner
      if (cmp < 0) p = p.venstre;            // går til venstre
      else if (p.harHøyreBarn) p = p.høyre;  // går til høyre
      else break;                            // har ikke høyre barn
    }

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

    if (q == null)
    {
      rot = p;                               // første node - rotnoden
    }
    else if (cmp < 0)                        // verdi < q.verdi
    {
      q.venstre = p;                         // p blir venstre barn til q
      p.høyre = q;                           // q er den neste til p
    }
    else                                     // verdi >= q.verdi
    {
      p.høyre = q.høyre;                     // p's neste settes lik q's neste
      q.høyre = p;                           // p blir høyre barn til q
      q.harHøyreBarn = true;                 // q har fått et høyre barn
    }

    endringer++;                             // en endring i treet
    antall++;                                // en ny verdi i treet

    return true;                             // vellykket innlegging
  }

  @Override
  public boolean inneholder(T verdi)
  {
    return false;  // mangler kode
  }

  @Override
  public boolean fjern(T verdi)
  {
    return false;  // mangler kode
  }

  @Override
  public String toString()
  {
    if (tom()) return "[]";                    // et tomt tre
    StringBuilder s = new StringBuilder();     // oppretter en StringBuilder
    s.append('[');                             // startparentes: [

    Node<T> p = rot;                     // starter i roten
    while (p.venstre != null) p = p.venstre;   // finner første i inorden
    s.append(p.verdi);                         // legger inn minste verdi

    while (true)
    {
      if (p.harHøyreBarn)
      {
        p = p.høyre;                           // p har høyre barn - går dit
        while (p.venstre != null)
        {
          p = p.venstre;                       // går videre til venstre
        }
      }
      else if (p.høyre == null) break;         // p er sist i inorden
      else p = p.høyre;                        // går til neste i inorden

      s.append(',').append(' ').append(p.verdi);  // legger inn p.verdi
    }

    s.append(']');                             // avslutningsparentes: ]

    return s.toString();                       // returnerer tegnstrengen
  }

  @Override
  public Iterator<T> iterator()
  {
    throw new UnsupportedOperationException("Not supported yet.");
  }

} // class STBinTre