// Note: All functions in this module must conform to DocumentGraphHandler's script engine API.
import {
	ProcessType,
	TableType,
	WorkStepType,
} from "qrc:/js/lib/generated/enum";

import {
	assumeGraphAxioms,
} from "./axioms";
import {
	tolerances,
} from "./constants";
import {
	computeSheetConsumption,
	grossTubeConsumptionForVertex,
	lookUpBendRateParams,
	lookUpBendTimeParams,
	nestingTargetBoxForVertex,
	PureBendRateParams,
	PureBendTimeParams,
	tubeForVertex,
} from "./node_utils";
import {
	getSettingOrDefault,
} from "./settings_table";
import {
	computeTubeVolume,
	getSheetsInStock,
	getTable,
	lookUpDensity,
	lookUpSheetId,
} from "./table_utils";
import {
	ArticleUserData,
	createUpdatedGraphUserData,
	getGraphUserDataEntry,
} from "./userdata_config";
import {
	collectNodeUserDataEntries,
	getNodeUserDataEntryOrThrow,
	userDataAccess,
} from "./userdata_utils";
import {
	assert,
	assertDebug,
	bbDimensionX,
	bbDimensionY,
	isArray,
	isEqual,
	isNumber,
	isString,
	lexicographicObjectLess,
	recursiveSubAssemblies,
} from "./utils";

export function collectSubGraphVertices(article: readonly Readonly<Vertex>[]): Vertex[] {
	const lastVertex = article[article.length - 1];
	return [
		...wsi4.graph.reaching(lastVertex),
		lastVertex,
	];
}

/**
 * Computes size of sub graph in terms of its number of vertices.
 *
 * Node multiplicity is *not* taken into account.
 */
export function computeSubGraphSize(article: readonly Readonly<Vertex>[]): number {
	// Note: it is possible for vertices to occur more than once as in general the graph is *not* a tree
	return collectSubGraphVertices(article).length;
}

/**
 * @param article The article
 * @returns true, if article consists of at least one joining vertex
 */
export function isJoiningArticle(article: readonly Readonly<Vertex>[]): boolean {
	return article.some(vertex => wsi4.node.workStepType(vertex) === WorkStepType.joining);
}

/**
 * @param article The article
 * @returns true, if article consists of one sheet node only
 */
export function isSheetArticle(article: readonly Readonly<Vertex>[]): boolean {
	assumeGraphAxioms([ "sheetArticlesConsistOfSheetNodesOnly" ]);
	return article.length === 1 && wsi4.node.workStepType(article[0]) === WorkStepType.sheet;
}

/**
 * @param article The article
 * @returns true, if article consists of one tube node only
 */
export function isTubeArticle(article: readonly Readonly<Vertex>[]): boolean {
	assumeGraphAxioms([ "tubeArticlesConsistOfTubeNodeOnly" ]);
	return article.length === 1 && wsi4.node.workStepType(article[0]) === WorkStepType.tube;
}

/**
 * @param article The article
 * @returns true, if article represents a semimanufactured part
 *
 * For now semimanufactureds are limited to sheet and tube nodes.
 */
export function isSemimanufacturedArticle(article: readonly Readonly<Vertex>[]): boolean {
	return isSheetArticle(article) || isTubeArticle(article);
}

/**
 * @param article The article
 * @returns true, if the article is neither a joining article (see [[isJoiningArticle]]) nor a sheet article (see [[isSheetArticle]])
 */
export function isComponentArticle(article: readonly Readonly<Vertex>[]): boolean {
	return !isSemimanufacturedArticle(article) && !isJoiningArticle(article);
}

export function countComponentArticles(vertices: Vertex[]): number {
	return vertices.map(vertex => wsi4.graph.article(vertex))
		.filter((lhs, index, self) => index === self.findIndex(rhs => isEqual(lhs, rhs)))
		.filter(article => isComponentArticle(article)).length;
}

/**
 * A sheet is considered allowed if
 * - material matches
 * - thickness matches
 * - twoDimRep of all targets could fit on the sheet (separately; *not* wrt fixed rotations)
 * - the sheet is in stock
 */
