Tree.js

import { _ } from '@kitmi/utils';

/**
 * A closure function to be called to check the data of each node whether meets certain condition
 * @callback predicateFunction
 * @param {Node} node
 * @returns {boolean}
 */

/**
 * Tree factory.
 * @param {Node} Node
 * @returns {Tree}
 */
const Tree = (Node) =>
    class extends Node {
        static Node = Node;

        /**
         * Find a node by BFS.
         * @param {predicateFunction} predicate
         */
        find(predicate) {
            let queue = Node.cloneChildrenList(this);

            while (queue.length > 0) {
                const node = queue.shift();

                if (predicate(node)) return node;

                queue = queue.concat(Node.cloneChildrenList(node));
            }

            return undefined;
        }
    };

/**
 * Tree node with data property.
 * @class
 */
class DataNode {
    static cloneChildrenList(node) {
        return node.children.concat();
    }

    /**
     * Array of children nodes.
     * @member {array}
     */
    children = [];

    /**
     * Create a data node with given data.
     * @param {*} data
     */
    constructor(data) {
        /**
         * Data property.
         * @member {*}
         */
        this.data = data;
    }

    /**
     * Number of nodes.
     * @member {number}
     */
    get size() {
        return this.children.length;
    }

    /**
     * Append the given node to the end of the children list.
     * @param {DataNode} node
     */
    append(node) {
        node.parent = this;
        this.children.push(node);
    }

    /**
     * Insert the given node at specified index in the children list.
     * @param {number} i
     * @param {DataNode} node
     */
    insert(i, node) {
        node.parent = this;
        this.children.splice(Math.max(0, i), 0, node);
    }

    /**
     * Remove the given node from the branch.
     * @param {DataNode} node
     * @returns {DataNode}
     */
    remove(node) {
        if (node.parent !== this) {
            throw new Error('Removing a node which is not a child of the current node.');
        }

        this.children = _.reject(this.children, (n) => n === node);
        delete node.parent;

        return node;
    }

    /**
     * Remove the node at the given index from the branch.
     * @param {number} i
     * @returns {DataNode}
     */
    removeAtIndex(i) {
        const [removed] = this.children.splice(i, 1);
        if (removed) {
            delete removed.parent;
        }

        return removed;
    }
}

/**
 * Tree node with key property and data property.
 * @class
 */
class KeyDataNode {
    static cloneChildrenList(node) {
        return Object.values(node.children);
    }

    /**
     * Map of keys to children nodes.
     * @member {object}
     */
    children = {};

    /**
     * Create a key-data node with key and given data.
     * @param {string} key
     * @param {*} data
     */
    constructor(key, data) {
        /**
         * Node key.
         * @member {string}
         */
        this.key = key;

        /**
         * Data property.
         * @member {*}
         */
        this.data = data;
    }

    /**
     * Number of nodes.
     * @member {number}
     */
    get size() {
        return Object.keys(this.children).length;
    }

    /**
     * Fina a node by path being an array of keys.
     * @param {array.<string>} keys
     */
    findByKeyPath(keys) {
        keys = keys.concat();

        if (keys.length === 0 || keys[0] !== this.key) {
            return undefined;
        }

        let value = { children: { [this.key]: this } };

        _.find(keys, (key) => {
            value = value.children[key];
            return typeof value === 'undefined';
        });

        return value;
    }

    /**
     * Append data by path being an array of keys.
     * @param {array.<string>} keys
     * @param {*} data
     * @returns {KeyDataNode} The newly created node containing the data.
     */
    appendDataByKeyPath(keys, data) {
        keys = keys.concat();

        if (keys.length === 0 || keys[0] !== this.key) {
            throw new Error(
                `The given key path "${keys.join(' / ')}" is not starting from the correct initial key "${this.key}".`
            );
        }

        const lastKey = keys.pop();
        let lastNode = { children: { [this.key]: this } };
        let node;

        _.each(keys, (key) => {
            if (key in lastNode.children) {
                lastNode = lastNode.children[key];
            } else {
                node = new KeyDataNode(key);
                lastNode.append(node);
                lastNode = node;
            }
        });

        node = new KeyDataNode(lastKey, data);
        lastNode.append(node);

        return node;
    }

    /**
     * Append the given node to the end of the children list.
     * @param {KeyDataNode} node
     */
    append(node) {
        node.parent = this;

        if (node.key in this.children) {
            throw new Error(`Duplicate node key: ${node.key}`);
        }

        this.children[node.key] = node;
    }

    /**
     * Remove the given node from the branch.
     * @param {KeyDataNode} node
     */
    remove(node) {
        if (node.parent !== this || !(node.key in this.children)) {
            throw new Error('Removing a node which is not a child of the current node.');
        }

        delete this.children[node.key];
        delete node.parent;

        return node;
    }

    /**
     * Get key path of current node (a key chain from root to itself).
     * @returns {array}
     */
    getKeyPath() {
        const paths = [this.key];
        let curr = this;

        while (curr.parent) {
            curr = curr.parent;
            paths.push(curr.key);
        }

        return paths.reverse();
    }
}

export const KeyTree = Tree(KeyDataNode);

export default Tree(DataNode);