Finds the smallest item in a subtree.

@param node The root node of the subtree.
969060
private V findSmallest(Node node) {
        if (node == null) {
            return null;
        }

        while (node.left != null) {
            node = node.left;
        }

        return node.item;
    }
522212
private final LeafNode<K, V> findSideLeafNode(final boolean lowORhigh) {
		if (_isEmpty()) {
			return null;
		}
		try {
			int nodeIdx = (lowORhigh ? lowIdx : highIdx); // rootIdx;
			Node<K, V> nodeFind = getNode((nodeIdx == 0) ? rootIdx : nodeIdx);
			while (!nodeFind.isLeaf()) {
				nodeIdx = ((InternalNode<K, V>) nodeFind).childs[(lowORhigh ? 0 : nodeFind.allocated)];
				nodeFind = getNode(nodeIdx);
			}
			return (nodeFind.isLeaf() ? (LeafNode<K, V>) nodeFind : null);
		} finally {
			releaseNodes();
		}
	}
433570
public static String child(String node) {
        final int index = node.lastIndexOf('/');
        if (index < 0 || index == node.length() - 1)
            return null;
        return node.substring(index + 1, node.length());
    }
1215928
private void delete(Node<K, V> n) {
        if (root == n) {
            deleteMin();
            n.o_c = null;
            n.y_s = null;
            n.o_s = null;
            return;
        }

        if (n.o_s == null) {
            throw new IllegalArgumentException("Invalid handle!");
        }

        // unlink from parent
        if (n.y_s != null) {
            n.y_s.o_s = n.o_s;
        }
        if (n.o_s.o_c == n) { // I am the oldest :(
            n.o_s.o_c = n.y_s;
        } else { // I have an older sibling!
            n.o_s.y_s = n.y_s;
        }
        n.y_s = null;
        n.o_s = null;

        // perform delete-min at tree rooted at this
        Node<K, V> t = combine(cutChildren(n));

        // and merge with other cut tree
        if (comparator == null) {
            root = link(root, t);
        } else {
            root = linkWithComparator(root, t);
        }

        size--;
    }
1178126
private static MinimizedCondition computeMinimizedCondition(Node n) {
    switch (n.getToken()) {
      case NOT: {
        MinimizedCondition subtree = computeMinimizedCondition(n.getFirstChild());
        MeasuredNode positive = pickBest(
            MeasuredNode.addNode(n, subtree.positive),
            subtree.negative);
        MeasuredNode negative = pickBest(
            subtree.negative.negate(),
            subtree.positive);
        return new MinimizedCondition(positive, negative);
      }
      case AND:
      case OR: {
        Node complementNode = new Node(n.getToken() == Token.AND ? Token.OR : Token.AND).srcref(n);
        MinimizedCondition leftSubtree = computeMinimizedCondition(n.getFirstChild());
        MinimizedCondition rightSubtree = computeMinimizedCondition(n.getLastChild());
        MeasuredNode positive = pickBest(
            MeasuredNode.addNode(n,
                leftSubtree.positive,
                rightSubtree.positive),
            MeasuredNode.addNode(complementNode,
                leftSubtree.negative,
                rightSubtree.negative).negate());
        MeasuredNode negative = pickBest(
            MeasuredNode.addNode(n,
                leftSubtree.positive,
                rightSubtree.positive).negate(),
            MeasuredNode.addNode(complementNode,
                leftSubtree.negative,
                rightSubtree.negative).change());
        return new MinimizedCondition(positive, negative);
      }
      case HOOK: {
        Node cond = n.getFirstChild();
        Node thenNode = cond.getNext();
        Node elseNode = thenNode.getNext();
        MinimizedCondition thenSubtree = computeMinimizedCondition(thenNode);
        MinimizedCondition elseSubtree = computeMinimizedCondition(elseNode);
        MeasuredNode positive = MeasuredNode.addNode(
            n,
            MeasuredNode.forNode(cond),
            thenSubtree.positive,
            elseSubtree.positive);
        MeasuredNode negative = MeasuredNode.addNode(
            n,
            MeasuredNode.forNode(cond),
            thenSubtree.negative,
            elseSubtree.negative);
        return new MinimizedCondition(positive, negative);
      }
      case COMMA: {
        Node lhs = n.getFirstChild();
        MinimizedCondition rhsSubtree = computeMinimizedCondition(lhs.getNext());
        MeasuredNode positive = MeasuredNode.addNode(
            n,
            MeasuredNode.forNode(lhs),
            rhsSubtree.positive);
        MeasuredNode negative = MeasuredNode.addNode(
            n,
            MeasuredNode.forNode(lhs),
            rhsSubtree.negative);
        return new MinimizedCondition(positive, negative);
      }
      default: {
        MeasuredNode pos = MeasuredNode.forNode(n);
        MeasuredNode neg = pos.negate();
        return new MinimizedCondition(pos, neg);
      }
    }
  }
865996
public Node<T> getNext(Node<T> node) {
    	if (node.right != null) {
    		node = node.right;
    		while (node.left != null) node = node.left;
    		return node;
    	}
    	// nothing at right, it may be the parent node if the node is at the left
    	if (node == last) return null;
    	return getNext(root, node.value);
    }