export function computeAllowedSheets(sheetVertex: Vertex, sheetTable = getTable(TableType.sheet)): Sheet[] {
	if (wsi4.node.workStepType(sheetVertex) !== "sheet") {
		return wsi4.throwError("computeAllowedSheets(): Wrong WorkStepType");
	}

	const thickness = (() => {
		const targets = wsi4.graph.targets(sheetVertex);
		if (targets.length === 0) {
			wsi4.util.error("computeAllowedSheets(): expecting one or more targets");
			return undefined;
		}
		const t = wsi4.node.sheetThickness(targets[0]);
		if (t === undefined) {
			wsi4.util.error("computeAllowedSheets(): sheet thickness not available");
			return undefined;
		}
		return t;
	})();
	if (thickness === undefined) {
		// Errors are written in lambda function
		return [];
	}

	const nestingDistance = getSettingOrDefault("sheetNestingDistance");
	const [
		minDimX,
		minDimY,
	] = wsi4.graph.targets(sheetVertex)
		.reduce((acc: [number, number], vertex) => {
			const twoDimRep = wsi4.node.twoDimRep(vertex);
			assert(twoDimRep !== undefined, "Expecting valid twoDimRep for each sheet target");
			const bbox = wsi4.cam.util.boundingBox2(twoDimRep);
			const dimX = bbDimensionX(bbox);
			const dimY = bbDimensionY(bbox);
			return [
				Math.max(acc[0], nestingDistance + Math.max(dimX, dimY)),
				Math.max(acc[1], nestingDistance + Math.min(dimX, dimY)),
			];
		}, [
			0,
			0,
		]);

	const sheetMaterialId = getAssociatedSheetMaterialId(sheetVertex);
	return getSheetsInStock(sheetTable)
		.filter(row => row.sheetMaterialId === sheetMaterialId
			&& Math.abs(row.thickness - thickness) < tolerances.thickness
			&& minDimX <= row.dimX
			&& minDimY <= row.dimY);
}

/**
 * Get name of project
 */
export function projectName(): string {
	const name = getGraphUserDataEntry("name");
	return name === undefined ? "" : name;
}

/**
 * Generate new name of project
 * If a projectName already exists, this is returned
 * Else if `name` is not empty, return name
 * Else return a default value
 */
function projectNameOrNameOfDefault(name: string) {
	const pn = projectName();
	if (pn === "") {
		if (name === "") {
			return wsi4.util.translate("New_Project");
		}
		return name;
	}
	return pn;
}

/**
 * Set project name to `name` or generate a new one
 * The name is only set if project has no name
 */
export function setProjectNameIfEmpty(name: string|undefined): StringIndexedInterface {
	const newName = projectNameOrNameOfDefault(name === undefined ? "" : name);
	if (newName === "") {
		return wsi4.throwError("Empty name");
	}
	return createUpdatedGraphUserData("name", newName);
}

export function isSubJoining(vertex: Vertex): boolean {
	if (wsi4.node.workStepType(vertex) !== WorkStepType.joining) {
		return false;
	}
	const targets = wsi4.graph.targets(vertex);
	return targets.length === 1 && wsi4.node.workStepType(targets[0]) === WorkStepType.joining;
}

/**
 * Get identifier of associated sheet material
 *
 * @param vertex Vertex of the associated node
 * @returns Identifier of the associated sheet material
 *
 * Note: This function is inteded to be used for nodes where exactly one material can be associated.
 * This is the case for nodes of WorkStepType sheet, sheetCutting, sheetBending and nodes that are
 * part of articles where the article holds at least one node where the node's WorkStepType is one
 * of the previously mentioned WorkStepTypes.
 *
 * Note: This function throws if there is not excatly one associated sheet material.
 */
export function getAssociatedSheetMaterialId(vertex: Vertex): string {
	// Special case for nodes of type sheet to improve performance:
	// Assumption: all target articles of a sheet share the same sheet material.
	if (wsi4.node.workStepType(vertex) === WorkStepType.sheet) {
		const targets = wsi4.graph.targets(vertex);
		assert(targets.length > 0, "Expecting at least one target");
		vertex = targets[0];
	}
	const materials = collectNodeUserDataEntries("sheetMaterial", vertex, userDataAccess.article | userDataAccess.reachable)
		.filter((lhs, index, self) => self.findIndex(rhs => lhs.identifier === rhs.identifier) === index);
	return materials.length === 1 ? materials[0].identifier : wsi4.throwError("Expecting exactly one material. Found materials: " + JSON.stringify(materials));
}

/**
 * Convert an array of vertex-keys to vertices
 *
 * @param vertexKeys Array of vertexKeys
 * @returns Array of vertices
 *
 * Note: Invalid values will be omitted
 */
export function vertexKeysToVertices(vertexKeys: unknown): Vertex[] {
	if (!isArray(vertexKeys, isString)) {
		return [];
	}
	return vertexKeys.map(vertexKey => wsi4.graph.vertices()
		.find(vertex => wsi4.util.toKey(vertex) === vertexKey))
		.filter((vertex: Vertex|undefined): vertex is Vertex => vertex !== undefined);
}

