Given a linked list of expressions, find the common ancestor that is
suitable for holding a psuedo variable for shared access.
178144
protected ElemTemplateElement findCommonAncestor(MultistepExprHolder head)
  {
  	// Not sure this algorithm is the best, but will do for the moment.
  	int numExprs = head.getLength();
  	// The following could be made cheaper by pre-allocating large arrays, 
  	// but then we would have to assume a max number of reductions, 
  	// which I am not inclined to do right now.
    ElemTemplateElement[] elems = new ElemTemplateElement[numExprs];
    int[] ancestorCounts = new int[numExprs];
    
    // Loop through, getting the parent elements, and counting the 
    // ancestors.
  	MultistepExprHolder next = head;
  	int shortestAncestorCount = 10000;
  	for(int i = 0; i < numExprs; i++)
  	{
  		ElemTemplateElement elem = 
  			getElemFromExpression(next.m_exprOwner.getExpression());
  		elems[i] = elem;
  		int numAncestors = countAncestors(elem);
  		ancestorCounts[i] = numAncestors;
  		if(numAncestors < shortestAncestorCount)
  		{
  			shortestAncestorCount = numAncestors;
  		}
  		next = next.m_next;
  	}
  	
  	// Now loop through and "correct" the elements that have more ancestors.
  	for(int i = 0; i < numExprs; i++)
  	{
  		if(ancestorCounts[i] > shortestAncestorCount)
  		{
  			int numStepCorrection = ancestorCounts[i] - shortestAncestorCount;
  			for(int j = 0; j < numStepCorrection; j++)
  			{
  				elems[i] = elems[i].getParentElem();
  			}
  		}
  	}
  	
  	// Now everyone has an equal number of ancestors.  Walk up from here 
  	// equally until all are equal.
  	ElemTemplateElement first = null;
  	while(shortestAncestorCount-- >= 0)
  	{
  		boolean areEqual = true;
  		first = elems[0];
  		for(int i = 1; i < numExprs; i++)
  		{
  			if(first != elems[i])
  			{
  				areEqual = false;
  				break;
  			}
  		}
  		// This second check is to make sure we have a common ancestor that is not the same 
  		// as the expression owner... i.e. the var decl has to go above the expression owner.
  		if(areEqual && isNotSameAsOwner(head, first) && first.canAcceptVariables())
  		{
  			if(DIAGNOSE_MULTISTEPLIST)
  			{
  				System.err.print(first.getClass().getName());
  				System.err.println(" at   " + first.getSystemId() + " Line " + first.getLineNumber());
  			}
  			return first;
  		}
   			
  		for(int i = 0; i < numExprs; i++)
  		{
  			elems[i] = elems[i].getParentElem();
  		}
  	}
  	
  	assertion(false, "Could not find common ancestor!!!");
  	return null;
  }
615777
function ancestor(node, visitors, base, state) {
  if (!base) base = exports.base;
  if (!state) state = [];(function c(node, st, override) {
    var type = override || node.type,
        found = visitors[type];
    if (node != st[st.length - 1]) {
      st = st.slice();
      st.push(node);
    }
    base[type](node, st, c);
    if (found) found(node, st);
  })(node, state);
}
292503
def _find_common_roots(paths):
    """"""
    paths = [x.split(os.path.sep) for x in paths]
    root = {}
    for chunks in sorted(paths, key=len, reverse=True):
        node = root
        for chunk in chunks:
            node = node.setdefault(chunk, {})
        node.clear()

    rv = set()

    def _walk(node, path):
        for prefix, child in iteritems(node):
            _walk(child, path + (prefix,))
        if not node:
            rv.add("/".join(path))

    _walk(root, ())
    return rv
418750
@Override
    public int find(int x) {
        int curr = x;
        int currp = p[curr];
        while (curr != currp) {
            curr = currp;
            currp = p[curr];
        }
        int ancestor = curr;
        curr = x;
        while (curr != ancestor) {
            int next = p[curr];
            p[curr] = ancestor;
            curr = next;
        }

        return ancestor;
    }
1033409
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
            TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
                tb = t.prev, tn = (TreeNode<K,V>)t.next;
            if (tb != null && tb.next != t)
                return false;
            if (tn != null && tn.prev != t)
                return false;
            if (tp != null && t != tp.left && t != tp.right)
                return false;
            if (tl != null && (tl.parent != t || tl.hash > t.hash))
                return false;
            if (tr != null && (tr.parent != t || tr.hash < t.hash))
                return false;
            if (t.red && tl != null && tl.red && tr != null && tr.red)
                return false;
            if (tl != null && !checkInvariants(tl))
                return false;
            if (tr != null && !checkInvariants(tr))
                return false;
            return true;
        }
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;
        }
    }
312275
@Override
  protected Expression visitVarRefNode(VarRefNode node) {
    Expression translation = variableMappings.maybeGet(node.getName());
    if (translation != null) {
      // Case 1: In-scope local var.
      return translation;
    } else {
      // Case 2: Data reference.
      return genCodeForParamAccess(node.getName(), node.getDefnDecl());
    }
  }
1078084
def ancestors(self, recurs=True, context=None):
        
        # FIXME: should be possible to choose the resolution order
        # FIXME: inference make infinite loops possible here
        yielded = {self}
        if context is None:
            context = contextmod.InferenceContext()
        if not self.bases and self.qname() != "builtins.object":
            yield builtin_lookup("object")[1][0]
            return

        for stmt in self.bases:
            with context.restore_path():
                try:
                    for baseobj in stmt.infer(context):
                        if not isinstance(baseobj, ClassDef):
                            if isinstance(baseobj, bases.Instance):
                                baseobj = baseobj._proxied
                            else:
                                continue
                        if not baseobj.hide:
                            if baseobj in yielded:
                                continue
                            yielded.add(baseobj)
                            yield baseobj
                        if not recurs:
                            continue
                        for grandpa in baseobj.ancestors(recurs=True, context=context):
                            if grandpa is self:
                                # This class is the ancestor of itself.
                                break
                            if grandpa in yielded:
                                continue
                            yielded.add(grandpa)
                            yield grandpa
                except exceptions.InferenceError:
                    continue
