package hjelpeklasser;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class SBinTre<T> implements Beholder<T>
{
private static final class Node<T>
{
private T verdi;
private Node<T> venstre, høyre;
private Node(T verdi, Node<T> v, Node<T> h)
{
this.verdi = verdi; venstre = v; høyre = h;
}
private Node(T verdi)
{
this(verdi, null, null);
}
}
private Node<T> rot;
private int antall;
private final Comparator<? super T> comp;
private int endringer;
public SBinTre(Comparator<? super T> c)
{
rot = null;
antall = 0;
comp = c;
endringer = 0;
}
public static <T extends Comparable<? super T>> SBinTre<T> lagTre()
{
return new SBinTre<>(Komparator.<T>naturlig());
}
public static <T> SBinTre<T> lagTre(Comparator<? super T> c)
{
return new SBinTre<>(c);
}
@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)
{
if (verdi == null) throw new NullPointerException("Ulovlig nullverdi!");
Node<T> p = rot, q = null;
int cmp = 0;
while (p != null)
{
q = p;
cmp = comp.compare(verdi,p.verdi);
p = cmp < 0 ? p.venstre : p.høyre;
}
p = new Node<>(verdi);
if (q == null) rot = p;
else if (cmp < 0) q.venstre = p;
else q.høyre = p;
endringer++;
antall++;
return true;
}
public static <T> SBinTre<T> lagTre(T[] a, Comparator<? super T> c)
{
SBinTre<T> tre = lagTre(c);
for (T verdi : a) tre.leggInn(verdi);
return tre;
}
public static <T extends Comparable<? super T>> SBinTre<T> lagTre(T[] a)
{
return lagTre(a,Komparator.<T>naturlig());
}
private static int høyde(Node<?> p)
{
if (p == null) return -1;
return 1 + Math.max(høyde(p.venstre), høyde(p.høyre));
}
public int høyde()
{
return høyde(rot);
}
@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);
}
}
private static <T> Node<T>
balansert(T[] a, int v, int h, Comparator<? super T> c)
{
if (v > h) return null;
else if (v == h) return new Node<>(a[v]);
int m = (v + h)/2;
T verdi = a[m];
while (v < m && c.compare(verdi, a[m-1]) == 0) m--;
Node<T> p = balansert(a, v, m - 1, c);
Node<T> q = balansert(a, m + 1, h, c);
return new Node<>(verdi, p, q);
}
public static <T extends Comparable<? super T>>
SBinTre<T> lagBalansertTre(T[] a)
{
SBinTre<T> tre = lagTre();
tre.rot = balansert(a, 0, a.length - 1, tre.comp);
tre.antall = a.length;
return tre;
}
public static <T>
SBinTre<T> lagBalansertTre(T[] a, Comparator<? super T> c)
{
SBinTre<T> tre = lagTre(c);
tre.rot = balansert(a, 0, a.length - 1, tre.comp);
tre.antall = a.length;
return tre;
}
@Override
public boolean inneholder(T verdi)
{
if (verdi == null) return false;
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;
}
public T min()
{
if (tom()) throw new NoSuchElementException("Treet er tomt!");
Node<T> p = rot;
while (p.venstre != null) p = p.venstre;
return p.verdi;
}
public T maks()
{
if (tom()) throw new NoSuchElementException("Treet er tomt!");
Node<T> p = rot;
while (p.høyre != null) p = p.høyre;
return p.verdi;
}
public T gulv(T verdi)
{
if (tom()) throw new NoSuchElementException("Treet er tomt!");
if (verdi == null) throw new NullPointerException("Ulovlig nullverdi!");
Node<T> p = rot; T gulv = null;
while (p != null)
{
int cmp = comp.compare(verdi, p.verdi);
if (cmp < 0) p = p.venstre;
else if (cmp > 0)
{
gulv = p.verdi;
p = p.høyre;
}
else return p.verdi;
}
return gulv;
}
public T tak(T verdi)
{
if (tom())
{
throw new NoSuchElementException("Treet er tomt!");
}
Node<T> p = rot;
T tak = null;
while (p != null)
{
int cmp = comp.compare(verdi, p.verdi);
if (cmp < 0)
{
tak = p.verdi;
p = p.venstre;
}
else if (cmp > 0)
{
p = p.høyre;
}
else
{
return p.verdi;
}
}
return tak;
}
public T større(T verdi)
{
if (tom()) throw new NoSuchElementException("Treet er tomt!");
if (verdi == null) throw new NullPointerException("Ulovlig nullverdi!");
Node<T> p = rot;
T større = null;
while (p != null)
{
int cmp = comp.compare(verdi, p.verdi);
if (cmp < 0)
{
større = p.verdi;
p = p.venstre;
}
else
{
p = p.høyre;
}
}
return større;
}
public T mindre(T verdi)
{
if (tom()) throw new NoSuchElementException("Treet er tomt!");
Node<T> p = rot;
T mindre = null;
while (p != null)
{
int cmp = comp.compare(verdi, p.verdi);
if (cmp <= 0)
{
p = p.venstre;
}
else
{
mindre = p.verdi;
p = p.høyre;
}
}
return mindre;
}
@Override
public boolean fjern(T verdi)
{
if (verdi == null) return false;
Node<T> p = rot, q = null;
while (p != null)
{
int cmp = comp.compare(verdi,p.verdi);
if (cmp < 0) { q = p; p = p.venstre; }
else if (cmp > 0) { q = p; p = p.høyre; }
else break;
}
if (p == null) return false;
if (p.venstre == null || p.høyre == null)
{
Node<T> b = p.venstre != null ? p.venstre : p.høyre;
if (p == rot) rot = b;
else if (p == q.venstre) q.venstre = b;
else q.høyre = b;
}
else
{
Node<T> s = p, r = p.høyre;
while (r.venstre != null)
{
s = r;
r = r.venstre;
}
p.verdi = r.verdi;
if (s != p) s.venstre = r.høyre;
else s.høyre = r.høyre;
}
endringer++;
antall--;
return true;
}
public void fjernMin()
{
if (tom()) throw new NoSuchElementException("Treet er tomt!");
if (rot.venstre == null) rot = rot.høyre;
else
{
Node<T> p = rot.venstre, q = rot;
while (p.venstre != null)
{
q = p;
p = p.venstre;
}
q.venstre = p.høyre;
}
endringer++;
antall--;
}
private class InordenIterator implements Iterator<T>
{
private Stakk<Node<T>> s = new TabellStakk<>();
private Node<T> p = null;
private Node<T> q = null;
private int iteratorendringer;
private Node<T> først(Node<T> q)
{
while (q.venstre != null)
{
s.leggInn(q);
q = q.venstre;
}
return q;
}
public InordenIterator()
{
if (rot == null) return;
p = først(rot);
iteratorendringer = endringer;
}
@Override
public T next()
{
if (!hasNext()) throw new NoSuchElementException();
if (iteratorendringer != endringer)
throw new ConcurrentModificationException();
T verdi = p.verdi;
q = p;
if (p.høyre != null) p = først(p.høyre);
else if (!s.tom()) p = s.taUt();
else p = null;
return verdi;
}
@Override
public boolean hasNext()
{
return p != null;
}
@Override
public void remove()
{
if (q == null)
{
throw new IllegalStateException();
}
if (iteratorendringer != endringer)
{
throw new ConcurrentModificationException();
}
if (q.høyre == null)
{
if (p == null)
{
if (q == rot)
{
rot = q.venstre;
} else
{
Node<T> f = rot;
while (f.høyre != q)
{
f = f.høyre;
}
f.høyre = q.venstre;
}
}
else
{
if (q == p.venstre)
{
p.venstre = q.venstre;
} else
{
Node<T> f = p.venstre;
while (f.høyre != q)
{
f = f.høyre;
}
f.høyre = q.venstre;
}
}
}
else
{
q.verdi = p.verdi;
if (q.høyre == p)
{
q.høyre = p.høyre;
} else
{
Node<T> f = s.taUt();
f.venstre = p.høyre;
while (f != q.høyre)
{
f = s.taUt();
}
}
p = q;
}
q = null;
iteratorendringer++;
endringer++;
antall--;
}
}
@Override
public Iterator<T> iterator()
{
return new InordenIterator();
}
}