export function nodeIdKeyToVertex(nodeIdKey: unknown): Vertex {
	assert(isNumber(nodeIdKey), "Node id key is expected to be of type number");
	const result = wsi4.graph.vertices()
		.find(vertex => wsi4.util.toKey(wsi4.node.nodeId(vertex)) === nodeIdKey.toString());
	assert(result !== undefined, "No vertex matches node id key " + nodeIdKey.toString());
	return result;
}

export function nodeIdKeysToVertices(nodeIdKeys: unknown): Vertex[] {
	if (isArray(nodeIdKeys, isNumber)) {
		return nodeIdKeys.map(nodeIdKey => wsi4.graph.vertices()
			.find(vertex => wsi4.util.toKey(wsi4.node.nodeId(vertex)) === nodeIdKey.toString()))
			.filter((vertex: Vertex|undefined): vertex is Vertex => vertex !== undefined);
	} else {
		return [];
	}
}

export function rootIdKeyToVertex(rootIdKey: unknown): Vertex {
	assert(isNumber(rootIdKey), "Root id key is expected to be of type number");
	const result = wsi4.graph.vertices()
		.find(vertex => wsi4.util.toKey(wsi4.node.rootId(vertex)) === rootIdKey.toString());
	assert(result !== undefined, "No vertex matches node id key " + rootIdKey.toString());
	return result;
}

export function rootIdKeysToVertices(rootIdKeys: unknown): Vertex[] {
	if (isArray(rootIdKeys, isNumber)) {
		return rootIdKeys.map(rootIdKey => wsi4.graph.vertices()
			.find(vertex => wsi4.util.toKey(wsi4.node.rootId(vertex)) === rootIdKey.toString()))
			.filter((vertex: Vertex|undefined): vertex is Vertex => vertex !== undefined);
	} else {
		return [];
	}
}

/**
 * @returns true if article has exactly one source article that also is a sheet article
 */
export function hasSheetSourceArticle(article: readonly Readonly<Vertex>[]): boolean {
	if (article.length === 0) {
		return false;
	}
	const sources = wsi4.graph.sources(article[0]);
	if (sources.length !== 1) {
		return false;
	}
	return isSheetArticle(wsi4.graph.article(sources[0]));
}

/**
 * @returns true if article has exactly one source article that also is a tube article
 */
export function hasTubeSourceArticle(article: readonly Readonly<Vertex>[]): boolean {
	if (article.length === 0) {
		return false;
	}
	const sources = wsi4.graph.sources(article[0]);
	if (sources.length !== 1) {
		return false;
	}
	return isTubeArticle(wsi4.graph.article(sources[0]));
}

/**
 * Compute volume (aka area) for the first TwoDimRepresentation found in the article
 *
 * Note: This function is *not* intended to be used for sheet nodes.
 */
export function computeArticleTwoDimRepVolume(article: readonly Readonly<Vertex>[]): number|undefined {
	if (isSheetArticle(article)) {
		return undefined;
	}

	const vertex = article.find(v => wsi4.node.twoDimRep(v) !== undefined);
	if (vertex === undefined) {
		return undefined;
	}

	const twoDimRep = wsi4.node.twoDimRep(vertex);
	assert(twoDimRep !== undefined);
	return wsi4.cam.util.twoDimRepVolume(twoDimRep);
}

function joiningArticleMass(article: readonly Vertex[]): number | undefined {
	assertDebug(() => isJoiningArticle(article), "Pre-condition violated");
	const firstVertex = article[0];
	const sources = wsi4.graph.sources(firstVertex);
	return sources.reduce((acc: number|undefined, sourceVertex) => {
		const mass = computeArticleMass(wsi4.graph.article(sourceVertex));
		if (acc === undefined || mass === undefined) {
			return undefined;
		}
		return acc + mass * wsi4.graph.sourceMultiplicity(sourceVertex, firstVertex);
	}, 0);
}

/**
 * Note: A sheetBending component is also considered sheet related in case the underlying
 * sheetCutting node has been turned into a userDefinedBase node.
 */
function isSheetRelatedArticle(article: readonly Vertex[]): boolean {
	return article.some(vertex => {
		const wst = wsi4.node.workStepType(vertex);
		return wst === WorkStepType.sheet || wst === WorkStepType.sheetCutting || wst === WorkStepType.sheetBending;
	});
}

