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

import mauda.operation.*;
import java.util.*;

/**
 * A fast-class for operations of FibHeaps
 * 
 * @author Markus Krebs
 */
public class FibHeapDS {

	FibNodeDS min;
	int size, potential, count;

	public static SubOperationQueue subOperations = new SubOperationQueue();	// MKrebs

	/**
	 * Creates a new, empty FibHeap.
	 */
	public FibHeapDS() {
		min = null;
		size = potential = 0;
	}

	/**
	 * Creates a new <tt>FibHeap</tt> consisting of one new <tt>FibNode</tt>.
	 */
	protected FibHeapDS(int k) {
		min = new FibNodeDS(k);
		size = potential = 1;
	}

	/**
	 * Creates a new <tt>FibHeap</tt> from an existing <tt>FibNode</tt>.
	 */
	private FibHeapDS(FibNodeDS existing) {
		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 (FibHeapDS other) {
		if (!this.isEmpty() && !other.isEmpty()) {
			this.min.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

	}

	/**
	 * 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 FibNodeDS insert(int k) {
		resetCount();
		FibHeapDS q = new FibHeapDS(k);

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

		//System.out.println("Insert " + q.min.getKey()); // debug
		meld(q);
		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() {
		if (isEmpty()) {
			return 999;   	// greatest possible integer
		} else {
			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() {
		// Falls der Minimum-Zeiger beim DELETE_MIN auf einen
		// inneren Knoten zeigt
		if(!isEmpty() && !min.isRoot()) {
			resetCount();
			int m = min.getKey();
			FibNodeDS 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()) {
			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
	 */
	void remove(FibNodeDS node) {
		size--;
		potential--;					// node deleted from rootlist
		if (node == min) {
			FibNodeDS 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();
	}

	/**
	 * Consolidates the rootlist.
	 * Uses an array in which the root nodes
	 * are entered according to their rank.
	 */
	protected void consolidate() {
		int length = maxRank()+1;
		FibNodeDS A[] = new FibNodeDS[length];				// initialize array
		count += length;				// additional cost

		FibNodeDS B = min;
		//System.out.println(min==null?"MIN is NULL!!!":"MIN is OK");
		FibNodeDS last = min.getLeftSibling();
		FibNodeDS next;
		while (B != last) {
			next = B.getRightSibling();
			enter(B,A);
			B = next;
			if (B.getKey() < accessmin()) {
				updateMin(B);
			}
		}
		enter(B,A);
	}

	/**
	 * 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(FibNodeDS B, FibNodeDS A[]) {
		// B.parent = null;					// parent pointer might still be set
		// B.unmark();	 				// node might still be marked

		if (A[B.getRank()] == null) {
			A[B.getRank()] = B;
		} else {
			int index = B.getRank();
			B = link(B,A[B.getRank()]);
			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 FibNodeDS link(FibNodeDS B, FibNodeDS C) {
		if (C.getKey() < B.getKey()) {					// swap B and C
			FibNodeDS temp = C;
			C = B;
			B = temp;
		}
		// SubOperation LINK
		add(new SubOperation("LINK", B.getKey(), C.getKey())); 
		if(C.isMarked()) { 	// MKrebs
			// SubOperation UNMARK
			add(new SubOperation("UNMARK", C.getKey())); 
		}
		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(FibNodeDS N, int k) {
		resetCount();
		if (k < N.getKey() && k > 0) {
			// System.out.println("Decrease "+N.getKey()+" to "+k); // debug
			// SubOperation SETKEY
			add(new SubOperation("SETKEY", N.getKey(), k));
			N.setKey(k);
		}
		FibNodeDS temp = N;
		if ((N.isRoot()) || (k >= N.getParentNode().getKey())) {
			count++;					// cost = 1
		} else {
			do {
				FibNodeDS parent = N.getParentNode();

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

				// SubOperation CUT
				add(new SubOperation("CUT", N.getKey()));
				N.cut(min);

				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(!N.isMarked()) { 	// MKrebs
					// SubOperation MARK
					add(new SubOperation("MARK", N.getKey()));
				}
				N.mark();
				potential += 2; 		// non-root node marked
			}
		}

		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(FibNodeDS node) {
		resetCount();
		if (node == min)
			return deletemin();
		else {
			if (!node.isRoot()) {
				FibNodeDS temp = node;
				do {
					FibNodeDS parent = temp.getParentNode();
					// SubOperation CUT
					add(new SubOperation("CUT", temp.getKey()));
					temp.cut(min);

					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(!temp.isMarked()) { 	// MKrebs
						// SubOperation MARK
						add(new SubOperation("MARK", temp.getKey()));
					}
					temp.mark();
				}
			} else {
				count++;				// cost = 1 if no cuts
			}
			remove(node);
			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;
	}

	/**
	 * 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(FibNodeDS newMinNode) {
		min = newMinNode;
	}

	// =======================================================================================
	/*
		Ab hier von
		Markus Krebs
		programmiert
	*/
	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
	*/
	public IdentityHashMap fibNodes;

	// Kompletten FibHeap kopieren
	public Object clone() {
		fibNodes = new IdentityHashMap();
		exploreNode(min);				// Alle Knoten ausfindig machen => fibNodes
		FibNodeDS newMin = copyNode(min);	// Alle Knoten duplizieren
		FibHeapDS fibHeapCopy = new FibHeapDS();
		if(this instanceof FibHeapDSExt) fibHeapCopy = new FibHeapDSExt();
		fibHeapCopy.min = newMin;
		fibHeapCopy.size = size;
		fibHeapCopy.potential = potential;
		fibHeapCopy.count = count;
		return fibHeapCopy;
	}

	// Ermitteln der vorkommenden Knoten
	private void exploreNode(FibNodeDS 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 Hashtable)
	// Rückgabe: Kopie des Original-Knotens (VALUE aus Hashtable)
	private FibNodeDS copyNode(FibNodeDS fibNode) {
		if(fibNode==null) return null;
		FibNodeDS n = (FibNodeDS)fibNodes.get(fibNode);
		if(n==null) {
			n = (FibNodeDS)fibNode.clone();	// Alles clonen ausser den Zeigern (werden auf NULL gesetzt)
			fibNodes.put(fibNode, n);		// Jetzt Abbildung machen
			n.left = copyNode(fibNode.left);
			n.right = copyNode(fibNode.right);
			n.parent = copyNode(fibNode.parent);
			n.child = copyNode(fibNode.child);
		}
		return n;
	}
}
