package mauda.plugin.fibheap;

import mauda.Exercise;
import mauda.operation.*;
import mauda.plugin.JedasMainCompObj;
import mauda.plugin.Copyable;

import java.util.*;
import java.awt.Color;
import jedas.*;

/**
 * Implements and animates the data structure 'Fibonacci heap' (F-heap)
 * and the operations defined to manipulate the structure.<br>
 * F-heaps are one way of implementing priority queues. They consist
 * of nodes ('tasks') with given keys ('priorities'). At any time,
 * a new node may be added, the node with minimum key can be accessed
 * or removed from the queue, the key value of a given node may be
 * decreased, or a given node may be deleted.
 * <br>
 * Calling the constructor with an instance of <tt>jedas.Scheduler</tt>
 * and adding the <tt>FibHeap</tt> to a <tt>jedas.CompPanel</tt> will
 * animate all the operations manipulating the F-heap structure.
 * <br>
 * In addition, this class offers a simple way to analyze the
 * actual time complexity of the individual heap operations.
 * In order to analyze a heap manipulation, call <tt>getCount()</tt>
 * after executing the respective operation.
 * <br>The analysis is idealized in the following sense:<ul>
 * <li>All operations with complexity <i>O</i>(1) take 1 time unit.</li>
 * <li>All other operations take 1 time unit per sub-operation (such as
 * linking or cutting nodes).</li>
 * <li><tt>deletemin()</tt> takes <i>l</i> additional steps, where
 * <i>l</i> equals the length of the array needed to consolidate the
 * root list [i>l = O</i>(log <i>heapsize</i>)].</li></ul>
 *
 * @author Tobias Lauer
 * @version 2.02 (14/08/03)
 */
public class FibHeap implements JedasMainCompObj, Copyable {
	
	protected CompObj mainCompObj;
	
	// Bei Exercise.quickAnim:
	// ENTRYTIME=1 / pointerSpeed=1

	protected FibNode min;
	int size, potential, count;
	
	public static SubOperationQueue subOperations = new SubOperationQueue();	// MKrebs
	//private TextObj idText;
	
	protected LineObj minPointer, rootList;
	private ArrayObj array;
	//protected transient Scheduler scheduler;

	static double nodePosX = 0.1;	// 0.075
	static double nodePosY = 0.25;
	static double pointerY = nodePosY-0.08;
	private static DPair initialPointerPos1 = new DPair(nodePosX, pointerY);
	private static DPair initialPointerPos2 = new DPair(nodePosX, pointerY+0.04);
	protected static DPair initialNodePos	= new DPair(nodePosX, nodePosY);
	private static DPair messagePos0		= new DPair(0.5, 0.85);
	private static DPair messagePos1		= new DPair(0.5, 0.90);
	private static DPair messagePos2		= new DPair(0.5, 0.95);

	static long pointerSpeed = 1;	//200;
	static long ENTRYTIME	= 1;	//300;
	static long pauseLength	= 500;
	static Color conflict = Color.red;
	static Color POINTERCOLOR = Color.blue;

	/**
	 * Detail levels of accompanying text.
	 */
	public static final int NONE	= 0;
	public static final int NORMAL	= 1;
	public static final int MORE	= 2;
	public static final int DETAIL	= 4;

	protected static boolean showArray = true;
	protected static boolean keyColorMode = true;
	protected static int textMode = MORE;
	private TextObj[] message;


	/**
	 * Creates a new, empty FibHeap.
	 */
	public FibHeap() {
		mainCompObj = new CompObj();
		
		min = null;
		size = potential = 0;
		// panel = getCompPanel();
		/*
		if (this instanceof BinQueue) {
			// System.out.println("Bin");
			POINTERCOLOR = Color.white;
		}
		*/
		minPointer = new LineObj(initialPointerPos1,
								initialPointerPos2,
								POINTERCOLOR,
								LineObj.END,
								LineObj.FILLED,
								POINTERCOLOR);
			
		//rootList = new LineObj(new DPair(-1.0,nodePosY),
		//						new DPair(2.0, nodePosY),
		//						Color.black);
		rootList = new LineObj(new DPair(nodePosX-FibNode.DISTANCE,nodePosY),	//-1.0
								new DPair(FibNode.DISTANCE*2, nodePosY), // 2.0
								Color.black);
					   			
		mainCompObj.addItem(minPointer);
		minPointer.setPos(initialPointerPos1);
		//System.out.println(minPointer.getParent()+"  "+minPointer.getPos());   // debug
		mainCompObj.addItem(rootList);
		message = new TextObj[3];
		message[0] = new TextObj("",
						messagePos0,
						14,
						TextObj.CENTER,
						TextObj.NORMAL,
						Color.black);
		message[1] = new TextObj("",
						messagePos1,
						13,
						TextObj.CENTER,
						TextObj.NORMAL,
						Color.red);
		message[2] = new TextObj("",
						messagePos2,
						12,
						TextObj.CENTER,
						TextObj.NORMAL,
						Color.blue);
		mainCompObj.addItem(message[0]);
		mainCompObj.addItem(message[1]);
		mainCompObj.addItem(message[2]);

		/*
		if (textMode > 0)
			showText("New Fibonacci Heap", 0);
		 */
	}

