/*
 * Created on 14.12.2003 18:33:31
 *
 * Multimediale Algorithmen und Datenstrukturen Assessments
 */
package mauda.plugin.fibheap;

import mauda.Exercise;	// für Exercise.quickAnim

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

/**
 * Describes a node in a Fibonacci heap.
 * On the logical side, each node has references to its parent,
 * its left and right sibling, and one of its children.
 * Thus, it is possible to use this node for trees with variable
 * node rank, using the 'child-sibling' representation of trees.
 * In addition, there are two <tt>int</tt>s reprenting the key
 * and the rank (= number of children) of this node.
 * A <tt>boolean</tt> indicates whether this node has lost one
 * of its children since it (=this node) was last made a child
 * of another node.
 * Physically, a node is represented by a <tt>FibNodeObj</tt> and
 * by a <tt>LineObj</tt> connecting it to its parent node.
 * The physical <tt>CompObj</tt> representing a node includes
 * the whole subtree rooted in this node. Thus, moving one
 * <tt>FibNode</tt> will move the subtree along.
 *
 * @version 2.01 (08/08/02)
 * @author Tobias Lauer
 */
public class FibNode {
	
	protected CompObj compObj;
	
	// Bei Exercise.quickAnim:
	// FLASHTIME=1 / MOVETIME=1 / MARKTIME=1

	/**
	 * The two animated objects visualizing this node
	 */
	protected FibNodeObj nodeObj;
	PlineObj line;
	/**
	 * The future position (=after the next animation step) of this node
	 */
	DPair fPos;
	private DPair[] geometry;
	private int orientation;
	private boolean highlighted;
	private static double amplitude;
	/**
	 * The logical attributes
	 */
	FibNode left, right, parent, child;
	private int key, rank;
	private boolean mark;
	/**
	 * Some settings
	 */
	static DTriple unmarkColor	= new DTriple(1,1,1);
	static DTriple appearColor	= new DTriple(0,0,1);
	static DTriple flashColor	= new DTriple(1,0,0);
	static DTriple markColor	= new DTriple(1,0.7,0.7);
	static DTriple drawColor	= new DTriple(0,0,0);
	static Color hilightColor	= Color.ORANGE;
	static long FLASHTIME		= 220;
	static long MOVETIME		= 600;
	static long MARKTIME		= 300;
	static double DISTANCE		= 0.08;		// MKrebs: normalerweise 0.1
	static double NODESIZE		= 0.06;
	static boolean keycolor		= true;
	static int flashNum			= 1;
	static int align			= 1;

	public static final int CENTER = 0;
	public static final int LEFT = 1;

	/**
	 * Creates a new node with the specified key.
	 * The node has no parent or child and is the only
	 * node in its list of siblings.
	 *
	 * @param key the key for this node
	 */
	public FibNode (int key) {
		compObj = new CompObj();
		
		this.key = key;
		left = right = this;

		nodeObj = new FibNodeObj(new DPair(0,0),""+key);
		line = new LineObj();
		//addItem(line);
		line.hide();
		compObj.addItem(nodeObj.compObj);
		fPos = (DPair)compObj.getPos().clone();
		geometry = new DPair[2];
		compObj.hide();
	}

	/**
	 * Creates an empty node.
	 * For internal use.
	 */
	FibNode() {
		compObj = new CompObj();
		
		this.key = 0;
		left = right = this;
	}

	void setParameters(int key, int rank, boolean mark, FibNode parent, FibNode child, FibNode left, FibNode right) {
		this.key = key;
		this.rank = rank;
		this.mark = mark;
		this.parent = parent;
		this.child = child;
		this.left = left;
		this.right = right;
	}



	/**
	 * Returns the (logical) parent <tt>FibNode</tt> of this node.
	 * Might differ from <tt>getParent()</tt>, which
	 * returns the (physical) parent <tt>Composite</tt>.
	 *
	 * @return the parent of this node
	 * (or null, if this node is a root).
	 */
	public FibNode getParentNode() {
		if (isRoot())
			return null;
		else
			return parent;
	}

	/**
	 * @return the leftmost child of this node
	 * (or <tt>null</tt>, if there is no child).
	 */
	public FibNode getChildNode() {
		return child;
	}

	/**
	 * Used for child-sibling format of trees.
	 *
	 * @return this node's (right) sibling
	 * (=<tt>null</tt> if there is no sibling!)
	 */
	public FibNode getSibling() {
		if (right == this)
			return null;
		else
			return right;
	}

	/**
	 * @return this node's right sibling
	 * (=this node if there is no sibling)
	 */
	public FibNode getRightSibling() {
		return right;
	}

	/**
	 * @return this node's right sibling
	 * (= this node if there is no sibling)
	 */
	public FibNode getLeftSibling() {
		return left;
	}

	/**
	 * @return the rank (= number of children) of this node.
	 */
	public int getRank() {
		return rank;
	}

	/**
	 * @return the key of this node
	 */
	public int getKey() {
		return key;
	}

	/**
	 * Sets the key of this node to the specified value.
	 *
	 * @param k the new key
	 */
	public void setKey(int k) {
		key = k;
		DTriple oldcolor = getUnmarkColor();
		nodeObj.setCenterLabel(k+"");
		if (!isMarked())  {
			if(Exercise.quickAnim) {
				nodeObj.oval.setFillColor(getUnmarkColor().getColor());
			}
			else {
				Path p = new Path();
				p.createDistance(oldcolor, getUnmarkColor(), Exercise.quickAnim?1:MARKTIME);
				Trans t = new Trans(nodeObj.oval, p, Trans.FILLCOLORCHANGE);
				Jedas.getScheduler().add(t);
			}
		}
	}

