Tree with namespaces

ScopeTree.ts

interface IScopeNodeIndex<T> {
	[path: string]: ScopeNode<T>
}

export class ScopeNode<T> {
	constructor(
		public value: T,
		public children: IScopeNodeIndex<T> = {}
	) {

	}

	/**
	 * Computes the size of the node. Includes this node + count of all child nodes
	 * @returns {}
	 */
	get size(): number {
		return Object
			.keys(this.children)
			.filter(key => this.children.hasOwnProperty(key))
			.reduce((total, currentKey) => {
				return total + this.children[currentKey].size;
			},
			1); // start with 1 to represent this node.
	}
}

export class ScopeTree<T> {
	private readonly _root: IScopeNodeIndex<T> = {};
	private _pathDelimiter: string = '.';

	constructor(
		private _defaultValue: T = null
	) {

	}

	public isValidPathToken(token: string): boolean {
		let regex = RegEx.buildRegexString(
			[
				this._pathDelimiter.charCodeAt(0) // tokens my not include the pathDelimiter
			],
			[
				..._.range(0x61, 0x7b), // a-z
				..._.range(0x41, 0x5b), // A-Z
				..._.range(0x30, 0x3a), // 0-9
				0x5f, // _ (underscore)
				0x7e // ~ (tilde)
			]
		);

		return RegExp(regex).test(token);
	}

	/**
	 * Size of the tree (in nodes)
	 * @returns count of nodes in the tree
	 */
	get size(): number {
		return Object
			.keys(this._root)
			.filter(key => this._root.hasOwnProperty(key))
			.reduce((total, currentKey) => {
				return total + this._root[currentKey].size;
			},
			0); // by default, the tree is empty; The size of this tree is the sum of the size of its children

	}

	/**
	 * Returns the root node index.
	 * @returns {}
	 */
	get root(): IScopeNodeIndex<T> {
		return this._root;
	}

	/**
	 * Sets the path delimiter used when resolving paths. Default is '.'
	 * @param delimiter	Path delimiter to use. Must be one character (delimiter.length == 1)
	 */
	set pathDelimiter(delimiter: string) {
		if (delimiter.length === 1)
			this._pathDelimiter = delimiter;
	}

	/**
	 * Returns the current path delimiter used when resolving paths. Default is '.';
	 * @returns {}
	 */
	get pathDelimiter(): string {
		return this._pathDelimiter;
	}

	/**
	 * Splits and validates the `pathString` into individual tokens. Throws Error on validation.
	 * @param pathString
	 */
	private _getPathTokens(pathString: string): string[] {
		let tokens = pathString.split(this._pathDelimiter);
		return tokens.map(token => {
			if (this.isValidPathToken(token))
				return token;
			else
				throw new Error(`Error parsing token string '${pathString}' at '${token}'`);
		});
	}

	/**
	 * Add a `value` to the tree at `path`; creates supporting tree structure, if necessary.
	 * @param path	The tree location where the value should be stored.
	 * @param value	A value to add to the tree. Type is templated.
	 */
	public add(path: string, value: T) {
		const keys: string[] = this._getPathTokens(path);

		let currentIndex = this._root;
		let currentNode: ScopeNode<T> = null;

		while (keys.length) {

			const key = keys.shift();

			if (currentNode) {
				currentIndex = currentNode.children;
			}

			if (!currentIndex[key]) {
				currentIndex[key] = new ScopeNode( this._defaultValue );
			}

			currentNode = currentIndex[key];
		}

		if (currentNode)
			currentNode.value = value;
	}

	/**
	 * Deletes a node specified at `path` and all children.
	 * @param path pathDelimiter-delimited path to delete from the tree.
	 */
	public remove(path: string) {
		const keys: string[] = this._getPathTokens(path);

		let currentIndex = this._root;
		let currentNode: ScopeNode<T> = null;
		let currentKey: string = null;

		while (keys.length) {
			currentKey = keys.shift();

			if (currentNode) {
				currentIndex = currentNode.children;
			}

			if (!currentIndex[currentKey]) {
				// nothing to delete
				return;
			}

			// must exist for the while loop to ratchet through the structure
			currentNode = currentIndex[currentKey];

		}

		delete currentIndex[currentKey];
	}

	/**
	 * Returns the node that exists at `path`
	 * @param path
	 */
	public getNode(path: string): ScopeNode<T> {
		const keys: string[] = this._getPathTokens(path);

		let currentIndex = this._root;
		let currentNode = null;

		while (keys.length) {

			const key = keys.shift();

			if (currentNode) {
				currentIndex = currentNode.children;
			}

			if (!currentIndex[key]) {
				return null;
			}

			currentNode = currentIndex[key];
		}

		return currentNode;
	}

	/**
	 * Gets a value from the node at `path`
	 * @returns null if there isn't a node available
	 * @param path
	 */
	public getValue(path: string): T {
		const node = this.getNode(path);
		if (node)
			return node.value;
		else
			return null;
	}

	/**
	 * Gets all nodes at and beneath a path.
	 * @param path
	 */
	public getNodes(path: string): ScopeNode<T>[] {
		let result = [];
		this.visitNodes(path,
			(node) => {
				result.push(node);
			});
		return result;
	}

	/**
	 * Gets all values from nodes at and beneath a path.
	 * @param path
	 */
	public getValues(path: string): T[] {
		return this
			.getNodes(path)
			.map(node => node.value);
	}

