public class GrausGauß extends MiniJava {
	private static int lines;
	
	// eigentliche main-Methode:
	public static void main(String[] args) {
		lines = read("Geben Sie die Anzahl der Gleichungen ein.");
		if (lines < 1) {
			write("Das ist nicht möglich.");
			return;
		}
		
		int[] matrix = readMatrix();
		writeLineConsole("Eingabe:");
		printMatrix(matrix);
		
		int[] solution = solveSystem(matrix);
		writeLineConsole("Zeilenstufenform:");
		printMatrix(matrix);
		writeLineConsole("Lösung:");
		printMatrix(solution);
	}
	
	public static int[] readMatrix() {
		int[] matrix = new int[lines*(lines+1)];  // Zeilenanzahl * Spaltenanzahl
		
		for (int line = 0; line < lines; line++) {  // jede Zeile
			for (int column = 0; column < lines; column++) {  // jede Spalte (außer Ergebnisspalte)
				set(matrix, line, column, read("Geben Sie den Koeffizienten für x" + (column+1)
											  + " aus Zeile " + (line+1) + " ein:"));
			}
			set(matrix, line, lines, read("Geben Sie das Ergebnis der " + (line+1) + ". Zeile ein."));
		}
		
		return matrix;
	}
	
	public static void printMatrix(int[] matrix) {
		int i = 0;
		while (i < matrix.length) {
			writeConsole(matrix[i++] + " ");
			if (i % (lines+1) == 0)
				writeLineConsole();
		}
	}
	
	public static int get(int[] matrix, int line, int column) {
		return matrix[line * (lines+1) + column];
	}
	
	public static void set(int[] matrix, int line, int column, int value) {
		matrix[line * (lines+1) + column] = value;
	}
	
	public static void multLine(int[] matrix, int line, int factor) {
		for (int column = 0; column <= lines; column++)  // lines+1 Spalten 
			matrix[line*(lines+1) + column] *= factor;
	}
	
	public static void multAddLine(int[] matrix, int line, int otherLine, int factor) {
		for (int column = 0; column <= lines; column++)  // lines+1 Spalten 
			matrix[line*(lines+1) + column] += matrix[otherLine*(lines+1) + column] * factor;
	}
	
	public static void swap(int[] matrix, int lineA, int lineB) {
		for (int column = 0; column <= lines; column++) {
			int tmpB = get(matrix, lineB, column);
			set(matrix, lineB, column, get(matrix, lineA, column));
			set(matrix, lineA, column, tmpB);		
		}
	}
	
	public static void searchSwap(int[] matrix, int fromLine) {
		if (get(matrix, fromLine, fromLine) == 0) {  // falls getauscht werden muss
			// Finde eine Zeile, mit der ich tauschen kann (!= 0) und tausche:
			int swapLine = fromLine;
			while (get(matrix, swapLine, fromLine) == 0)
				swapLine++;
			swap(matrix, fromLine, swapLine);
		}
	}
	
	public static int kgv(int a, int b) {
		if (a == 0 || b == 0)  // Sonderfall: Eine von beiden Zahlen ist 0 -> kgV ist 0.
			return 0;
		
		// Negative Werte zunächst positiv machen (kgV bleibt gleich):
		if (a < 0)
			a *= -1;
		if (b < 0)  // !
			b *= -1;
		
		final int aCopy = a, bCopy = b; // a und b zwischenspeichern (final ist nicht nötig)
		
		// Gehe immer mit dem Kleineren zum nächstgrößeren Vielfachen, bis
		// das gefundene Vielfache von a und das von b identisch sind.
		while (a != b)
			if (a < b)
				a += aCopy;
			else
				b += bCopy;
		
		return a;  // a == b -> eins von beiden zurückgeben

		// Alternative Lösung: kgv(a, b) = b / ggT(a, b) * a
	}
	
	public static int[] rowEchelonToResult(int[] matrix) {
		int[] solution = new int[lines];
		
		for (int line = lines-1; line >= 0; line--) {  // jede Zeile
			solution[line] = get(matrix, line, lines);  // Ergebnis (... = y) annehmen
			
			// Alle Spalten rechts von der Diagonalenspalte abziehen (zuvor berechnet):
			for (int column = lines-1; column > line; column--)
				solution[line] -= get(matrix, line, column) * solution[column];
			
			solution[line] /= get(matrix, line, line);  // durch Diagonalenwert (!=0) teilen
		}
		
		return solution;
	}
	
	public static int[] solveSystem(int[] matrix) {
		// für jeden Eintrag auf der Diagonalen (von links oben nach rechts unten)
		for (int j = 0; j < lines; j++) {			
			// 1. Mit irgendeiner darunterliegenden Zeile tauschen, 
			//    falls der Diagonaleneintrag gleich 0 ist
			searchSwap(matrix, j);
			
			// 2.:
			int d = get(matrix, j, j);  // Diagonaleneintrag d neu holen (ist jetzt != 0)
			// Alle darunterliegenden Zeilen dieser Spalte auf 0 bringen: 
			for (int i = j+1; i < lines; i++) {  // darunterliegende Zeilenindizes
				int e = get(matrix, i, j);  // Eintrag derselben Spalte (e_i)
				int kgv = kgv(e, d);  // KGV vom e mit d (kgv_i)
				
				if (kgv != 0) { // nur wenn überhaupt etwas getan werden muss (e!=0)
					multLine(matrix, i, kgv/e);  // Zeile mit kgv/e multiplizieren
					multAddLine(matrix, i, j, -kgv/d);  // subtrahiere d-Zeile*(kgv/d)
				}
			}
		}
		
		return rowEchelonToResult(matrix);  // Ergebnis aus Zeilestufenform berechnen
	}

}