	/**
	 * Creates a new <tt>FibHeap</tt> consisting of one new <tt>FibNode</tt>.
	 */
	//private FibHeap(int k, Scheduler scheduler) {
	protected FibHeap(int k) {
		mainCompObj = new CompObj();
		
		min = new FibNode(k);
		
		// FibHeap-Referenz -> FibNode
		min.setFibHeap(this);
		
		size = potential = 1;
	}

	/**
	 * Creates a new <tt>FibHeap</tt> from an existing <tt>FibNode</tt>.
	 */
	private FibHeap(FibNode existing) {
		mainCompObj = new CompObj();
		
		size = potential = 0;
		min = existing;
	}


	/**
	 * @return true if this <tt>FibHeap</tt> is empty
	 */
	public boolean isEmpty() {
		// System.out.println("Heap size = "+size);
		return (size==0);
	}

	/**
	 * Melds another <tt>FibHeap</tt> into this one.
	 * The other rootlist is inserted to the right
	 * of the given node.
	 *
	 * @param other the <tt>FibHeap</tt> to be joined with this one
	 */
	public void meld (FibHeap other) {
		if (textMode > 2)
			showText("Merging F-heaps",1);
			
		// FibHeap-Referenz -> FibNode
		other.min.setFibHeap(this);			
		
		if (!this.isEmpty() && !other.isEmpty()) {
			this.min.getRoot().join(other.min, false);
			if (other.min.getKey() < min.getKey()) {
				updateMin(other.min);
				// SubOperation UPDATEMIN
				add(new SubOperation("UPDATEMIN", min.getKey()));
			}
		} else {
			if (this.isEmpty()) {
				updateMin(other.min);
				// SubOperation UPDATEMIN
				add(new SubOperation("UPDATEMIN", min.getKey()));
			}
		}

		this.size += other.getHeapSize();
		this.potential += other.potential;
		count++;	// cost = 1 unit

		// this.transferItem();	Transfer ALL root nodes of other!!!!!!!
	}

	/**
	 * Inserts a new node to this Fibonacci heap.
	 * Creates a new <tt>FibNode</tt> with given key and
	 * inserts in rootlist right of the <tt>min</tt> node.
	 *
	 * @param k key of new FibNode
	 * @return new FibNode with key k
	 */
	public FibNode insert(int k) {
		clearText();
		if (textMode > 0) {
			showText("insert("+k+")",0);
		}

		resetCount();

		if (textMode > 2)
			showText("Creating new F-heap",1);

		FibHeap q = new FibHeap(k);
		
		// SubOperation NEWFHEAP
		add(new SubOperation("NEWFHEAPMELD", k));

		//System.out.println("Insert " + q.min.getKey()); // debug
		mainCompObj.transferItem(q.min.compObj);
		DPair pos;
		if (isEmpty()) {
			pos = initialNodePos;
		} else {
			pos = new DPair(min.getRoot().compObj.getPos().get(0) +
							min.getRoot().getTreeWidth()*FibNode.DISTANCE,
							nodePosY-FibNode.DISTANCE);
		}
		q.min.compObj.setPos(pos);
		q.min.fPos = pos;
		q.min.appear();
		if (!isEmpty()) {
			min.getRoot().makeRoomFor(q.min);
		}
		if (!Exercise.quickAnim)
			animate();
			
		meld(q);

		animate();

		return q.min;
	}

	/**
	 * Returns the minimum key in this Fibonacci heap.
	 * If FibHeap is empty, returns -1.
	 *
	 * @return minimum key (or 999)
	 */
	public int accessmin() {
		// clearText();
		if (isEmpty()) {
			if (textMode > 2)
				showText("F-heap empty",2);
			return 999;   	// greatest possible integer
		} else {
			if (textMode > 2)
			showText("Minimum key is "+min.getKey(),2);
			return min.getKey();
		}
	}

