@doc
Implementation based on <http://www.gossamer-threads.com/lists/linux/kernel/667935>

 
Tree

Implements the interface of BinarySearchTree.Tree

An implementation of an in memory B-Tree.
973911
function(order,f) {
    if(arguments.length != 0) {
        this.order = order;
        this.root = this._allocateNode();
        this.root.isLeaf = true;
        this.root.level = 0;
        var that = this;
        this._diskWrite(this.root, function(root){
            that.root = root;
            that._updateRootNode(that.root, function(n){
                that.comparator = function(a,b) {
                    if(a < b) {
                        return -1;
                    } else if(a > b){
                        return 1;
                    } else {
                        return 0;
                    }
                };
                that.merger = null;
                // we notify we are ready
                if(f!=null) {
                    f(that);
                }
            })});
    }
}
1169421
public static void main(String[] args) {
    try {
      TreeReader tr = new PennTreeReader(new StringReader("(S (NP (NNP Sam)) (VP (VBD died) (NP (NN today))))"), new LabeledScoredTreeFactory());
      Tree t = tr.readTree();
      System.out.println(t);
      TreeGraphNode tgn = new TreeGraphNode(t, (TreeGraphNode) null);
      System.out.println(tgn.toPrettyString(0));
      tgn.indexNodes();
      System.out.println(tgn.toPrettyString(0));
      tgn.percolateHeads(new SemanticHeadFinder());
      System.out.println(tgn.toPrettyString(0));
    } catch (Exception e) {
      System.err.println("Horrible error: " + e);
      e.printStackTrace();
    }
  }
1238438
private static List<Tree<Node>> getNewTree(Tree<Node> inst){	
		delDefault(inst);
		List<Tree<Node>> newTreeList = new ArrayList<Tree<Node>>();
		List<Tree<Node>> children = new ArrayList<Tree<Node>>();
		if(!inst.isLeaf()&&!inst.getFirstChild().isLeaf()){
			boolean hasPu = false;
			Tree<Node> newInst=null;
			for(int i=0;i<inst.getFirstChild().children.size();i++){
				children.add(inst.getFirstChild().getChild(i));				
				String tag = inst.getFirstChild().getLabel().getTag();
				String flag0 = inst.getFirstChild().getChild(i).getLabel().getTag();
				String data0 = inst.getFirstChild().getChild(i).getLabel().getData();			
				if(flag0.equals("PU")&&
						(data0.equals("，")
						||data0.equals("；")
						||data0.equals("、")
						||data0.equals("。")
						||data0.equals("！")
						||data0.equals("？"))){
					hasPu = true;
					if(children.size()!=0)
						newInst = new Tree<Node>(new Node(tag,"",0),children);
					else
						newInst = new Tree<Node>(new Node(tag,"",0));
					
					newTreeList.add(newInst);
					children = new ArrayList<Tree<Node>>();
				}				
			}
			if(!hasPu)
				newTreeList.add(inst);
		}
		return newTreeList;
	}