function isTubeRelatedArticle(article: readonly Vertex[]): boolean {
	return article.some(vertex => {
		const wst = wsi4.node.workStepType(vertex);
		return wst === WorkStepType.tube || wst === WorkStepType.tubeCutting;
	});
}

function sheetRelatedArticleMass(article: readonly Vertex[]): number | undefined {
	assertDebug(() => isSheetRelatedArticle(article), "Pre-condition violated");

	const materials = collectNodeUserDataEntries("sheetMaterial", article[0], userDataAccess.article | userDataAccess.reachable)
		.filter((material, index, self) => self.findIndex(mat => mat.identifier === material.identifier) === index);
	assert(materials.length === 1, "Expecting exactly one material");

	// [kg/mm³]
	const density = lookUpDensity(materials[0].identifier);
	if (density === undefined) {
		return undefined;
	}

	const vertex = (() => {
		if (isSheetArticle(article)) {
			return article.find(vertex => wsi4.node.workStepType(vertex) === WorkStepType.sheet);
		} else {
			return article.find(vertex => {
				const wst = wsi4.node.workStepType(vertex);

				// Note: This should work also in case a sheet bending component's sheetCutting
				// node has been turned into a userDefinedBase node
				return wst === WorkStepType.sheetCutting || wst === WorkStepType.sheetBending;
			});
		}
	})();
	assert(vertex !== undefined);

	// [mm³]
	const volume = nodeVolume(vertex);
	if (volume === undefined) {
		return undefined;
	}

	// [kg]
	return volume * density;
}

function tubeRelatedArticleMass(article: readonly Vertex[]): number | undefined {
	assertDebug(() => isTubeRelatedArticle(article), "Pre-condition violated");

	const materials = collectNodeUserDataEntries("tubeMaterial", article[0], userDataAccess.article | userDataAccess.reachable);
	assert(materials.length <= 1, "Expecting at most one material");
	if (materials.length === 0 || materials[0] === undefined) {
		return undefined;
	}

	const material = materials[0];
	assert(material !== undefined);

	const densityRow = getTable(TableType.tubeMaterialDensity)
		.find(row => row.tubeMaterialId === material.identifier);
	if (densityRow === undefined) {
		return undefined;
	}

	// [kg / m³] -> [kg / mm³]
	const density = 0.001 * 0.001 * 0.001 * densityRow.density;

	const vertex = (() => {
		if (isTubeArticle(article)) {
			return article.find(vertex => wsi4.node.workStepType(vertex) === WorkStepType.tube);
		} else {
			return article.find(vertex => wsi4.node.workStepType(vertex) === WorkStepType.tubeCutting);
		}
	})();
	assert(vertex !== undefined);

	// [mm³]
	const volume = nodeVolume(vertex);
	if (volume === undefined) {
		return undefined;
	}

	// [kg]
	return volume * density;
}

export function computeArticleMass(article: readonly Vertex[]): number | undefined {
	if (isJoiningArticle(article)) {
		return joiningArticleMass(article);
	} else if (isSheetRelatedArticle(article)) {
		return sheetRelatedArticleMass(article);
	} else if (isTubeRelatedArticle(article)) {
		return tubeRelatedArticleMass(article);
	} else {
		// E.g. userDefinedBase nodes
		return undefined;
	}
}

// Compute mass of associated node in [kg]
export function computeNodeMass(inputVertex: Vertex): number|undefined {
	assumeGraphAxioms([ "mergeNodesAreJoining" ]);
	// Assumption: Mass is the same for all vertices of an article
	return computeArticleMass(wsi4.graph.article(inputVertex));
}

function tubeVertexVolume(tubeVertex: Vertex): number | undefined {
	assertDebug(() => wsi4.node.workStepType(tubeVertex) === WorkStepType.tube, "Pre-condition violated");

	const tubeCuttingVertex = wsi4.graph.reachable(tubeVertex)
		.find(vertex => wsi4.node.workStepType(vertex) === WorkStepType.tubeCutting);
	assert(tubeCuttingVertex !== undefined, "Expecting valid tube cutting vertex");

	const tube = tubeForVertex(tubeCuttingVertex);
	if (tube === undefined) {
		return undefined;
	}

	const profileGeometry = wsi4.node.tubeProfileGeometry(tubeCuttingVertex);
	if (profileGeometry === undefined) {
		return undefined;
	}

	// [mm³]
	const volumePerTube = computeTubeVolume(tube, profileGeometry);
	if (volumePerTube === undefined) {
		return undefined;
	}

	const consumption = grossTubeConsumptionForVertex(tubeCuttingVertex, tube);
	if (consumption === undefined) {
		return undefined;
	}

	// [mm³]
	return consumption * volumePerTube;
}

