buildtree.mjs

/**
 * Copyright schukai GmbH and contributors 2023. All Rights Reserved.
 * Node module: @schukai/monster
 * This file is licensed under the AGPLv3 License.
 * License text available at https://www.gnu.org/licenses/agpl-3.0.en.html
 */

import { isArray, isObject } from "../types/is.mjs";
import { Node } from "../types/node.mjs";
import { NodeList } from "../types/nodelist.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
 * @memberOf Monster.Data
 */

/**
 * 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();

    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) => {
        let id = node?.["value"]?.[idKey];

        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;
}