245031
public Iterable<? extends TypeElement> enter(Iterable<? extends CompilationUnitTree> trees)
        throws IOException
    {
        if (trees == null && notYetEntered != null && notYetEntered.isEmpty())
            return List.nil();

        prepareCompiler();

        ListBuffer<JCCompilationUnit> roots = null;

        if (trees == null) {
            // If there are still files which were specified to be compiled
            // (i.e. in fileObjects) but which have not yet been entered,
            // then we make sure they have been parsed and add them to the
            // list to be entered.
            if (notYetEntered.size() > 0) {
                if (!parsed)
                    parse(); // TODO would be nice to specify files needed to be parsed
                for (JavaFileObject file: fileObjects) {
                    JCCompilationUnit unit = notYetEntered.remove(file);
                    if (unit != null) {
                        if (roots == null)
                            roots = new ListBuffer<JCCompilationUnit>();
                        roots.append(unit);
                    }
                }
                notYetEntered.clear();
            }
        }
        else {
            for (CompilationUnitTree cu : trees) {
                if (cu instanceof JCCompilationUnit) {
                    if (roots == null)
                        roots = new ListBuffer<JCCompilationUnit>();
                    roots.append((JCCompilationUnit)cu);
                    notYetEntered.remove(cu.getSourceFile());
                }
                else
                    throw new IllegalArgumentException(cu.toString());
            }
        }

        if (roots == null)
            return List.nil();

        try {
            List<JCCompilationUnit> units = compiler.enterTrees(roots.toList());

            if (notYetEntered.isEmpty())
                compiler = compiler.processAnnotations(units);

            ListBuffer<TypeElement> elements = new ListBuffer<TypeElement>();
            for (JCCompilationUnit unit : units) {
                for (JCTree node : unit.defs) {
                    if (node.hasTag(JCTree.Tag.CLASSDEF)) {
                        JCClassDecl cdef = (JCClassDecl) node;
                        if (cdef.sym != null) // maybe null if errors in anno processing
                            elements.append(cdef.sym);
                    }
                }
            }
            return elements.toList();
        }
        finally {
            compiler.log.flush();
        }
    }
580499
def remodelTreeRemovingRoot(root, node):
    
    import bioio
    assert root.traversalID.mid != node
    hash = {}
    def fn(bT):
        if bT.traversalID.mid == node:
            assert bT.internal == False
            return [ bT ]
        elif bT.internal:
            i = fn(bT.left)
            if i is None:
                i = fn(bT.right)
            if i is not None:
                hash[i[-1]]= bT
                i.append(bT)
            return  i
        return None
    l = fn(root)
    def fn2(i, j):
        if i.left == j:
            return i.right
        assert i.right == j
        return i.left
    def fn3(bT):
        if hash[bT] == root:
            s = '(' + bioio.printBinaryTree(fn2(hash[bT], bT), bT, True)[:-1] + ')'
        else:
            s = '(' + bioio.printBinaryTree(fn2(hash[bT], bT), bT, True)[:-1] + ',' + fn3(hash[bT]) + ')'
        return s + ":" + str(bT.distance)
    s = fn3(l[0]) + ';'
    t = bioio.newickTreeParser(s)
    return t
387505
@SuppressWarnings("unchecked")
    public <T extends TreeNode> TreeNode treeFrom(Object source)
            throws IOException, JSONObjectException
    {
        if (_treeCodec == null) {
             _noTreeCodec("read TreeNode");
        }
        if (source instanceof JsonParser) {
            JsonParser p = _initForReading((JsonParser) source);
            T result = (T) _treeCodec.readTree(p);
            p.clearCurrentToken();
            return result;
        }
        JsonParser p = _parser(source);
        try {
            _initForReading(_config(p));
            T result = (T) _treeCodec.readTree(p);
            JsonParser p0 = p;
            p = null;
            _close(p0, null);
            return result;
        } catch (Exception e) {
            _close(p, e);
            return null;
        }
    }