	/**
	 * Deletes the node with minimum key in this Fibonacci heap.
	 * Then consolidates rootlist to restore heap.
	 *
	 * @return minimum key
	 */
	public int deletemin() {
		clearText();
		if (textMode > 0)
			showText("deletemin()",0);
		
		// Falls der Minimum-Zeiger beim DELETE_MIN auf einen
		// inneren Knoten zeigt
		if(!isEmpty() && !min.isRoot()) {
			resetCount();
			int m = min.getKey();
			FibNode toRemove = min;
			updateMin(min.getRoot());
			delete(toRemove);
			if(!isEmpty()) {
				consolidate();
				// SubOperation UPDATEMIN
				add(new SubOperation("UPDATEMIN", min.getKey()));
			} else {
				min = null;
			}
			return m;
		}

		resetCount();
		int m = accessmin();
		// System.out.println("Delete minimum node ("+m+")"); // debug
		if (!isEmpty()) {
			min.focus();
			//animate();
			remove(min);
			if (!isEmpty()) {
				consolidate();
				// SubOperation UPDATEMIN
				add(new SubOperation("UPDATEMIN", min.getKey()));
			} else {
				min = null;
			}
		}

		return m;
	}

	/**
	 * Removes a node from the rootlist.
	 * Then melds the list of that node's children
	 * into the rootlist. If the node removed was
	 * the minimum node, the min pointer is set to
	 * the adjacent node to the right.
	 *
	 * @param node the node to be removed
	 */
	protected void remove(FibNode node) {
		if (textMode > 1)
			showText("Removing node",1);

		size--;
		potential--;					// node deleted from rootlist
		if (node == min) {
			FibNode nextmin;
			if (!isEmpty()) {
				if (min.getRightSibling() != min) {
					nextmin = min.getRightSibling();
				} else {
					nextmin = min.getChildNode();
				}
			} else {
				nextmin = null;
			}
		 	updateMin(nextmin);
		}
		
		// SubOperation REMOVE
		add(new SubOperation("REMOVE", node.getKey()));
		node.delete();

		animate();
		node.compObj.hide();					// just to be sure!
		// deleteItem(node);   // schadet das???
	}

	/**
	 * Consolidates the rootlist.
	 * Uses an array in which the root nodes
	 * are entered according to their rank.
	 */
	protected void consolidate() {
		if (textMode > 1)
			showText("Consolidating root list",1);

		int length = maxRank()+1;
		if (textMode > 1)
			showText("Creating rank array with size "+length,2);
		FibNode A[] = new FibNode[length];				// initialize array
		count += length;				// additional cost

		if (showArray) {
			array = new ArrayObj(length); // display array
			mainCompObj.addItem(array.compObj);
		}

		FibNode B = min;
		FibNode last = min.getLeftSibling();
		FibNode next;
		while (B != last) {
			next = B.getRightSibling();
			enter(B,A);
			B = next;
			if (B.getKey() < accessmin()) {
				updateMin(B);
			}
		}
		
		enter(B,A);

		if (showArray)
			pause(pauseLength);

		if (showArray) {
			array.compObj.hide();
			mainCompObj.deleteItem(array.compObj);
			for (int j = 0; j < length; j++) {
				if (A[j] != null) {
					A[j].line.hide();
					mainCompObj.deleteItem(A[j].line);
					A[j].line = new LineObj();
					A[j].line.hide();
					mainCompObj.transferItem(A[j].line);
				}
			}
		}
		//updateRootListLine(0);
		Jedas.updateDisplay();
	}

	/**
	 * Enters a node in an array.
	 * The specified <tt>FibNode</tt> is placed
	 * at the array position matching its rank.
	 * If this position is occupied the two nodes
	 * of equal rank will be linked.
	 *
	 * @param B node to be entered
	 * @param A array in which node B is to be entered
	 */
	private void enter(FibNode B, FibNode A[]) {
		if (textMode > 1)
			showText("Entering node with rank "+B.getRank(),2);

		// B.parent = null;					// parent pointer might still be set
		// B.unmark();	 				// node might still be marked

		if (showArray)
			drawLine(B);

		if (A[B.getRank()] == null) {
			if (textMode > 2)
				showText("Entered node "+B.getKey()+" in array",2);

			A[B.getRank()] = B;
		} else {
			if (textMode > 2)
				showText("Array position occupied",2);

			int index = B.getRank();
			B = link(B,A[B.getRank()]);
			animate();
			A[index] = null;
			enter(B,A);
		}
	}

