// 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 {
	back,
	front,
	itemAt,
} from "./array_util";
import {
	articleUserDatum,
} from "./article_userdata_config";
import {
	assumeGraphAxioms,
} from "./axioms";
import {
	tolerances,
} from "./constants";
import {
	getDeducedDataEntryOrThrow,
} from "./deduceddata_utils";
import {
	computeMaxBendLineNetLength,
	grossTubeConsumptionForVertex,
	nestingTargetBoxForVertex,
	tubeForVertex,
} from "./node_utils";
import {
	getSettingOrDefault,
} from "./settings_table";
import {
	sheetFilterSheetIds,
} from "./sheet_util";
import {
	BendParamsUniqueMembers,
	computeTubeVolume,
	getSheetsInStock,
	getTable,
	lookUpDensity,
	lookUpSheetId,
	pickBendParameterRow,
} from "./table_utils";
import {
	createUpdatedGraphUserData,
	getGraphUserDataEntry,
} from "./userdata_config";
import {
	collectNodeUserDataEntries,
	userDataAccess,
} from "./userdata_utils";
import {
	assert,
	assertDebug,
	bbDimensionX,
	bbDimensionY,
	isArray,
	isEqual,
	isNumber,
	isString,
	lexicographicObjectLess,
	recursiveSubAssemblies,
} from "./utils";
import {
	computeSignatureWst,
	isSignatureWst,
} from "./workstep_util";

