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 ; }
Given a linked list of expressions find the common ancestor that is suitable for holding a psuedo variable for shared access .