	/**
	 * @return TRUE iff 'key color' feature is turned on
	 */
	public boolean getColorMode() {
		return keycolor;
	}

	/**
	 * Sets the 'key color' feature of this class.
	 * If turned on, the brightness of the node's fill color reflects
	 * its key value.
	 *
	 * @param b TRUE iff color is to reflect the key value
	 */
	public static void setColorMode(boolean b) {
		keycolor = b;
	}

	/**
	 * @return <tt>TRUE</tt> iff this node is part of the rootlist
	 */
	public boolean isRoot() {
		return ((parent == null) || (parent.child == null));
	}

	/**
	 * @return <tt>TRUE</tt> iff this node has at least one child
	 */
	public boolean hasChildren() {
		return (rank > 0);
	}

	/**
	  * @return <tt>TRUE</tt> iff this node is marked
	  * (=has lost a child since last linked to another node)
	  */
	public boolean isMarked() {
		return mark;
	}

	/**
	 * Marks this node.
	 */
	public void mark() {
		if (!mark) {
			mark = true;
			if(Exercise.quickAnim) {
				this.nodeObj.oval.setFillColor(markColor.getColor());
			}
			else {
				Path p = new Path();
				p.createDistance(getUnmarkColor(), markColor, Exercise.quickAnim?1:MARKTIME);
				Trans t = new Trans(this.nodeObj.oval, p, Trans.FILLCOLORCHANGE);
				Jedas.getScheduler().add(t);
			}
		}
	}

	/**
	 * Un-marks (removes mark from) this node.
	 */
	public void unmark() {
		if (mark) {
			mark = false;

			if(Exercise.quickAnim) {
				this.nodeObj.oval.setFillColor(getUnmarkColor().getColor());
			}
			else {
				Path p = new Path();
				p.createDistance(markColor, getUnmarkColor(), MARKTIME);
				Trans t = new Trans(this.nodeObj.oval, p, Trans.FILLCOLORCHANGE);
				Jedas.getScheduler().add(t);
			}
		}
	}

	/**
	 * Sets the focus of attention to this node.
	 * Various implementations thinkable.
	 */
	public void focus() {
		flash(flashNum);
	}

	/**
	 * Highlights this node with the current highlight color.
	 * Can be used, e.g., to signal that a user has selected this node
	 * with the mouse etc.
	 *
	 * @param on highlight status.
	 */
	public void setHighlight(boolean on) {
		highlighted = on;
		if (highlighted) {
			 nodeObj.oval.setFillColor(hilightColor);
		} else {
		 	if(mark) nodeObj.oval.setFillColor(markColor.getColor());	// MKrebs
		 	else														// MKrebs
			nodeObj.oval.setFillColor(getUnmarkColor().getColor());
		}
		Jedas.updateDisplay();
	}

	/**
	 *
	 * @return true iff this node is highlighted.
	 */
	public boolean getHighlight() {
		return highlighted;
	}

	/**
	 * Sets the highlight color of FibNodes.
	 *
	 * @param color the desired highlight color
	 */
	public static void setHighlightColor(Color color) {
		hilightColor = color;
	}

	/**
	 * Node will appear in a smooth animation.
	 */
	public void appear() {
		compObj.show();
		/*if(quickAnim) {
			nodeObj.oval.setPos(new DPair(-NODESIZE/2,-NODESIZE/2));	// Problem
			nodeObj.oval.setSize(new DPair(NODESIZE,NODESIZE));			// Problem
			nodeObj.oval.setFillColor(getUnmarkColor().getColor());
			nodeObj.centerLabel.setColor(drawColor.getColor());
			return;
		}*/
		Path sizePath = new Path();
		sizePath.createDistance(new DPair(0,0),
					new DPair(NODESIZE,NODESIZE),
					Exercise.quickAnim?1:MARKTIME);
		Trans sizeTrans = new Trans(nodeObj.oval, sizePath, Trans.RESIZE);

		Path movePath = new Path();
		movePath.createDistance(new DPair(0,0),
					new DPair(-NODESIZE/2,-NODESIZE/2),
					Exercise.quickAnim?1:MARKTIME);
		Trans moveTrans = new Trans(nodeObj.oval, movePath, Trans.MOVE);

		Jedas.getScheduler().add(moveTrans);
		Jedas.getScheduler().add(sizeTrans);

		if(Exercise.quickAnim) {
			nodeObj.oval.setFillColor(getUnmarkColor().getColor());
			nodeObj.centerLabel.setColor(drawColor.getColor());
		}
		else {
			Path colorPath = new Path();
			colorPath.createDistance(appearColor, getUnmarkColor(), Exercise.quickAnim?1:MOVETIME);
			Trans colorTrans = new Trans(nodeObj.oval, colorPath, Trans.FILLCOLORCHANGE);

			Path textcolor = new Path();
			textcolor.createDistance(unmarkColor, drawColor, Exercise.quickAnim?1:MARKTIME);
			Trans colorTrans2 = new Trans(nodeObj.centerLabel,
						textcolor, Trans.COLORCHANGE);

			Jedas.getScheduler().add(colorTrans);
			Jedas.getScheduler().add(colorTrans2);
		}

	}