export function collectSubGraphVertices(article: readonly Readonly<Vertex>[]): Vertex[] {
	const lastVertex = back(article);
	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[] {
	assumeGraphAxioms([ "deducedDataConsistent" ]);
	if (wsi4.node.workStepType(sheetVertex) !== "sheet") {
		return wsi4.throwError("computeAllowedSheets(): Wrong WorkStepType");
	}

	const deducedData = wsi4.node.deducedData(sheetVertex);
	// deduced data has to be filled
	assertDebug(() => Object.keys(deducedData).length > 0, "Deduced data is not filled for sheet node");

	if (!getDeducedDataEntryOrThrow("targetsFitOnSheet", sheetVertex, deducedData)) {
		// no sheet is allowed because targets are too big
		return [];
	}

	const thickness = wsi4.node.sheetThickness(sheetVertex);
	if (thickness === undefined) {
		// Errors are written in lambda function
		return [];
	}

	const sheetMaterial = getDeducedDataEntryOrThrow("sheetMaterial", sheetVertex, deducedData);
	if (sheetMaterial === undefined) {
		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 s = getSheetsInStock(sheetTable)
		.filter(row => row.sheetMaterialId === sheetMaterial.identifier
			&& Math.abs(row.thickness - thickness) < tolerances.thickness
			&& minDimX <= row.dimX
			&& minDimY <= row.dimY);
	// There has to be at least one sheet because we already returned if the targets don't fit
	assert(s.length > 0, "No sheets found.");
	return s;
}

/**
 * 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 intended 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 | undefined {
	// 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 materialIds = collectNodeUserDataEntries("sheetMaterialId", vertex, userDataAccess.article | userDataAccess.reachable)
		.filter((lhs, index, self) => lhs !== undefined && self.findIndex(rhs => rhs !== undefined && lhs === rhs) === index);
	return materialIds.length === 1 ? materialIds[0] : undefined;
}

/**
 * Get identifier of associated tube material
 *
 * @param vertex Vertex of the associated node
 * @returns Identifier of the associated tube material
 *
 * Note: This function is intended to be used for nodes where exactly one tube material can be associated.
 * This is the case for nodes of WorkStepType tube, tubeCutting 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 tube material.
 */
export function getAssociatedTubeMaterialId(vertex: Vertex): string | undefined {
	// Special case for nodes of type tube to improve performance:
	// Assumption: all target articles of tube share the same tube material.
	if (wsi4.node.workStepType(vertex) === WorkStepType.tube) {
		const targets = wsi4.graph.targets(vertex);
		assert(targets.length > 0, "Expecting at least one target");
		vertex = targets[0]!;
	}
	const materialIds = collectNodeUserDataEntries("tubeMaterialId", vertex, userDataAccess.article | userDataAccess.reachable)
		.filter((lhs, index, self) => lhs !== undefined && self.findIndex(rhs => rhs !== undefined && lhs === rhs) === index);
	return materialIds.length === 1 ? materialIds[0] : undefined;
}

/**
 * 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(front(article));
	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(front(article));
	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 = front(article);
	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 materialIds = collectNodeUserDataEntries("sheetMaterialId", front(article), userDataAccess.article | userDataAccess.reachable)
		.filter((lhs, index, self) => lhs !== undefined && self.findIndex(rhs => rhs !== undefined && rhs === lhs) === index)
		.filter((value): value is string => value !== undefined);
	if (materialIds.length !== 1) {
		return undefined;
	}

	// [kg/mm³]
	const density = lookUpDensity(materialIds[0]!);
	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 materialIds = collectNodeUserDataEntries("tubeMaterialId", front(article), userDataAccess.article | userDataAccess.reachable);
	assert(materialIds.length <= 1, "Expecting at most one material");
	if (materialIds.length === 0 || materialIds[0] === undefined) {
		return undefined;
	}

	const materialId = materialIds[0];
	assert(materialId !== undefined);

	const densityRow = getTable(TableType.tubeMaterialDensity)
		.find(row => row.tubeMaterialId === materialId);
	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;
}

type NestingFraction = {
	nestingDescriptor: number,
	fractionPerSheet: number,
	effectiveDimX: number,
	effectiveDimY: number,
};

/**
 * For a given nesting compute the fractions for each nesting
 *
 * Note: All underlying nestings for a sheet node are (now) based on the same target boundary.
 */
export function computeNestingFractions(twoDimRep: Readonly<TwoDimRepresentation>, targetBox: Readonly<Box2>, sheetModulusRow: Readonly<{
	xModulus: number,
	yModulus: number,
	applyToAll: boolean,
}>): NestingFraction[] {
	const targetBoxDimX = bbDimensionX(targetBox);
	const targetBoxDimY = bbDimensionY(targetBox);

	const nestingDistance = getSettingOrDefault("sheetNestingDistance");
	const nestingDescriptors: readonly number[] = wsi4.cam.nest2.nestingDescriptors(twoDimRep);
	return nestingDescriptors.map(nestingDescriptor => {
		const bbox = wsi4.cam.nest2.nestingBoundingBox(twoDimRep, nestingDescriptor);
		const bbDimX = Math.min(nestingDistance + bbDimensionX(bbox), targetBoxDimX);
		const bbDimY = Math.min(nestingDistance + bbDimensionY(bbox), targetBoxDimY);

		const computeEffectiveDim = (bbDim: number, sheetDim: number, modulus: number) => {
			const modulusEps = 0.0001;
			if (modulus < modulusEps) {
				return bbDim;
			} else {
				const modulusFraction = sheetDim * modulus;
				const numModulus = Math.ceil(bbDim / modulusFraction);
				return Math.min(sheetDim, numModulus * modulusFraction);
			}
		};

		const clamp = (modulus: number) => Math.max(0, Math.min(1, modulus));
		const dimX = computeEffectiveDim(bbDimX, targetBoxDimX, clamp(sheetModulusRow.xModulus));
		const dimY = computeEffectiveDim(bbDimY, targetBoxDimY, clamp(sheetModulusRow.yModulus));

		const fraction = (dimX * dimY) / (targetBoxDimX * targetBoxDimY);
		assert(
			fraction > 0 && fraction <= 1,
			"Sheet fraction for nesting invalid; expecting 0 < fraction <= 1; actual fraction: " + fraction.toString(),
		);

		return {
			nestingDescriptor: nestingDescriptor,
			fractionPerSheet: fraction,
			effectiveDimX: dimX,
			effectiveDimY: dimY,
		};
	});
}

/**
 * For a given nesting compute the sheet consumption (floating-point value)
 *
 * Note: All underlying nestings for a sheet node are (now) based on the same target boundary.
 *
 * Note: If there is no valid nesting for the vertex submitted the consumption is undefined.
 * Note: If there is no valid sheet for the vertex submitted the consumption is undefined.
 *
 * For each sheet the consumption is computed as floating-point value v; v can be
 * >= 1. if *no* modulus operation is applied to the sheet
 * > 0. if modulus operation is applied to the sheet
 * Values > 1. occur for sheets with multiplicity > 1
 *
 * @param vertex Vertex with associated Nesing
 * @returns Sheet consumption (if any; in fractions of one sheet so no unit)
 */
export function computeSheetConsumption(vertex: Vertex, sheetTable?: readonly Readonly<Sheet>[]): number | undefined {
	assertDebug(
		() => wsi4.node.workStepType(vertex) === WorkStepType.sheet,
		"Pre-condition violated: Expecting WST sheet",
	);

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

	const sheetId = sheetIdForVertex(vertex, sheetTable);
	if (sheetId === undefined) {
		return undefined;
	}

	const targetBox = nestingTargetBoxForVertex(vertex);
	assert(targetBox !== undefined, "Execting valid target box");

	// Sheet modulus table entry is not mandatory.
	// Using neutral default value as fallback.
	const sheetModulusRow: Readonly<{
		xModulus: number,
		yModulus: number,
		applyToAll: boolean,
	}> = getTable(TableType.sheetModulus)
		.find(row => row.sheetId === sheetId) ?? {
		xModulus: 0,
		yModulus: 0,
		applyToAll: true,
	};

	const nestingFractions = computeNestingFractions(twoDimRep, targetBox, sheetModulusRow);

	// Undefined if modulus should be applied to all sheets
	const bestNestingDescriptor = (() => {
		if (sheetModulusRow.applyToAll) {
			return undefined;
		} else {
			const nestingDescriptors: readonly number[] = wsi4.cam.nest2.nestingDescriptors(twoDimRep);
			// If there is at least one sheet with multiplicity === 1 then the sheet where modulus operation is applied must have multiplicity === 1
			const multiplicityOneAvailable = nestingDescriptors.some(nestingDescriptor => wsi4.cam.nest2.nestingMultiplicity(twoDimRep, nestingDescriptor) === 1);
			return nestingFractions.filter(item => !multiplicityOneAvailable || wsi4.cam.nest2.nestingMultiplicity(twoDimRep, item.nestingDescriptor) === 1)
				.sort((lhs, rhs) => lhs.fractionPerSheet - rhs.fractionPerSheet)[0]!.nestingDescriptor;
		}
	})();

	return nestingFractions.reduce((acc, obj) => {
		const numSheets = wsi4.cam.nest2.nestingMultiplicity(twoDimRep, obj.nestingDescriptor);
		if (bestNestingDescriptor === undefined) {
			return acc + numSheets * obj.fractionPerSheet;
		} else if (obj.nestingDescriptor === bestNestingDescriptor) {
			return acc + numSheets + obj.fractionPerSheet - 1;
		} else {
			return acc + numSheets;
		}
	}, 0);
}

/**
 * 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.
 *
 * In case die bending tool partitioning is disabled then each input vertex forms its own partition.
 *
 * Pre-condition:  All vertices are of process type dieBending
 */
export function computeDieSharingPartitions(vertices: readonly Readonly<Vertex>[]): Readonly<Vertex>[][] | undefined {
	assert(vertices.every(vertex => wsi4.node.processType(vertex) === ProcessType.dieBending));

	if (!getSettingOrDefault("dieBendingSetupTimeDistributionEnabled")) {
		return vertices.map(vertex => [ vertex ]);
	}

	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) ?? null,
			rate: lookUpBendRateParams(vertex, bendRateParamTable) ?? null,
		});

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

	if (Array.from(paramsMap.values()).some(value => value.rate === null || value.time === null)) {
		return undefined;
	}

	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 {
			itemAt(matchingPartitionIndex, partitions).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 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];
}

