public class Timetable {

	private class DateList {
		private Date info;
		private DateList next;
		
		public DateList(Date info) {
			this.info = info;  // Parameter info verschattet Membervar. info, daher this.info nötig
		}
		
		public String toString() {
			String result = info.toString();  // String-Repräsentation des Dates
			
			// Abbruchbedingung
			if (next == null) // es gibt keinen Nachfolger -> Abbruch
				return result;
			
			result += "; ";  // irgendein Trennzeichen zwischen zwei Dates
			result += next.toString(); // der Rest (next ruft für den übernächstes auf usw. (bis zum Ende))
			return result;
		}
	}


	private DateList dates = null;  // = null ist implizit, also überflüssig
	
	public Timetable() { }  // hier passiert nichts (-> nicht nötig)
	
	public boolean addDate(Date newDate) {
		if (dates == null) { // noch kein Element
			dates = new DateList(newDate);
			return true;
		}
		
		/* MÖGLICHKEIT 1: Hinten einfügen */
		
//		// Iteriere über alle Elemente und prüfe auf zeitliche Kollision:
//		DateList current = dates;  // dient als "Zähler"
//		while (true) { 
//			if (overlap(current.info, newDate)) // die Elemente kollidieren zeitlich (Methode weiter unten)
//				return false;
//			if (current.next == null)
//				break;  // nicht weiterzählen, weil wir das letzte Element brauchen
//			current = current.next;  // weiterzählen
//		}
//		
//		// Jetzt steht in current das letzte Element der Liste
//		current.next = new DateList(newDate);
//		return true;
		
		/* MÖGLICHKEIT 2 addDate(newDate): Vorne einfügen */
		
		// Prüfe, ob eines überlappt:
		boolean overlap = false;
		// dazu über alle Elemente iterieren (wie for(int i = 0; i < length; i++))
		DateList current = dates;  // erstes Element (entspricht "int i = 0;")
		while (current != null) {  // entspricht "i < length"
			if (overlap(current.info, newDate)) {  // overlap Methode soll prüfen
				overlap = true;
				break;  // muss gar nicht weiterkucken
			}
			current = current.next;  // entspricht "i++"
		}
		
		if (overlap) // darf nicht eingefügt werden
			return false;
		
		// Keine Überlappung -> Einfügen
		DateList neu = new DateList(newDate);  // 1.
		neu.next = dates;  // 2.
		dates = neu;  // 3.
		
		return true;  // wurde eingefügt
	}
	
	public boolean deleteDate(Date date) {
		// Wir iterieren wieder über alle Elemente und prüfen jedes auf Gleichheit, wobei man dazu alle
		// Membervariablen vergleichen muss (sonst: Referenzgleichheit, d. h. nicht mittels "=="!).
		// Außerdem merken wir uns jeweils noch den Vorgänger, sodass wir bei einem Fund ganz einfach
		// löschen können, indem wir den Nachfolger des Vorgängers auf den Nachfolger des aktuellen setzen.
		
		DateList current = dates;
		DateList prev = null;  // Vorgänger
		
		while (current != null) {
			if (equals(current.info, date)) {  // stimmen überein (-> Methode siehe unten) -> entfernen
				if (prev == null)  // Sonderfall: das erste Element wird gelöscht.
					dates = current.next;
				else
					prev.next = current.next;  // Der nächste des vorherigen ist nun der nächste des aktuellen (-> aktueller fliegt raus)
				return true;  // wurde gefunden
			}
			
			// Weiterzählen:
			prev = current;
			current = current.next;
		}
		
		return false;  // nichts entfernt
	}
	
	public String toString() {
		// Mit dieser Implementierung müssen wir, nachdem unsortiert gespeichert wurde, alles neu sortieren.
		// In einem neuen Timetable werden alle Daten neu gespeichert. Dabei teilen wir diejenigen, die So 24 Uhr
		// überschreiten, in zwei.		
		
		Timetable copySplitted = new Timetable();
		
		DateList current = dates;
		while (current != null) {
			Date date = current.info;
			
			int startTime = date.getWeekday() * (60*24) + date.getStarthour() * 60 + date.getStartmin();
			int endTime = startTime + date.getDuration();
			int maxTime = 7 * 24 * 60;
			
			if (endTime > maxTime) {  // wir müssen splitten
				int duration1 = maxTime - startTime;  // bis So. 24:00
				int duration2 = date.getDuration() - duration1;  // ab Mo. 0:00
				
				Date d1 = new Date(date.getWeekday(), date.getStarthour(), date.getStartmin(), duration1, date.getTitle());
				Date d2 = new Date(0, 0, 0, duration2, date.getTitle());

				copySplitted.addDate(d1);
				copySplitted.addDate(d2);
			} else {
				copySplitted.addDate(date);
			}
			
			current = current.next; // Weiterzählen
		}
		
		
		// Anschließend suchen wir (zwar ineffizient) einfach immer das Element mit der# niedrigsten Startzeit, 
		// entfernen es aus der temporären Timetable und hängen es an den Ausgabestrin an (bis Timetable leer ist).
		
		String output = "";
		
		while (copySplitted.dates != null) {
			Date min = copySplitted.dates.info;
			int minStartTime = min.getWeekday() * (60*24) + min.getStarthour() * 60 + min.getStartmin();
			DateList next = copySplitted.dates.next;
			
			// Finde das Minimum (für Startzeit)
			while (next != null) {
				Date date = next.info;
				int startTime = date.getWeekday() * (60*24) + date.getStarthour() * 60 + date.getStartmin();
				
				if (startTime < minStartTime) { // neues Minimum gefunden
					min = date;
					minStartTime = startTime;
				}
				
				next = next.next; // weiterzählen
			}
			
			// Minimum entfernen und zum Ausgabestring anfügen:
			copySplitted.deleteDate(min);
			output += min + "\n";
		}
		
		return output;
	}
	
	
	// Prüft, ob zwei Dates äquivalent sind
	static boolean equals(Date a, Date b) {
		return a.getWeekday() == b.getWeekday() && a.getStarthour() == b.getStarthour() &&
			   a.getStartmin() == b.getStartmin() && a.getDuration() == b.getDuration() &&
			   a.getTitle().equals(b.getTitle());  // Strings (bzw. Objekte allgemein) werden immer mit equals verglichen!
	}
	