	/**
	 * Node will disappear in a smooth animation.
	 */
	public void disappear() {
		/*if(quickAnim) {
			nodeObj.oval.setPos(new DPair(0,0));	// Problem
			nodeObj.oval.setSize(new DPair(0,0));	// Problem
			nodeObj.oval.setFillColor(appearColor.getColor());
			nodeObj.centerLabel.setColor(unmarkColor.getColor());
			return;
		}*/
		Path sizePath = new Path();
		sizePath.createDistance(new DPair(NODESIZE,NODESIZE),
					new DPair(0,0),
					Exercise.quickAnim?1:MARKTIME);
		Trans sizeTrans = new Trans(nodeObj.oval, sizePath, Trans.RESIZE);

		Path movePath = new Path();
		movePath.createDistance(new DPair(-NODESIZE/2,-NODESIZE/2),
					new DPair(0,0),
					Exercise.quickAnim?1:MARKTIME);
		Trans moveTrans = new Trans(nodeObj.oval, movePath, Trans.MOVE);

		Jedas.getScheduler().add(moveTrans);
		Jedas.getScheduler().add(sizeTrans);

		if(Exercise.quickAnim) {
			nodeObj.oval.setFillColor(appearColor.getColor());
			nodeObj.centerLabel.setColor(unmarkColor.getColor());
		}
		else {
			Path colorPath = new Path();
			DTriple color = unmarkColor;
			if (isMarked()) {
				color = markColor;
			}
			colorPath.createDistance(color, appearColor, Exercise.quickAnim?1:MOVETIME);
			Trans colorTrans = new Trans(nodeObj.oval, colorPath, Trans.FILLCOLORCHANGE);

			Path textcolor = new Path();
			textcolor.createDistance(drawColor, unmarkColor, Exercise.quickAnim?1:MARKTIME);
			Trans colorTrans2 = new Trans(nodeObj.centerLabel,
						  textcolor, Trans.COLORCHANGE);
			Jedas.getScheduler().add(colorTrans);
			Jedas.getScheduler().add(colorTrans2);
		}
	}

	/**
	 * Links another node N to this one.
	 * Inserts N as the rightmost child of this node.
	 *
	 * @param newChild the node to be added
	 */
	public void addChild(FibNode newChild) {
		//System.out.println("Adding " + newChild.key + " to " + key); 	// debug
		// Close gap and/or make room
		FibNode moveNode;

		int dist = newChild.getTreeWidth();
		
		if (!hasChildren()) {
			//System.out.println(key + " childless.");	// debug
			moveNode = newChild.right;
			while (!moveNode.isLeftmost()) {
				//System.out.println("Start pull.");						// debug
				moveNode.pullLeft(dist);
				moveNode = moveNode.right;
			}
		} else if (isLeftOf(newChild)) {
			//System.out.println(key + " left of " + newChild.key); 	// debug
			moveNode = right;
			//int c = 0;
			while (moveNode != newChild) {
				//System.out.println("Moving " + moveNode.key); 		// debug
				moveNode.pushRight(dist);
				moveNode = moveNode.right;
				//c++; if(c>10) break;
			}
		} else {
			//System.out.println(key + " right of " + newChild.key); 	// debug
			moveNode = newChild.right;
			while (moveNode != this.right) {
				//System.out.println("Start pull 2.");					  // debug
				moveNode.pullLeft(dist);
				moveNode = moveNode.right;
			}
		}

		newChild.separate(false);
		newChild.parent = this;
	
		compObj.transferItem(newChild.compObj);
		DPair trans = new DPair(newChild.compObj.getPos().get(0)-compObj.getPos().get(0),0);
		newChild.compObj.setPos(trans);
		newChild.fPos = trans;
		//System.out.println("Transposing " + newChild.key);	 		// debug

		if (this.hasChildren()) {
			child.left.join(newChild, false);  				// room already made
		} else {
			child = newChild;
			child.fPos = new DPair(0, DISTANCE);
			Path p = new Path();
			if (child.compObj.getPos().get(0) < child.fPos.get(0)) {
				orientation = Path.STRAIGHT; //COUNTERCLOCKWISE;
			} else if (child.compObj.getPos().get(0) == child.fPos.get(0)) {
				orientation = Path.STRAIGHT;
			} else {
				orientation = Path.STRAIGHT; //CLOCKWISE;
			}
			amplitude = 0.1;
			/*if(quickAnim) {
				child.setPos(child.fPos);	// Problem
			}
			else {*/
				p.createMotion(child.compObj.getPos(), child.fPos, orientation,
						   amplitude, Exercise.quickAnim?1:MOVETIME);

				//p.createDistance(child.getPos(), child.fPos, MOVETIME);
				Trans t = new Trans(child.compObj, p, Trans.MOVE);
				Jedas.getScheduler().add(t);
			//}

			compObj.transferItem(newChild.line);

			geometry[0] = newChild.compObj.getPos();
			geometry[1] = new DPair(0,0);
			newChild.line.setGeometry(geometry);
			newChild.line.show();
			//System.out.println("Line transposed");			// debug
			compObj.lowerItem(newChild.line);
			
			//newChild.line.setColor(new Color(30,255,30));
			//newChild.line.setArrowMode(PlineObj.END);
		}
		rank++;

		centerNode();
	}

