/**
  *
  * Programmieraufgabe P-19 (Median.java)
  *
  * @author Leonhard Fellermayr
  * @version 1.0
  *
  */

/** Benoetigtes Package: der Comparator zum Vergleichen von Daten */

import java.util.Comparator;

/** Implementierung der Klasse Median. */

public class Median
{

   /******************************************************************************************
      * median (Object[], Comparator) : Gibt den Median des Arrays (a) unter Verwendung
      * des Comparator zurueck.
      *
      * @param a Array, dessen Median bestimmt werden soll
      * @param c Comparator-Objekt, das beim Vergleich zum Einsatz kommt
      * @return Median des Arrays
      *
      **/

    public static Object median (Object[] a, Comparator c)
    {
	/** Der Median wird bestimmt, indem nach dem n.-kleinsten Element in ganz (a)
	  * gesucht wird, wobei n := a.length / 2. */

	int ntkleinstes;

	/** Sonderbehandlung fuer Arraylaenge 1 - denn bei Ganzzahldivision wird stets
	  * abgerundet */

	ntkleinstes = a.length / 2;

	if (a.length == 1)
		ntkleinstes++;	/* war: 0, jetzt: 1 */

	return finde (a, ntkleinstes, 0, a.length - 1, c);

    } // median ()

   /******************************************************************************************
      * finde (Object[], int, int, int, Comparator) : Findet Array-Index des (n).-kleinsten
      * Objekts in (o) (im Bereich [start..end]), und gibt diesen Index zurueck.
      *
      * @param o Array, auf dem gesucht wird
      * @param n Suche nach dem n.-kleinsten Objekt
      * @param start Suche ab Array-Position start
      * @param end Suche bis Array-Position end
      * @param c Comparator-Objekt, das beim Vergleich zum Einsatz kommt
      * @return Array-Index des n.-kleinsten Objekts in (o)
      *
      **/

    public static Object finde (Object[] o, int n, int start, int end, Comparator c)
    {

	/* Fehlerbehandlung fuer unsinnige Methodenparameter */

	if (o.length == 0)
		throw new RuntimeException ("Leeres Array - kein kleinstes Element!");

	if ((start < 0) || (start >= o.length) || (end < 0) || (end >= o.length))
		throw new RuntimeException ("Start- und Endwert muessen in [0.." + (o.length-1) + "] liegen.");

	if (start > end)
		throw new RuntimeException ("Startwert groesser als Endwert!");

	if ((n < 1) || (n > o.length))
		throw new RuntimeException ("n muss in [1.." + o.length + "] liegen.");

	/** Instantiiere ein Sortieren-Objekt, da wir uns der Methode partition() bedienen. */

	Sortieren sorter = new Sortieren ();

	/** Wenn durch rekursive Aufrufe das Operationsintervall nur noch die Laenge 1
	  * hat, haben wir das gesuchte Objekt gefunden. */

	if (start == end)
		return o[start];

	/** Finde mit Hilfe von partition() einen Teilungspunkt, so dass alle Arraywerte
	  * links davon kleiner oder gleich denen rechts davon sind. */

	int result = sorter.partition (o, start, end, c);

	/** "+ 1" jeweils deshalb, weil das kleinste Element das 1.-kleinste ist,
	  * die Array-Indizes aber bei 0 beginnen. */

	if (n <= result - start + 1)

		/** n.-kleinstes E. muss LINKS liegen, genauer in [start..result]    */

		return finde (o, n, start, result, c);

	else

		/** n.-kleinstes E. muss RECHTS liegen, genauer in [(result+1)..end]
		  * und ist in diesem Intervall das n-(result-start+1).-kleinste E.  */

		return finde (o, n - (result - start + 1), result + 1, end, c);

    } // finde ()

} // Klasse Median