/**
 * Get name of article `vertex` belongs to
 */
export function getArticleName(vertex: Vertex): string {
	return articleUserDatum("name", vertex) ?? "";
}

/**
 * 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 ids = sheetFilterSheetIds(vertex);

	const sheetMaterialId = getAssociatedSheetMaterialId(vertex);

	const targetBox = nestingTargetBoxForVertex(vertex);
	if (targetBox === undefined || sheetMaterialId === undefined) {
		// Valid case - nesting failed
		return undefined;
	} else {
		return lookUpSheetId(targetBox, thickness, sheetMaterialId, ids, 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 | undefined {
	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);
		if (sheetMaterialId === undefined) {
			return undefined;
		}

		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 u = getGraphUserDataEntry("name", userData);
	const projectName = projectNameInput ?? (u === undefined ? "undef" : u) + "_" + getArticleName(vertex);
	userData = createUpdatedGraphUserData("name", projectName, userData);
	userData = createUpdatedGraphUserData("attachments", [], userData);
	return wsi4.graph.serializeUndirectedConnectedComponent(vertex, userData);
}

type PureBendParams<T> = Omit<T, "sheetBendingMaterialId"|"thickness"|"bendLineNetLength">;
function lookUpBendParams<T extends BendParamsUniqueMembers>(vertex: Vertex, table: readonly Readonly<T>[], defaultValue: PureBendParams<T>): PureBendParams<T> | undefined {
	const actualThickness = wsi4.node.sheetThickness(vertex);
	if (actualThickness === undefined) {
		return wsi4.throwError("Expecting sheet actualThickness");
	}
	const maxThickness = actualThickness + tolerances.thickness;

	const sheetMaterialId = getAssociatedSheetMaterialId(vertex);
	if (sheetMaterialId === undefined) {
		return undefined;
	}
	const materialMapping = getTable(TableType.sheetBendingMaterialMapping)
		.find(row => row.sheetMaterialId === sheetMaterialId);
	if (materialMapping === undefined) {
		return undefined;
	}

	const maxBendLineNetLength = computeMaxBendLineNetLength(vertex) + tolerances.thickness;
	const row = pickBendParameterRow(table, materialMapping.sheetBendingMaterialId, maxThickness, maxBendLineNetLength);
	return row === undefined ? defaultValue : row;
}

export type PureBendTimeParams = Omit<BendTimeParameters, "sheetBendingMaterialId"|"thickness"|"bendLineNetLength">;

/**
 * Table value is not enforced for all possible unique member combinations.
 * If no matching row is available a neutral default value is returned.
 */
