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>
{
private T verdi;
private Node<T> venstre;
private Node<T> høyre;
private boolean farge;
private Node(T verdi, Node<T> v, Node<T> h, boolean farge)
{
this.verdi = verdi;
venstre = v; høyre = h;
this.farge = farge;
}
}
private final Node<T> NULL;
private Node<T> rot;
private int antall;
private Comparator<? super T> comp;
public RSBinTre(Comparator<? super T> comp)
{
rot = NULL = new Node<>(null,null,null,SVART);
this.comp = comp;
}
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)
{
rot = new Node<>(verdi,NULL,NULL,SVART);
antall++;
return true;
}
Stakk<Node<T>> stakk = new TabellStakk<>();
Node<T> p = rot;
int cmp = 0;
while (p != NULL)
{
stakk.leggInn(p);
cmp = comp.compare(verdi,p.verdi);
if (cmp < 0) p = p.venstre;
else if (cmp > 0) p = p.høyre;
else return false;
}
Node<T> x = new Node<>(verdi,NULL,NULL,RØD);
antall++;
Node<T> f = stakk.taUt();
if (cmp < 0) f.venstre = x;
else f.høyre = x;
if (f.farge == SVART) return true;
Node<T> b = stakk.taUt();
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)
{
if (f == b.venstre)
{
p = EHR(b); f.farge = SVART;
}
else
{
p = DVR(b); x.farge = SVART;
}
}
else
{
if (f == b.venstre)
{
p = DHR(b); x.farge = SVART;
}
else
{
p = EVR(b); f.farge = SVART;
}
}
if (b == rot) rot = p;
else
{
Node<T> q = stakk.taUt();
if (b == q.venstre) q.venstre = p;
else q.høyre = p;
}
return true;
}
else
{
f.farge = s.farge = SVART;
if (b == rot) return true;
b.farge = RØD;
Node<T> o = stakk.taUt();
if (o.farge == SVART) return true;
x = b;
f = o;
b = stakk.taUt();
}
}
}
@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;
}
@Override
public boolean fjern(T verdi)
throws UnsupportedOperationException
{
throw new UnsupportedOperationException();
}
@Override
public String toString()
{
StringBuilder s = new StringBuilder();
s.append('[');
if (!tom()) toString(rot,s);
s.append(']');
return s.toString();
}
private void toString(Node<T> p, StringBuilder s)
{
if (p.venstre != NULL)
{
toString(p.venstre, s);
s.append(',').append(' ');
}
s.append(p.verdi);
if (p.høyre != NULL)
{
s.append(',').append(' ');
toString(p.høyre, s);
}
}
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;
else p = først(s,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()
{
throw new UnsupportedOperationException();
}
@Override
public T next()
{
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;
}
}
private static <T> Node<T> EHR(Node<T> p)
{
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)
{
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)
{
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)
{
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;
}
}