package ads1ss11.pa1;



/**
 * Sorter Klasse in der die Methode {@link #mergesort(DoublyLinkedList, int)}
 * implementiert werden soll.
 * 
 * <p>
 * In dieser Klasse m&uuml;ssen Sie Ihren Code einf&uuml;gen und die Method
 * {@link #mergesort(DoublyLinkedList, int)} implementieren.
 * </p>
 * 
 * <p>
 * Sie k&ouml;nnen beliebige neue Variablen und Methoden in dieser Klasse
 * hinzuf&uuml;gen. 
 * </p>
 */

public class Sorter {
	


	
	DoublyLinkedList slist;

	/**
	 * MergeSort Implementierung
	 * 
	 * @param in Unsortierte Eingabefolge
	 * @param numOfElements Gr&ouml;&szlig;e der Eingabefolge 
	 * @return Sortiterte Eingabefolge
	 */
	public DoublyLinkedList mergesort(DoublyLinkedList in, int numOfElements) 
	{
		this.slist = in;
		mergesort (slist.first, slist.first.prev);
		
		//TestweisecAusgabe
		System.out.println("-------------------------------");
		ListElement bla = slist.first;
		do
		{		
			System.out.println(bla.getId() + "|" + bla.getKey());
			bla = bla.next;
		} while (bla.getId() != slist.first.getId());
		
		return slist;
	}

	
	/**
	 * mergesort Implementierung
	 * 
	 * @param in zwei pointer als grenzen der Unsortierte Eingabefolge
	 * @return den Pointer der auf das linksliegende element der Sortiterte Eingabefolge zeigt
	 */
	private ListElement mergesort(ListElement beginn , ListElement ende)
	{
		//abfrage obe mehr als ein element enthalten ist
		if (beginn.getId() != ende.getId())
		{
			int a = 0;
			ListElement temp = beginn;
			ListElement tempa,tempb,reta,retb;
			
			//bestimmung der mitte(aufgerundet)
			while (temp.getId() != ende.getId() )
			{
				temp = temp.next;
				a++;
			}
			a = (int) Math.ceil(a/2);  
			temp = beginn;
			for (int i=0;i < a; i++)
			{
				temp = temp.next;
			}

			
			//rekursiver aufruf
			reta = mergesort(beginn, temp);
			retb = mergesort(temp.next, ende);
	
			
			tempb = reta;
			//s um bei dem 1. durchgang das minimum für den return zu bestimmen
			int s = 0;
			
			//vertauschung falls beide isten mehr als eine element enthalten
			while ((tempb.getId() != temp.getId()) && (retb.getId() != ende.getId()))
			{
			
				
				if (tempb.getKey() <= retb.getKey())
				{
					if (s == 0)
					{
					
						beginn = tempb;
						s++;
					}
					tempb = tempb.next;
				} else {

					if (s == 0)
					{
	
						beginn = retb;
						s++;
					}
					
					tempa = retb.next;
					swaptwo(tempb,retb);
					retb = tempa;

				}
			}
			//vertauschung falls liste A (noch) ein element und B mehr enthält
			while ((tempb.getId() == temp.getId()) && (retb.getId() != ende.getId()))
			{

				
				if (tempb.getKey() <= retb.getKey())
				{
					if (s == 0)
					{
					
						beginn = tempb;
						s++;
					}
					tempb = tempb.next;
				} else {
	
					if (s == 0)
					{
			
						beginn = retb;
						s++;
					}
					
					tempa = retb.next;
					swaptwo(tempb,retb);
					retb = tempa;

				}
			}
			//vertauschung falls liste B (noch) ein element und A mehr enthält
			while ((tempb.getId() != temp.getId()) && (retb.getId() == ende.getId()))
			{

				
				if (tempb.getKey() <= retb.getKey())
				{
					if (s == 0)
					{
			
						beginn = tempb;
						s++;
					}
					tempb = tempb.next;
				} else {

					if (s == 0)
					{
					
						beginn = retb;
						s++;
					}
					
					tempa = retb.next;
					swaptwo(tempb,retb);
					retb = tempa;

				}
			}
			
			//vertauschung fall beide listen nur ein element enthalten
			while ((tempb.getId() == temp.getId()) && (retb.getId() == ende.getId()))
			{

				
				if (tempb.getKey() <= retb.getKey())
				{
					if (s == 0)
					{
					
						beginn = tempb;
						s++;
					}
					tempb = tempb.next;
				} else {

					if (s == 0)
					{
				
						beginn = retb;
						s++;
					}
					tempa = retb.next;
					swaptwo(tempb,retb);
					retb = tempa;

				}
			}
			
		}
		//return des linkesten elements des merges	
		return beginn;

	
	}
	
