buildtree.mjs

/**
 * Copyright © schukai GmbH and all contributing authors, {{copyRightYear}}. All rights reserved.
 * Node module: @schukai/monster
 *
 * This source code is licensed under the GNU Affero General Public License version 3 (AGPLv3).
 * The full text of the license can be found at: https://www.gnu.org/licenses/agpl-3.0.en.html
 *
 * For those who do not wish to adhere to the AGPLv3, a commercial license is available.
 * Acquiring a commercial license allows you to use this software without complying with the AGPLv3 terms.
 * For more information about purchasing a commercial license, please contact schukai GmbH.
 *
 * SPDX-License-Identifier: AGPL-3.0
 */

import { isArray, isObject } from "../types/is.mjs";
import { Node } from "../types/node.mjs";
import { NodeList } from "../types/nodelist.mjs";
import { clone } from "../util/clone.mjs";
import { assembleParts } from "./buildmap.mjs";
import { extend } from "./extend.mjs";

export { buildTree };

/**
 * @private
 * @type {symbol}
 */
const parentSymbol = Symbol("parent");

/**
 * @private
 * @type {symbol}
 */
const rootSymbol = Symbol("root");

/**
 * @typedef {Object} buildTreeOptions
 * @property {array} options.rootReferences=[null, undefined] defines the values for elements without parents
 * @property {Monster.Data~exampleFilterCallback} options.filter filtering of the values
 */

/**
 * Creates a tree structure from a given subject using a selector and specified ID and parent ID keys.
 *
 * The buildTree function is a powerful tool for creating tree-like data structures from plain JavaScript
 * objects. It takes in four required parameters: the subject object that you want to turn into a tree, a
 * selector that identifies which parts of the subject to use when building the tree, and two keys
 * (idKey and parentIDKey) that specify which properties in the subject represent the unique identifiers
 * and parent-child relationships between nodes in the tree.
 *
 * Optionally, you can also pass in an options object to further configure the behavior of the function,
 * such as specifying which values should be treated as roots of the tree, or providing a custom filter
 * function to only include certain nodes in the final output.
 *
 * The buildTree function works by first using the assembleParts helper function to extract the relevant
 * parts of the subject based on the selector, and then iterates over the resulting map to create Node
 * objects and organize them into parent-child relationships based on the values of the idKey and parentIDKey properties.
 *
 * The resulting NodeList represents the tree structure, with each Node object containing the original
 * object data as well as additional metadata about its position in the tree. You can then use the childNodes
 * property of each Node to access its children, or the parent property to access its parent.
 *
 * Overall, the buildTree function is a flexible and powerful way to transform flat data into hierarchical
 * structures, and can be especially useful in scenarios such as displaying folder structures or
 * visualizing complex data relationships.
 *
 * Let's say you have an array of data objects representing a file system directory structure, and you want
 * to turn it into a tree-like structure where each node represents a folder or file, and child nodes
 * represent the contents of the folder:
 *
 * ```javascript
 * const fileSystem = [
 *   { id: 'folder1', name: 'Folder 1', type: 'folder', parent: null },
 *   { id: 'file1', name: 'File 1', type: 'file', parent: 'folder1' },
 *   { id: 'file2', name: 'File 2', type: 'file', parent: 'folder1' },
 *   { id: 'subfolder1', name: 'Subfolder 1', type: 'folder', parent: 'folder1' },
 *   { id: 'file3', name: 'File 3', type: 'file', parent: 'subfolder1' },
 *   { id: 'file4', name: 'File 4', type: 'file', parent: 'subfolder1' },
 *   { id: 'subfolder2', name: 'Subfolder 2', type: 'folder', parent: 'folder1' },
 *   { id: 'file5', name: 'File 5', type: 'file', parent: 'subfolder2' },
 *   { id: 'file6', name: 'File 6', type: 'file', parent: 'subfolder2' },
 *   { id: 'folder2', name: 'Folder 2', type: 'folder', parent: null },
 *   { id: 'file7', name: 'File 7', type: 'file', parent: 'folder2' },
 *   { id: 'file8', name: 'File 8', type: 'file', parent: 'folder2' },
 *   { id: 'subfolder3', name: 'Subfolder 3', type: 'folder', parent: 'folder2' },
 *   { id: 'file9', name: 'File 9', type: 'file', parent: 'subfolder3' },
 *   { id: 'file10', name: 'File 10', type: 'file', parent: 'subfolder3' },
 * ];
 *
 * const tree = buildTree(fileSystem, 'id', 'id', 'parent', { rootReferences: [null] });
 *
 * console.log(tree.toString());
 * ```
 *
 * The buildTree function takes in the array of data objects, as well as some configuration options specifying
 * the keys to use for identifying nodes and their parent-child relationships. In this example, we use the id
 * key to identify nodes, and the parent key to specify the parent of each node.
 *
 * The resulting tree object is a nested tree structure, where each node is an object representing a file or
 * folder, and has child nodes representing its contents. The toString method of the tree object
 * can be used to print out the tree in a readable format:
 *
 * ```markdown
 * - Folder 1
 *   - File 1
 *   - File 2
 *   - Subfolder 1
 *     - File 3
 *     - File 4
 *   - Subfolder 2
 *     - File 5
 *     - File 6
 * - Folder 2
 *   - File 7
 *   - File 8
 *   - Subfolder 3
 *     - File 9
 *     - File 10
 * ```
 *
 * @memberof Monster.Data
 *
 * @param {*} subject - The object or array to build the tree from.
 * @param {string|Monster.Data~exampleSelectorCallback} selector - Either a string to specify a property of each object to use as a selector, or a selector function to generate a map of objects.
 * @param {string} idKey - The property key to use as the unique ID of each node.
 * @param {string} parentIDKey - The property key to use as the parent ID of each node.
 * @param {object} [options] - Additional options to modify the function behavior.
 * @param {Array} [options.rootReferences=[null, undefined]] - An array of values to treat as root references when creating the tree.
 * @param {function} [options.filter] - A filter function to apply to each node.
 *
 * @return {*} The resulting tree structure as a NodeList.
 *
 * @throws {TypeError} selector is neither a string nor a function.
 * @throws {TypeError} the selector callback must return a map.
 * @throws {Error} the object has no value for the specified id.
 *
 * @license AGPLv3
 *
 * @since 1.26.0
 */