	/**
	 * Links two trees to form a new one.
	 * The root with smaller key becomes a child
	 * of the other root.
	 *
	 * @param B root of first tree
	 * @param C root of second tree
	 * @return root of resulting tree
	 */
	private FibNode link(FibNode B, FibNode C) {
		if (textMode > 1)
			showText("Linking nodes "+B.getKey()+" and "+C.getKey(),2);

		B.line.setColor(conflict);
		C.line.setColor(conflict);
		B.focus();
		C.focus();
		animate();

		removeLines(B,C);

		if (C.getKey() < B.getKey()) {					// swap B and C
			FibNode temp = C;
			C = B;
			B = temp;
		}

		if (C.isMarked() && textMode > 1)
			showText("Un-marking node "+C.getKey(),2);

		// SubOperation LINK
		add(new SubOperation("LINK", B.getKey(), C.getKey())); 
		if(C.isMarked()) {
			// SubOperation UNMARK
			add(new SubOperation("UNMARK", C.getKey())); 
		} 	// MKrebs

		C.unmark();					// don't unmark until necessary!
		
		B.addChild(C);
		count++;					// cost = 1
		return B;
	}

	/**
	 * Decreases the key of the specified node to the specified value.
	 * If necessary (to restore heap), cuts the node
	 * off its parent and inserts into rootlist.
	 * In this case, the parent will then be marked,
	 * or, if marked already, also cut off, and so on.
	 *
	 * @param N node whose key is to be decreased
	 * @param k new key value
	 */
	public void decreasekey(FibNode N, int k) {
		clearText();
		resetCount();
		//if (k < N.getKey() && k > 0) {
			if (textMode > 0) {
				showText("decreasekey("+N.getKey()+", "+k+")",0);
			}

			// System.out.println("Decrease "+N.getKey()+" to "+k); // debug
			N.focus();
			animate();
			// SubOperation SETKEY
			add(new SubOperation("SETKEY", N.getKey(), k));
			N.setKey(k);

			Jedas.updateDisplay();
		//}
		FibNode temp = N;
		if ((N.isRoot()) || (k >= N.getParentNode().getKey())) {
			count++;					// cost = 1
		} else {
			do {
				FibNode parent = N.getParentNode();

				if (temp.getKey()<accessmin() && N != temp) {
					updateMin(temp);
					// SubOperation UPDATEMIN
					add(new SubOperation("UPDATEMIN", min.getKey()));
				}

				animate();
				if (textMode > 1)
					showText("Cutting node "+N.getKey(),1);
				// SubOperation CUT
				add(new SubOperation("CUT", N.getKey()));

				N.cut(min.getRoot());

				potential++; 			// node added to root list
				if (N.isMarked())
					potential -= 2;		// mark is redundant in rootlist
				count++;			// cost = 1 per cut

				N = parent;
			} while (N.isMarked() && !N.isRoot());
			if (!N.isRoot()) {
				if (textMode > 1)
					showText("Marking node "+N.getKey(),2);
				if(!N.isMarked()) {
					// SubOperation MARK
					add(new SubOperation("MARK", N.getKey()));
				} 	// MKrebs
				N.mark();
				potential += 2; 		// non-root node marked
			}
			//updateRootListLine(0);
			animate();
		}

		if (temp.getKey() < accessmin()) {
			updateMin(temp);
			// SubOperation UPDATEMIN
			add(new SubOperation("UPDATEMIN", min.getKey()));
		}
	}

	/**
	 * Deletes the specified node from this Fibonacci heap.
	 * If the node is the min node, the <tt>deletemin</tt>
	 * method will be carried out.
	 *
	 * @param node node to be deleted
	 * @return key of the deleted node
	 */
	public int delete(FibNode node) {
		clearText();
		resetCount();
		if (node == min)
			return deletemin();
		else {
			// System.out.println("Delete "+node.getKey()); // debug
			if (textMode > 0) {
				showText("delete( "+node.getKey()+")",0);
			}

			node.focus();
			animate();

			if (!node.isRoot()) {
				FibNode temp = node;
				do {
					FibNode parent = temp.getParentNode();
					animate();
					if (textMode > 1)
						showText("Cutting node "+temp.getKey(),1);
					// SubOperation CUT
					add(new SubOperation("CUT", temp.getKey()));
					temp.cut(min.getRoot());

					count++;				// cost = 1 per cut;
					potential++;			// node added to root list
					if (temp.isMarked())
						potential -= 2;				// mark is redundant in rootlist
					temp = parent;
				} while (temp.isMarked() && !temp.isRoot());
				if (!temp.isRoot()) {
					if (textMode > 1)
						showText("Marking node "+temp.getKey(),2);
					if(!temp.isMarked()) {
						// SubOperation MARK
						add(new SubOperation("MARK", temp.getKey()));
					} 	// MKrebs
					temp.mark();
				}
			} else {
				count++;				// cost = 1 if no cuts
			}
			animate();
			remove(node);
			//updateRootListLine(-FibNode.DISTANCE);
			return node.getKey();
		}
	}

