/* non-recursive internal search function
[ nodes | objects ] = searchSubtree(rectangle, [return node data], [array to fill], root to begin search at)
@private
496554
function (rect, returnNode, returnArray, root) {
    var hitStack = []; // Contains the elements that overlap

    if (!rectangle.overlapRectangle(rect, root)) {
      return returnArray;
    }


    hitStack.push(root.nodes);

    while (hitStack.length > 0) {
      var nodes = hitStack.pop();

      for (var i = nodes.length - 1; i >= 0; i--) {
        var ltree = nodes[i];
        if (rectangle.overlapRectangle(rect, ltree)) {
          if ('nodes' in ltree) { // Not a Leaf
            hitStack.push(ltree.nodes);
          } else if ('leaf' in ltree) { // A Leaf !!
            if (!returnNode) {
              returnArray.push(ltree.leaf);
            } else {
              returnArray.push(ltree);
            }
          }
        }
      }
    }

    return returnArray;
  }
777523
function traverseRecursive(rootNode, options) {
  options = extend({
    subnodesAccessor: function(node) { return node.subnodes; },
    onNode: function(node, callback, userdata) {},
    onComplete: function(rootNode) {},
    userdata: null
  }, options);

  (function visitNode(node, callback) {
    var subnodes = options.subnodesAccessor(node);
    async.eachSeries(subnodes, function(subnode, next) {
      visitNode(subnode, function() {
        async.setImmediate(next);
      });
    },
    function() {
      options.onNode(node, function() {
        async.setImmediate(callback);
      }, options.userdata);
    });
  })(rootNode, function() {
    options.onComplete(rootNode);
  });
}
270914
def searchRootOfTree(reducibleChildren: Set[LNode], nodeFromTree: LNode):
    

    while True:
        out_e = nodeFromTree.east[0].outgoingEdges
        # node has no successors
        if not out_e:
            return nodeFromTree

        nextNode = out_e[0].dsts[0].parentNode
        if nextNode in reducibleChildren:
            # can reduce node, walk the tree to root
            nodeFromTree = nextNode
        else:
            # can not reduce, return last root of tree
            return nodeFromTree
23023
function arrayTreeFilter (data, filterFn, options) {
    options = options || {}
    options.childrenKeyName = options.childrenKeyName || 'children'
    let children = data || []
    const result = []
    let level = 0
    do {
        const foundItem = children.filter(function (item) {
            return filterFn(item, level)
        })[0]
        if (!foundItem) {
            break
        }
        result.push(foundItem)
        children = foundItem[options.childrenKeyName] || []
        level += 1
    } while (children.length > 0)
    return result
}
171046
function(nodeList, parent) {
            // One level down
            nodeDepth++;

            // Create corresponding tree node if not already there for this depth
            if(!tree[nodeDepth]) {
                tree[nodeDepth] = [];
            }


            // Parse each node at this depth for attributes and any children
            for(var j=0; j<nodeList.length; j++) {
                var currentNode = nodeList[j];

                // Instantiate a new Column for each node
                var oColumn = new YAHOO.widget.Column(currentNode);
                
                // Cross-reference Column ID back to the original object literal definition
                currentNode.yuiColumnId = oColumn._sId;
                
                // Add the new Column to the flat list
                flat.push(oColumn);

                // Assign its parent as an attribute, if applicable
                if(parent) {
                    oColumn._oParent = parent;
                }

                // The Column has descendants
                if(YAHOO.lang.isArray(currentNode.children)) {
                    oColumn.children = currentNode.children;

                    // Determine COLSPAN value for this Column
                    var terminalChildNodes = 0;
                    var countTerminalChildNodes = function(ancestor) {
                        var descendants = ancestor.children;
                        // Drill down each branch and count terminal nodes
                        for(var k=0; k<descendants.length; k++) {
                            // Keep drilling down
                            if(YAHOO.lang.isArray(descendants[k].children)) {
                                countTerminalChildNodes(descendants[k]);
                            }
                            // Reached branch terminus
                            else {
                                terminalChildNodes++;
                            }
                        }
                    };
                    countTerminalChildNodes(currentNode);
                    oColumn._nColspan = terminalChildNodes;

                    // Cascade certain properties to children if not defined on their own
                    var currentChildren = currentNode.children;
                    for(var k=0; k<currentChildren.length; k++) {
                        var child = currentChildren[k];
                        if(oColumn.className && (child.className === undefined)) {
                            child.className = oColumn.className;
                        }
                        if(oColumn.editor && (child.editor === undefined)) {
                            child.editor = oColumn.editor;
                        }
                        //TODO: Deprecated
                        if(oColumn.editorOptions && (child.editorOptions === undefined)) {
                            child.editorOptions = oColumn.editorOptions;
                        }
                        if(oColumn.formatter && (child.formatter === undefined)) {
                            child.formatter = oColumn.formatter;
                        }
                        if(oColumn.resizeable && (child.resizeable === undefined)) {
                            child.resizeable = oColumn.resizeable;
                        }
                        if(oColumn.sortable && (child.sortable === undefined)) {
                            child.sortable = oColumn.sortable;
                        }
                        if(oColumn.hidden) {
                            child.hidden = true;
                        }
                        if(oColumn.width && (child.width === undefined)) {
                            child.width = oColumn.width;
                        }
                        if(oColumn.minWidth && (child.minWidth === undefined)) {
                            child.minWidth = oColumn.minWidth;
                        }
                        if(oColumn.maxAutoWidth && (child.maxAutoWidth === undefined)) {
                            child.maxAutoWidth = oColumn.maxAutoWidth;
                        }
                        // Backward compatibility
                        if(oColumn.type && (child.type === undefined)) {
                            child.type = oColumn.type;
                        }
                        if(oColumn.type && !oColumn.formatter) {
                            YAHOO.log("The property type has been" +
                            " deprecated in favor of formatter", "warn", oColumn.toString());
                            oColumn.formatter = oColumn.type;
                        }
                        if(oColumn.text && !YAHOO.lang.isValue(oColumn.label)) {
                            YAHOO.log("The property text has been" +
                            " deprecated in favor of label", "warn", oColumn.toString());
                            oColumn.label = oColumn.text;
                        }
                        if(oColumn.parser) {
                            YAHOO.log("The property parser is no longer supported",
                            "warn", this.toString());
                        }
                        if(oColumn.sortOptions && ((oColumn.sortOptions.ascFunction) ||
                                (oColumn.sortOptions.descFunction))) {
                            YAHOO.log("The properties sortOptions.ascFunction and " +
                            " sortOptions.descFunction have been deprecated in favor " +
                            " of sortOptions.sortFunction", "warn", oColumn.toString());
                        }
                    }

                    // The children themselves must also be parsed for Column instances
                    if(!tree[nodeDepth+1]) {
                        tree[nodeDepth+1] = [];
                    }
                    parseColumns(currentChildren, oColumn);
                }
                // This Column does not have any children
                else {
                    oColumn._nKeyIndex = keys.length;
                    oColumn._nColspan = 1;
                    keys.push(oColumn);
                }

                // Add the Column to the top-down tree
                tree[nodeDepth].push(oColumn);
            }
            nodeDepth--;
        }
1017728
public static OrganigramNode findTreeNode(OrganigramNode searchRoot, String rowKey) {

        if (rowKey == null || searchRoot == null) {
            return null;
        }

        if (searchRoot.getRowKey().equals(rowKey)) {
            return searchRoot;
        }

        if (searchRoot.getChildren() != null) {
            for (OrganigramNode child : searchRoot.getChildren()) {
                OrganigramNode childResult = findTreeNode(child, rowKey);
                if (childResult != null) {
                    return childResult;
                }
            }
        }

        return null;
    }
55023
function _collapseTree(node: TreeNode, depth: number): TreeNode {
  // Node is a folder.
  if (node.type === "directory") {
    if (!Array.isArray(node.contents)) {
      console.log(`Expected array at: ${node.path}`);
    }

    // Node is not a root/domain node, and only contains 1 item.
    if (depth > 1 && node.contents.length === 1) {
      const next = node.contents[0];
      // Do not collapse if the next node is a leaf node.
      if (next.type === "directory") {
        if (!Array.isArray(next.contents)) {
          console.log(
            `Expected array at: ${next.name} -- ${
              node.name
            } -- ${JSON.stringify(next.contents)}`
          );
        }
        const name = `${node.name}/${next.name}`;
        const nextNode = createDirectoryNode(name, next.path, next.contents);
        return _collapseTree(nextNode, depth + 1);
      }
    }

    // Map the contents.
    return createDirectoryNode(
      node.name,
      node.path,
      node.contents.map(next => _collapseTree(next, depth + 1))
    );
  }

  // Node is a leaf, not a folder, do not modify it.
  return node;
}
784752
function depth(root) {
	let i = 0;
	let walker = document.createTreeWalker(root, 0xFFFFFFFF, {
		acceptNode: function(node){
			let nt = node.nodeType;
			return nt === 1 || nt === 3;
		}
	});

	while(walker.nextNode()) {
		i++;
	}
	return i;
}
1228499
function createBlockLookup(tree) {
	const lookup = new Map();

	tree.walk(node => {
		const classNames = node.classList;
		if (classNames.length) {
			// guess best block name from class or use parent’s block name
			lookup.set(node,
				find(classNames, blockCandidates1)
				|| find(classNames, blockCandidates2)
				|| lookup.get(node.parent)
			);
		}
	});

	return lookup;
}
1007683
private static Treenode search(Iterable<Treenode> root, String text, ITreenodeSearch search) {
        for (Treenode node : root) {
            if (search.isMatch(node, text)) {
                return node;
            }
        }
        return null;
    }
1359314
public void setSearchSubtree(boolean searchSubtree) {
        int searchScope = searchSubtree ? SearchControls.SUBTREE_SCOPE : SearchControls.ONELEVEL_SCOPE;
        searchControls.setSearchScope(searchScope);
    }
793036
function(str, pos) {
    var T = this, k, child;
    if (str.length == 0) {
      if (pos === undefined) {
        return T.getAllWords(str);
      } else {
        return [];
      }
    }
    if (pos === undefined) {
      pos = 0;
    }
    k = str[pos];
    child = T.children[k];
    if (child === undefined) {
      //node doesn't exist
      return [];
    }
    if (pos === str.length - 1) {
      return child.getAllWords(str);
    }
    return child.autoComplete(str, pos + 1);
  }
980123
function searchListenerTree(handlers, type, tree, i) {
    if (!tree) {
      return [];
    }
    var listeners=[], leaf, len, branch, xTree, xxTree, isolatedBranch, endReached,
        typeLength = type.length, currentType = type[i], nextType = type[i+1];
    if (i === typeLength && tree._listeners) {
      //
      // If at the end of the event(s) list and the tree has listeners
      // invoke those listeners.
      //
      if (typeof tree._listeners === 'function') {
        handlers && handlers.push(tree._listeners);
        return [tree];
      } else {
        for (leaf = 0, len = tree._listeners.length; leaf < len; leaf++) {
          handlers && handlers.push(tree._listeners[leaf]);
        }
        return [tree];
      }
    }

    if ((currentType === '*' || currentType === '**') || tree[currentType]) {
      //
      // If the event emitted is '*' at this part
      // or there is a concrete match at this patch
      //
      if (currentType === '*') {
        for (branch in tree) {
          if (branch !== '_listeners' && tree.hasOwnProperty(branch)) {
            listeners = listeners.concat(searchListenerTree(handlers, type, tree[branch], i+1));
          }
        }
        return listeners;
      } else if(currentType === '**') {
        endReached = (i+1 === typeLength || (i+2 === typeLength && nextType === '*'));
        if(endReached && tree._listeners) {
          // The next element has a _listeners, add it to the handlers.
          listeners = listeners.concat(searchListenerTree(handlers, type, tree, typeLength));
        }

        for (branch in tree) {
          if (branch !== '_listeners' && tree.hasOwnProperty(branch)) {
            if(branch === '*' || branch === '**') {
              if(tree[branch]._listeners && !endReached) {
                listeners = listeners.concat(searchListenerTree(handlers, type, tree[branch], typeLength));
              }
              listeners = listeners.concat(searchListenerTree(handlers, type, tree[branch], i));
            } else if(branch === nextType) {
              listeners = listeners.concat(searchListenerTree(handlers, type, tree[branch], i+2));
            } else {
              // No match on this one, shift into the tree but not in the type array.
              listeners = listeners.concat(searchListenerTree(handlers, type, tree[branch], i));
            }
          }
        }
        return listeners;
      }

      listeners = listeners.concat(searchListenerTree(handlers, type, tree[currentType], i+1));
    }

    xTree = tree['*'];
    if (xTree) {
      //
      // If the listener tree will allow any match for this part,
      // then recursively explore all branches of the tree
      //
      searchListenerTree(handlers, type, xTree, i+1);
    }

    xxTree = tree['**'];
    if(xxTree) {
      if(i < typeLength) {
        if(xxTree._listeners) {
          // If we have a listener on a '**', it will catch all, so add its handler.
          searchListenerTree(handlers, type, xxTree, typeLength);
        }

        // Build arrays of matching next branches and others.
        for(branch in xxTree) {
          if(branch !== '_listeners' && xxTree.hasOwnProperty(branch)) {
            if(branch === nextType) {
              // We know the next element will match, so jump twice.
              searchListenerTree(handlers, type, xxTree[branch], i+2);
            } else if(branch === currentType) {
              // Current node matches, move into the tree.
              searchListenerTree(handlers, type, xxTree[branch], i+1);
            } else {
              isolatedBranch = {};
              isolatedBranch[branch] = xxTree[branch];
              searchListenerTree(handlers, type, { '**': isolatedBranch }, i+1);
            }
          }
        }
      } else if(xxTree._listeners) {
        // We have reached the end and still on a '**'
        searchListenerTree(handlers, type, xxTree, typeLength);
      } else if(xxTree['*'] && xxTree['*']._listeners) {
        searchListenerTree(handlers, type, xxTree['*'], typeLength);
      }
    }

    return listeners;
  }
989199
function dom (tree, node, data) {
  let findElseBranch = false
  let logical = false

  function getValue (data, info, str) {
    if (!EQ_RE.test(str)) return str
    let exp = str.replace(EQ_RE, '')
    if (FMT_RE.test(exp)) exp = '__format(' + exp + ')'
    logical = true
    const value = common.scopedExpression(data, info, exp)
    return value // he.escape(value + '')
  }

  function compile (child, index) {
    // if (child.dom) return node.appendChild(child.dom)
    const locationData = { pos: child.pos || {}, location }

    // if (child.unescaped) {
    //  child.content = he.escape(child.content)
    // }

    const firstLetter = child.tagOrSymbol.charCodeAt(0)

    //
    // first handle any flow control statements
    //
    if (child.tagOrSymbol === 'else') {
      if (!findElseBranch) return

      logical = true
      // if this is an else-if
      if (IF_RE.test(child.content)) {
        const exp = child.content.replace(IF_RE, '')
        if (common.scopedExpression(data, locationData, exp)) {
          findElseBranch = false
          const branch = document.createDocumentFragment()
          const children = dom(child, branch, data)
          if (children) node.appendChild(branch)
        }
        return
      }

      findElseBranch = false
      const branch = document.createDocumentFragment()
      const children = dom(child, branch, data)
      if (children) node.appendChild(branch)
      return
    }

    if (child.tagOrSymbol === 'comment') {
      const comment = document.createComment(child.content)
      node.appendChild(comment)
      return
    }

    if (child.tagOrSymbol === 'if') {
      logical = true
      if (common.scopedExpression(data, locationData, child.content)) {
        const branch = document.createDocumentFragment()
        const children = dom(child, branch, data)
        if (children) node.appendChild(branch)
        return
      }
      findElseBranch = true
      return
    }

    if (child.tagOrSymbol === 'while') {
      logical = true
      while (common.scopedExpression(data, locationData, child.content)) {
        const children = dom(child, node, data)
        if (children) node.appendChild(children)
      }
      return
    }

    if (child.tagOrSymbol === 'for') {
      logical = true

      const parts = child.content.split(IN_RE)
      if (!parts[0]) common.die(locationData, 'TypeError', 'Unknown mixin')

      const object = common.scopedExpression(data, locationData, parts[1])

      common.each(object, function (val, key) {
        // determine if there are identifiers for key and value
        const identifiers = parts[0].split(',')
        const keyIdentifier = identifiers[0]
        const valIdentifier = identifiers[1]
        const locals = { [keyIdentifier]: key }

        if (valIdentifier) {
          locals[valIdentifier] = val
        }
        // create a new shallow scope so that locals don't persist
        const scope = Object.assign({}, data, locals)
        const children = dom(child, node, scope)
        if (children) node.appendChild(children)
      })
      return
    }

    if (child.tagOrSymbol === 'each') {
      common.die(locationData, 'TypeError', 'Each not supported (use for)')
    }

    // treat all piped text as plain content
    if (child.tagOrSymbol === '|') {
      return (node.textContent += getValue(data, locationData, child.content))
    }

    if (firstLetter === HYPHEN) {
      common.die(locationData, 'Error', 'No inline code!')
    }

    /* if (firstLetter === COLON && cb) {
      logical = true
      const name = 'jstransformer-' + child.tagOrSymbol.slice(1)
      let t = null
      try {
        t = transformer(require(name))
      } catch (ex) {
        common.die(child.pos, 'Error', fmt('%s not installed', name))
      }
      const path = child.content
      const data = cb({ path, location })
      const parsed = t.render(data.tree, child.attributes)
      node.textContent += parsed.body
      return
    }

    // anything prefixed with '+' is a mixin call.
    if (firstLetter === PLUS && cb) {
      logical = true
      const name = child.tagOrSymbol.slice(1)
      if (!cache[name]) {
        common.die(child.pos, 'TypeError', 'Unknown mixin')
      }

      const locals = {}
      const args = Object.keys(child.attributes).map(attr => {
        return common.scopedExpression(data, child.pos, attr)
      })

      cache[name].keys.map((k, index) => (locals[k] = args[index]))
      const scope = Object.assign({}, data, locals)
      const children = dom(cache[name].child, node, scope)
      node.appendChild(children)
      return
    } */

    // defines a mixin
    if (firstLetter >= A && firstLetter <= Z) {
      logical = true
      const keys = Object.keys(child.attributes)
      cache[child.tagOrSymbol] = { child, keys }
      return
    }

    //
    // everything else is a tag
    //
    const props = common.resolveTagOrSymbol(child.tagOrSymbol)

    let el = document.createElement(props.tagname)

    if (props.id) el.id = props.id
    if (props.classname) el.className = props.classname

    if (child.attributes) {
      Object.keys(child.attributes).map(key => {
        let value = child.attributes[key]

        // if this attribute is a boolean, make its value its key
        if (typeof value === 'boolean') {
          el.setAttribute(key, key)
        }

        if (value) {
          // all values are expressions
          value = common.scopedExpression(data, locationData, value)
          // a class should not be empty
          if (key === 'class' && !value) return

          // data-* attributes should be escaped
          if (key.indexOf('data-') === 0) {
            if (typeof value !== 'string' && typeof value !== 'number') {
              value = JSON.stringify(value)
            }
          }
        }
        el.setAttribute(key, value)
      })
    }

    if (child.content) {
      el.textContent = (child.tagOrSymbol === 'script')
        ? child.content
        : getValue(data, locationData, child.content)
    }

    // nothing left to decide, recurse if there are child nodes
    if (child.children.length) {
      const children = dom(child, el, data)
      if (children) node.appendChild(children)
    }

    // if this is not a logical node, we can make an optimization
    // if (!logical) child.dom = el
    node.appendChild(el)
  }

  if (tree.children && tree.children.length) {
    tree.children.map(compile)
  }
  return node
}
1135233
function (callback, ctx) {
            var depth, node;
            for (depth = 0, node = this; node !== null; node = node.parent(), depth++)
                ctx = callback(depth, node, ctx);
            return ctx;
        }
