@theia/core/lib/browser/tree/tree-iterator.js

"use strict";
// *****************************************************************************
// Copyright (C) 2017 TypeFox and others.
//
// This program and the accompanying materials are made available under the
// terms of the Eclipse Public License v. 2.0 which is available at
// http://www.eclipse.org/legal/epl-2.0.
//
// This Source Code may also be made available under the following Secondary
// Licenses when the conditions for such availability set forth in the Eclipse
// Public License v. 2.0 are satisfied: GNU General Public License, version 2
// with the GNU Classpath Exception which is available at
// https://www.gnu.org/software/classpath/license.html.
//
// SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-only WITH Classpath-exception-2.0
// *****************************************************************************
Object.defineProperty(exports, "__esModule", { value: true });
exports.Iterators = exports.BottomUpTreeIterator = exports.TopDownTreeIterator = exports.BreadthFirstTreeIterator = exports.DepthFirstTreeIterator = exports.AbstractTreeIterator = exports.TreeIterator = void 0;
const tree_1 = require("./tree");
const tree_expansion_1 = require("./tree-expansion");
var TreeIterator;
(function (TreeIterator) {
    TreeIterator.DEFAULT_OPTIONS = {
        pruneCollapsed: false,
        pruneSiblings: false
    };
})(TreeIterator = exports.TreeIterator || (exports.TreeIterator = {}));
class AbstractTreeIterator {
    constructor(root, options) {
        this.root = root;
        this.options = {
            ...TreeIterator.DEFAULT_OPTIONS,
            ...options
        };
        this.delegate = this.iterator(this.root);
    }
    // tslint:disable-next-line:typedef
    [Symbol.iterator]() {
        return this.delegate;
    }
    next() {
        return this.delegate.next();
    }
    children(node) {
        if (!tree_1.CompositeTreeNode.is(node)) {
            return undefined;
        }
        if (this.options.pruneCollapsed && this.isCollapsed(node)) {
            return undefined;
        }
        return node.children.slice();
    }
    isCollapsed(node) {
        return tree_expansion_1.ExpandableTreeNode.isCollapsed(node);
    }
    isEmpty(nodes) {
        return nodes === undefined || nodes.length === 0;
    }
}
exports.AbstractTreeIterator = AbstractTreeIterator;
class DepthFirstTreeIterator extends AbstractTreeIterator {
    iterator(root) {
        return Iterators.depthFirst(root, this.children.bind(this));
    }
}
exports.DepthFirstTreeIterator = DepthFirstTreeIterator;
class BreadthFirstTreeIterator extends AbstractTreeIterator {
    iterator(root) {
        return Iterators.breadthFirst(root, this.children.bind(this));
    }
}
exports.BreadthFirstTreeIterator = BreadthFirstTreeIterator;
/**
 * This tree iterator visits all nodes from top to bottom considering the following rules.
 *
 * Let assume the following tree:
 * ```
 *   R
 *   |
 *   +---1
 *   |   |
 *   |   +---1.1
 *   |   |
 *   |   +---1.2
 *   |   |
 *   |   +---1.3
 *   |   |    |
 *   |   |    +---1.3.1
 *   |   |    |
 *   |   |    +---1.3.2
 *   |   |
 *   |   +---1.4
 *   |
 *   +---2
 *       |
 *       +---2.1
 * ```
 * When selecting `1.2` as the root, the normal `DepthFirstTreeIterator` would stop on `1.2` as it does not have children,
 * but this iterator will visit the next sibling (`1.3` and `1.4` but **not** `1.1`) nodes. So the expected traversal order will be
 * `1.2`, `1.3`, `1.3.1`, `1.3.2`,  and `1.4` then jumps to `2` and continues with `2.1`.
 */
class TopDownTreeIterator extends AbstractTreeIterator {
    iterator(root) {
        const doNext = this.doNext.bind(this);
        return (function* () {
            let next = root;
            while (next) {
                yield next;
                next = doNext(next);
            }
        }).bind(this)();
    }
    doNext(node) {
        return this.findFirstChild(node) || this.findNextSibling(node);
    }
    findFirstChild(node) {
        return (this.children(node) || [])[0];
    }
    findNextSibling(node) {
        if (!node) {
            return undefined;
        }
        if (this.options.pruneSiblings && node === this.root) {
            return undefined;
        }
        if (node.nextSibling) {
            return node.nextSibling;
        }
        return this.findNextSibling(node.parent);
    }
}
exports.TopDownTreeIterator = TopDownTreeIterator;
/**
 * Unlike other tree iterators, this does not visit all the nodes, it stops once it reaches the root node
 * while traversing up the tree hierarchy in an inverse pre-order fashion. This is the counterpart of the `TopDownTreeIterator`.
 */
class BottomUpTreeIterator extends AbstractTreeIterator {
    iterator(root) {
        const doNext = this.doNext.bind(this);
        return (function* () {
            let next = root;
            while (next) {
                yield next;
                next = doNext(next);
            }
        }).bind(this)();
    }
    doNext(node) {
        const previousSibling = node.previousSibling;
        const lastChild = this.lastChild(previousSibling);
        return lastChild || node.parent;
    }
    lastChild(node) {
        const children = node ? this.children(node) : [];
        if (this.isEmpty(children)) {
            return node;
        }
        if (tree_1.CompositeTreeNode.is(node)) {
            const lastChild = tree_1.CompositeTreeNode.getLastChild(node);
            return this.lastChild(lastChild);
        }
        return undefined;
    }
}
exports.BottomUpTreeIterator = BottomUpTreeIterator;
var Iterators;
(function (Iterators) {
    /**
     * Generator for depth first, pre-order tree traversal iteration.
     */
    function* depthFirst(root, children, include = () => true) {
        let stack = [];
        stack.push(root);
        while (stack.length > 0) {
            const top = stack.pop();
            yield top;
            stack = stack.concat((children(top) || []).filter(include).reverse());
        }
    }
    Iterators.depthFirst = depthFirst;
    /**
     * Generator for breadth first tree traversal iteration.
     */
    function* breadthFirst(root, children, include = () => true) {
        let queue = [];
        queue.push(root);
        while (queue.length > 0) {
            const head = queue.shift();
            yield head;
            queue = queue.concat((children(head) || []).filter(include));
        }
    }
    Iterators.breadthFirst = breadthFirst;
    /**
     * Returns with the iterator of the argument.
     */
    function asIterator(elements) {
        return elements.slice()[Symbol.iterator]();
    }
    Iterators.asIterator = asIterator;
    /**
     * Returns an iterator that cycles indefinitely over the elements of iterable.
     *  - If `start` is given it starts the iteration from that element. Otherwise, it starts with the first element of the array.
     *  - If `start` is given, it must contain by the `elements` array. Otherwise, an error will be thrown.
     *
     * **Warning**: Typical uses of the resulting iterator may produce an infinite loop. You should use an explicit break.
     */
    function* cycle(elements, start) {
        const copy = elements.slice();
        let index = !!start ? copy.indexOf(start) : 0;
        if (index === -1) {
            throw new Error(`${start} is not contained in ${copy}.`);
        }
        while (true) {
            yield copy[index];
            index++;
            if (index === copy.length) {
                index = 0;
            }
        }
    }
    Iterators.cycle = cycle;
})(Iterators = exports.Iterators || (exports.Iterators = {}));
//# sourceMappingURL=tree-iterator.js.map