	/**
	 * Cuts this node off its parent and joins with target
	 *
	 * @param target the node where this one is attached
	 */
	public void cut(FibNode target) {
		if (!isRoot()) {
			focus();
			fibHeap.animate();
			//Jedas.getScheduler().start();
			boolean isOnlyChild = (parent.rank==1 && getTreeWidth()==1);

			int dist = getTreeWidth();
			if (parent.rank == 1)
				 dist--;

			FibNode temp = getRoot();
			separate(!isOnlyChild);
			line.hide();
			compObj.transferItem(line);
			if (!isOnlyChild) {
				//System.out.print("Spacing ...");
				//System.out.println("root is " + temp.key);
				if (temp.isLeftOf(target)) {
					//System.out.println("Root left of target");
					while (temp.isLeftOf(target)) {
						temp = temp.right;
						temp.pullLeft(dist);  // getTreeWidth());
					}
					// Bugfix 17/02/03
					temp = target.right;
					while (!temp.isLeftmost()) {
						temp.pushRight(getTreeWidth()-dist);
						temp = temp.right;
					}
					// end bugfix
				} else {
					//System.out.println("Root right of target");

					FibNode rest = temp.right;  // bugfix 17/02/03

					while (target.isLeftOf(temp)) {
						temp.pushRight(getTreeWidth());
						temp = temp.left;
					}
					// Bugfix 17/02/03
					while (!rest.isLeftmost()) {
						rest.pushRight(getTreeWidth()-dist);
						rest = rest.right;
					}
					// end bugfix
				}
			}
			target.join(this, isOnlyChild);
		}
	}

	/**
	 * Separates this node from its parent and siblings.
	 * Left and right sibling are joined instead.
	 * Parent's child pointer is updated, if necessary.
	 * All children remain unchanged.
	 *
	 * @param thereIsGap true if a gap will be created
	 */
	private void separate(boolean thereIsGap) {
		if (thereIsGap) {
			//System.out.println("Gap must be closed."); 			// debug
			closeGap();
		}
		if (!isRoot()) {
			parent.rank--;
			if (!parent.hasChildren()) {
			    parent.child = null;
			    parent.centerNode();
			} else if (parent.child == this) {
				parent.child = this.right;
			}
	    }
	    left.right = right;
		right.left = left;
		left       = this;
	    right      = this;
	    if (!isRoot()) {
			parent.centerNode();
		} //else System.out.println(key+" is Root. No centering."); 	// debug
	    parent = null;
	}

	/**
	 * Joins another node list to the sibling list of this one.
	 * Inserts the other node and its siblings right next to this node.
	 * All parents and children remain.
	 *
	 * @param other node of the list to join
	 * @param spaceNeeded true if additional space is needed
	 */
	public void join(FibNode other, boolean spaceNeeded) {
	    if (spaceNeeded) {
			makeRoomFor(other);
	    }

	    moveHere(other);

	    this.right.left  = other.left;
	    other.left.right = this.right;
	    this.right       = other;
		other.left	   = this;

	    // visualize
	    if (!isRoot() && compObj.getParent()!=null) {
			compObj.getParent().transferItem(other.line);
			geometry[0] = other.getRootPos();
			
			// PROBLEMATISCH
			//geometry[1] = ((FibNode)getParent()).nodeObj.getPos();
			geometry[1] = ((FibNode)parent).nodeObj.compObj.getPos();
			
			other.line.setGeometry(geometry);
			other.line.show();
			// System.out.println("Line adjusted");    	        // debug
			compObj.getParent().lowerItem(other.line);
	    } else if (compObj.getParent() == null) {
			System.out.println("Error! -- No parent found!");
			System.exit(0);
	    }
	}

	/**
	 * Deletes this node from the root list.
	 */
	public void delete() {
	    if (isRoot()) {
			line.hide();
			compObj.transferItem(line);
			liftUp();
			fibHeap.animate();
			//Jedas.getScheduler().start();
			if (hasChildren()) {
				// ==== MKrebs: parent-Zeiger der Kinder auf null setzen ====
				FibNode temp = child;
				do {
					temp.parent = null;
					temp = temp.right;
				} while(temp!=child);
				// ==========================================================
			    //scheduler.start();
				if (left != this) {  					// must have siblings
					left.right       = child;
					right.left	   = child.left;
					child.left.right = right;
					child.left	   = left;
					left = right = this;
				}
			    transferChildren();
			} else {
				separate(true);
			}
			child = null;
			disappear();
		}
	}

	/**
	 * @return this node's current root position relative to its parent
	 */
	public DPair getRootPos() {
		double x = compObj.getPos().get(0);
		double y = compObj.getPos().get(1);
	    x += nodeObj.compObj.getPos().get(0);
		y += nodeObj.compObj.getPos().get(1);
	    return new DPair(x,y);
	}

	/**
	 * Adds the minimum pointer object to this node.
	 *
	 * @param item the arrow to be added
	 */
	public void addPointer(LineObj item) {
		nodeObj.compObj.transferItem(item);
	    item.setPos(new DPair(0,-0.08));
	}

	/**
	 * @return width of the (sub)tree rooted in this node
	 */
	public int getTreeWidth() {
		int width = 1;
		FibNode temp;
		if (child != null) {
		  temp = child.right;
		  width = child.getTreeWidth();
		  while (temp != child) {
			  width += temp.getTreeWidth();
			  temp = temp.right;
		  }
		}
		return width;
	}