1039302
function(tree) {
            var maxRowDepth = 1;
            var currentRow;
            var currentColumn;

            // Calculate the max depth of descendants for this row
            var countMaxRowDepth = function(row, tmpRowDepth) {
                tmpRowDepth = tmpRowDepth || 1;

                for(var n=0; n<row.length; n++) {
                    var col = row[n];
                    // Column has children, so keep counting
                    if(YAHOO.lang.isArray(col.children)) {
                        tmpRowDepth++;
                        countMaxRowDepth(col.children, tmpRowDepth);
                        tmpRowDepth--;
                    }
                    // No children, is it the max depth?
                    else {
                        if(tmpRowDepth > maxRowDepth) {
                            maxRowDepth = tmpRowDepth;
                        }
                    }

                }
            };

            // Count max row depth for each row
            for(var m=0; m<tree.length; m++) {
                currentRow = tree[m];
                countMaxRowDepth(currentRow);

                // Assign the right ROWSPAN values to each Column in the row
                for(var p=0; p<currentRow.length; p++) {
                    currentColumn = currentRow[p];
                    if(!YAHOO.lang.isArray(currentColumn.children)) {
                        currentColumn._nRowspan = maxRowDepth;
                    }
                    else {
                        currentColumn._nRowspan = 1;
                    }
                }

                // Reset counter for next row
                maxRowDepth = 1;
            }
        }
482387
function flattenTree(root) {
  let newChildren = [];
  root.children.forEach(child => {
    const commonParent = getDeepMoreThenOneChild(child);
    if (commonParent.children.length === 0) {
      newChildren.push(commonParent);
    } else {
      newChildren = newChildren.concat(commonParent.children);
    }
  });
  root.children = newChildren;
}