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