src/consolidate.js

import {_append as list_insert} from '@data-structure-algebra/circularly-linked-list';
import link from './link.js';

/**
 * CONSOLIDATE: Consolidate the root list of a heap.
 *
 * The next step, in which we reduce the number of trees in the Fibonacci heap,
 * is consolidating the root list of H, which the call CONSOLIDATE(H)
 * accomplishes. Consolidating the root list consists of repeatedly executing
 * the following steps until every root in the root list has a distinct degree
 * value:
 *
 *   1. Find two roots x and y in the root list with the same degree. Without
 *   loss of generality, let x.key <= y.key.
 *
 *   2. Link y to x: remove y from the root list, and make y a child of x by
 *   calling the FIB-HEAP-LINK procedure. This procedure increments the
 *   attribute x:degree and clears the mark on y.
 *
 * The procedure CONSOLIDATE uses an auxiliary array A[0..D(H.n)] to
 * keep track of roots according to their degrees. If A[i] = y, then y is
 * currently a root with y.degree = i. Of course, in order to allocate the
 * array we have to know how to calculate the upper bound D(H.n) on the maximum
 * degree, but we will see how to do so in Section 19.4.
 *
 * @param compare Comparison function.
 * @param l Root list.
 */
export default function consolidate(compare, l) {
	const A = [];

	let next = l;

	do {
		let x = next;
		next = x.next;
		let d = x.degree;

		let n = d - A.length;
		if (n >= 0) {
			while (n-- > 0) A.push(null);
			A.push(x);
		} else {
			while (A[d] !== null) {
				let y = A[d]; // Another node with the same degree as x
				if (compare(y.value, x.value) < 0) {
					// CANNOT EXCHANGE VALUES BECAUSE THAT WOULD INVALIDATE
					// EXISTING POINTERS
					y = x;
					x = A[d];
				}

				link(y, x);
				A[d] = null; // Put before link if using x.degree ?
				++d;
				if (d === A.length) {
					A.push(null);
					break;
				}
			}

			A[d] = x;
		}
	} while (next !== l);

	let min = null;

	for (const x of A) {
		if (x === null) continue;
		if (min === null) {
			// Create a root list for H containing just A[i]
			x.next = x;
			x.prev = x;
			min = x;
		} else {
			// Insert A[i] into H's root list
			list_insert(min, x);
			// Update minimum if necessary
			if (compare(x.value, min.value) < 0) min = x;
		}
	}

	return min;
}