	/**
	 * Replaces the node at `path` with `node`, no questions asked.
	 *
	 * ⚠️⚠️ WARNING: advanced usage only; you can ruin the tree with this ⚠️⚠️
	 *
	 * @param path
	 * @param node
	 * @returns replaced node on success; null if there was nothing to replace (incomplete path)
	 */
	public replaceNode(path: string, node: ScopeNode<T>) {
		const keys: string[] = this._getPathTokens(path);

		let currentIndex = this._root;
		let currentNode = null;

		while (keys.length) {

			const key = keys.shift();

			if (currentNode) {
				currentIndex = currentNode.children;
			}

			if (!currentIndex[key]) {
				return null;
			}

			currentNode = currentIndex[key];
		}

		currentNode = node;

		return currentNode;
	}

	public with(path: string, callback: (node: ScopeNode<T>) => ScopeNode<T> ) {
		let node = callback(this.getNode(path));
		this.replaceNode(path, node);
	}

	/**
	 * Sets the value for the node specified by `path`.  Returns the node on success; null if path doesn't exist
	 * @param path
	 * @param value
	 */
	public setValue(path: string, value: T): ScopeNode<T> {
		const keys: string[] = this._getPathTokens(path);

		let currentIndex: IScopeNodeIndex<T> = this._root;
		let currentNode: ScopeNode<T> = null;

		while (keys.length) {

			const key = keys.shift();

			if (currentNode) {
				currentIndex = currentNode.children;
			}

			if (!currentIndex[key]) {
				return null;
			}

			currentNode = currentIndex[key];
		}

		if (currentNode)
			currentNode.value = value;

		return currentNode;
	}

	/**
	 * Tests to see if a node with the specified `value` is in the tree.
	 * Note: this function will return true on the first discovery of `value` in the tree
	 * @param path		pathDelimiter-delimited location to begin search
	 * @param value		value to look for
	 */
	public contains(path: string, value: T): boolean {
		return this._bfsSearch(
			this.getNode(path),
			(node) => node.value === value,
			true
		).length > 0;
	}

	/**
	 *
	 * @param path
	 * @param predicate
	 * @param order
	 */
	public find(
		path: string,
		predicate: (node: ScopeNode<T>) => boolean,
		order: "pre" | "post" | "bfs" = "bfs"
	): ScopeNode<T>[] {
		return this[`_${order}Search`](this.getNode(path), predicate, false);
	}

	/**
	 * Visits nodes on the tree
	 * @param path
	 * @param callback
	 * @param order Order to traverse the tree (pre, post, dfs, bfs)
	 */
	public visitNodes(
		path: string,
		callback: (node: ScopeNode<T>) => void,
		order: "pre" | "post" | "bfs" = "post"
	) {
		return this[`_${order}Order`](this.getNode(path), callback);
	}

	/**
	 * Traverses the tree using BFS and returns all nodes that pass the predicate function
	 * @param startNode	node from which to begin the BFS
	 * @param predicate	function that returns true or false if the node should be collected
	 * @param first	boolean	true if you're only interested in the first result, false for all
	 */
	private _bfsSearch(
		startNode: ScopeNode<T>,
		predicate: (node: ScopeNode<T>) => boolean,
		first: boolean = false
	) {
		const result = [];
		if (startNode) {
			const nodeQueue: ScopeNode<T>[] = [startNode];
			while (nodeQueue.length) {
				const currentNode = nodeQueue.shift();

				if (predicate && predicate(currentNode)) {
					if (first) {
						return [currentNode];
					} else {
						result.push(currentNode);
					}
				}
				// add children to work queue
				Object
					.keys(currentNode.children)
					.filter(key => currentNode.children.hasOwnProperty(key))
					.forEach(key => {
						nodeQueue.push(currentNode.children[key]);
					});
			}
		}
		return result;
	}

	/**
	 * Applies a callback function to nodes, in breadth-first order (level by level, left to right)
	 * @param parentNode
	 * @param callback
	 */
	private _bfsOrder(parentNode: ScopeNode<T>, callback: (node: ScopeNode<T>) => void): void {
		const nodeQueue: ScopeNode<T>[] = [parentNode];

		while (nodeQueue.length) {
			const currentNode = nodeQueue.shift();
			if (callback) {
				callback(currentNode);
			}
			// add children to work queue
			Object
				.keys(currentNode.children)
				.filter(key => currentNode.children.hasOwnProperty(key))
				.forEach(key => {
					nodeQueue.push(currentNode.children[key]);
				});
		}
	}

	/**
	 * Applies a callback function to nodes, children first.
	 * @param parentNode
	 * @param callback
	 */
	private _postOrder(parentNode: ScopeNode<T>, callback: (node: ScopeNode<T>) => void): void {
		if (parentNode) {
			Object
				.keys(parentNode.children)
				.filter(key => parentNode.children.hasOwnProperty(key))
				.forEach(key => {
					this._postOrder(parentNode.children[key], callback);
				});

			if (callback) {
				callback(parentNode);
			}
		}
		return;
	}

	/**
	 * Applies a callback function to nodes, parent first.
	 * @param startNode
	 * @param callback
	 */
	private _preOrder(startNode: ScopeNode<T>, callback: (node: ScopeNode<T>) => void): void {
		if (startNode) {
			if (callback) {
				callback(startNode);
			}
			Object
				.keys(startNode.children)
				.filter(key => startNode.children.hasOwnProperty(key))
				.forEach(key => {
					this._preOrder(startNode.children[key], callback);
				});
		}
		return;
	}

	/**
	 * Visits values in the tree at or beneath `path`,
	 * @param path	location in the tree to visit nodes.
	 * @param callback a value transformation callback function
	 */
	public visitValues(path: string, callback: (value: T) => T) {
		return this.visitNodes(path, (n) => {
			n.value = callback(n.value);
			return n;
		});
	}

}