404650
def tree_to_graph(bbltree:BubbleTree) -> Graph or Digraph:
    
    GraphObject = Digraph if bbltree.oriented else Graph
    def create(name:str):
        """Return a graphviz graph figurating a powernode"""
        ret = GraphObject('cluster_' + name)
        # dirty hack to get links between clusters: add a blank node inside
        # so the subgraph don't take it's name directly, but the blank node do.
        # ret.body.append('label = "{}"'.format(name))  # replaced by:
        ret.node(name, style='invis', shape='point')
        # ret.body.append('style=plaintext')
        ret.body.append('color=lightgrey')
        ret.body.append('label=""')
        ret.body.append('shape=ellipse')
        ret.body.append('penwidth=2')
        ret.body.append('pencolor=black')
        return ret
    nodes = frozenset(bbltree.nodes())
    subgraphs = {}
    # build for each powernode the associated subgraph, and add its successors
    for powernode in bbltree.powernodes():
        if powernode not in subgraphs:
            subgraphs[powernode] = create(powernode)
        for succ in bbltree.inclusions[powernode]:
            if succ not in subgraphs:
                if succ not in nodes:
                    subgraphs[succ] = create(succ)
                else:
                    subgraphs[powernode].node(succ)
    # add to Graph instances the Graph of successors as subgraphs 
    for powernode, succs in bbltree.inclusions.items():
        for succ in succs:
            if succ not in nodes:
                subgraphs[powernode].subgraph(subgraphs[succ])
    # build the final graph by adding to it subgraphs of roots
    graph = GraphObject('graph', graph_attr={'compound': 'true'})
    for root in bbltree.roots:
        if root in subgraphs:
            graph.subgraph(subgraphs[root])
    # add the edges to the final graph
    for source, targets in bbltree.edges.items():
        for target in targets:
            if source <= target:
                attrs = {}
                if source not in nodes:
                    attrs.update({'ltail': 'cluster_' + source})
                if target not in nodes:
                    attrs.update({'lhead': 'cluster_' + target})
                graph.edge(source, target, **attrs)
    # print(graph)  # debug line
    # graph.view()  # debug line
    return graph
887929
public IntArrayList bfs(int root, boolean isRootT1, boolean[] marked1, boolean[] marked2) {
        IntArrayList ccorder = new IntArrayList();
        Queue<Integer> qNode = new ArrayDeque<>();
        Queue<Boolean> qIsT1 = new ArrayDeque<>();
        qNode.add(root);
        qIsT1.add(isRootT1);

        while (!qNode.isEmpty()) {
            // Process the next node in the queue.
            int parent = qNode.remove();
            boolean isT1 = qIsT1.remove();

            if (isT1) {
                // Visit node only if not marked.
                if (!marked1[parent]) {
                    log.trace("Visiting node {} of type T1", parent);
                    // For each neighbor...
                    for (int nb = 0; nb < this.numNbsT1(parent); nb++) {
                        int e = this.edgeT1(parent, nb);
                        int child = this.childE(e);
                        if (!marked2[child]) {
                            // If the neighbor is not marked, queue the node and add the edge to
                            // the order.
                            qNode.add(child);
                            qIsT1.add(false);
                            ccorder.add(e);
                        }
                    }
                    // Mark the node as visited.
                    marked1[parent] = true;
                }
            } else {
                // Visit node only if not marked.
                if (!marked2[parent]) {
                    log.trace("Visiting node {} of type T2", parent);
                    // For each neighbor...
                    for (int nb = 0; nb < this.numNbsT2(parent); nb++) {
                        int e = this.edgeT2(parent, nb);
                        int child = this.childE(e);
                        if (!marked1[child]) {
                            // If the neighbor is not marked, queue the node and add the edge to
                            // the order.
                            qNode.add(child);
                            qIsT1.add(true);
                            ccorder.add(e);
                        }
                    }
                    // Mark the node as visited.
                    marked2[parent] = true;
                }
            }
        }
        return ccorder;
    }
575484
private static <T> Optional<T> lowestCommonAncestor(TreeDef.Parented<T> treeDef, T nodeA, T nodeB) {
		class TreeSearcher {
			private T tip;
			private final Set<T> visited;

			public TreeSearcher(T start) {
				this.tip = start;
				this.visited = new HashSet<>();
			}

			public boolean hasMore() {
				return tip != null;
			}

			public Optional<T> march(TreeSearcher other) {
				if (other.visited.contains(tip)) {
					return Optional.of(tip);
				} else {
					visited.add(tip);
					tip = treeDef.parentOf(tip);
					return Optional.empty();
				}
			}
		}

		// make a list of a's parents (bottom of stack is 'a' itself, top of is root)
		TreeSearcher searchA = new TreeSearcher(nodeA);
		TreeSearcher searchB = new TreeSearcher(nodeB);

		Optional<T> commonAncestor = searchB.march(searchA);
		// so long as both searches
		while (searchA.hasMore() && searchB.hasMore()) {
			commonAncestor = searchA.march(searchB);
			if (commonAncestor.isPresent()) {
				return commonAncestor;
			}
			commonAncestor = searchB.march(searchA);
			if (commonAncestor.isPresent()) {
				return commonAncestor;
			}
		}
		while (searchA.hasMore() && !commonAncestor.isPresent()) {
			commonAncestor = searchA.march(searchB);
		}
		while (searchB.hasMore() && !commonAncestor.isPresent()) {
			commonAncestor = searchB.march(searchA);
		}
		return commonAncestor;
	}
