// 定义一个递归函数来查找指定 id 的节点及其上级链路
function findParentChain(tree: any, targetId: number, chain: any = []): any {
	for (let node of tree) {
		if (node.menuId === targetId) {
			// 找到目标节点，返回当前链路
			return [...chain, node];
		}

		if (node.routes && node.routes.length > 0) {
			const result = findParentChain(node.routes, targetId, [
				...chain,
				node,
			]);
			if (result) {
				return result;
			}
		}
	}

	return null;
}

export function findParentChains(
	tree: any,
	targetIds: Array<number>,
): Array<number> {
	const parentChains = [] as Array<number>;

	for (let targetId of targetIds) {
		const chain = findParentChain(tree, targetId);
		if (!chain) {
			// continue;
		}

		// 遍历chain 插入 到parentChains
		for (let i = 0; i < chain.length; i++) {
			// 如果当前chain[i].menuId 在 parentChains 中 则跳过
			if (parentChains.includes(chain[i].menuId)) {
				continue;
			}

			parentChains.push(chain[i].menuId);
		}
	}
	return parentChains;
}

export function filterTreeAndKeepParents(
	treeData: any,
	menuIds: Array<number>,
): Array<number> {
	const result = [] as Array<number>;

	function traverse(
		node: any,
		allChildrenIncluded: boolean,
	): boolean | undefined {
		if (menuIds.includes(node.menuId)) {
			// 如果当前节点的menuId在menuIds中，则添加到结果集（如果其所有子节点也都在menuIds中）
			if (
				allChildrenIncluded ||
				!node.routes ||
				node.routes.length === 0
			) {
				result.push(node.menuId);
				return true;
			}
		}

		if (node.routes && node.routes.length > 0) {
			let childrenIncludedCount = 0;
			for (const child of node.routes) {
				const childAllIncluded = traverse(child, false);
				if (childAllIncluded) {
					childrenIncludedCount++;
				}
			}

			// 检查当前节点的所有子节点是否都在menuIds中
			const allChildrenAreIncluded =
				childrenIncludedCount === node.routes.length;
			if (allChildrenAreIncluded) {
				return traverse(node, true); // 重新调用自身，这次设置allChildrenIncluded为true
			}
		}
	}

	treeData.forEach((node: any) => {
		traverse(node, false);
	});

	return result;
}
