/*!
 * Copyright (c) Microsoft Corporation and contributors. All rights reserved.
 * Licensed under the MIT License.
 */

import { strict as assert } from "node:assert";

import { type IGCResult, runGarbageCollection } from "../../gc/index.js";

interface IGCNode {
	id: string;
	outboundRoutes: string[];
}

describe("Garbage Collector", () => {
	function runGCAndValidateResults(
		gcNodes: IGCNode[],
		startingIds: string[],
		deletedNodes: IGCNode[],
	) {
		const referenceGraph: { [id: string]: string[] } = {};
		for (const node of gcNodes) {
			referenceGraph[node.id] = node.outboundRoutes;
		}

		// Referenced nodes are all nodes in the gcNodes that are not in deletedNodes.
		const referencedNodes = gcNodes.filter((node) => !deletedNodes.includes(node));
		const referencedNodeIds = Array.from(referencedNodes, (node: IGCNode) => node.id);
		const deletedNodeIds = Array.from(deletedNodes, (node: IGCNode) => node.id);

		const gcResult: IGCResult = runGarbageCollection(referenceGraph, startingIds);
		assert.deepStrictEqual(
			gcResult.referencedNodeIds.sort(),
			referencedNodeIds.sort(),
			"Referenced nodes generated by GC are incorrect",
		);
		assert.deepStrictEqual(
			gcResult.deletedNodeIds.sort(),
			deletedNodeIds.sort(),
			"Deleted nodes generated by GC are incorrect",
		);
	}

	it("should not collect nodes when all nodes are referenced", () => {
		const gcNode1: IGCNode = { id: "/", outboundRoutes: ["/ds1"] };
		const gcNode2: IGCNode = { id: "/ds1", outboundRoutes: ["/ds1/dds1"] };
		const gcNode3: IGCNode = { id: "/ds2", outboundRoutes: [] };
		const gcNode4: IGCNode = { id: "/ds1/dds1", outboundRoutes: ["/ds2"] };

		const gcNodes = [gcNode1, gcNode2, gcNode3, gcNode4];
		const deletedNodes = [];

		runGCAndValidateResults(gcNodes, ["/"], deletedNodes);
	});

	it("should collect nodes that are not referenced", () => {
		const gcNode1: IGCNode = { id: "/", outboundRoutes: ["/ds1"] };
		const gcNode2: IGCNode = { id: "/ds1", outboundRoutes: ["/ds1/dds1"] };
		const gcNode3: IGCNode = { id: "/ds1/dds1", outboundRoutes: [] };
		// The following nodes are not referenced by any of the nodes above.
		const gcNode4: IGCNode = { id: "/ds2", outboundRoutes: ["/ds2/dds1"] };
		const gcNode5: IGCNode = { id: "/ds2/dds1", outboundRoutes: [] };

		const gcNodes = [gcNode1, gcNode2, gcNode3, gcNode4, gcNode5];
		const deletedNodes = [gcNode4, gcNode5];

		runGCAndValidateResults(gcNodes, ["/"], deletedNodes);
	});

	it("should collect nodes with cycles in the graph", () => {
		const gcNode1: IGCNode = { id: "/", outboundRoutes: ["/ds1"] };
		const gcNode2: IGCNode = { id: "/ds1", outboundRoutes: ["/ds1/dds1"] };
		const gcNode3: IGCNode = { id: "/ds2", outboundRoutes: ["/ds2/dds1"] };
		const gcNode4: IGCNode = { id: "/ds1/dds1", outboundRoutes: ["/ds2", "/ds1"] };
		const gcNode5: IGCNode = { id: "/ds2/dds1", outboundRoutes: ["/ds1", "/ds2"] };
		// The following node is not referenced by any of the nodes above.
		const gcNode6: IGCNode = { id: "/ds3", outboundRoutes: [] };

		const gcNodes = [gcNode1, gcNode2, gcNode3, gcNode4, gcNode5, gcNode6];
		const deletedNodes = [gcNode6];

		runGCAndValidateResults(gcNodes, ["/"], deletedNodes);
	});

	it("should collect nodes with multiple starting ids", () => {
		const gcNode1: IGCNode = { id: "/", outboundRoutes: ["/ds1"] };
		const gcNode2: IGCNode = { id: "/ds1", outboundRoutes: ["/ds1/dds1"] };
		const gcNode3: IGCNode = { id: "/ds1/dds1", outboundRoutes: [] };
		// The following node is not referenced by any of the nodes above. But its id will be given as starting id to
		// GC, so it will be referenced.
		const gcNode4: IGCNode = { id: "/ds2", outboundRoutes: ["/ds2/dds1"] };
		const gcNode5: IGCNode = { id: "/ds2/dds1", outboundRoutes: [] };
		// The following node is not referenced by any of the nodes above.
		const gcNode6: IGCNode = { id: "/ds3", outboundRoutes: [] };

		const gcNodes = [gcNode1, gcNode2, gcNode3, gcNode4, gcNode5, gcNode6];
		const deletedNodes = [gcNode6];

		runGCAndValidateResults(gcNodes, ["/", "/ds2"], deletedNodes);
	});
});
