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

/**
 * @author Markus Krebs
 *
 * Code
 */
// extends jedas.CompObj wegen Serialisierung bei Speicherung
public class FibNodeDS {
	/**
	 * The logical attributes
	 */
	FibNodeDS left, right, parent, child;
	private int key, rank;
	private boolean mark;

	/**
	 * 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 FibNodeDS (int key) {
		this.key = key;
		left = right = this;
	}

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

	void setParameters(int key, int rank, boolean mark, FibNodeDS parent, FibNodeDS child, FibNodeDS left, FibNodeDS 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 FibNodeDS 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 FibNodeDS 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 FibNodeDS getSibling() {
		if (right == this)
			return null;
		else
			return right;
	}

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

	/**
	 * @return this node's right sibling
	 * (= this node if there is no sibling)
	 */
	public FibNodeDS 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;
	}

	/**
	 * @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;
		}
	}

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

	/**
	 * 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(FibNodeDS newChild) {
		//System.out.println("Adding " + newChild.key + " to " + key); 	// debug
		FibNodeDS moveNode;

		newChild.separate(false);
		newChild.parent = this;

		if (this.hasChildren()) {
			child.left.join(newChild, false);  				// room already made
		}
		else child = newChild;
		rank++;
	}

	/**
	 * Cuts this node off its parent and joins with target
	 *
	 * @param target the node where this one is attached
	 */
	public void cut(FibNodeDS target) {
		if (!isRoot()) {
			boolean isOnlyChild = (parent.rank==1 && getTreeWidth()==1);
			separate(!isOnlyChild);
			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 (!isRoot()) {
			parent.rank--;
			if (!parent.hasChildren()) {
			    parent.child = null;
			} else if (parent.child == this) {
				parent.child = this.right;
			}
	    }
	    left.right = right;
		right.left = left;
		left       = this;
	    right      = this;
	    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(FibNodeDS other, boolean spaceNeeded) {
	    this.right.left  = other.left;
	    other.left.right = this.right;
	    this.right       = other;
		other.left	   = this;
	}

	/**
	 * Deletes this node from the root list.
	 */
	public void delete() {
	    if (isRoot()) {
			if (hasChildren()) {
			    //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;
				}
			} else {
				separate(true);
			}
			child = null;
		}
	}

	/**
	 * @return width of the (sub)tree rooted in this node
	 */
	public int getTreeWidth() {
		int width = 1;
		FibNodeDS 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;
		FibNodeDS 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 FibNodeDS[] getChildlist() {
	    if (!this.hasChildren()) {
			return null;
	    } else {
			FibNodeDS[] childlist = new FibNodeDS[rank];
			FibNodeDS 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;
			FibNodeDS 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()) {
			FibNodeDS 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;
		FibNodeDS temp = this;
		while (!temp.isRoot()) {
			depth++;
			temp = temp.parent;
		}
		return depth;
	}

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

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

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

	*/

	// Kompletten FibHeap kopieren
	public Object clone() {
		FibNodeDS newFibNode = new FibNodeDS(getKey());
		// Zeiger (muss in FHeap gesetzt werden, oder nach hier übergeben)
		newFibNode.setParameters(getKey(), getRank(), isMarked(), null, null, null, null);
		return newFibNode;
	}
}
