the smallest key in subtree rooted at x; null if no such key
359462
private Node<T> min(Node<T> x) {
    	do {
    		if (x.left == null) return x;
    		x = x.left;
    	} while (true);
    }
389689
private Tree<Row> findNext( Tree<Row> pointer ){
        if( pointer.hasNext() ){
            // The given tree-node is not the last in its block.
            if( Type.END.equals( pointer.getNext().getContent().getType() ) ){
                return null;
            }
            else{
                return pointer.getNext();
            }
        }
        // The given tree-node was last in its block. Then we return the
        // the block closing tree-node.
        Tree<Row> parent = pointer.getParent();
        Type parentType = parent.getContent().getType();
        if( Type.WHILE_DO_BEGIN.equals( parentType ) ){

            return parent.getNext();
        }
        else if( Type.DO_WHILE_BEGIN.equals( parentType ) ){
            return parent.getNext();
        }
        if( Type.BRANCH.equals( parentType ) ){
            Tree<Row> join = parent.getParent().getNext();
            return join;
        }
        else if( Type.IF.equals( parentType ) || Type.ELSE_IF.equals( parentType ) || Type.ELSE.equals( parentType ) ){
            Tree<Row> endIf = findEndIf( parent );
            return endIf;
        }
        else{
            throw new IllegalStateException( "Unknown containting block type for row " + parent.getContent() );
        }
    }
719707
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
390906
public static <T> Optional<T> lowestCommonAncestor(TreeDef.Parented<T> treeDef, List<T> nodes) {
		if (nodes.size() == 0) {
			return Optional.empty();
		} else {
			Optional<T> soFar = Optional.of(nodes.get(0));
			for (int i = 1; i < nodes.size() && soFar.isPresent(); ++i) {
				soFar = lowestCommonAncestor(treeDef, soFar.get(), nodes.get(i));
			}
			return soFar;
		}
	}
257961
function getNextKeyWith( keys, fullSid, ndx ) {

		for ( ; ndx < keys.length; ndx ++ ) {

			var key = keys[ ndx ];

			if ( key.hasTarget( fullSid ) ) {

				return key;

			}

		}

		return null;

	}
957874
def _get_node_pos(self, key):
        
        if not self._hashring:
            return None

        key = self._gen_key(key)

        nodes = self._sorted_keys
        pos = bisect(nodes, key)

        if pos == len(nodes):
            return 0
        return pos
956668
def _get(self, node_hash, keypath):
        
        # Empty trie
        if node_hash == BLANK_HASH:
            return None
        nodetype, left_child, right_child = parse_node(self.db[node_hash])
        # Key-value node descend
        if nodetype == LEAF_TYPE:
            if keypath:
                return None
            return right_child
        elif nodetype == KV_TYPE:
            # Keypath too short
            if not keypath:
                return None
            if keypath[:len(left_child)] == left_child:
                return self._get(right_child, keypath[len(left_child):])
            else:
                return None
        # Branch node descend
        elif nodetype == BRANCH_TYPE:
            # Keypath too short
            if not keypath:
                return None
            if keypath[:1] == BYTE_0:
                return self._get(left_child, keypath[1:])
            else:
                return self._get(right_child, keypath[1:])
329557
function SMALLER(tree, n, m) {
		return tree[n].fc < tree[m].fc || (tree[n].fc === tree[m].fc && depth[n] <= depth[m]);
	}
844710
private void getLastChild() {

        // nodekey of the root of the current subtree
        final long parent = getNode().getDataKey();

        // traverse tree in pre order to the leftmost leaf of the subtree and
        // push
        // all nodes to the stack
        if (((ITreeStructData)getNode()).hasFirstChild()) {
            while (((ITreeStructData)getNode()).hasFirstChild()) {
                mStack.push(getNode().getDataKey());
                moveTo(((ITreeStructData)getNode()).getFirstChildKey());
            }

            // traverse all the siblings of the leftmost leave and all their
            // descendants and push all of them to the stack
            while (((ITreeStructData)getNode()).hasRightSibling()) {
                mStack.push(getNode().getDataKey());
                moveTo(((ITreeStructData)getNode()).getRightSiblingKey());
                getLastChild();
            }

            // step up the path till the root of the current subtree and process
            // all
            // right siblings and their descendants on each step
            if (getNode().hasParent() && (getNode().getParentKey() != parent)) {

                mStack.push(getNode().getDataKey());
                while (getNode().hasParent() && (getNode().getParentKey() != parent)) {

                    moveTo(getNode().getParentKey());

                    // traverse all the siblings of the leftmost leave and all
                    // their
                    // descendants and push all of them to the stack
                    while (((ITreeStructData)getNode()).hasRightSibling()) {

                        moveTo(((ITreeStructData)getNode()).getRightSiblingKey());
                        getLastChild();
                        mStack.push(getNode().getDataKey());
                    }
                }

                // set transaction to the node in the subtree that is last in
                // document
                // order
                moveTo(mStack.pop());
            }
        }
    }