1072143
public static <T> T root(TreeDef.Parented<T> treeDef, T node) {
		T lastParent;
		T parent = node;
		do {
			lastParent = parent;
			parent = treeDef.parentOf(lastParent);
		} while (parent != null);
		return lastParent;
	}
883056
public Iterable<? extends Element> enter(Iterable<? extends CompilationUnitTree> trees)
    {
        if (trees == null && notYetEntered != null && notYetEntered.isEmpty())
            return List.nil();

        boolean wasInitialized = compiler != null;

        prepareCompiler(true);

        ListBuffer<JCCompilationUnit> roots = null;

        if (trees == null) {
            // If there are still files which were specified to be compiled
            // (i.e. in fileObjects) but which have not yet been entered,
            // then we make sure they have been parsed and add them to the
            // list to be entered.
            if (notYetEntered.size() > 0) {
                if (!parsed)
                    parseInternal(); // TODO would be nice to specify files needed to be parsed
                for (JavaFileObject file: args.getFileObjects()) {
                    JCCompilationUnit unit = notYetEntered.remove(file);
                    if (unit != null) {
                        if (roots == null)
                            roots = new ListBuffer<>();
                        roots.append(unit);
                    }
                }
                notYetEntered.clear();
            }
        }
        else {
            for (CompilationUnitTree cu : trees) {
                if (cu instanceof JCCompilationUnit) {
                    if (roots == null)
                        roots = new ListBuffer<>();
                    roots.append((JCCompilationUnit)cu);
                    notYetEntered.remove(cu.getSourceFile());
                }
                else
                    throw new IllegalArgumentException(cu.toString());
            }
        }

        if (roots == null) {
            if (trees == null && !wasInitialized) {
                compiler.initModules(List.nil());
            }
            return List.nil();
        }

        List<JCCompilationUnit> units = compiler.initModules(roots.toList());

        try {
            units = compiler.enterTrees(units);

            if (notYetEntered.isEmpty())
                compiler.processAnnotations(units);

            ListBuffer<Element> elements = new ListBuffer<>();
            for (JCCompilationUnit unit : units) {
                boolean isPkgInfo = unit.sourcefile.isNameCompatible("package-info",
                                                                     JavaFileObject.Kind.SOURCE);
                if (isPkgInfo) {
                    elements.append(unit.packge);
                } else {
                    for (JCTree node : unit.defs) {
                        if (node.hasTag(JCTree.Tag.CLASSDEF)) {
                            JCClassDecl cdef = (JCClassDecl) node;
                            if (cdef.sym != null) // maybe null if errors in anno processing
                                elements.append(cdef.sym);
                        } else if (node.hasTag(JCTree.Tag.MODULEDEF)) {
                            JCModuleDecl mdef = (JCModuleDecl) node;
                            if (mdef.sym != null)
                                elements.append(mdef.sym);
                        }
                    }
                }
            }
            return elements.toList();
        }
        finally {
            compiler.log.flush();
        }
    }
