/**
 * Imperative Programmierung von AVL-Bäumen mit Visitor-Pattern
 * Informatik II, Universität München, Sommersemester 2004
 * zu Aufgabe P-25
 * @author Ralph Matthes
 */
public abstract class AVLBaum {

    public String toString() {
	
	return (String)accept(new ToStringVisitor());
    }

    /**
     * prüft, ob alle Balancefaktoren korrekt angegeben sind
     */
    public boolean balanceKorrekt() {
	
	BalanceKorrektVisitor v= new BalanceKorrektVisitor();
	accept(v);
	return v.ok;
    }

    /**
     * prüft, ob es sich um einen binären Suchbaum handelt
     */
    public boolean istSuchbaum() {

	return ((Boolean)accept(new IstSuchbaumVisitor())).booleanValue();
    }

    /**
     * prüft, ob es sich um einen balancierten Baum handelt
     */
    public boolean istBalanciert() {
	
	return balanceKorrekt() &&
	    ((Boolean)accept(new IstBalanciertVisitor())).booleanValue();
    }

    public abstract Object accept(AVLBaumVisitor v);

    public abstract Object accept(AVLBaumVisitorI v);

    int letztesDelta = 0;
    // letzter berechneter delta-Wert für die Höhe

    private void rotate_left() {
	// Analyse
	Build wurzel = (Build)this;
	if (!(wurzel.bf == 2))
	    throw new IllegalArgumentException("BF an Wurzel muss 2 sein.");
	Comparable a = wurzel.data;
	AVLBaum u = wurzel.left;
	Build rechts = (Build)(wurzel.right);
	int bfRechts = rechts.bf;
	Comparable b = rechts.data;
	AVLBaum v = rechts.left;
	AVLBaum w = rechts.right;
	// Umbildung
	wurzel.data = b;
	rechts.data = a;
	rechts.left = u;
	rechts.right = v;
	wurzel.left = rechts;  // nach links umgehängt
	wurzel.right = w;
	if (bfRechts == 1) {
	    wurzel.bf = 0;
	    rechts.bf = 0;
	    letztesDelta = -1;
	} else if (bfRechts == 0) {
	    wurzel.bf = -1;
	    rechts.bf = 1;
	    letztesDelta = 0;
	} else
	    throw new IllegalArgumentException("BF rechts ist unpassend.");
    }

    private void rotate_right() {
	// Analyse
	Build wurzel = (Build)this;
	if (!(wurzel.bf == -2))
	    throw new IllegalArgumentException("BF an Wurzel muss -2 sein.");
	Comparable a = wurzel.data;
	Build links = (Build)(wurzel.left);
	int bfLinks = links.bf;
	Comparable b = links.data;
	AVLBaum u = links.left;
	AVLBaum v = links.right;	
	AVLBaum w = wurzel.right;
	// Umbildung
	wurzel.data = b;
	links.data = a;	
	links.left = v;
	links.right = w;	
	wurzel.left = u;
	wurzel.right = links; // nach rechts umgehängt
	if (bfLinks == -1) {
	    wurzel.bf = 0;
	    links.bf = 0;
	    letztesDelta = -1;
	} else if (bfLinks == 0) {
	    wurzel.bf = 1;
	    links.bf = -1;
	    letztesDelta = 0;
	} else
	    throw new IllegalArgumentException("BF links ist unpassend.");
    }

    private void rotate_double_left() {
	// Analyse
	Build wurzel = (Build)this;
	if (!(wurzel.bf == 2))
	    throw new IllegalArgumentException("BF an Wurzel muss 2 sein.");
	Comparable a = wurzel.data;
	AVLBaum t1 = wurzel.left;
	Build rechts = (Build)(wurzel.right);
	int bfRechts = rechts.bf;
	if (!(bfRechts == -1))
	    throw new IllegalArgumentException("BF rechts muss -1 sein.");
	Comparable s = rechts.data;
	Build rechtsLinks = (Build)(rechts.left);
	int bfRechtsLinks = rechtsLinks.bf;
	Comparable b = rechtsLinks.data;
	AVLBaum t2 = rechtsLinks.left;
	AVLBaum t3 = rechtsLinks.right;
	// AVLBaum t4 = rechts.right;
	// Umbildung
	wurzel.data = b;
	rechtsLinks.data = a;
	rechtsLinks.left = t1;
	rechtsLinks.right = t2;
	wurzel.left = rechtsLinks; // nach links umhängen
	rechts.left = t3;	
	if (bfRechtsLinks == 1) {
	    wurzel.bf = 0;
	    rechtsLinks.bf = -1;
	    rechts.bf = 0;
	} else if (bfRechtsLinks == 0) {
	    wurzel.bf = 0;
	    rechtsLinks.bf = 0;
	    rechts.bf = 0;
	} else if (bfRechtsLinks == -1) {
	    wurzel.bf = 0;
	    rechtsLinks.bf = 0;
	    rechts.bf = 1;
	} else
	    throw new IllegalArgumentException("BF rechts links ist falsch.");
	letztesDelta = -1;
    }