	/**
	 * @return the number of nodes in this Fibonacci heap
	 */
	public int getHeapSize() {
		return size;
	}

	/**
	 * Call this method to analyze a just completed heap operation.
	 * This will give you that operation's actual time complexity
	 * (see class intro for more details).
	 *
	 * @return the current value of the step counter.
	 */
	public int getCount() {
		return count;
	}

	/**
	 * Resets the step counter to 0.
	 * This method is called at the start of all heap operations.
	 * After executing the operation, use <tt>getCount()</tt> to
	 * get the time complexity of that operation (see class intro
	 * for more details).
	 */
	public void resetCount() {
		count = 0;
	}

	/**
	 * @return TRUE iff 'key color' mode is active
	 */
	public static boolean getKeyColorMode() {
		return keyColorMode;
	}

	/**
	 * Sets the 'key color' mode. In this mode, the fill color of
	 * each node relfects that node's key value.
	 *
	 * @param b TRUE iff 'key color' is on
	 */
	public static void setKeyColorMode(boolean b) {
		keyColorMode = b;
	}

	/**
	 * Sets the 'text mode' to accompany operations by text.
	 * Possible values are: NONE, NORMAL, DETAIL
	 *
	 * @param mode the text mode
	 */
	public static void setTextMode(int mode) {
		textMode = mode;
	}

	/**
	 * Returns the maximum possible rank of a node in this <tt>FibHeap</tt>.
	 * This number is in <i>O</i>(log <i>n</i>) where <i>n</i>
	 * is the heap size.
	 *
	 * @return maximum possible rank of a node
	 */
	public int maxRank() {
		if (isEmpty())
			return 0;
		else
			return (int)(1.4404 * Math.log(size)/Math.log(2));
	}

	/**
	 * Updates the minimum node of this FibHeap.
	 * Moves arrow to new minimum and adjusts colors.
	 *
	 * @param newMinNode the new minimum node
	 */
	protected void updateMin(FibNode newMinNode) {
		if (textMode > 2)
			showText("Setting minimum pointer to "+newMinNode.getKey(),2);

		//System.out.println("UpdateMin");  // debug

		if (newMinNode!=null && min!=null) {
			// System.out.println("IF");  // debug
			mainCompObj.transferItem(minPointer);
			DPair source = min.getRootPos();
			source.set(1, pointerY);
			DPair target = newMinNode.getRootPos();
			target.set(1, pointerY);
			if(Exercise.quickAnim) {
				minPointer.setPos(target);	// Problem
			}
			else {
				Path p = new Path();
				p.createDistance(source, target, Exercise.quickAnim?1:pointerSpeed);
				Trans t = new Trans(minPointer, p, Trans.MOVE);
				Jedas.getScheduler().add(t);
			}
		} else if (newMinNode == null) {
			// System.out.println("ELSE");  // debug
			mainCompObj.transferItem(minPointer);
			minPointer.setPos(initialPointerPos1);
		}

		min = newMinNode;
		
		animate();
		//Jedas.getScheduler().start();
		if (min != null) {
			//System.out.println(minPointer.getParent()+"  "+minPointer.getPos());
			min.addPointer(minPointer);
			//System.out.println(minPointer.getParent()+"  "+minPointer.getPos());
		}
	}

	/**
	 * Connects a root node to an array position.
	 * An arrow is drawn and animated.
	 *
	 * @param node the node to be connected
	 */
	private void drawLine(FibNode node) {
		Vector vector = new Vector();
		DPair[] geometry = {node.getRootPos(),
				new DPair(node.getRootPos().get(0),
						nodePosY-0.05-0.01*node.getRank()),
				new DPair(array.getPosition(node.getRank()).get(0),
						nodePosY-0.05-0.01*node.getRank()),
				array.getPosition(node.getRank())};
		Path[] p = new Path[4];
		for (int i=0; i<4; i++) {
			vector.addElement(node.getRootPos());
			if(!Exercise.quickAnim) {
				p[i] = new Path();
				p[i].createDistance((DPair)vector.elementAt(i), geometry[i], Exercise.quickAnim?1:ENTRYTIME);
			}
		}
		node.line= new PlineObj(vector, Color.gray, PlineObj.END);
		mainCompObj.transferItem(node.line);
		mainCompObj.lowerItem(node.line);
		node.line.show();
		if(Exercise.quickAnim) {
			node.line.setGeometry(geometry);
		}
		else {
			Trans t = new Trans(node.line, p, Trans.GEOMETRY);
			Jedas.getScheduler().add(t);
			animate();
			//Jedas.getScheduler().start();
		}
	}