/**
 * Compute volume for a node
 *
 * For sheet nodes the volume is based on the sheet consumption based on the underlying nesting
 * For nodes with valid TwoDimRep (besides sheet nodes) the volume is computed from the TwoDimRep directly
 * If none of the above conditions hold the assembly or input assembly is used (if any)
 */
export function nodeVolume(vertex: Vertex): number|undefined {
	const thickness = wsi4.node.sheetThickness(vertex);
	const twoDimRep = wsi4.node.twoDimRep(vertex);
	const wst = wsi4.node.workStepType(vertex);
	if (wst === WorkStepType.sheet) {
		if (twoDimRep === undefined || !isNumber(thickness)) {
			// No nesting available
			return undefined;
		} else {
			const volumePerSheet = (() => {
				const bbox = nestingTargetBoxForVertex(vertex);
				assert(bbox !== undefined, "Expecting valid target box");
				return thickness * bbDimensionX(bbox) * bbDimensionY(bbox);
			})();
			const sheetConsumption = computeSheetConsumption(vertex);
			if (sheetConsumption === undefined) {
				return undefined;
			} else {
				return sheetConsumption * volumePerSheet;
			}
		}
	} else if (wst === WorkStepType.tube) {
		return tubeVertexVolume(vertex);
	} else if (twoDimRep !== undefined && isNumber(thickness)) {
		return thickness * wsi4.cam.util.twoDimRepVolume(twoDimRep);
	} else {
		const assembly = wsi4.node.assembly(vertex);
		if (assembly !== undefined) {
			return wsi4.geo.util.volume(assembly);
		}

		const inputAssembly = wsi4.node.inputAssembly(vertex);
		if (inputAssembly !== undefined) {
			return wsi4.geo.util.volume(inputAssembly);
		}
		return undefined;
	}
}

/**
 * Net consumption for *all* part instances without scrap
 *
 * In combination with grossTubeConsumptionForVertex() the result is
 * complementary w.r.t the scrap.
 */
export function netTubeConsumptionForVertex(vertex: Vertex, tubeInput?: Readonly<Tube>): number | undefined {
	assertDebug(() => wsi4.node.workStepType(vertex) === WorkStepType.tubeCutting, "Pre-condition violated");

	const tube = tubeInput ?? tubeForVertex(vertex);
	if (tube === undefined) {
		return undefined;
	}

	const profileGeometry = wsi4.node.tubeProfileGeometry(vertex);
	if (profileGeometry === undefined) {
		return undefined;
	}

	const volumePerTube = computeTubeVolume(tube, profileGeometry);
	if (volumePerTube === undefined) {
		return undefined;
	}

	const volumePerPart = nodeVolume(vertex);
	if (volumePerPart === undefined) {
		return undefined;
	}

	assert(volumePerTube > 0, "Tube volume invalid");
	return wsi4.node.multiplicity(vertex) * volumePerPart / volumePerTube;
}

/**
 * Find vertex corresponding to the assembly referred to by path and inputVertex's inputAssembly
 *
 * Note: path is assumed to refer to a component, not a sub-assembly.
 */
export function findVertexForAssemblyPath(inputVertex: Vertex, path: AssemblyPath): Vertex|undefined {
	const targetAsm = (() => {
		const asm = wsi4.node.assembly(inputVertex);
		if (asm === undefined) {
			return undefined;
		} else {
			return wsi4.geo.assembly.resolvePath(asm, path);
		}
	})();
	return targetAsm === undefined ? undefined : Array.from([
		inputVertex,
		...collectSubGraphVertices(wsi4.graph.article(inputVertex)),
	])
		.filter(vertex => { // eslint-disable-line array-callback-return
			switch (wsi4.node.workStepType(vertex)) {
				case WorkStepType.undefined: return false;
				case WorkStepType.sheet: return false;
				case WorkStepType.sheetCutting: return true;
				case WorkStepType.joining: return false;
				case WorkStepType.tubeCutting: return true;
				case WorkStepType.sheetBending: return true;
				case WorkStepType.userDefined: return false;
				case WorkStepType.userDefinedBase: return true;
				case WorkStepType.packaging: return false;
				case WorkStepType.transform: return true;
				case WorkStepType.tube: return false;
			}
		})
		.find(vertex => {
			const topAsm = wsi4.node.assembly(vertex);
			return topAsm !== undefined && recursiveSubAssemblies(topAsm)
				.reduce(
					(acc, subAsm) => acc || wsi4.geo.util.isIsomorphic(subAsm, targetAsm),
					wsi4.geo.util.isIsomorphic(topAsm, targetAsm),
				);
		});
}