771736
def precedes(self, other):
        """"""
        try:
            ancestor = next(commonancestors(AbstractElement, self, other))
        except StopIteration:
            raise Exception("Elements share no common ancestor")
        #now we just do a depth first search and see who comes first
        def callback(e):
            if e is self:
                return True
            elif e is other:
                return False
            return None
        result = ancestor.depthfirstsearch(callback)
        if result is None:
            raise Exception("Unable to find relation between elements! (shouldn't happen)")
        return result
862289
public static int[] cs_etree(DZcs A, boolean ata)
	{
		int i, k, p, m, n, inext, Ap[], Ai[], w[], parent[], ancestor[], prev[] ;
		if (!CS_CSC (A)) return (null) ;		/* check inputs */
		m = A.m ; n = A.n ; Ap = A.p ; Ai = A.i ;
		parent = new int [n] ;				/* allocate result */
		w = new int [n + (ata ? m : 0)] ;		/* get workspace */
		if (w == null || parent == null) return (cs_idone (parent, null, w, false)) ;
		ancestor = w ; prev = w ;
		int prev_offset = n ;
		if (ata) for (i = 0 ; i < m ; i++) prev [prev_offset + i] = -1 ;
		for (k = 0 ; k < n ; k++)
		{
			parent [k] = -1 ;			/* node k has no parent yet */
			ancestor [k] = -1 ;			/* nor does k have an ancestor */
			for (p = Ap [k] ; p < Ap [k + 1] ; p++)
			{
				i = ata ? (prev [prev_offset + Ai [p]]) : (Ai [p]) ;
				for ( ; i != -1 && i < k ; i = inext)  /* traverse from i to k */
				{
					inext = ancestor [i] ;	/* inext = ancestor of i */
					ancestor [i] = k ;	/* path compression */
					if (inext == -1)
						parent [i] = k ;  /* no anc., parent is k */
				}
				if (ata) prev [prev_offset + Ai [p]] = k ;
			}
		}
		return (cs_idone (parent, null, w, true)) ;
	}
646535
private static AccessibilityNodeInfoCompat getMatchingAncestor(
            Context context, AccessibilityNodeInfoCompat node, NodeFilter filter) {
        if (node == null) {
            return null;
        }

        final HashSet<AccessibilityNodeInfoCompat> ancestors =
                new HashSet<AccessibilityNodeInfoCompat>();

        try {
            ancestors.add(AccessibilityNodeInfoCompat.obtain(node));
            node = node.getParent();

            while (node != null) {
                if (!ancestors.add(node)) {
                    // Already seen this node, so abort!
                    node.recycle();
                    return null;
                }

                if (filter.accept(context, node)) {
                    // Send a copy since node gets recycled.
                    return AccessibilityNodeInfoCompat.obtain(node);
                }

                node = node.getParent();
            }
        } finally {
            recycleNodes(ancestors);
        }

        return null;
    }
614318
private static void traverseExpression(final ognl.Node node, final Set<String> params) {
		if (node == null) {
			return;
		}
		if (node instanceof ASTProperty) {
			ASTProperty prop = (ASTProperty) node;
			params.add(prop.toString());
		} else {
			int childCount = node.jjtGetNumChildren();
			for (int i = 0; i < childCount; i++) {
				ognl.Node child = node.jjtGetChild(i);
				traverseExpression(child, params);
			}
		}
	}
1134670
private static String getFreeVariable(Expression2 expression, int index, Scope scope) {
    Expression2 sub = expression.getSubexpression(index);
    if (sub.isConstant()) {
      String constant = sub.getConstant();
      if (!constant.equals(LAMBDA) && !scope.isBound(constant)) {
        return sub.getConstant();
      } 
    }
    return null;
  }
1096556
private boolean isInstanceofFor(Node expression, Node reference) {
    return expression.isInstanceOf() && expression.getLastChild().isEquivalentTo(reference);
  }
1105341
private static List<Resource> getAncestors(Resource currentResource, Resource rootResource) {
    List<Resource> results = new ArrayList<Resource>();

    if (currentResource == null || rootResource == null || StringUtils.equals(currentResource.getPath(), rootResource.getPath())) {
      return results;
    }

    Resource parent = currentResource.getParent();
    while (parent != null) {
      results.add(0, parent);
      if (parent.getPath().equals(rootResource.getPath())) {
        break;
      }
      parent = parent.getParent();
    }
    return results;
  }
596104
def find_root_and_sink_variables(self):
        '''
        
        '''
        # First we assume all variables are roots
        is_root = {name: True for scope in self.scopes for name in scope.variables.keys()}
        # Then, we remove those variables which are outputs of some operators
        for operator in self.unordered_operator_iterator():
            for variable in operator.outputs:
                is_root[variable.onnx_name] = False
        is_sink = {name: True for scope in self.scopes for name in scope.variables.keys()}
        for operator in self.unordered_operator_iterator():
            for variable in operator.inputs:
                is_sink[variable.onnx_name] = False
        return [variable for scope in self.scopes for name, variable in scope.variables.items()
                if is_root[name] or is_sink[name]]
687214
def lowest_common_ancestor(root, p, q):
    
    while root:
        if p.val > root.val < q.val:
            root = root.right
        elif p.val < root.val > q.val:
            root = root.left
        else:
            return root