src/FibonacciHeap.js

import {
	_append as list_insert,
	_remove as list_remove,
	_concat as list_concatenate,
} from '@data-structure-algebra/circularly-linked-list';
import Node from './Node.js';

import list_reset_parent from './list_reset_parent.js';

import consolidate from './consolidate.js';
import cut from './cut.js';
import cascading_cut from './cascading_cut.js';

/**
 * See CLRS09 Chapter 19 on the Fibonacci Heap.
 */
export default class FibonacciHeap {
	/**
	 * Make-heap: creates a new empty heap.
	 *
	 * To make an empty Fibonacci heap, the MAKE-FIB-HEAP procedure
	 * allocates and returns the Fibonacci heap object H, where H.n = 0 and
	 * H.min = NIL ; there are no trees in H. Because t(H) = 0 and m(H) = 0,
	 * the potential of the empty Fibonacci heap is pot(H) = 0. The amortized
	 * cost of MAKE-FIB-HEAP is thus equal to its O(1) actual cost.
	 */
	constructor(compare) {
		this.compare = compare; // Comparison function
		/**
		 * We access a given Fibonacci heap H by a pointer H.min to the root of
		 * a tree containing the minimum key; we call this node the minimum
		 * node of the Fibonacci heap. If more than one root has a key with the
		 * minimum value, then any such root may serve as the minimum node.
		 * When a Fibonacci heap H is empty, H.min is NIL.
		 */
		this.min = null;
	}

	/**
	 * Find-min: simply return the top element of the heap.
	 */
	head() {
		if (this.min === null) return undefined;
		return this.min.value;
	}

	/**
	 * Minimum: return a pointer to the element whose key is minimum
	 *
	 * The minimum node of a Fibonacci heap H is given by the pointer H.min, so
	 * we can find the minimum node in O(1) actual time. Because the potential
	 * of H does not change, the amortized cost of this operation is equal to
	 * its O(1) actual cost.
	 */
	headreference() {
		return this.min;
	}

	/**
	 */
	pop() {
		const min = this.popreference();
		return min === null ? undefined : min.value;
	}

	/**
	 * FIB-HEAP-EXTRACT-MIN(H):
	 *
	 * Extracting the minimum node
	 *
	 * The process of extracting the minimum node is the most complicated of
	 * the operations presented in this section. It is also where the delayed
	 * work of consolidating trees in the root list finally occurs. The
	 * following pseudocode extracts the minimum node. The code assumes for
	 * convenience that when a node is removed from a linked list, pointers
	 * remaining in the list are updated, but pointers in the extracted node
	 * are left unchanged. It also calls the auxiliary procedure CONSOLIDATE,
	 * which we shall see shortly.
	 */
	popreference() {
		const z = this.min;
		if (z === null) return null;
		if (z.children !== null) {
			list_reset_parent(z.children);
			list_concatenate(z, z.children);
		}

		if (z === z.next) this.min = null;
		else {
			list_remove(z);
			this.min = consolidate(this.compare, z.next);
		}

		z.next = z; // (Re)move this?
		z.prev = z;
		z.children = null;
		z.degree = 0;
		z.mark = false;
		return z;
	}

	/**
	 * Create a new node for the inserted element and put it into the heap.
	 */
	push(value) {
		const node = new Node(value);
		return this.pushreference(node);
	}

	/**
	 * Insert: insert new node.
	 * /!\ ref.next = ref.prev = ref which means all references that are
	 * external to the tree must reset .next and .prev and one must not call
	 * FibonacciHeap#pushreference with an internal reference from this tree or
	 * another, except the root of another tree.
	 *
	 * Change in potential is 1. Therefore amortized cost is O(1).
	 */
	pushreference(ref) {
		if (this.min === null) {
			// Create a root list for H containing just x (by precondition)
			this.min = ref;
		} else {
			// This.min != null != ref
			// Insert x into H's root list
			list_insert(this.min, ref);
			// Update minimum
			if (this.compare(ref.value, this.min.value) < 0) {
				this.min = ref;
			}
		}

		return ref;
	}

	/**
	 * Union: Uniting two Fibonacci heaps
	 *
	 * The following procedure unites Fibonacci heaps H_1 and H_2, destroying
	 * H_1 and H_2 in the process. It simply concatenates the root lists of H_1
	 * and H_2 and then determines the new minimum node. Afterward, the objects
	 * representing H_1 and H_2 will never be used again.
	 *
	 * /!\ Assumes the same comparison function is used in both trees.
	 *
	 * Change in potential is zero. Amortized cost is O(1), the actual cost.
	 */
	meld(other) {
		const ref = other.min;
		if (ref === null) return;
		if (this.min === null) this.min = ref;
		else {
			// This.min != null != ref
			// Concatenate the root list of H_2 with the root list of H
			list_concatenate(this.min, ref);
			// Update minimum
			if (this.compare(ref.value, this.min.value) < 0) {
				this.min = ref;
			}
		}
	}

	/**
	 * Synonym for FibonacciHeap#meld.
	 * TODO Remove this.
	 */
	merge(other) {
		this.meld(other);
	}

	/**
	 * @param {Node} ref Non-null internal node object.
	 * @param {Object} value The new value for ref.
	 */
	update(ref, value) {
		const d = this.compare(value, ref.value);

		if (d < 0) this.decreasekey(ref, value);
		else if (d > 0) this.increasekey(ref, value);
		else ref.value = value;
	}

	/**
	 * FIB-HEAP-DECREASE-kEY:
	 * @param {Node} ref Non-null internal node object.
	 * @param {Object} value The new value for ref.
	 */
	decreasekey(ref, value) {
		ref.value = value;
		if (ref !== this.min) {
			// This.min != null, ref != null
			const y = ref.parent;
			if (y !== null && this.compare(ref.value, y.value) < 0) {
				cut(ref, y);
				list_insert(this.min, ref);
				for (const x of cascading_cut(y)) list_insert(this.min, x);
			}

			if (this.compare(ref.value, this.min.value) < 0) {
				this.min = ref;
			}
		}
	}

	/**
	 * Increase-key: remove the item at the key to be increased, replace
	 * the key with a larger key, then push the result back into the heap.
	 *
	 * @param {Node} ref Non-null internal node object.
	 * @param {Object} value The new value for ref.
	 *
	 */
	increasekey(ref, value) {
		this.delete(ref);

		ref.value = value;

		this.pushreference(ref);
	}

	/**
	 * Delete
	 * ref must be internal
	 * ref.prev and ref.next get reset to null
	 */
	delete(ref) {
		if (ref !== this.min) {
			// This.min != null, ref != null
			const y = ref.parent;
			if (y !== null) {
				cut(ref, y);
				list_insert(this.min, ref);
				for (const x of cascading_cut(y)) list_insert(this.min, x);
			}

			this.min = ref;
		}

		this.popreference();
	}
}