	/**
	 * @return the sum of widths of all subtrees in this list
	 */
	private int getListWidth() {
	    int width = 0;
		FibNode temp = this;
		do {
			width += temp.getTreeWidth();
			temp = temp.right;
		} while (temp.right != this);
	    return width;
	}

	/**
	 * @return an array containing all children of this node.
	 */
	private FibNode[] getChildlist() {
	    if (!this.hasChildren()) {
			return null;
	    } else {
			FibNode[] childlist = new FibNode[rank];
			FibNode temp = child;
			for (int i=0; i<rank; i++) {
				childlist[i] = temp;
				temp = temp.right;
			}
			return childlist;
	    }
	}

	/**
	 * @return the depth of this (sub)tree (from this node to bottom)
	 */
	public int getTreeDepth() {
		if (child == null)
			return 1;
	    else {
			int depth = 0;
			FibNode temp = child;
			do {
				if (temp.getTreeDepth() > depth)
					depth = temp.getTreeDepth();
				temp = temp.right;
			} while (temp != child);
			return depth+1;
		}
	}

	/**
	 * @return the size (=number of nodes) in this (sub)tree
	 */
	public int getTreeSize() {
		int size = 1;
		if (this.hasChildren()) {
			FibNode temp = child;
			do {
				size = size + temp.getTreeSize();
				temp = temp.right;
			} while (temp != child);
		}
		return size;
	}

	/**
	 * @return the depth of this node in its tree
	 * (=distance from root to this node)
	 */
	public int getDepth() {
		int depth = 1;
		FibNode temp = this;
		while (!temp.isRoot()) {
			depth++;
			temp = temp.parent;
		}
		return depth;
	}

	/**
	 * @return the root of the tree this node is part of
	 */
	public FibNode getRoot() {
		FibNode temp = this;
		while (!temp.isRoot()) {
			temp = temp.parent;
		}
		return temp;
	}

	/**
	 * Makes room for another subtree to be inserted to the right of this node
	 *
	 * @param inserted the node to be inserted
	 */
	public void makeRoomFor(FibNode inserted) {
		FibNode toMove = this;
		while (!toMove.isRoot()) {
			toMove = toMove.parent;
		}
		toMove = toMove.right;
		while (!toMove.isLeftmost()) {
			toMove.pushRight(inserted.getListWidth());
			toMove = toMove.right;
		} // else System.out.println(toMove.key + " is leftmost!"); 	// debug
	}

	/**
	 * Closes the gap a separated node has left.
	 */
	private void closeGap() {
		int dist = getTreeWidth();
		if (parent != null && parent.rank == 1 && !isRoot())
			dist--;
		FibNode temp = this;
		do {
			temp = temp.right;
			while (!temp.isLeftmost()) {
				//System.out.println("Pull " + temp.key); 			// debug
				temp.pullLeft(dist);
				temp = temp.right;
			}
			if (!temp.isRoot())
				temp = temp.parent;
		} while (!temp.isRoot());
	}

	/**
	 * Moves this node and all its right neighbors to the right.
	 *
	 * @param dist the distance to move
	 */
	private void pushRight(int dist) {
		//System.out.println("Push " + key + " by " + dist); 		// debug
		fPos = new DPair(compObj.getPos().get(0) + dist * DISTANCE,
			compObj.getPos().get(1));
		Path p = new Path();
		p.createDistance(compObj.getPos(), fPos, Exercise.quickAnim?1:MOVETIME);
		Trans t = new Trans(this.compObj, p, Trans.MOVE);
		Jedas.getScheduler().add(t);
				
		if (isRoot() && line.isVisible()) {		// move line along
			//System.out.println("Arrow "+key+" visible: "+line.isVisible());
			DPair[] geometry = {getCenterPos(),
					new DPair(getCenterPos().get(0),
						  fPos.get(1)-0.05-0.01*getRank()),
					line.getGeometry()[2],
					line.getGeometry()[3]};
			Path[] pl = new Path[4];
			for (int i=0; i<4; i++) {
				pl[i] = new Path();
				pl[i].createDistance(line.getGeometry()[i],
					 geometry[i],
					Exercise.quickAnim?1:MOVETIME);
			}
			Trans tl = new Trans(line, pl, Trans.GEOMETRY);
			Jedas.getScheduler().add(tl);
		}
	}

	/**
	 * Moves this node and all its right neighbors to the left.
	 *
	 * @param dist the distance to move
	 */
	private void pullLeft(int dist) {
		//System.out.println("Pull " + key + " by " + dist); 		// debug
		fPos = new DPair(compObj.getPos().get(0) - dist * DISTANCE,
			compObj.getPos().get(1));
		Path p = new Path();
		p.createDistance(compObj.getPos(), fPos, Exercise.quickAnim?1:MOVETIME);
		Trans t = new Trans(this.compObj, p, Trans.MOVE);
		Jedas.getScheduler().add(t);
		
		// for array
		if (isRoot() && line.isVisible()) { 	// move line along
			//System.out.println("Arrow "+key+" visible: "+line.isVisible());
			DPair[] geometry = {getCenterPos(),
					new DPair(getCenterPos().get(0),
						  fPos.get(1)-0.05-0.01*getRank()),
						line.getGeometry()[2],
						line.getGeometry()[3]};
			Path[] pl = new Path[4];
			for (int i=0; i<4; i++) {
				pl[i] = new Path();
				pl[i].createDistance(line.getGeometry()[i],
					 geometry[i],
					Exercise.quickAnim?1:MOVETIME);
			}
			Trans tl = new Trans(line, pl, Trans.GEOMETRY);
			Jedas.getScheduler().add(tl);
		}
	}