/**
 * Create partitions from vertices so that for each partition all nodes can be manufactured using the same set of dies
 *
 * This allows for sharing of setup costs for all nodes of a partition.
 *
 * Pre-condition:  All vertices are of process type dieBending
 */
export function computeDieSharingPartitions(vertices: readonly Readonly<Vertex>[]): Readonly<Vertex>[][] {
	assert(vertices.every(vertex => wsi4.node.processType(vertex) === ProcessType.dieBending));

	const dieGroupIdMap = (() => {
		const map = new Map<string, {upperDieGroupId : string, lowerDieGroupId : string}[]>();
		vertices.forEach(vertex => {
			const dieChoiceMap = wsi4.node.dieChoiceMap(vertex);
			assert(dieChoiceMap !== undefined, "Expecting valid die choice map");
			const sortedIds = dieChoiceMap.map(entry => ({
				upperDieGroupId: entry.bendDieChoice.upperDieGroupId,
				lowerDieGroupId: entry.bendDieChoice.lowerDieGroupId,
			}))
				.sort(lexicographicObjectLess);
			map.set(wsi4.util.toKey(vertex), sortedIds);
		});
		return map;
	})();

	const paramsMap = (() => {
		const bendTimeParamTable = getTable(TableType.bendTimeParameters);
		const bendRateParamTable = getTable(TableType.bendRateParameters);

		const getParams = (vertex: Vertex) => ({
			time: lookUpBendTimeParams(vertex, bendTimeParamTable),
			rate: lookUpBendRateParams(vertex, bendRateParamTable),
		});

		return vertices.reduce((acc, vertex) => {
			acc.set(wsi4.util.toKey(vertex), getParams(vertex));
			return acc;
		}, new Map<string, {time : PureBendTimeParams, rate : PureBendRateParams}>());
	})();

	const sheetSourceMap = vertices.reduce((acc, sheetBendingVertex) => {
		const sheetVertex = wsi4.graph.reaching(sheetBendingVertex)
			.find(vertex => wsi4.node.workStepType(vertex) === WorkStepType.sheet);
		// Note:  In general there is no guarantee for a reaching sheet node as e.g. the source could also be a purchased part.
		acc.set(wsi4.util.toKey(sheetBendingVertex), sheetVertex);
		return acc;
	}, new Map <string, Vertex|undefined>());

	return vertices.reduce((partitions: Readonly<Vertex>[][], lhs) => {
		const matchingPartitionIndex = partitions.findIndex(partition => {
			assert(partition.length > 0, "Expecting only non-empty partitions"); const rhs = partition[0];

			const lhsKey = wsi4.util.toKey(lhs);
			const rhsKey = wsi4.util.toKey(rhs);

			let result = true;
			result = result && isEqual(
				dieGroupIdMap.get(lhsKey),
				dieGroupIdMap.get(rhsKey),
			);
			result = result && isEqual(
				paramsMap.get(lhsKey),
				paramsMap.get(rhsKey),
			);
			result = result
				&& sheetSourceMap.get(lhsKey) !== undefined
				&& isEqual(
					sheetSourceMap.get(lhsKey),
					sheetSourceMap.get(rhsKey),
				);
			return result;
		});
		if (matchingPartitionIndex === -1) {
			partitions.push([ lhs ]);
		} else {
			partitions[matchingPartitionIndex].push(lhs);
		}
		return partitions;
	}, []);
}

function appendNumberIndex(nameInput: string, existingNames: readonly Readonly<string>[]) {
	const newNameBase = (() => {
		const numberIndexPosition = nameInput.search(/_[0-9]+$/);
		if (numberIndexPosition === -1) {
			return nameInput;
		} else {
			return nameInput.substring(0, numberIndexPosition);
		}
	})();

	for (let i = 0; i <= existingNames.length; ++i) {
		const newName = newNameBase + "_" + i.toFixed(0);
		if (existingNames.every(name => name !== newName)) {
			return newName;
		}
	}

	wsi4.throwError("Should not be reached");
}

export function makeArticleNameUnique(nameInput: string, existingNames?: readonly Readonly<string>[]): string {
	existingNames = existingNames === undefined ? wsi4.graph.articles()
		.map(article => getArticleName(article[0])) : existingNames;

	if (existingNames.some(name => name === nameInput)) {
		return appendNumberIndex(nameInput, existingNames);
	} else {
		return nameInput;
	}
}