1042967
Node<K, V> find(K key, boolean create) {
    Comparator<? super K> comparator = this.comparator;
    Node<K, V>[] table = this.table;
    int hash = secondaryHash(key.hashCode());
    int index = hash & (table.length - 1);
    Node<K, V> nearest = table[index];
    int comparison = 0;

    if (nearest != null) {
      // Micro-optimization: avoid polymorphic calls to Comparator.compare().
      @SuppressWarnings("unchecked") // Throws a ClassCastException below if there's trouble.
      Comparable<Object> comparableKey = (comparator == NATURAL_ORDER)
          ? (Comparable<Object>) key
          : null;

      while (true) {
        comparison = (comparableKey != null)
            ? comparableKey.compareTo(nearest.key)
            : comparator.compare(key, nearest.key);

        // We found the requested key.
        if (comparison == 0) {
          return nearest;
        }

        // If it exists, the key is in a subtree. Go deeper.
        Node<K, V> child = (comparison < 0) ? nearest.left : nearest.right;
        if (child == null) {
          break;
        }

        nearest = child;
      }
    }

    // The key doesn't exist in this tree.
    if (!create) {
      return null;
    }

    // Create the node and add it to the tree or the table.
    Node<K, V> header = this.header;
    Node<K, V> created;
    if (nearest == null) {
      // Check that the value is comparable if we didn't do any comparisons.
      if (comparator == NATURAL_ORDER && !(key instanceof Comparable)) {
        throw new ClassCastException(key.getClass().getName() + " is not Comparable");
      }
      created = new Node<K, V>(nearest, key, hash, header, header.prev);
      table[index] = created;
    } else {
      created = new Node<K, V>(nearest, key, hash, header, header.prev);
      if (comparison < 0) { // nearest.key is higher
        nearest.left = created;
      } else { // comparison > 0, nearest.key is lower
        nearest.right = created;
      }
      rebalance(nearest, true);
    }

    if (size++ > threshold) {
      doubleCapacity();
    }
    modCount++;

    return created;
  }
304176
public void remove(int node) {
        if (node == NIL) {
            throw new IllegalArgumentException();
        }
        if (left(node) != NIL && right(node) != NIL) {
            // inner node
            final int next = next(node);
            assert next != NIL;
            swap(node, next);
        }
        assert left(node) == NIL || right(node) == NIL;

        final int parent = parent(node);
        int child = left(node);
        if (child == NIL) {
            child = right(node);
        }

        if (child == NIL) {
            // no children
            if (node == root) {
                assert size() == 1 : size();
                root = NIL;
            } else {
                if (node == left(parent)) {
                    left(parent, NIL);
                } else {
                    assert node == right(parent);
                    right(parent, NIL);
                }
            }
        } else {
            // one single child
            if (node == root) {
                assert size() == 2;
                root = child;
            } else if (node == left(parent)) {
                left(parent, child);
            } else {
                assert node == right(parent);
                right(parent, child);
            }
            parent(child, parent);
        }

        release(node);
        rebalance(parent);
    }
1074790
public Node<T> getPrevious(Node<T> node) {
    	if (node.left != null) {
    		node = node.left;
    		while (node.right != null) node = node.right;
    		return node;
    	}
    	// nothing at left, it may be the parent node if the node is at the right
    	if (node == first) return null;
    	return getPrevious(root, node.value);
    }
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;
	}
592734
public static void mergeNodeChildren(TreeNode node) {
        DefaultMutableTreeNode masterNode = (DefaultMutableTreeNode) node;

        // The rules are there are no rules. Nothing else needs to be done
        // except for merging through the children
        for (int i = 0; i < masterNode.getChildCount(); i++) {
            DefaultMutableTreeNode child = (DefaultMutableTreeNode) masterNode.getChildAt(i);

            if (!child.isLeaf()) {
                MergeHelpUtilities.mergeNodeChildren(DEFAULT_MERGE_TYPE, child);
            }
        }
    }
1075148
public final int prev(int node) {
        final int left = left(node);
        if (left != NIL) {
            return last(left);
        } else {
            int parent = parent(node);
            while (parent != NIL && node == left(parent)) {
                node = parent;
                parent = parent(parent);
            }
            return parent;
        }
    }
4875
private static int countNodes(TreeModel treeModel, Object node)
    {
        int sum = 1;
        int n = treeModel.getChildCount(node);
        for (int i=0; i<n; i++)
        {
            sum += countNodes(treeModel, treeModel.getChild(node, i));
        }
        return sum;
    }
1304749
public void remove(Node<T> node) {
    	if (first == node) {
    		removeMin();
    		return;
    	}
    	if (last == node) {
    		removeMax();
    		return;
    	}
    	// if both children of root are black, set root to red
    	if ((root.left == null || !root.left.red) && (root.right == null || !root.right.red))
            root.red = true;

        root = remove(root, node);
        if (root != null) root.red = false;
        else first = last = null;
    }
546457
function(node){
			var context = this,
				children = [],
				child,
				classes,
				items = [],
				out = [];

			classes = this.getUfClassNames(node);
			// if it is a root microformat node
			if(classes && classes.root.length > 0){
				items = this.walkTree(node);

				if(items.length > 0){
					out = out.concat(items);
				}
			}else{
				// check if there are children and one of the children has a root microformat
				children = modules.domUtils.getChildren( node );
				if(children && children.length > 0 && this.findRootNodes(node, true).length > -1){
					for (var i = 0; i < children.length; i++) {
						child = children[i];
						items = context.walkRoot(child);
						if(items.length > 0){
							out = out.concat(items);
						}
					}
				}
			}
			return out;
		}
398403
private void checkNodeRecursive(Node node)
	{
		if (isDangling(node))
		{
			removeNode(node);

			for (Edge edge : node.getUpstream())
			{
				checkNodeRecursive(edge.getSourceNode());
			}
			for (Edge edge : node.getDownstream())
			{
				checkNodeRecursive(edge.getTargetNode());
			}
			for (Node parent : node.getUpperEquivalent())
			{
				checkNodeRecursive(parent);
			}
			for (Node child : node.getLowerEquivalent())
			{
				checkNodeRecursive(child);
			}
		}
	}
220239
public static boolean isEmpty(Node node) {
        return (node == null || (node.children() != null && node.children().size() == 0));
    }