	// Prüft, ob zwei Termine zeitlich kollidieren (diese Methode kann man kürzen; hier aber der Ausführlichkeit halber mal lang)
	static boolean overlap(Date a, Date b) {
		// Wir berechnen eine eindeutige Startzeit (und Endzeit) in Minuten
		// Startzeit von Mittwoch 13:30 Uhr wäre (Mo.+Di.) + 13Std. + 30 Min. = 2 * 24 * 60 + 13 * 60 + 30
		int startTimeA = a.getWeekday() * (60*24) + a.getStarthour() * 60 + a.getStartmin();
		int startTimeB = b.getWeekday() * (60*24) + b.getStarthour() * 60 + b.getStartmin();
		int endTimeA = startTimeA + a.getDuration();
		int endTimeB = startTimeB + b.getDuration();
		
		int maxTime = 7 * 24 * 60;  // das wäre die Zeit nach Sonntag 23:59, also wieder Montag 0:00
		
		
		if (endTimeB > maxTime) {  // b ist ein Termin der vor Sonntag 24 Uhr beginnt, aber danach endet
			// -> Wir teilen b einfach in zwei Termine und prüfen diese separat auf Kollision
			int duration1 = maxTime - startTimeB;  // bis So. 24:00
			int duration2 = b.getDuration() - duration1;  // ab Mo. 0:00
			
			Date b1 = new Date(b.getWeekday(), b.getStarthour(), b.getStartmin(), duration1, "b1");
			Date b2 = new Date(0, 0, 0, duration2, "b2");
			
			return overlap(a, b1) || overlap(a, b2);  // überlappt einer der beiden Teile nun?
		}
		
		if (endTimeA > maxTime) {  // a geht über So. 24:00 hinaus -> Wir teilen a in zwei Termine und prüfen diese erneut
			int duration1 = maxTime - startTimeA;  // bis So. 24:00
			int duration2 = a.getDuration() - duration1;  // ab Mo. 0:00
			
			Date a1 = new Date(a.getWeekday(), a.getStarthour(), a.getStartmin(), duration1, "a1");
			Date a2 = new Date(0, 0, 0, duration2, "a2");
			
			return overlap(b, a1) || overlap(b, a2);
		}
		
		// else: wir haben zwei "normale" Termine (Im Bereich von Mo bis So)
		// -> Entweder liegt a vor b oder b vor a. Ist das nicht der Fall, so überlappen die beiden
		return !(endTimeA <= startTimeB || endTimeB <= startTimeA);  // ! steht für not, d. h. !true == false, !false == true
	}

	/* TEST */
	public static void main(String[] arguments) {
		// Vorsicht unschön, nur zum Testen:
		Date d2 = new Date(0, 5, 0, 240, "PGdP Abgabe 5-9");
		Date d1 = new Date(0, 0, 0, 60, "Mitternachtsstunde");
		Date d3 = new Date(6, 23, 0, 120, "Sunny Moon");
		Date d4 = new Date(2, 12, 00, 120, "test");
		Date d5 = new Date(2, 13, 00, 5, "xxx");
		Date d6 = new Date(2, 11, 00, 60, "");
		Date d7 = new Date(4, 12, 00, 900, "");

		/*
		System.out.println(overlap(d1, d2));
		System.out.println(overlap(d1, d3));
		System.out.println(overlap(d3, d2));
		System.out.println(overlap(d4, d4));
		System.out.println(overlap(d6, d4));
		System.out.println(overlap(d5, d4));
		System.out.println(overlap(d6, d5));
		*/
		
		Timetable t = new Timetable();
		
		System.out.println("Add:");
		System.out.println(t.addDate(d3));
		System.out.println(t.addDate(d1));
		System.out.println(t.addDate(d2));
		System.out.println(t.addDate(d4));
		System.out.println(t.addDate(d5));
		System.out.println(t.addDate(d6));
		System.out.println(t.addDate(d7));
		
		System.out.println(t);
		
		System.out.println("Delete:");
		System.out.println(t.deleteDate(d2));
		System.out.println(t.deleteDate(new Date(2, 12, 00, 120, "")));
		System.out.println(t.deleteDate(new Date(2, 12, 0, 120, "test")));
	}
}