	/**
	 * Removes the lines connecting two nodes with the array.
	 *
	 * @param node1 first node to be disconnected
	 * @param node2 second node to be disconnected
	 */
	private void removeLines(FibNode node1, FibNode node2) {
		if (showArray) {
			node1.line.hide();
			mainCompObj.deleteItem(node1.line);
		}
		node1.line = new LineObj();
		node1.line.hide();
		mainCompObj.transferItem(node1.line);
		if (showArray) {
			node2.line.hide();
			mainCompObj.deleteItem(node2.line);
		}
		node2.line = new LineObj();
		mainCompObj.transferItem(node2.line);
		node2.line.hide();
	}

	/**
	 * Starts the <tt>Scheduler</tt> instance of this <tt>FibHeap</tt>.
	 * Carries out all animation steps that have been accumulated since
	 * this method was called last.
	 */
	protected void animate() {
		if(min!=null) updateRootlistLine();
		Jedas.getScheduler().start();
	}

	/**
	 * Creates a pause of the given duration.
	 *
	 * @param time the duration of the pause (in ms)
	 */
	private void pause(long time) {
		if(Exercise.quickAnim) return;
		Path p = new Path();
		p.createNull(time, 1);
		Trans pause = new Trans(rootList, p, Trans.NOTHING);
		Jedas.getScheduler().add(pause);
		animate();
		//Jedas.getScheduler().start();
	}

	/**
	 * Shows a text message on the animation panel.
	 * Text can be displayed on different levels (of detail).
	 *
	 * @param text the text to be displayed
	 * @param level the level of detail
	 */
	void showText(String text, int level) {
		// create TextObj and place where appropriate
		if (level==0)
			text = "Current operation:  "+text;
		message[level].setText(text);
		message[level].setVisible(true);
	}

	/**
	 * Hides the text messages.
	 */
	void clearText() {
		message[0].setText(""); //Visible(false);
		message[1].setText(""); //Visible(false);
		message[2].setText(""); //Visible(false);
	}

	/**
	 * @return the leftmost node in the graphical representation
	 */
	protected FibNode getLeftmostNode() {
		FibNode temp = min;
		while (!temp.isLeftmost()) {
			temp = temp.getLeftSibling();
		}
		return temp;
	}

	// =======================================================================================
	/*
		Ab hier von
		Markus Krebs
		programmiert
	*/
	protected void updateRootlistLine() {
		FibNode fibNode = min; 
		if(fibNode!=null) {
			fibNode = fibNode.getRoot();
			//while(!fibNode.right.isLeftmost()) fibNode = fibNode.right;
			// Links-herum absuchen, da rechts neben dem Minimum
			// etwas eingefügt werden könnte (z.B. cut-Operation).
			// Die Zeiger würden in so einem Fall nicht stimmen.
			while(!fibNode.isLeftmost()) fibNode = fibNode.left;
			fibNode = fibNode.left;
			//System.out.println("-> rightmost="+fibNode.key);
		}
		double x = 0;
		if(fibNode!=null) {
			//System.out.println("updateRootlistLine: "+fibNode.getKey());
			
			// TODO: Überhang der Rootlist-Linie (Schönheitsfehler: Linie geht zu weit über rechtesten Knoten hinaus)
			// PROBLEM: Wenn der rechteste Knoten Kinder hat, dann
			// wäre ein korrekter Überhang der Rootlist-Linie schön.
			// Leider funktionieren folgende beide Ansätze so nicht
			// ganz korrekt!
			
			x = fibNode.getAbsPos(mainCompObj).get(0)-fibNode.compObj.getPos().get(0)+fibNode.fPos.get(0);
			int w = fibNode.getTreeWidth();
			//System.out.println("TreeWidth="+w);
			if(w>1) x += ((double)(w-1))*FibNode.DISTANCE;
			
			/*
			// Rechtesten Knoten suchen
			// Funktioniert so allerdings auch nicht ganz
			x = fibNode.getAbsPos(mainCompObj).get(0)-fibNode.compObj.getPos().get(0)+fibNode.fPos.get(0);
			System.out.print("x = "+x+" -> ");
			while(fibNode.getChildNode()!=null) {
				fibNode = fibNode.getChildNode();
				while(!fibNode.isLeftmost()) fibNode = fibNode.left;
				fibNode = fibNode.left;
				x += fibNode.fPos.get(0);
				System.out.print(x+" -> ");
			}
			System.out.println();
			System.out.println("rightmost node = "+fibNode.getKey());
			*/
		}
		x += FibNode.DISTANCE;
		// bei keiner Veränderung nichts machen
		if(x == rootList.getSize().get(0)) return;
		// Animation
		DPair newSize = new DPair(x, 0.0);
		if(!Exercise.quickAnim) {
			Path sizePath = new Path();
			sizePath.createDistance(rootList.getSize(), newSize, FibNode.MOVETIME);
			Trans sizeTrans = new Trans(rootList, sizePath, Trans.RESIZE);
			Jedas.getScheduler().add(sizeTrans);
		} else {
			rootList.setSize(newSize);
		}
	}
	
