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;
private Node<T> venstre;
private Node<T> høyre;
private boolean harHøyreBarn;
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;
private int antall;
private final Comparator<? super T> comp;
private int endringer;
public STBinTre(Comparator<? super T> c)
{
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;
int cmp = 0;
while (p != null)
{
q = p;
cmp = comp.compare(verdi,p.verdi);
if (cmp < 0) p = p.venstre;
else if (p.harHøyreBarn) p = p.høyre;
else break;
}
p = new Node<>(verdi,null,null);
if (q == null)
{
rot = p;
}
else if (cmp < 0)
{
q.venstre = p;
p.høyre = q;
}
else
{
p.høyre = q.høyre;
q.høyre = p;
q.harHøyreBarn = true;
}
endringer++;
antall++;
return true;
}
@Override
public boolean inneholder(T verdi)
{
return false;
}
@Override
public boolean fjern(T verdi)
{
return false;
}
@Override
public String toString()
{
if (tom()) return "[]";
StringBuilder s = new StringBuilder();
s.append('[');
Node<T> p = rot;
while (p.venstre != null) p = p.venstre;
s.append(p.verdi);
while (true)
{
if (p.harHøyreBarn)
{
p = p.høyre;
while (p.venstre != null)
{
p = p.venstre;
}
}
else if (p.høyre == null) break;
else p = p.høyre;
s.append(',').append(' ').append(p.verdi);
}
s.append(']');
return s.toString();
}
@Override
public Iterator<T> iterator()
{
throw new UnsupportedOperationException("Not supported yet.");
}
}