export function lookUpBendTimeParams(vertex: Vertex, table?: readonly Readonly<BendTimeParameters>[]): PureBendTimeParams | undefined {
	table = table === undefined ? getTable(TableType.bendTimeParameters) : table;
	const defaultValue = {
		setupTimeFactor: 1.,
		setupTimeDelta: 0.,
		setupTimePerBendFactor: 1.,
		setupTimePerBendDelta: 0.,
		unitTimeFactor: 1.,
		unitTimeDelta: 0.,
		unitTimePerBendFactor: 1.,
		unitTimePerBendDelta: 0.,
	};
	return lookUpBendParams(vertex, table, defaultValue);
}

export type PureBendRateParams = Omit<BendRateParameters, "sheetBendingMaterialId"|"thickness"|"bendLineNetLength">;

/**
 * Table value is not enforced for all possible unique member combinations.
 * If no matching row is available a neutral default value is returned.
 */
export function lookUpBendRateParams(vertex: Vertex, table?: readonly Readonly<BendRateParameters>[]): PureBendRateParams | undefined {
	table = table === undefined ? getTable(TableType.bendRateParameters) : table;
	const defaultValue = {
		hourlyRateFactor: 1.,
		hourlyRateDelta: 0.,
	};
	return lookUpBendParams(vertex, table, defaultValue);
}

/**
 * Get all subjoinings from graph
 */
export function getAllSubJoinings(): Vertex[] {
	return wsi4.graph.vertices()
		.filter(candidateVertex => isSubJoining(candidateVertex));
}