	public CompObj getMainCompObj() {
		return mainCompObj;
	}
	
	public SubOperationQueue getSubOperationQueue() {
		return subOperations;
	}
	public void add(SubOperation so) { subOperations.add(so); }
	public void clearSubOperationQueue() { subOperations.clear(); }

	/*
		Methoden zum Kopieren des kompletten Fibonacci-Heaps
		08.11.2003 16:25:30

		Lösungsansatz: Dynamische Programmierung
	*/
	protected transient IdentityHashMap fibNodes;
	private static final int initialCapacity = 30;	// für HashMap

	public Object deepCopy() {
		return copy();
	}

	// Kompletten FibHeap kopieren
	public Object copy() {
		//this.newScheduler = newScheduler;	// wird für copyNode gebraucht
		//this.newScheduler = Jedas.getScheduler();

		fibNodes = new IdentityHashMap(initialCapacity);
		exploreNode(min);				// Alle Knoten ausfindig machen => fibNodes
		
		// Klasse auch verwendbar für BinQueues machen
		//FibHeapExt fibHeapCopy = new FibHeapExt(newScheduler);
		FibHeapExt fibHeapCopy;
		if(this instanceof mauda.plugin.binqueue.BinQueue)
			fibHeapCopy = new mauda.plugin.binqueue.BinQueue();
		else
			fibHeapCopy = new FibHeapExt();
		// --------------------------------			
		
		FibNode newMin = copyNode(fibHeapCopy, min);	// Alle Knoten duplizieren
		//FibHeap fibHeapCopy = null;
		//if(this instanceof FibHeapExt) fibHeapCopy = new FibHeapExt(newScheduler);
		//else fibHeapCopy = new FibHeap(newScheduler);
		fibHeapCopy.min = newMin;
		fibHeapCopy.size = size;
		fibHeapCopy.potential = potential;
		fibHeapCopy.count = count;
		// ======== Nachfolgendes für Animation ==========
		if(newMin!=null) {
			newMin.addPointer(fibHeapCopy.minPointer);
			//newMin.transferItem(fibHeapCopy.minPointer);
			//fibHeapCopy.minPointer.setPos(minPointer.getPos());
		}
		//fibHeapCopy.minPointer.show();
		//fibHeapCopy.rootlist = new LineObj(...):	// Wird vom Konstruktor erledigt (ändert sich auch nicht)
		fibHeapCopy.rootList.setPos(rootList.getPos());
		fibHeapCopy.rootList.setSize(rootList.getSize());
		//fibHeapCopy.array = new ArrayObj(...);	// Wir vom Konstruktor erledigt (braucht nicht angepasst werden)
		//fibHeapCopy.showArray = showArray;
		for(int i=0; i<3; i++) {
			//((FibHeap)fibHeapCopy).message[i].setText(message[i].getText());
			//((FibHeap)fibHeapCopy).message[i].setVisible(message[i].isVisible());
		}
		// ===============================================
		return fibHeapCopy;
	}

	// Ermitteln der vorkommenden Knoten
	private void exploreNode(FibNode fibNode) {
		if(fibNode == null) return;	// Dieser Fall sollte nicht vorkommen
		if(fibNodes.containsKey(fibNode)) return;
		fibNodes.put(fibNode, null);
		exploreNode(fibNode.left);
		exploreNode(fibNode.right);
		exploreNode(fibNode.parent);
		exploreNode(fibNode.child);
	}

	// Knoten kopieren
	// Aufruf immer mit Original-Knoten (KEY aus HashMap)
	// Rückgabe: Kopie des Original-Knotens (VALUE aus HashMap)
	private FibNode copyNode(FibHeap fibHeap, FibNode fibNode) {
		if(fibNode==null) return null;
		FibNode n = (FibNode)fibNodes.get(fibNode);
		if(n==null) {
			n = (FibNode)fibNode.copy();	// Alles clonen ausser den Zeigern (werden auf NULL gesetzt)
			
			// FibHeap-Referenz -> FibNode
			n.setFibHeap(fibHeap);
			
			fibNodes.put(fibNode, n);		// Jetzt Abbildung machen
			n.left = copyNode(fibHeap, fibNode.left);
			n.right = copyNode(fibHeap, fibNode.right);
			n.parent = copyNode(fibHeap, fibNode.parent);
			n.child = copyNode(fibHeap, fibNode.child);
			if(n.parent!=null) {
				n.parent.compObj.addItem(n.compObj);
				n.parent.compObj.transferItem(n.line);
				n.parent.compObj.lowerItem(n.line);
				// Folgende Zeile gegen Linien-Verschwinden-Problem bei neuem JEDAS
				n.line.setGeometry(fibNode.line.getGeometry());
			}
			else fibHeap.mainCompObj.addItem(n.compObj);
		}
		return n;
	}

