////////////////// class RSBinTre //////////////////////////////

package hjelpeklasser;

import java.util.*;

public class RSBinTre<T> implements Beholder<T>
{
  private static final boolean SVART = true;
  private static final boolean RØD   = false;

  private static final class Node<T>    // en indre nodeklasse
  {
    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 farge;       // RØD eller SVART

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

  } // slutt på class Node

  private final Node<T> NULL;            // en svart nullnode
  private Node<T> rot;                   // treets rot
  private int antall;                    // antall verdier
  private Comparator<? super T> comp;    // treets komparator

  public RSBinTre(Comparator<? super T> comp)  // konstruktør
  {
    rot = NULL = new Node<>(null,null,null,SVART);
    this.comp = comp;
  }

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

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

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

  @Override
  public boolean leggInn(T verdi)
  {
    if (rot == NULL)         // treet er tomt
    {
      rot = new Node<>(verdi,NULL,NULL,SVART);
      antall++;
      return true;
    }

    // bruke en stakk for å kunne gå oppover etterpå
    Stakk<Node<T>> stakk = new TabellStakk<>();

    Node<T> p = rot;   // hjelpevariabel
    int cmp = 0;       // hjelpevariabel

    while (p != NULL)
    {
      stakk.leggInn(p);                   // legger p på stakken

      cmp = comp.compare(verdi,p.verdi);  // sammenligner

      if (cmp < 0) p = p.venstre;         // til venstre
      else if (cmp > 0) p = p.høyre;      // til høyre
      else return false;                  // duplikater ikke tillatt
    }

    Node<T> x = new Node<>(verdi,NULL,NULL,RØD);

    antall++;                             // en ny verdi i treet

    Node<T> f = stakk.taUt();             // forelder til x

    if (cmp < 0) f.venstre = x;           // x blir venstre barn
    else f.høyre = x;                     // x blir høyre barn

    if (f.farge == SVART) return true;    // vellykket innlegging

    // Hva hvis f er RØD?

    Node<T> b = stakk.taUt();    // b for besteforelder

    while (true)
    {
      Node<T> s = (f == b.venstre) ? b.høyre : b.venstre;

      if (s.farge == SVART)
      {
        b.farge = RØD;

        if (x == f.venstre)         // 1a) eller 2b)
        {
          if (f == b.venstre)       // 1a)
          {
            p = EHR(b); f.farge = SVART;  // enkel høyrerotasjon + fargeskifte
          }
          else  // x == f.høyre     // 2b)
          {
            p = DVR(b); x.farge = SVART;  // dobbel venstrerotasjon + fargeskifte
          }
        }
        else // x == f.høyre        // 1b) eller 2a)
        {
          if (f == b.venstre)       // 2a)
          {
            p = DHR(b); x.farge = SVART;  // dobbel høyrerotasjon + fargeskifte
          }
          else  // f == b.høyre     // 1b)
          {
            p = EVR(b); f.farge = SVART;  // enkel venstrerotasjon + fargeskifte
          }
        }

        if (b == rot) rot = p;  // Hvis b var rotnoden, så må roten oppdateres
        else
        {
          Node<T> q = stakk.taUt();
          if (b == q.venstre) q.venstre = p;
          else q.høyre = p;
        }

        return true;  // to røde noder på rad er nå avverget
      }
      else  // s.farge == RØD
      {
        f.farge = s.farge = SVART;          // f og s blir svarte

        if (b == rot) return true;          // vi stopper

        b.farge = RØD;                      // b blir RØD  

        // er forelder til b (dvs. oldeforelder til x) rød?

        Node<T> o = stakk.taUt();           // oldeforelder til x
        if (o.farge == SVART) return true;  // vi stopper

        // nå har den røde node b en rød forelder
        // vi omdøper x, f og b og fortsetter oppover

        x = b;                  // ny x
        f = o;                  // ny f
        b = stakk.taUt();       // ny b

      } // else  

    } // while

  } // leggInn

  @Override
  public boolean inneholder(T verdi)
  {
    for (Node<T> p = rot; p != NULL; )
    {
      int cmp = comp.compare(verdi,p.verdi);
      if (cmp > 0) p = p.høyre;
      else if (cmp < 0) p = p.venstre;
      else return true;
    }
    return false;  // ikke funnet
  }

  @Override
  public boolean fjern(T verdi)
    throws UnsupportedOperationException
  {
    // ikke implementert
    throw new UnsupportedOperationException();
  }

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

  public int høyde()
  {
    return høyde(rot);
  }

  private int høyde(Node<T> p)
  {
    if (p == NULL) return -1;
    return 1 + Math.max(høyde(p.venstre), høyde(p.høyre));
  }

  @Override
  public void nullstill()
  {
    rot = NULL;
    antall = 0;
  }

  @Override
  public Iterator iterator()
  {
    return new InordenIterator();
  }

  private final class InordenIterator implements Iterator<T>
  {
    private final Stakk<Node<T>> s;
    private Node<T> p;

    private InordenIterator()
    {
      s = new TabellStakk<>();
      if (rot == NULL) p = NULL;     // tomt tre
      else p = først(s,rot);
    }

    // den første i inorden i det treet som har p som rot
    private Node<T> først(Stakk<Node<T>> s, Node<T> p)
    {
      while (p.venstre != NULL)
      {
        s.leggInn(p);
        p = p.venstre;
      }
      return p;
    }

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

    @Override
    public void remove()
    {
      // ikke implementert
      throw new UnsupportedOperationException();
    }

    @Override
    public T next()  // neste er med hensyn på inorden
    {
      if (p == NULL)
        throw new NoSuchElementException();

      T verdi = p.verdi;

      if (p.høyre != NULL) p = først(s,p.høyre);
      else p = s.tom() ? NULL : s.taUt();
      return verdi;
    }

  } // slutt på class InordenIterator  

  //////////////////////////////////
  /// Private hjelpemetoder ////////
  //////////////////////////////////

  private static <T> Node<T> EHR(Node<T> p)  // Enkel høyrerotasjon
  {
    Node<T> q = p.venstre;

    p.venstre = q.høyre;
    q.høyre = p;
    return q;
  }

  private static <T> Node<T> EVR(Node<T> p)  // Enkel venstrerotasjon
  {
    Node<T> q = p.høyre;

    p.høyre = q.venstre;
    q.venstre = p;
    return q;
  }

  private static <T> Node<T> DHR(Node<T> p)  // Dobbel høyrerotasjon
  {
    Node<T> q = p.venstre;
    Node<T> r = q.høyre;

    q.høyre = r.venstre;
    r.venstre = q;
    p.venstre = r.høyre;
    r.høyre = p;
    return r;
  }

  private static <T> Node<T> DVR(Node<T> p)  // Dobbel venstrerotasjon
  {
    Node<T> q = p.høyre;
    Node<T> r = q.venstre;

    q.venstre = r.høyre;
    r.høyre = q;
    p.høyre = r.venstre;
    r.venstre = p;
    return r;
  }

} // class RSTre