	/**
	 * Lifts up a node to be removed from the rootlist
	 */
	private void liftUp() {
		// System.out.println(key + " -- up we go..."); 			// debug
		fPos = new DPair(compObj.getPos().get(0),
			compObj.getPos().get(1) - DISTANCE);
		if(Exercise.quickAnim) {
			this.compObj.setPos(fPos);	// Problem
			return;
		}
		Path p = new Path();
		p.createDistance(compObj.getPos(), fPos, Exercise.quickAnim?1:MOVETIME);
		Trans t = new Trans(this.compObj, p, Trans.MOVE);
		Jedas.getScheduler().add(t);
	}

	/**
	 * @param dist the distance
	 * @return a transition for the line to be moved along with this node.
	 */
	/*
	private Trans lineTrans(int dist) {
		Path p = new Path();
		p.createDistance(line.getPos(),
				new DPair(line.getPos().get(0)+dist*DISTANCE,
					   line.getPos().get(1)),
						Exercise.quickAnim?1:MOVETIME);
		return new Trans(line, p, Trans.MOVE);
	}*/

	/*
	 * Moves the specified node to the right side of this one
	 *
	 * @param node the node to be moved
	 */
	private void moveHere(FibNode node) {
		if (compObj.getParent() != node.compObj.getParent()) {
			transPos(node);
		} else {
			//System.out.println("No transposing"); 			// debug
		}
		//System.out.println("Moving " + node.key + " to " + key); 		// debug
		node.fPos = new DPair(fPos.get(0) + DISTANCE*getTreeWidth(),
				  			fPos.get(1));

		Path p = new Path();

		// System.out.println(node.getPos().get(0) + " -> " + node.fPos.get(0));
		if (Math.abs(node.compObj.getPos().get(0) - node.fPos.get(0)) < DPair.epsilon) {
			orientation = Path.STRAIGHT;
		} else if (node.compObj.getPos().get(0) < node.fPos.get(0)) {
			orientation = Path.STRAIGHT; //COUNTERCLOCKWISE;
		} else {
			orientation = Path.STRAIGHT; //CLOCKWISE;
		}
		amplitude = 0.3;
		/*if(quickAnim) {
			node.setPos(node.fPos);	// Problem
			return;
		}*/
		p.createMotion(node.compObj.getPos(), node.fPos, orientation,
				amplitude, Exercise.quickAnim?1:MOVETIME);
		Trans t = new Trans(node.compObj, p, Trans.MOVE);
		Jedas.getScheduler().add(t);
	}

	/**
	 * @return <tt>true</tt> iff this node is the leftmost one in its list
	 */
	boolean isLeftmost() {
		return (this.compObj.getPos().get(0) <= left.compObj.getPos().get(0));
	}

	/**
	 * Transfers the specified node to the parent of this node.
	 * Transposes coordinates accordingly.
	 *
	 * @param node the node to be transferred
	 */
	private void transPos(FibNode node) {
		// System.out.println("Transpose " + node.key); 			// debug
		node.fPos = (DPair)node.compObj.getPos().clone();
		CompObj commonParent = (CompObj)node.compObj.getParent();
		while (commonParent != compObj.getParent() && commonParent.getParent() != null) {
			node.fPos.set(0,node.fPos.get(0) + commonParent.getPos().get(0));
			node.fPos.set(1,node.fPos.get(1) + commonParent.getPos().get(1));
			commonParent = (CompObj)commonParent.getParent();
		}
		if (commonParent != compObj.getParent()) {
			System.out.println("Error occurred while transposing.");
			System.exit(0);
		}
		commonParent.transferItem(node.compObj);
		/*
		 commonParent.transferItem(node.line);
		 node.line.setPos(pos);
		*/
		node.compObj.setPos(node.fPos);
	}

	/**
	 * Returns the absolute position of this node in the FibHeap object.
	 *
	 * @return absolute position
	 */
	public DPair getAbsPos(CompObj mainco) {
		//System.out.println("FibNode.getAbsPos(): "+key);
		DPair abspos = getRootPos();
		CompObj parent = (CompObj)compObj.getParent();
		while (!(parent == mainco)) {
			//System.out.println("abspos = "+abspos);
			//System.out.println("this.getKey() = "+this.getKey());
			//System.out.println("parent = "+parent);
			abspos.set(0, abspos.get(0) + parent.getPos().get(0));
			abspos.set(1, abspos.get(1) + parent.getPos().get(1));
			parent = (CompObj)parent.getParent();
		}
		return abspos;
	}

	/**
	 * Transfers (and transposes the coordinates of) this node's
	 * children to this node's parent.
	 */
	private void transferChildren() {
		if (hasChildren()) {
			// System.out.println("Transferring children");
			FibNode temp = child;
			do {
				transPos(temp);
				temp.line.hide();   				// before??
				temp = temp.right;
			} while (temp != child);
		}
	}