	// Ausgabe des FibHeaps:
	public String toString() {
		String s = "FibHeap:";
		if(this instanceof FibHeapExt) {
			s = "FibHeapExt:\n";
			s += "Node-Array: ";
			FibNode[] nodes = ((FibHeapExt)this).getAllNodes();
			for(int i=0; i<nodes.length; i++) {
				if(nodes[i]!=null) s += nodes[i].getKey()+" ";
			}
			s += "\n";
		} 		
		if(isEmpty()) {
			s += "empty\n";
		} else {
			s += "MIN: "+min.getKey()+"\n";
			fibNodes = new IdentityHashMap(initialCapacity);
			s = s + exploreNodeDump(min);
		}
		return s;
	}
	// Ermitteln der vorkommenden Knoten
	private String exploreNodeDump(FibNode fibNode) {
		if(fibNode == null) return "";	// Dieser Fall sollte nicht vorkommen
		if(fibNodes.containsKey(fibNode)) return "";
		// Ausgabe zum debuggen
		String s =
				"Key    = "+fibNode.getKey()+" | "+
				"Rank   = "+fibNode.getRank()+" | "+
				"Mark   = "+fibNode.isMarked()+" | "+
				"left   = "+(fibNode.left==null?"n":fibNode.left.getKey()+"")+" | "+
				"right  = "+(fibNode.right==null?"n":fibNode.right.getKey()+"")+" | "+
				"parent = "+(fibNode.parent==null?"n":fibNode.parent.getKey()+"")+" | "+
				"child  = "+(fibNode.child==null?"n":fibNode.child.getKey()+"")+
				"\n";
		//System.out.println();
		//System.out.println(fibNode.getKey());
		fibNodes.put(fibNode, null);
		s += exploreNodeDump(fibNode.left);
		s += exploreNodeDump(fibNode.right);
		s += exploreNodeDump(fibNode.parent);
		s += exploreNodeDump(fibNode.child);
		return s;
	}
	
	/*
	 * ===================================================================
	 * Ab HIER:
	 * Kopieren des FibHeaps in die schnelle FibHeapDS-Struktur
	 * ===================================================================
	 */
	// Kompletten FibHeap kopieren
	public Object copyDS() {
		fibNodes = new IdentityHashMap(initialCapacity);
		exploreNode(min);	// Alle Knoten ausfindig machen => fibNodes
		FibHeapDSExt fibHeapCopy = new FibHeapDSExt();
		FibNodeDS newMin = copyNodeDS(fibHeapCopy, min);	// Alle Knoten duplizieren
		fibHeapCopy.min = newMin;
		fibHeapCopy.size = size;
		fibHeapCopy.potential = potential;
		fibHeapCopy.count = count;
		return fibHeapCopy;
	}
	// Knoten kopieren
	// Aufruf immer mit Original-Knoten (KEY aus HashMap)
	// Rückgabe: Kopie des Original-Knotens (VALUE aus HashMap)
	private FibNodeDS copyNodeDS(FibHeapDS fibHeap, FibNode fibNode) {
		if(fibNode==null) return null;
		FibNodeDS n = (FibNodeDS)fibNodes.get(fibNode);
		if(n==null) {
			// Anstatt eine copyDS-Routine in FibNode zu legen, erledige ich das hier
			//n = (FibNodeDS)fibNode.copyDS();	// Alles clonen ausser den Zeigern (werden auf NULL gesetzt)
			n = new FibNodeDS(fibNode.getKey());
			n.setParameters(fibNode.getKey(), fibNode.getRank(), fibNode.isMarked(), null, null, null, null);
			
			fibNodes.put(fibNode, n);		// Jetzt Abbildung machen
			n.left = copyNodeDS(fibHeap, fibNode.left);
			n.right = copyNodeDS(fibHeap, fibNode.right);
			n.parent = copyNodeDS(fibHeap, fibNode.parent);
			n.child = copyNodeDS(fibHeap, fibNode.child);
		}
		return n;
	}
}