738625
function(tree, n, m) {
    return tree[n].fc < tree[m].fc ||
      (tree[n].fc == tree[m].fc && zip_depth[n] <= zip_depth[m]);
}
1014135
private void condenseTree(IndexTreePath<E> subtree, Stack<N> stack) {
    N node = getNode(subtree.getEntry());
    // node is not root
    if(!isRoot(node)) {
      N parent = getNode(subtree.getParentPath().getEntry());
      int index = subtree.getIndex();
      if(hasUnderflow(node)) {
        if(parent.deleteEntry(index)) {
          stack.push(node);
        }
        else {
          node.adjustEntry(parent.getEntry(index));
        }
      }
      else {
        node.adjustEntry(parent.getEntry(index));
      }
      writeNode(parent);
      // get subtree to parent
      condenseTree(subtree.getParentPath(), stack);
    }

    // node is root
    else {
      if(hasUnderflow(node) && node.getNumEntries() == 1 && !node.isLeaf()) {
        N child = getNode(node.getEntry(0));
        final N newRoot;
        if(child.isLeaf()) {
          newRoot = createNewLeafNode();
          newRoot.setPageID(getRootID());
          for(int i = 0; i < child.getNumEntries(); i++) {
            newRoot.addLeafEntry(child.getEntry(i));
          }
        }
        else {
          newRoot = createNewDirectoryNode();
          newRoot.setPageID(getRootID());
          for(int i = 0; i < child.getNumEntries(); i++) {
            newRoot.addDirectoryEntry(child.getEntry(i));
          }
        }
        writeNode(newRoot);
        height--;
      }
    }
  }
996074
final public AuxiliaryTree TreeRoot(boolean requiresFoot) throws ParseException {
 /*@bgen(jjtree) TreeRoot */
  SimpleNode jjtn000 = new SimpleNode(JJTTREEROOT);
  boolean jjtc000 = true;
  jjtree.openNodeScope(jjtn000);Tree t;
    try {
      t = TreeNode();
      jjtree.closeNodeScope(jjtn000, true);
      jjtc000 = false;
      {if (true) return new AuxiliaryTree(t,requiresFoot);}
    } catch (Throwable jjte000) {
    if (jjtc000) {
      jjtree.clearNodeScope(jjtn000);
      jjtc000 = false;
    } else {
      jjtree.popNode();
    }
    if (jjte000 instanceof RuntimeException) {
      {if (true) throw (RuntimeException)jjte000;}
    }
    if (jjte000 instanceof ParseException) {
      {if (true) throw (ParseException)jjte000;}
    }
    {if (true) throw (Error)jjte000;}
    } finally {
    if (jjtc000) {
      jjtree.closeNodeScope(jjtn000, true);
    }
    }
    throw new Error("Missing return statement in function");
  }
722275
boolean isIdenticalTree(MathNode aTree, MathNode bTree) {
        // first check if they have the same number of children
        if (aTree.equals(bTree) && aTree.getChildren().size() == bTree.getChildren().size()) {
            if (aTree.isOrderSensitive()) {
                // all children order sensitive
                for (int i = 0; i < aTree.getChildren().size(); i++) {
                    if (!isIdenticalTree(aTree.getChildren().get(i), bTree.getChildren().get(i))) {
                        return false;
                    }
                }
            } else {
                // order insensitive
                List<MathNode> bChildren = new ArrayList<>(bTree.getChildren());
                OUTER:
                for (MathNode aChild : aTree.getChildren()) {
                    for (MathNode bChild : filterSameChildren(aChild, bChildren)) {
                        if (isIdenticalTree(aChild, bChild)) {
                            // found an identical child
                            bChildren.remove(bChild);
                            continue OUTER;
                        }
                    }
                    // aChild is missing in bChildren
                    return false;
                }
            }
            return true;
        }
        return false;
    }
23056
private int binarySearch(SimpleMDAGNode[] mdagDataArray, char node)
    {
        if (transitionSetSize < 1)
        {
            return -1;
        }
        int high = transitionSetBeginIndex + transitionSetSize - 1;
        int low = transitionSetBeginIndex;
        while (low <= high)
        {
            int mid = ((low + high) >>> 1);
            int cmp = mdagDataArray[mid].getLetter() - node;

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid;
        }
        return -1;
    }
440013
def _bfs_from_cluster_tree(tree, bfs_root):
    

    result = []
    to_process = [bfs_root]

    while to_process:
        result.extend(to_process)
        to_process = tree['child'][np.in1d(tree['parent'], to_process)].tolist()

    return result