import { Comparator , mergeSort } from './merge-sort' ; import { findInsertIndex } from './find-insert-index' ; export { Comparator } from './merge-sort' ; /**
 * // Usage examples
 * this._tree.traverseDFS((node)=> {
 *    console.log(node);
 * });
 *
 * this._tree.traverseBFS((node)=> {
 *    console.log(node);
 * });
 *
 * const level4 = this._tree.findByPredicateBFS((node) => {
 *    return node.link === "/level1/level2/level3/level4"
 * });
 * console.log(level4);
 *
 * const level4Parents = this.getAllParents(level4);
 * console.log(level4Parents)
 *
 * for(const node of this._tree) {
 *   if(node.link ==="/admin/overview") {
 *     console.log("found");
 *     break;
 *   }
 * }
 */ export enum TraversalStrategy { PreOrder = 'PreOrder' , PostOrder = 'PostOrder' } export interface TreeNode < T > { parent ? : T ; children ? : T [ ] ; [ key ] : any ; } export interface TreeConfig < T > { nodeComparatorFn ? : Comparator < T > ; } export class Tree < T extends TreeNode < T > > implements Iterable < T > { config : TreeConfig < T > = { } ; root : T ; constructor ( root , config ? ) { this . root = this . addParentLinks ( root ) ; } private addParentLinks ( parent ) { if ( parent . children ) { if ( this . config && this . config . nodeComparatorFn ) { parent . children = mergeSort < any > ( parent . children , this . config . nodeComparatorFn ) ; } parent . children . forEach ( ( d ) => { d . parent = parent ; this . addParentLinks ( d ) ; } ) ; } else { parent . children = [ ] ; } return parent ; } isRoot ( node ) { return node . parent === undefined ; } isLeaf ( node ) { return node . children . length === 0 ; } add ( node , toNode ) { const parent = toNode ? this . findBFS ( toNode ) : null ; if ( parent ) { parent . children . push ( node ) ; } else { if ( ! this . root ) { this . root = node ; } else { return 'Root node is already assigned' ; } } } remove ( node ) { if ( this . root === node ) { this . root = null ; } const queue = [ this . root ] ; while ( queue . length ) { const nodeTemp = queue . shift ( ) ; for ( let i = 0 ; i < nodeTemp . children . length ; i ++ ) { if ( nodeTemp . children [ i ] === node ) { nodeTemp . children . splice ( i , 1 ) ; } else { queue . push ( nodeTemp . children [ i ] ) ; } } } } contains ( node ) { return ! ! this . findBFS ( node ) ; } findBFS ( node ) { const queue = [ this . root ] ; while ( queue . length ) { const nodeTemp = queue . shift ( ) ! ; if ( nodeTemp === node ) { return nodeTemp ; } for ( const child of nodeTemp . children ) { queue . push ( child ) ; } } return null ; } findByPredicateBFS ( predicate ) { const queue = [ this . root ] ; while ( queue . length ) { const nodeTemp = queue . shift ( ) ! ; if ( predicate ( nodeTemp ) ) { return nodeTemp ; } for ( const child of nodeTemp . children ) { queue . push ( child ) ; } } return null ; } findByPredicateDFS ( predicate , strategy = TraversalStrategy . PreOrder ) { return null ; } private _preOrder ( node , fn ) { if ( node ) { if ( fn ) { fn ( node ) ; } for ( const child of node . children ) { this . _preOrder ( child , fn ) ; } } } private _postOrder ( node , fn ) { if ( node ) { for ( const child of node . children ) { this . _postOrder ( child , fn ) ; } if ( fn ) { fn ( node ) ; } } } traverseDFS ( fn , method = TraversalStrategy . PreOrder ) { const current = this . root ; if ( method === TraversalStrategy . PostOrder ) { this . _postOrder ( current , fn ) ; } else { this . _preOrder ( current , fn ) ; } } traverseBFS ( fn ) { const queue = [ this . root ] ; while ( queue . length ) { const node = queue . shift ( ) ; if ( fn ) { fn ( node ) ; } for ( const child of node . children ) { queue . push ( child ) ; } } } * [ Symbol . iterator ] ( ) { const queue = [ this . root ] ; while ( queue . length ) { const node = queue . shift ( ) ! ; yield node ; for ( const child of node . children ) { queue . push ( child ) ; } } } getAllParents ( item ) { const parents = [ ] ; parents . unshift ( item ) ; let parent = item . parent ; while ( parent ) { parents . unshift ( parent ) ; parent = parent . parent ; } return parents ; } }