	/**
	 * Centers this node relative to its children
	 */
	private void centerNode() {
		// System.out.println("Centering " + key); 				// debug
		if (rank > 0) {
			//System.out.println(rank + " children"); 			// debug
			FibNode temp = getChildlist()[rank/2];
			DPair centerPos = (DPair)nodeObj.compObj.getPos().clone();
			double p1 = temp.getCenterPos().get(0);
			if (rank%2 == 0) {
				p1 = (p1 + temp.left.getCenterPos().get(0))/2;
			}
			centerPos.set(0,p1);
			/*if(quickAnim) {
				nodeObj.setPos(centerPos);	// Problem
			}
			else {*/
				Path p = new Path();
				p.createDistance(nodeObj.compObj.getPos(), centerPos, Exercise.quickAnim?1:MOVETIME);
				Trans t = new Trans(nodeObj.compObj, p, Trans.MOVE);
				Jedas.getScheduler().add(t);
			//}
			temp = child;
			do {
				temp.adjustLine(centerPos);
				temp = temp.right;
			} while (temp != child);
		} else {
			// Spezialfall
			if (Math.abs(nodeObj.compObj.getPos().get(0))>DPair.epsilon) {
				/*if(quickAnim) {
					nodeObj.setPos(new DPair(0,0));	// Problem
				}
				else {*/
					Path p = new Path();
					p.createDistance(nodeObj.compObj.getPos(), new DPair(0,0), Exercise.quickAnim?1:MOVETIME);
					Trans t = new Trans(nodeObj.compObj, p, Trans.MOVE);
					Jedas.getScheduler().add(t);
				//}
			}
		}
		if (!isRoot()) {
			parent.centerNode();
		}
	}

	/**
	 * Aligns this node relative to its children.
	 * Alignment can be CENTER (default), LEFT, or RIGHT.
	 *
	 * not working yet!!!
	 */
	private void alignNode() {
		//System.out.println("Aligning " + key);				// debug

		if (align == CENTER) {
			if (rank > 0) {
				//System.out.println(rank + " children"); 			// debug
				FibNode temp = getChildlist()[rank/2];
				DPair centerPos = (DPair)nodeObj.compObj.getPos().clone();
				double p1 = temp.getCenterPos().get(0);
				if (rank%2 == 0) {   // even number of children
					p1 = (p1 + temp.left.getCenterPos().get(0))/2;
				}
				centerPos.set(0,p1);
				/*if(quickAnim) {
					nodeObj.setPos(centerPos);	// Problem
				}
				else {*/
					Path p = new Path();
					p.createDistance(nodeObj.compObj.getPos(), centerPos, Exercise.quickAnim?1:MOVETIME);
					Trans t = new Trans(nodeObj.compObj, p, Trans.MOVE);
					Jedas.getScheduler().add(t);
				//}
				temp = child;
				do {
					temp.adjustLine(centerPos);
					temp = temp.right;
				} while (temp != child);
			} else {
				// Spezialfall
				if (Math.abs(nodeObj.compObj.getPos().get(0))>DPair.epsilon) {
					/*if(quickAnim) {
						nodeObj.setPos(new DPair(0,0));	// Problem
					}
					else {*/
						Path p = new Path();
						p.createDistance(nodeObj.compObj.getPos(), new DPair(0,0), Exercise.quickAnim?1:MOVETIME);
						Trans t = new Trans(nodeObj.compObj, p, Trans.MOVE);
						Jedas.getScheduler().add(t);
					//}
				}
			}
			if (!isRoot()) {
				parent.alignNode();
			}
		}
		else {	// align == LEFT

		}
	}

	/**
	 * Adjusts the line of this node when parent is centered.
	 *
	 * @param pos the position
	 */
	private void adjustLine(DPair pos) {
		geometry[0] = getCenterPos();
		geometry[1] = pos;
		Path[] p = new Path[2];
		p[0] = new Path();
		p[1] = new Path();
		int orientation;
		if (Math.abs(line.getGeometry()[0].get(0)-geometry[1].get(0))<DPair.epsilon) {
			orientation = Path.STRAIGHT;
		} else if (line.getGeometry()[0].get(0) < geometry[1].get(0)) {
			orientation = Path.STRAIGHT; //COUNTERCLOCKWISE;
		} else {
			orientation = Path.STRAIGHT; //CLOCKWISE;
		}
		/*if(quickAnim) {
			line.setGeometry(geometry);
		}
		else {*/
			p[0].createDistance(line.getGeometry()[0], geometry[0], Exercise.quickAnim?1:MOVETIME);
			p[1].createMotion(line.getGeometry()[1], geometry[1],
					  orientation, amplitude, Exercise.quickAnim?1:MOVETIME);
			Trans t = new Trans(line, p, Trans.GEOMETRY);
			Jedas.getScheduler().add(t);
		//}
	}

	/**
	 * @return the centered position of this node's nodeObj relative to its parent
	 */
	private DPair getCenterPos() {
		DPair centerPos = (DPair)fPos.clone();
		if (rank > 0) {
			//System.out.println(getChildlist().length + " children"); 	// debug
			FibNode temp = getChildlist()[rank/2];
			//System.out.println(centerPos.get(0)+", "+centerPos.get(1)); 	// debug
			double p1 = temp.getCenterPos().get(0);
			if (rank % 2 == 0) {
				// System.out.println("Even number of children.");	   // debug
				p1 = (p1 + temp.left.getCenterPos().get(0)) / 2;
			}
			centerPos.set(0,centerPos.get(0) + p1);
		}
		return centerPos;
	}