    private void rotate_double_right() {
	// Analyse
	Build wurzel = (Build)this;
	if (!(wurzel.bf == -2))
	    throw new IllegalArgumentException("BF an Wurzel muss -2 sein.");
	Comparable a = wurzel.data;
	Build links = (Build)(wurzel.left);
	int bfLinks = links.bf;
	if (!(bfLinks == 1))
	    throw new IllegalArgumentException("BF links muss 1 sein.");
	Comparable s = links.data;
	// AVLBaum t1 = links.left;
	Build linksRechts = (Build)(links.right);
	int bfLinksRechts = linksRechts.bf;
	Comparable b = linksRechts.data;
	AVLBaum t2 = linksRechts.left;
	AVLBaum t3 = linksRechts.right;
	AVLBaum t4 = wurzel.right;
	// Umbildung
	wurzel.data = b;
	linksRechts.data = a;
	linksRechts.left = t3;
	linksRechts.right = t4;
	wurzel.right = linksRechts; // nach rechts umhängen
	links.right = t2;	
	if (bfLinksRechts == -1) {
	    wurzel.bf = 0;
	    linksRechts.bf = 1;
	    links.bf = 0;
	} else if (bfLinksRechts == 0) {
	    wurzel.bf = 0;
	    linksRechts.bf = 0;
	    links.bf = 0;
	} else if (bfLinksRechts == 1) {
	    wurzel.bf = 0;
	    linksRechts.bf = 0;
	    links.bf = -1;
	} else
	    throw new IllegalArgumentException("BF links rechts ist falsch.");
	letztesDelta = -1;
    }

    void rotate() {

	Build wurzel = (Build)this; 
	int bf = wurzel.bf;
	if (bf == -1 || bf == 0 || bf == 1) {
	} else if (bf == 2) {
	    int bfRechts = ((Build)(wurzel.right)).bf;
	    if (bfRechts == 1 || bfRechts == 0)
		rotate_left();
	    else if (bfRechts == -1) 
		rotate_double_left();
	    else
		throw new IllegalArgumentException("BF rechts ist falsch.");
	} else if (bf == -2) {
	    int bfLinks = ((Build)(wurzel.left)).bf;
	    if (bfLinks == -1 || bfLinks == 0)
		rotate_right();
	    else if (bfLinks == 1) 
		rotate_double_right();
	    else
		throw new IllegalArgumentException("BF links ist falsch.");
	} else 
	    throw new IllegalArgumentException("|BF| an Wurzel >2.");
    }

    /**
     * siehe Vorlesung
     */
    public AVLBaum insert_avl(Comparable x) {

	// hier fehlt eine sinnvolle Implementierung
	return null;
    }

    Comparable entfernterEintrag = null;

    /**
     * siehe Vorlesung
     */
    public AVLBaum remove_max_avl() {

	RemoveMaxVisitor v = new RemoveMaxVisitor();
	AVLBaum ergebnis = (AVLBaum)accept(v);
	letztesDelta = v.delta;
	ergebnis.entfernterEintrag = v.entfernt; 
	// nicht this.entfernterEintrag modifizieren!

	return ergebnis;
    }

    /**
     * siehe Vorlesung
     */
    public AVLBaum delete_avl(Comparable x) {

	DeleteVisitor v = new DeleteVisitor(x);
	AVLBaum ergebnis = (AVLBaum)accept(v);
	letztesDelta = v.delta;
	return ergebnis;
    }
}

class Empty extends AVLBaum {

    Empty() {};

    public Object accept(AVLBaumVisitor v) {

	return v.visitEmpty();
    }

    public Object accept(AVLBaumVisitorI v) {

	return v.visitEmpty(this);
    }
}

class Build extends AVLBaum {

    int bf;  // Balance-Faktor
    Comparable data;
    AVLBaum left;
    AVLBaum right;

    Build(int bf, Comparable data, AVLBaum left, AVLBaum right) {

	this.bf=bf;
	this.data = data;
	this.left = left;
	this.right=right;
    } 

    public Object accept(AVLBaumVisitor v) {

	return v.visitBuild(bf, data, left, right);
    }

    public Object accept(AVLBaumVisitorI v) {

	return v.visitBuild(this, bf, data, left, right);
    }
}

interface AVLBaumVisitor {

    Object visitEmpty();

    Object visitBuild(int bf, Comparable data,
		      AVLBaum left, AVLBaum right);
}

interface AVLBaumVisitorI {

    Object visitEmpty(Empty it);

    Object visitBuild(Build it, int bf, Comparable data,
		      AVLBaum left, AVLBaum right);
}

class ToStringVisitor implements AVLBaumVisitor {
    
    public Object visitEmpty() {

	return "Empty";
    }

    public Object visitBuild(int bf, Comparable data,
			     AVLBaum left, AVLBaum right) {

	return "Build((" + bf + "," + data + "), " + 
	    (String)left.accept(this) + ", " +
	    (String)right.accept(this) + ")";
    }
}