function buildTree(subject, selector, idKey, parentIDKey, options) {
	const nodes = new Map();

	const maxDepth = 100;

	if (!isObject(options)) {
		options = {};
	}

	options = extend(
		{},
		{
			rootReferences: [null, undefined],
			filter: undefined,
		},
		options,
	);

	const filter = options?.filter;
	let rootReferences = options.rootReferences;
	if (!isArray(rootReferences)) {
		rootReferences = [rootReferences];
	}

	const childMap = assembleParts(subject, selector, filter, function (o, k, m) {
		const key = o?.[idKey];
		let ref = o?.[parentIDKey];
		if (rootReferences.indexOf(ref) !== -1) ref = rootSymbol;

		if (key === undefined) {
			throw new Error("the object has no value for the specified id");
		}

		o[parentSymbol] = ref;

		const node = new Node(o);
		this.has(ref)
			? this.get(ref).add(node)
			: this.set(ref, new NodeList().add(node));
		nodes.set(key, node);
	});

	nodes.forEach((node) => {
		const id = node?.["value"]?.[idKey];

		if (id === undefined) {
			throw new Error("the object has no value for the specified id");
		}

		if (childMap.has(id)) {
			node.childNodes = childMap.get(id);
			childMap.delete(id);
		}
	});

	const list = new NodeList();

	childMap.forEach((s) => {
		if (s instanceof Set) {
			s.forEach((n) => {
				list.add(n);
			});
		}
	});

	return list;
}