	/**
	 * Adjusts coordinates of the specified item in relation to this node.
	 *
	 * @param item the item
	 * @return the new coordinates
	 */
	private DPair adjustCoord(Item item) {
		CompObj par;
		boolean found = false;
		double x = item.getPos().get(0);
		double y = item.getPos().get(1);
		if (item.getParent() != null) {
			par = (CompObj)item.getParent();
		} else {
			System.out.println("Error -- item has no parent!");
			par = this.compObj;
			System.exit(0);
		}
		while (par.getParent() != null) {
			if (par != compObj) {
				par = (CompObj)par.getParent();
				x = x + par.getPos().get(0);
				y = y + par.getPos().get(1);
			} else {
				found = true;
			}
		}
		if (!found) {
			par = (CompObj)compObj.getParent();
			double myX = fPos.get(0);
			double myY = fPos.get(1);
			while (par.getParent() != null) {
				par = (CompObj)par.getParent();
				myX = myX + par.getPos().get(0);
				myY = myY + par.getPos().get(1);
			}
			x = x - myX;
			y = y - myY;
		}
		return new DPair(x,y);
	}

	/**
	 * @param other the node to compare
	 * @return <tt>TRUE</tt> iff this node is further left than other
	 */
	public boolean isLeftOf(FibNode other) {
		return (compObj.getPos().get(0) < other.compObj.getPos().get(0));
	}

	/**
	 * This node will be flashing a certain number of times.
	 * Used to set the focus of attention to this node.
	 *
	 * @param times the number of flashes.
	 */
	private void flash(int times) {
		DTriple currentColor = getUnmarkColor();

		if (isMarked())
			currentColor = markColor;

		if(Exercise.quickAnim) {
			this.nodeObj.oval.setFillColor(currentColor.getColor());
			return;
		}

		Path p = new Path();
		for (int i=0; i<times; i++) {
			p.createDistance(currentColor, flashColor, Exercise.quickAnim?1:FLASHTIME);
			p.createDistance(flashColor, currentColor, Exercise.quickAnim?1:FLASHTIME);
		}
		Trans t = new Trans(this.nodeObj.oval, p, Trans.FILLCOLORCHANGE);
		Jedas.getScheduler().add(t);
	}

	/*
	 * Provides a color (brightness) corresponding to the key value.
	 *
	 * @return DTriple representing the color.
	 */
	private DTriple getUnmarkColor() {
		if (!keycolor)
			return new DTriple(1,1,1);
		else
			return new DTriple(0.5+(100.0-key)/200.0, 0.5+(100.0-key)/200.0, 1);
	}

	// =======================================================================================
	/*
		Ab hier von
		Markus Krebs
		programmiert
	*/

	private FibHeap fibHeap;
	protected void setFibHeap(FibHeap fibHeap) {
		this.fibHeap = fibHeap;
	}

	/*
		Methoden zum Kopieren des kompletten Fibonacci-Nodes
		08.11.2003 17:24:36

	*/

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

	// Kompletten FibNode kopieren
	public Object copy() {
		FibNode newFibNode = new FibNode(getKey());
		// ToDo: Zeiger (muss in FHeap gesetzt werden, oder nach hier übergeben)
		newFibNode.setParameters(getKey(), getRank(), isMarked(), null, null, null, null);

		newFibNode.compObj.show();	// sichtbarmachen
		// ======== Nachfolgendes für Animation ==========
		// ToDo: Anpassen von FibNodeObj
		// -> schöner: clone()-Routine in FibNodeObj
		// Problem: Anderer Konstruktor für FibNode notwendig!
		newFibNode.compObj.setPos(compObj.getPos());
		newFibNode.compObj.setSize(compObj.getSize());

		// PROBLEMATISCH
		//FibNodeObj newNodeObj = (FibNodeObj)newFibNode.getNodeItem();
		FibNodeObj newNodeObj = (FibNodeObj)newFibNode.nodeObj;

		newNodeObj.compObj.setPos(nodeObj.compObj.getPos());
		newNodeObj.compObj.setSize(nodeObj.compObj.getSize());
		newNodeObj.compObj.setColor(nodeObj.centerLabel.getColor());
		newNodeObj.oval.setPos(nodeObj.oval.getPos());
		newNodeObj.oval.setSize(nodeObj.oval.getSize());
		newNodeObj.oval.setFillColor(nodeObj.getFillColor());
		newNodeObj.leftLabel.setPos(nodeObj.leftLabel.getPos());
		newNodeObj.rightLabel.setPos(nodeObj.rightLabel.getPos());
		newNodeObj.centerLabel.setPos(nodeObj.centerLabel.getPos());
		// ToDo: Änderungen an line
		newFibNode.line.setVisible(line.isVisible());
		newFibNode.line.setGeometry(line.getGeometry());
		//newFibNode.setProperties(line.getProperties());
		/*DPair[] newGeometry = new DPair[line.getGeometry().length];
		for(int i=0; i<line.getGeometry().length; i++)
			newGeometry[i] = (DPair)line.getGeometry()[i].clone();
		newFibNode.line.setGeometry(newGeometry);*/			
		newFibNode.line.setPos(line.getPos());
		newFibNode.line.setSize(line.getSize());
		// Rest
		newFibNode.fPos = (DPair)fPos.clone();
		// ToDo: Schleife anstatt bis auf 2, generalisieren (auf richtige Länge)
		for(int i=0; i<2; i++) {
			if(geometry[i]!=null) newFibNode.geometry[i]=(DPair)geometry[i].clone();
			else newFibNode.geometry[i]=null;
		}
		// Rest
		newFibNode.orientation = orientation;
		newFibNode.highlighted = highlighted;
		// ===============================================
		return newFibNode;
	}
}