1072943
@SuppressWarnings("unchecked")
    private void decreaseKey(Node<K, V> n, K newKey) {
        int c = ((Comparable<? super K>) newKey).compareTo(n.key);
        if (c > 0) {
            throw new IllegalArgumentException("Keys can only be decreased!");
        }
        n.key = newKey;
        if (c == 0) {
            return;
        }

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

        // if not root and heap order violation
        Node<K, V> y = n.parent;
        if (y != null && ((Comparable<? super K>) n.key).compareTo(y.key) < 0) {
            cut(n, y);
            cascadingCut(y);
        }

        // update minimum root
        if (((Comparable<? super K>) n.key).compareTo(minRoot.key) < 0) {
            minRoot = n;
        }
    }
806851
function getLowestCommonAncestor(instA, instB) {
  var depthA = 0;
  for (var tempA = instA; tempA; tempA = getParent(tempA)) {
    depthA++;
  }
  var depthB = 0;
  for (var tempB = instB; tempB; tempB = getParent(tempB)) {
    depthB++;
  }

  // If A is deeper, crawl up.
  while (depthA - depthB > 0) {
    instA = getParent(instA);
    depthA--;
  }

  // If B is deeper, crawl up.
  while (depthB - depthA > 0) {
    instB = getParent(instB);
    depthB--;
  }

  // Walk in lockstep until we find a match.
  var depth = depthA;
  while (depth--) {
    if (instA === instB || instA === instB.alternate) {
      return instA;
    }
    instA = getParent(instA);
    instB = getParent(instB);
  }
  return null;
}
549997
function(ns, root){
    if (!ns) {
      return null;
    }
    var nsParts = ns.split(".");
    root = root || this;
    for (var i = 0, len = nsParts.length; i < len; i++) {
      if (typeof root[nsParts[i]] === "undefined") {
        root[nsParts[i]] = {};
      }
      root = root[nsParts[i]];
    }
    return root;
  }
382157
private void forceDecreaseKeyToMinimum(Node<K, V> n) {
        // if not root
        Node<K, V> y = n.parent;
        if (y != null) {
            cut(n, y);
            cascadingCut(y);
        }
        minRoot = n;
    }
844570
def subtree_of?(parent_tree)
      parent_tree = make_object_id(parent_tree)
      if parent_tree.length > self.length
        false
      else
        parent_tree.each_index do |i|
          return false if parent_tree[i] != self[i]
        end
        true
      end
    end
969856
def get_node(self, key):
        """"""
        pos = self._get_node_pos(key)
        if pos is None:
            return None
        return self._hashring[self._sorted_keys[pos]]
827657
@SuppressWarnings("unchecked")
    private void comparableDecreaseKey(Node<K, V> n, K newKey) {
        int c = ((Comparable<? super K>) newKey).compareTo(n.key);
        if (c > 0) {
            throw new IllegalArgumentException("Keys can only be decreased!");
        }
        n.key = newKey;
        if (c == 0) {
            return;
        }

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

        // if not root and heap order violation
        Node<K, V> y = n.parent;
        if (y != null && ((Comparable<? super K>) n.key).compareTo(y.key) < 0) {
            cut(n, y);
            root.mark = false;
            cascadingRankChange(y);
            if (((Comparable<? super K>) n.key).compareTo(root.key) < 0) {
                root = link(root, n);
            } else {
                link(n, root);
            }
        }
    }
531154
function lookup(tree, key) {
  if (!tree) {
    return null
  }

  switch (compare(tree.key, key)) {
    case 0:
      return tree
    case 1:
      return lookup(tree.right, key)
    case -1:
      return lookup(tree.left, key)
    default:
      break
  }
}