/**
 * A "signature" WorkStepType defines the characteristics of an article
 *
 * A signature WorkStepType is deduced from the list of all `WorkStepType`s of an article.
 */
export function computeSignatureWst(articleWsts: readonly WorkStepType[]): WorkStepType {
	// Prioritize `WorkStep`s so when sorting all nodes of an article the signature node is the left-most value.
	// As not all `WorkStepType`s can be part of the same article, the order is arbitrary to a certain degree.
	// Relevant WorkStepType relations are asserted below.
	// Two `WorkStepType`s are related if they can occur in the same article
	const wstPriorityMap: {[wst in WorkStepType]: number} = {
		sheetBending: 0,
		sheetCutting: 1,
		tubeCutting: 2,
		joining: 3,
		userDefinedBase: 4,
		sheet: 5,
		tube: 6,
		userDefined: 7,
		packaging: 8,
		transform: 9,
		undefined: 10,
	};

	if (wsi4.util.isDebug()) {
		assert(wstPriorityMap[WorkStepType.sheetBending] < wstPriorityMap[WorkStepType.sheetCutting], "sheetBending must dominate sheetCutting");
		assert(wstPriorityMap[WorkStepType.sheetCutting] < wstPriorityMap[WorkStepType.userDefined], "sheetCutting must dominate userDefined");
		assert(wstPriorityMap[WorkStepType.sheetCutting] < wstPriorityMap[WorkStepType.transform], "sheetBending must dominate transform");
		assert(wstPriorityMap[WorkStepType.sheetCutting] < wstPriorityMap[WorkStepType.packaging], "sheetBending must dominate packaging");
		assert(wstPriorityMap[WorkStepType.sheetCutting] < wstPriorityMap[WorkStepType.sheet], "sheetCutting must dominate sheet");
		assert(wstPriorityMap[WorkStepType.joining] < wstPriorityMap[WorkStepType.userDefined], "joining must dominate userDefined");
		assert(wstPriorityMap[WorkStepType.joining] < wstPriorityMap[WorkStepType.transform], "joining must dominate transform");
		assert(wstPriorityMap[WorkStepType.joining] < wstPriorityMap[WorkStepType.packaging], "joining must dominate packaging");
		assert(wstPriorityMap[WorkStepType.userDefinedBase] < wstPriorityMap[WorkStepType.userDefined], "userDefinedBase must dominate userDefined");
		assert(wstPriorityMap[WorkStepType.userDefinedBase] < wstPriorityMap[WorkStepType.transform], "userDefinedBase must dominate transform");
	}

	const signatureWst = articleWsts.map((wst): [ WorkStepType, number ] => [
		wst,
		wstPriorityMap[wst],
	])
		.sort((lhs, rhs) => lhs[1] - rhs[1])[0][0];
	return signatureWst;
}

export function isSignatureWst(targetWst: WorkStepType, articleWsts: readonly WorkStepType[]): boolean {
	return computeSignatureWst(articleWsts) === targetWst;
}

/**
 * A vertex is an article's signature vertex if its WorkStepType is the article's signature WorkStepType (see [[isSignatureWst]])
 */
export function isSignatureVertex(targetVertex: Vertex, article?: Vertex[]): boolean {
	article = article === undefined ? wsi4.graph.article(targetVertex) : article;
	const articleWsts = article.map(vertex => wsi4.node.workStepType(vertex));
	const targetWst = wsi4.node.workStepType(targetVertex);
	return isSignatureWst(targetWst, articleWsts);
}

/**
 * Convenience function to extract the associated article's signature vertex
 */
export function getArticleSignatureVertex(article: readonly Vertex[]): Vertex {
	const vertexAndWsts = article.map((vertex): [ Vertex, WorkStepType ] => [
		vertex,
		wsi4.node.workStepType(vertex),
	]);

	const articleWsts = vertexAndWsts.map(tuple => tuple[1]);
	const signatureWst = computeSignatureWst(articleWsts);

	const signatureTuple = vertexAndWsts.find(tuple => tuple[1] === signatureWst);
	assert(signatureTuple !== undefined, "Expecting valid signature node");

	return signatureTuple[0];
}

/**
 * Convenience function to extract an article's user data
 */
export function getArticleUserData(inputVertex: Vertex): ArticleUserData {
	const signatureVertex = getArticleSignatureVertex(wsi4.graph.article(inputVertex));
	return getNodeUserDataEntryOrThrow("articleUserData", signatureVertex);
}

/**
 * Get name of article `vertex` belongs to
 */
export function getArticleName(vertex: Vertex): string {
	const userData = getArticleUserData(vertex);
	return userData.name;
}

