package lsystem;

import java.util.*;
import java.awt.*;
/**
 * Lindenmayer-System <br>
 * Belegarbeit AlgoDat WS99/SS2000, Aufgabe 8
 * <p>
 * Lindenmayer-System.
 *
 * @author Christian Semrau<br>
 * Christian.Semrau@student.uni-magdeburg.de<br>
 */
public final class LSystem {

	/** Name des LSystems.
	 * Kann nach der Konstruktion nicht mehr geaendert werden.
	 * Aendert sich u.U. selbst, wenn sich das LSystem ueber addToVector()
	 * in einen Vector eingefuegt.
	 */
	private String Name;
	/** Startausdruck (ein Grossbuchstabe) */
	private char Axiom;
	/** die Regeln von A bis Z (in Grossbuchstaben) */
	private String[] Regeln;
	/** Drehwinkel */
	private float Winkel;
	/** Rekursionstiefe */
	private int Tiefe;
	/** Anfaenglicher Winkel */
	private float StartWinkel;
/**
 * Erzeugt ein LSystem aus einem String des Formats:
 * (Name, Axiom, Formel, Winkel, Tiefe, Startwinkel)
 * @param S java.lang.String
 */
public LSystem(String S) {
	String[] A = splitLine(S);

	char axiom; float winkel, startwinkel; int tiefe;
	axiom = (A[1].length()<1) ? 'F' : A[1].charAt(0);
	// axiom wird von init() auf Korrektheit geprueft
	try{
		winkel = new Float(A[3]).floatValue();
	}catch(NumberFormatException e){ winkel = 0; }
	try{
		tiefe = new Integer(A[4]).intValue();
	}catch(NumberFormatException e){ tiefe = 1; }
	try{
		startwinkel = new Float(A[5]).floatValue();
	}catch(NumberFormatException e){ startwinkel = 0; }

	init(A[0], axiom, parseRegelString(A[2]), winkel, tiefe, startwinkel);
}
/**
 * Uebernimmt die Werte in ein neues LSystem.
 * Auch das komplette Regeln-Feld wird kopiert.
 *
 * @param n Name
 * @param a Axiom
 * @param r Regeln
 * @param w Winkel
 * @param t Tiefe
 * @param s Startwinkel
 */
public LSystem(String n, char a, String[] r, float w, int t, float s) {
	init (n, a, r, w, t, s);
}
/**
 * Uebernimmt die Werte in ein neues LSystem.
 * r gibt alle Regeln in einem String an, fehlerhafte Regeln werden ignoriert.
 *
 * @param n Name
 * @param a Axiom
 * @param r Regeln (Format: Buchstabe ':' Regel ';' ... z.B. "F:F+G; G:F-G;")
 * @param w Winkel
 * @param t Tiefe
 * @param s Startwinkel
 */
public LSystem(String n, char a, String r, float w, int t, float s) {
	init (n, a, parseRegelString(r), w, t, s);
//	System.out.println(r+"\n"+this);
}
/**
 * Kopiert die Werte eines LSystems.
 * @param L belegLsystem.LSystem
 */
public LSystem(LSystem L) {
	if (L != null)
		init (L.Name, L.Axiom, L.Regeln, L.Winkel, L.Tiefe, L.StartWinkel);
	else
		init ("", 'F', (String[])null, 0, 1, 0);
}
/**
 * Fuegt das LSystem zum Vector hinzu und passt seinen Namen so an, dass
 * keiner doppelt vorkommt.
 * @param v (LSystem-)Vector in den das LSystem alphabetisch einsortiert wird
 */
public int addToVector(Vector v) {
	if (v==null) throw new NullPointerException("LSystem: add to null-Vector!");
	Name = findUniqueName(v);
	if (v.size()==0){
		v.addElement(this);
		return 0;
	}else{
		// fuegt das LSystem alphabetisch sortiert in den Vector ein
		int index = binaereSuche(v, 0, v.size()-1, Name);
		if (index >= v.size()){
			v.addElement(this);
			return v.size();
		}else{
			v.insertElementAt(this, index);
			return index;
		}
	}
}
/**
 * Liefert den Index von key in feld bzw die Stelle, an der key stehen muesste.
 *
 * @return int der Index von key
 * @param feld der zu durchsuchende (LSystem-)Vector
 * @param un untere Suchgrenze (kleinster zu untersuchender Index)
 * @param ob obere Suchgrenze (groesster zu untersuchender Index)
 * @param key der zu suchende Name
 */
public static int binaereSuche(Vector feld, int un, int ob, String key){
  if (un<0) un=0;
  if (ob>=feld.size()) ob = feld.size();
  if (un>ob) return un;
  
  int mid, a;
  do{
	mid = (un+ob)/2;                // Mitte berechnen
	a = ((LSystem)feld.elementAt(mid)).compareName(key);    // vergleichen
	if (a>0)                        // auswerten
	  ob = mid-1;
	  // feld[mid] > key, obere Grenze ist unter alter Mitte
	else if (a<0)
	  un = mid+1;
	  // feld[mid] < key, untere Grenze ist ueber alter Mitte
	else
	  {un = ob = mid; break;}
	  // feld[mid] == key, Abbruch der Suchschleife

  }while(un<=ob);

  return un;
  // wenn gefunden, dann un==ob==mid
  // wenn nicht gefunden, dann ist feld[ob] < key < feld[un], ob+1 == un,
  // und key muss an der Stelle un eingeordnet werden
}
/**
 * Berechnet die Anzahl der auszuwertenden Zeichen.
 * @return int
 */
public static long calcChars(LSystem LS) {
	long Chars[][];
	Chars = new long[26][LS.getTiefe()+1];
	// Stufe 0 initialisieren
	for (int r=0; r < 26; r++)
		Chars[r][0] = (r<23) ? 1 : 0;
		// X,Y,Z bewirken keine Linie, index('X')==23
	// alle anderen Stufen aufbauen
	for (int t = 1; t<=LS.getTiefe(); t++)
		// alle Regeln durchgehen
		for (int r=0; r < 26; r++){
			int gT = 0;
			String F = LS.getRegel(r);
			for (int i=0; i<F.length(); i++){
				char c = F.charAt(i);
				if (Utils.isLatinLetter(c) && (t>1||gT==0)){
					Chars[r][t] += Chars[Utils.index(c)][t-1];
				}else
				if (c=='<'||c=='>'||c=='/'||c=='\\'){
					i+=2;
					Chars[r][t]+=2;
				}else
				if (c=='1') gT = 1;
				else
				if (c=='0') gT = 0;
				Chars[r][t]++;
			}
		}
	return Chars[Utils.index(LS.getAxiom())][LS.getTiefe()];
}
/**
 * Berechnet die Anzahl der zu zeichnenden Linien.
 * @return int
 */
public static long calcLines(LSystem LS) {
	long Lines[][];
	Lines = new long[26][LS.getTiefe()+1];
	// Stufe 0 initialisieren
	for (int r=0; r < 26; r++)
		Lines[r][0] = (r<23) ? 1 : 0;
		// X,Y,Z bewirken keine Linie, index('X')==23
	// alle anderen Stufen aufbauen
	for (int t = 1; t<=LS.getTiefe(); t++)
		// alle Regeln durchgehen
		for (int r=0; r < 26; r++){
			int gT = 0;
			String F = LS.getRegel(r);
			for (int i=0; i<F.length(); i++){
				char c = F.charAt(i);
				if (Utils.isLatinLetter(c) && (t>1||gT==0)){
					Lines[r][t] += Lines[Utils.index(c)][t-1];
				}else
				if (c=='<'||c=='>'||c=='/'||c=='\\'){
					i+=2;
				}else
				if (c=='1') gT = 1;
				else
				if (c=='0') gT = 0;
			}
		}
	return Lines[Utils.index(LS.getAxiom())][LS.getTiefe()];
}
/**
 * Liefert R, wenn die Regel OK ist, liefert die default-Regel, wenn R
 * fehlerhaft ist.
 * @return java.lang.String
 * @param s java.lang.String
 */
public static String checkRegel(int i, String R) {
	return regelOK(R) ? R.toUpperCase() : Utils.letterString(i);
}
/**
 * Vergleicht den Namen des LSystems mit dem uebergebenen String, ignoriert
 * Gross/Kleinschreibung.
 */
public int compareName(String X) {
	return Utils.compare(Name, X);
}
/**
 * Liefert ein Feld mit den Buchstaben "A" bis "Z".
 * @return java.lang.String[]
 */
public static String[] defRegeln() {
	String[] R = new String[26];
	for (int i=0; i<26; i++)
		R[i] = Utils.letterString(i);
	return R;
}
/**
 * Filtert Anfuehrungszeichen und doppelte Backslashes aus dem String.
 * @return java.lang.String
 * @param S java.lang.String
 */
public static String filterQuotations(String S) {
	if (S==null||S.length()<=0) return ""; // Leerstring

	if (S.charAt(0)=='\'' && S.length()==3 && S.charAt(2)=='\'')
	// einzelnes char in Hochkommas
		return S.substring(1,2);

	StringBuffer sb = new StringBuffer(S.length());
	while (S.length()>0){
		// ein Zeichen nach dem anderen vom Anfang des Strings entfernen
		if (S.startsWith("\"+\""))
			S = S.substring(3); // "+" entfernen
		else
		if (S.charAt(0)=='"')
			S = S.substring(1); // " entfernen
		else
		if (S.startsWith("\\\\")){
			sb.append("\\");    // \\ ersetzen durch \
			S = S.substring(2);
		}
		else{
			sb.append(S.charAt(0)); // alle anderen uebernehmen
			S = S.substring(1);
		}
	}
	return sb.toString();
}
/**
 * Bildet aus dem Namen des LSystems einen im Vector eindeutigen Namen.
 * @return String Im Vector eindeutiger Name
 * @param v (LSystem-)Vector in dem der Name eindeutig sein soll
 */
private String findUniqueName(Vector v) {
	if (indexOfName(Name, v)<0) return Name;
	int nr = 1;
	String name;
	while (indexOfName(name = Name+"_"+nr, v)>=0) nr++;
	return name;
}
public char getAxiom() { return Axiom; }
public String getName() { return Name; }
/**
 * Liefert die zum Buchstaben c gehoerende Regel.
 * Wenn c kein Buchstabe ist, wird "" geliefert.
 * @return String Die gewuenschte Regel
 * @param c Buchstabe der gewuenschten Regel
 */
public String getRegel(char c) {
	int i=Utils.index(c);
	return (i>=0) ? Regeln[i] : "";
}
/**
 * Liefert die Regel mit Index i.
 * Wenn i nicht in 0..25 liegt, wird "" geliefert.
 * @return String Die gewuenschte Regel
 * @param i Index der gewuenschten Regel
 */
public String getRegel(int i) {
	return (i>=0&&i<26) ? Regeln[i] : "";
}
/**
 * Liefert eine Kopie des Regeln-Feldes.
 * @return String[] Kopie des Regeln-Feldes
 */
public String[] getRegeln() {
	String[] R = defRegeln();
	for (int i=0; i < 26; i++)
		R[i] = Regeln[i].toUpperCase();
	return R;
}
/**
 * Liefert die Startregel.
 * @return String Die Regel, durch die das Axiom ersetzt wird
 */
public String getStartRegel() {
	return Regeln[Axiom-'A'];
}
public float getStartWinkel() { return StartWinkel; }
public int getTiefe() { return Tiefe; }
public float getWinkel() { return Winkel; }
/**
 * Liefert den Index von name im (LSystem-)Vector.
 * @return int
 * @param name java.lang.String
 * @param v java.util.Vector
 */
public static int indexOfName(String name, Vector v) {
	if (v==null||v.size()<=0) return -1;

	// setzt voraus, dass der Vektor sortiert ist
	int index = binaereSuche(v, 0, v.size()-1, name);
	// -1, wenn am gelieferten Index nicht der gesuchte Name steht
	return (index<v.size() &&
		((LSystem)v.elementAt(index)).compareName(name)==0) ? index : -1;
}
/**
 * Uebernimmt die Werte in ein neues LSystem.
 * Auch das komplette Regeln-Feld wird kopiert.
 */
private void init(String n, char a, String[] r, float w, int t, float s) {
	if (n==null||n.length()<=0) n = "-ohne Namen";
	Name = n;
	// fehlerhaftes Axiom -> 'F'
	setAxiom(a);
	Regeln = defRegeln();
	// r == null bedeutet: keine Regeln zu uebernehmen
	if (r!=null){
		// korrekte Regeln werden uebernommen
		for (int i=0; i < Math.min(26, r.length); i++)
			if (regelOK(r[i]))
				Regeln[i] = r[i].toUpperCase();
			else
				System.out.println("LSystem: Regel-Fehler: "+
					Utils.letter(i)+":"+r[i]+";");
	}
	Winkel = w%360;
	Tiefe = Math.max(t,1); // falls t<1
	StartWinkel = s%360;
}
/**
 * Bildet aus einem String mit mehreren Regeln ein Feld, das alle 26 Regeln
 * enthaelt, wobei nicht angegebene Buchstaben durch sich selbst ersetzt werden.
 * Wenn die Struktur fehlerhaft ist, wird defRegeln() geliefert, fehlerhafte
 * Regeln werden ignoriert und uebersprungen.
 *
 * @return java.lang.String[]
 * @param F java.lang.String
 */
public static String[] parseRegelString(String F) {
	F = Utils.filterSpaces(F);

	// initialisieren
	String[] r = defRegeln();
	// wenn die Struktur nicht stimmt, abbrechen
	if (!strukturOK(F)) {
		System.out.println("LSystem: Struktur-Fehler: "+F);
		return r;
	}

	int anzRegeln = Utils.countChar(F, ':');
	for (int i=0; i<anzRegeln; i++){
		char a = F.charAt(0);
		// hier ist bereits durch strukturOK gesichert,
		// dass die Axiome Buchstaben sind
		F = F.substring(2);
		int p = F.indexOf(';');
		String fo = F.substring(0, p);
		F = F.substring(p+1);
		if (!regelOK(fo)){
			System.out.println("LSystem: Regel-Fehler: "+a+":"+fo+";");
		}else
			// wenn die Regel fehlerfrei ist, uebernehmen
			r[Utils.index(a)] = fo;
	}
	return r;
}
/**
 * Liefert <code>true</code>, wenn s eine erlaubte LSystem-Regel ist.
 * @return boolean
 * @param s String Zu ueberpruefende Regel
 */
public static boolean regelOK(String s) {
	if (s==null) return false; // null ist nicht OK

	int eklammern = 0, rklammern = 0;
	s = Utils.filterSpaces(s);

	for (int i=0; i<s.length(); i++){
		char c = s.charAt(i);

		if (Utils.isLatinLetter(c)){
			// (lateinischer) Buchstabe ist OK
		}else
		if (c=='<'||c=='>'||c=='/'||c=='\\'){
			if (i+2>=s.length()) return false;
			// zwei Zeichen muessen noch folgen
			if (!Utils.isLatinDigit(s.charAt(i+1))
			|| !Utils.isLatinDigit(s.charAt(i+2)))
				return false;
			// es muessen beides Ziffern sein
			i += 2;
		}else
		switch(c){
			case '+': case '-':
			case '!': case '_':
			case '0': case '1':
			break;
//			case '#': return false; // RESERVIERT
			
			case '(': rklammern++; break;
			case ')': rklammern--; if (rklammern<0) return false; break;
			case '[': eklammern++; break;
			case ']': eklammern--; if (eklammern<0) return false; break;
			default: return false;
		}; // switch
	}; // for
	return (eklammern==0)&&(rklammern==0);
}
/**
 * Ersetzt im Vector das LSystem mit dem gleichen Namen oder fuegt es in
 * den Vector ein, wenn es noch nicht drin war.
 * @return int ret>=0: der Index, an dem das LSystem EINGEFUEGT wurde,
 * ret&lt;0: -ret-1 == Index, an dem das LSystem ERSETZT wurde
 * @param v (LSystem-)Vector, in den das LSystem alphabetisch einsortiert wird
 */
public int replaceInVector(Vector v) {
	if (v==null) throw new NullPointerException();
	// Name wird nicht geaendert
	if (v.size()==0){
		v.addElement(this);
		return 0;
	}else{
		// fuegt das LSystem alphabetisch sortiert in den Vector ein
		int index = binaereSuche(v, 0, v.size()-1, Name);
		if (index >= v.size()){
			v.addElement(this);
			return v.size();
		}else{
			if ( ((LSystem)v.elementAt(index)).compareName(Name)==0 ){
				v.setElementAt(this, index);
				return -(index+1);
			}else{
				v.insertElementAt(this, index);
				return index;
			}
		}
	}
}
/**
 * Setzt das Axiom auf c.
 * Ist c kein Buchstabe, wird das Axiom auf 'F' gesetzt.
 * @param c Neues Axiom
 */
public void setAxiom(char c) {
	Axiom = Utils.isLatinLetter(c) ? Utils.upCase(c) : 'F';
}
/**
 * Setzt die Regel mit Index i auf R.
 * wenn R fehlerhaft ist, wird statt R die Standardregel eingesetzt
 * (die nichts veraendert).
 * @param i Index der Regel (0 bis 25)
 * @param R Neue Regel
 */
public void setRegel(int i, String R) {
	if (i>=0&&i<26)
		Regeln[i] = regelOK(R) ? R.toUpperCase() : Utils.letterString(i);
}
/**
 * Zerlegt die Zeile in 6 Strings.
 * @param akt Zu zerlegende Zeile
 * @return String[] wird mit den 6 Strings gefuellt
 */
public static String[] splitLine(String akt) {
	String[] A = new String[6];
	A[0] = ""; A[1] = "F"; A[2] = "F:F;"; A[3] = "0"; A[4] = "1"; A[5] = "0";
	if (akt==null||akt.length()<7) return A;
	if (!akt.startsWith("(")||!akt.endsWith(")")) return A;

	akt = akt.substring(1, akt.length()-1).trim(); // Klammern entfernen
	for (int i=0; i<5; i++){
		int p = akt.indexOf(',');
		if (p<0) return A;
		A[i] = akt.substring(0, p).trim();
		akt = akt.substring(p+1).trim();
	}
	A[5] = akt;
	for (int i=0; i<6; i++)
		A[i] = filterQuotations(A[i]);
	return A;
}
/**
 * Liefert <code>true</code>, wenn s eine erlaubte Regeln-Struktur hat.
 * @return boolean
 * @param s Zu ueberpruefende Formel
 */
public static boolean strukturOK(String s) {
	if (s==null||s.length()<=0) return false; // Leerstring ist nicht OK

	int axiomlen = 0; // zaehlt die Laenge eines Axioms
	boolean inFormel = false; // true, wenn wir innerhalb einer Regel sind

	s = Utils.filterSpaces(s);

	for (int i=0; i<s.length(); i++){
		char c = s.charAt(i);
		if (c==':'){
			if (inFormel) return false;
			if (axiomlen!=1) return false;
			if (!Utils.isLatinLetter(s.charAt(i-1))) return false;
			// neue Formel darf nicht mitten in einer Formel beginnen
			// Axiom muss genau ein Zeichen sein
			// Axiom muss ein Buchstabe sein
			inFormel=true;
			axiomlen = 0;
		}else
		if (c==';'){
			if (!inFormel) return false;
			inFormel=false;
		}else
			if (!inFormel) axiomlen++;
	}; // for
	return (!inFormel);
}
/**
 * Liefert einen String, der das komplette LSystem wiedergibt.
 * @return String Format: (Name, Axiom, Formel, Winkel, Tiefe, Startwinkel)
 */
public String toString() {
	StringBuffer s = new StringBuffer();
	s.append("(").append(Name).append(", ").append(Axiom).append(", \"");
	for (int i=0; i<26; i++)
	// es werden nur die Regeln ausgegeben, die etwas veraendern, und
	// zusaetzlich die Regel, die zum Axiom gehoert
	if ((Utils.index(Axiom)==i)||(!Regeln[i].equals(Utils.letterString(i)))){
		s.append(Utils.letter(i)).append(':').append(Regeln[i]).append("; ");
	}
	s.append("\", ").append(Winkel);
	s.append(", ").append(Tiefe);
	s.append(", ").append(StartWinkel).append(")");
	return s.toString();
}
}