class BalanceKorrektVisitor implements AVLBaumVisitor {

    boolean ok;

    BalanceKorrektVisitor() {

	ok = true;
    }
    
    public Object visitEmpty() {

	return new Integer(0);
    }

    public Object visitBuild(int bf, Comparable data,
			     AVLBaum left, AVLBaum right) {

	int hoehelinks = ((Integer)left.accept(this)).intValue();
	int hoeherechts = ((Integer)right.accept(this)).intValue();
	if (!(hoeherechts - hoehelinks == bf)) ok = false;
	return new Integer(Math.max(hoehelinks, hoeherechts)+1);
    }
}

class IstSuchbaumVisitor implements AVLBaumVisitor {

    Comparable min;
    Comparable max;

    public Object visitEmpty() {

	min = null;
	max = null;
	return Boolean.TRUE;
    }

    public Object visitBuild(int bf, Comparable data,
			     AVLBaum left, AVLBaum right) {

	boolean linksOk = ((Boolean)left.accept(this)).booleanValue();
	Comparable minLinks = min;
	Comparable maxLinks = max;
	boolean rechtsOk = ((Boolean)right.accept(this)).booleanValue();
	Comparable minRechts = min;
	Comparable maxRechts = max;
	boolean ok = linksOk && rechtsOk;
	if ((!(maxLinks==null) && maxLinks.compareTo(data) > 0) ||
	    (!(minRechts==null) && minRechts.compareTo(data) < 0))
	    ok = false;
	if (minLinks == null) min = data;
	else min = minLinks; // nur korrekt für Suchbaum!
	if (maxRechts == null) max = data;
	else max = maxRechts; // nur korrekt für Suchbaum!
	return new Boolean(ok);
    }
}

class IstBalanciertVisitor implements AVLBaumVisitor {
    
    public Object visitEmpty() {

	return Boolean.TRUE;
    }

    public Object visitBuild(int bf, Comparable data,
			     AVLBaum left, AVLBaum right) {

	boolean bfok = bf == 0 || bf ==-1 || bf==1;
	return new Boolean(bfok &&
			   ((Boolean)left.accept(this)).booleanValue() &&
			   ((Boolean)right.accept(this)).booleanValue());
    }
}

class RemoveMaxVisitor implements AVLBaumVisitorI {

    Comparable entfernt = null;
    int delta = 0;

    public Object visitEmpty(Empty it) {

	throw new IllegalArgumentException("Kein Entfernen " +
					   "aus leerem AVL-Baum.");
    }

    public Object visitBuild(Build it, int bf, Comparable x,
			     AVLBaum l, AVLBaum r) {

	if (r instanceof Empty) {
	    entfernt = x;
	    delta = -1;
	    return l;
	} else {
	    AVLBaum r1 = (AVLBaum)(r.accept(this));
	    int m1 = delta;
	    it.bf = bf + m1;
	    it.right = r1;
	    it.rotate();
	    int m2 = it.letztesDelta;
	    if (m1==-1&&(bf==1||(bf==-1&&m2==-1))) delta = -1;
	    else delta = 0;
	    return it;
	}
    }
}

class DeleteVisitor implements AVLBaumVisitorI {

    Comparable x;
    int delta;

    public DeleteVisitor(Comparable x) {

	this.x = x;
	delta = 0;
    }
    
    public Object visitEmpty(Empty it) {

	delta = 0;
	// da ist nichts zu entfernen
	return it;
    }

    public Object visitBuild(Build it, int bf, Comparable y,
			     AVLBaum l, AVLBaum r) {

	if (x.compareTo(y)==0) {
	    if (l instanceof Empty) {
		delta = -1;
		return r;
	    } else if (r instanceof Empty) {  // nur eine Optimierung
		delta = -1;
		return l;
	    } else {
		AVLBaum l1 = l.remove_max_avl();
		int m1 = l.letztesDelta;
		Comparable z = l1.entfernterEintrag;
		it.bf = bf - m1;
		it.data = z;
		it.left = l1;
		it.rotate();
		int m2 = it.letztesDelta;
		if (m1==-1&&(bf==-1||(bf==1&&m2==-1))) delta = -1;
		else delta = 0;
	    }
	} else if (x.compareTo(y)<0){
	    AVLBaum l1 = (AVLBaum)(l.accept(this));
	    int m1 = delta;
	    it.bf = bf - m1;
	    it.left = l1;
	    it.rotate();
	    int m2 = it.letztesDelta;
	    if (m1==-1&&(bf==-1||(bf==1&&m2==-1))) delta = -1;
	    else delta = 0;
	} else { //  x.compareTo(y)>0
	    AVLBaum r1 = (AVLBaum)(r.accept(this));
	    int m1 = delta;
	    it.bf = bf + m1;
	    it.right = r1;
	    it.rotate();
	    int m2 = it.letztesDelta;
	    if (m1==-1&&(bf==1||(bf==-1&&m2==-1))) delta = -1;
	    else delta = 0;
	}
	return it;
    }
}