/**
 * For a sheet vertex get the ID of the associated sheet (if any)
 */
export function sheetIdForVertex(vertex: Vertex, sheetTable?: readonly Readonly<Sheet>[]): string|undefined {
	assertDebug(
		() => wsi4.node.workStepType(vertex) === WorkStepType.sheet,
		"Pre-condition violated: Expecting WST sheet",
	);

	const thickness = wsi4.node.sheetThickness(vertex);
	assert(thickness !== undefined, "Expecting valid thickness");

	const sheetFilter = wsi4.node.sheetFilter(vertex);
	assert(sheetFilter !== undefined, "Expecting sheet filter");

	const sheetMaterialId = getAssociatedSheetMaterialId(vertex);

	const targetBox = nestingTargetBoxForVertex(vertex);
	if (targetBox === undefined) {
		// Valid case - nesting failed
		return undefined;
	} else {
		return lookUpSheetId(targetBox, thickness, sheetMaterialId, sheetFilter, sheetTable);
	}
}

/**
 * Compute mass of one complete sheet of the underlying nesting (if any)
 *
 * In case there is no valid nesting, 0 is returned.
 *
 * Note:  The resulting mass comprises *one complete sheet instance*, not only the nested part of it.
 * Note:  The resulting mass comprises *one instance* of the underlying sheet, not all sheets of the nesting.
 */
export function computeCompleteSingleSheetMass(vertex: Vertex): number {
	assertDebug(
		() => wsi4.node.workStepType(vertex) === WorkStepType.sheet,
		"Pre-condition violated:  Expecting sheet node",
	);

	const twoDimRep = wsi4.node.twoDimRep(vertex);
	if (twoDimRep === undefined) {
		return 0;
	} else {
		const thickness = wsi4.node.sheetThickness(vertex);
		assert(thickness !== undefined, "Expecting valid sheet thickness");

		const sheetMaterialId = getAssociatedSheetMaterialId(vertex);
		const sheetTable = getTable(TableType.sheet);

		const sheetId = sheetIdForVertex(vertex, sheetTable);
		assert(sheetId !== undefined, "Expecting valid sheet id");

		const sheet = sheetTable.find(row => row.identifier === sheetId);
		assert(sheet !== undefined, "Expecting valid sheet");

		const density = lookUpDensity(sheetMaterialId) ?? 0;
		return thickness * sheet.dimX * sheet.dimY * density;
	}
}

/**
 * Run `callback` for each unique maximal path through the graph.
 *
 * A maximal path is a list of vertices with the following properties:
 * 	- The first vertex has no sources
 * 	- The last vertex has no targets
 * 	- There is an arc between each consecutive pair of vertices
 *
 * For each unique maximal path the callback is called exactly once.
 *
 * Example:
 * 0 ---> 1 ---> 2 ---> 3
 *   \              /
 *    `-> 4 ---> 5 ---> 6
 *
 * 7 ---> 8
 *
 * Maximal paths:
 * [ 0, 1, 2, 3 ]
 * [ 0, 4, 5, 6 ]
 * [ 0, 4, 5, 3 ]
 * [ 7, 8 ]
 */
export function visitMaximalPaths(callback: (path: Vertex[]) => void): void {
	const queues: Vertex[][] = [
		wsi4.graph.vertices()
			.filter(v => wsi4.graph.sources(v).length === 0),
	];
	while (queues.length > 0) {
		const currentQueue = queues[queues.length - 1];
		if (currentQueue.length === 0) {
			queues.pop();
			continue;
		}

		const currentVertex = currentQueue[0];
		const targets = wsi4.graph.targets(currentVertex);
		if (targets.length > 0) {
			queues.push(targets);
			continue;
		}

		assertDebug(() => queues.every(queue => queue.length > 0));
		const maximalPath = queues.map(queue => queue[0]);
		callback(maximalPath);

		for (let i = queues.length - 1; i >= 0; --i) {
			queues[i].shift();
			if (queues[i].length > 0) {
				break;
			}
		}
	}
}

export function serializeUndirectedConnectedComponent(vertex: Vertex, projectNameInput?: string): ArrayBuffer {
	let userData = wsi4.graph.userData();
	const projectName = projectNameInput ?? getGraphUserDataEntry("name", userData) + "_" + getArticleName(vertex);
	userData = createUpdatedGraphUserData("name", projectName, userData);
	userData = createUpdatedGraphUserData("attachments", [], userData);
	return wsi4.graph.serializeUndirectedConnectedComponent(vertex, userData);
}