	/**
	 * swaptwo Implementierung
	 * 
	 * @param in zwei zu tauschende List-Elemente
	 */
	private void swaptwo (ListElement eins, ListElement zwei)
	{
		
		// "first" neu setzen wenn das 1.element der Liste vertauscht wird
		if (slist.first.getId() == eins.getId())
		{
			slist.first = zwei;
		}
		
		//2 elemente tauschen
		zwei.prev.next = zwei.next;
		zwei.next.prev = zwei.prev;
		zwei.prev = eins.prev;
		zwei.prev.next = zwei;
		zwei.next = eins;
		eins.prev = zwei;
		
		
		
	}

}

package ads1ss11.pa1;


/**
 * Klasse zur Repräsentation einer doppelt verketteten Liste.
 *
 * <p>
 * <b>WICHTIG:</b> Nehmen Sie keine &Auml;nderungen in dieser Klasse vor. Bei
 * der Abgabe werden diese &Auml;nderungen verworfen und es k&ouml;nnte dadurch
 * passieren, dass Ihr Programm somit nicht mehr korrekt funktioniert.
 * </p>
 */
public class DoublyLinkedList {
	
	private static int counter=0;
	
	/** Zeiger auf das erste Element in der Liste */
	public ListElement first;

	/**
	 * Erzeugt eine doppelt verkettete Liste mit <code>start</code> als 
	 * Startelement.
	 * 
	 * @param start	das erste Element der Liste.
	 */
	protected DoublyLinkedList(ListElement start) {
		first = start;
		first.next = first;
		first.prev = first;
		if(counter == Integer.MAX_VALUE) {
			System.out.println("Zu viele DoublyLinkedLists angelegt!");
			System.exit(1);
		}
		counter++;
	}

	/**
	 * @return counter
	 */
	public static int getCounter() {
		return counter;
	}
	
	
	
}

package ads1ss11.pa1;

/**
 * Klasse zur Kapselung eines Listenelements.
 * 
 * <p>
 * <b>WICHTIG:</b> Nehmen Sie keine &Auml;nderungen in dieser Klasse vor. Bei
 * der Abgabe werden diese &Auml;nderungen verworfen und es k&ouml;nnte dadurch
 * passieren, dass Ihr Programm somit nicht mehr korrekt funktioniert.
 * </p>
 */
public class ListElement {
	
	private static int counter = 0;
	
	private int id;
	
	@Override
	public String toString() {
		return ""+key+"";
	}

	/** Schl&uuml;ssel dieses Listenelements */
	private int key;
	
	/** Zeiger auf das vorhergehende Listenelement */
	public ListElement prev;
	
	/** Zeiger auf das nachfolgende Listenelement */
	public ListElement next;
	
	/**
	 * Erzeugt ein neues Listenelement mit dem Schl&uuml;ssel <code>_key</code>.
	 * 
	 * @param _key	der Schl&uuml;ssel f&uuml;r das neue Listenelement.
	 */
	protected ListElement(int _key) {
		key = _key;
		prev = null;
		next = null;
		if(counter == Integer.MAX_VALUE) {
			System.out.println("Zu viele ListElements angelegt!");
			System.exit(1);
		}
		counter++;
		id = counter;
	}

	/**
	 * Liefert den Schl&uuml;ssel dieses Listenelements zur&uuml;ck.
	 * 
	 * @return	den Schl&uuml;ssel dieses Listenelements.
	 */
	public int getKey() {
		return key;
	}
	
	/**
	 * @return id
	 */
	public int getId() {
		return id;
	}

	/**
	 * @return counter
	 */
	public static int getCounter() {
		return counter;
	}
	
	
}

private void swaptwo (ListElement eins, ListElement zwei)
	{
		
		// "first" neu setzen wenn das 1.element der Liste vertauscht wird
		if (slist.first.getId() == eins.getId())
		{
			slist.first = zwei;
		}
		
		//2 elemente tauschen
		zwei.prev.next = zwei.next;
		zwei.next.prev = zwei.prev;
		zwei.prev = eins.prev;
		zwei.prev.next = zwei;
		zwei.next = eins;
		eins.prev = zwei;
		
		
		
	}