/*****************************************************************************

* \file match-ors.cc *

* *

* Description: Contains the matchORs() functions for the EntList descen- *

* dants. The matchORs() of AndOrList and AndList recursively *

* loop through their non-SIMPLE EntList children to determine *

* how well their OR descendants match an EntNode. OrList's *

* matchORs() function checks its children one at a time for *

* both complete and incomplete matches of EntNode and stores *

* the resulting information. *

* *

* Created by: David Rosenfeld *

* Date: 10/17/96 *

*****************************************************************************/

#include "clstepcore/complexSupport.h"

/**

* Loops through descendants of this, invoking their matchOR functions.

* Returns the status of how well this's OR descendants match the nodes of

* ents. We only check our children whose viable values = UNKNOWN. This

* signifies that when we checked them previously with matchNonORs(), we

* couldn't determine their match value. And that happens when there are

* OR descendants we didn't test. Thus, UNKNOWN tells us that this child

* is an OR, or has an OR somewhere beneath it which we must process now.

*/

MatchType AndOrList::matchORs( EntNode * ents ) {

EntList * child = childList->firstWanted( UNKNOWN );

while( child != NULL ) {

if( ( dynamic_cast< MultList * >(child))->matchORs( ents ) == UNSATISFIED ) {

// Unmark whatever we may have marked. (E.g., there may have

// been an AND beneath and it started marking and then found one

// it couldn't match.)

child->unmarkAll( ents );

}

child = child->nextWanted( UNKNOWN );

}

// NOTE - We went through entire loop above even if we found a MATCHALL

// sometime in the middle. After finding a bug, I realized we couldn't

// stop in the middle. So long as there are more UNKNOWN children, one

// of those children may become UNSAT later and we'll have to unmark all

// its descendants. If so, some of the marks we have now may disappear.

setViableVal( ents );

return viable;

}

/**

* Loops through the descendants of this with viable val = UNKNOWN, invo-

* king their matchOR functions. Returns the status of how well this's OR

* descendants match the nodes of ents. We only take UNKNOWN's because

* they will lead us to OR's, as explained in AndOrList::matchORs().

*/

MatchType AndList::matchORs( EntNode * ents ) {

EntList * child = childList->firstWanted( UNKNOWN );

while( child != NULL ) {

if( ( dynamic_cast< MultList * >(child) )->matchORs( ents ) == UNSATISFIED ) {

viable = UNSATISFIED;

return UNSATISFIED;

// This means the whole AndList has failed, by definition.

}

child = child->nextWanted( UNKNOWN );

// Note - we loop through all even if one of our children returned

// MATCHALL. Since we're an AND, we must look through all branches -

// to search for any other conditions we can't meet. If one of our

// children did MATCHALL, its viable val will be set to MATCHALL and

// we'll catch it in setViableVal() called below.

}

setViableVal( ents );

return viable;

}

/**

* Checks the branches of an OrList to search for a match to the nodes of

* ents. This function searches this's children and marks all the viable

* paths, or paths which mark off at least some of the remaining nodes of

* ents. It then selects the first one, marking it only with an ORMARK to

* retain the info that these were only conditionally marked. Also, if a

* MATCHALL solution was found, that is returned immediately.

*/

MatchType OrList::matchORs( EntNode * ents ) {

int count;

EntList * child = childList;

MatchType retval = UNKNOWN;

for( count = 0; count < numchildren; count++, child = child->next ) {

// First call (recursively) matchNonORs() to check off all nodes that

// the descendants of this branch can definitely mark off:

if( child->join != OR ) {

retval = child->matchNonORs( ents );

}

// Then try the OR's. At this point, any OR's that we get to (in

// recursively checking the descendants of child) will know that if

// it can mark new node(s), it's a viable option.

if( child->viable == UNKNOWN ) {

// If viable = UNKNOWN, this child must either be an OR or a Mult

// with an OR underneath. Only ORs are still indeterminate after

// running matchNonORs() above. (We also exclude the case of an

// AND child who may have OR desc's, but already determined that

// it can't satisfy one of its paths and so returned UNSAT.)

retval = ( dynamic_cast< MultList * >(child) )->matchORs( ents );

}

// Now register the result:

if( retval >= MATCHSOME ) {

// Note: In the past I would return immediately if retval =

// MATCHALL, thinking our job was done. I changed it when we

// started dealing with combo-CLists (sub w/ >1 super). I realized

// that even if down here we got a MATCHALL, we may have to reject

// above, so we must keep searching.

if( choice == -1 ) {

choice1 = choice = count;

}

choiceCount++;

if( viable < retval ) {

viable = retval;

}

} else {

// At this point, retval must = SATISFIED or UNSAT. Neither

// result gives us a possible solution since neither marks any

// new nodes. He we keep track of the best retval we've gotten

// between the two remaining values. It's important to know if

// retval = SATISFIED. In case there is no better result, this

// Will cause us to tell our parent that we have at least one

// satisfactory path. Thus, if our parent is an AND, it'll know

// that this branch doesn't violate anything.

if( viable < retval ) {

viable = retval;

}

}

// Undo this choice before we try the next:

child->unmarkAll( ents );

}

// Accept the first viable solution, if there is one:

if( viable >= MATCHSOME ) {

// If there are some MATCHSOME solutions, accept the first. accept-

// Choice() begins by accepting the child at "choice". But if this

// does not mark anything new, it loops until it finds a choice that

// does mark (if there is one). There's no point marking any earlier

// ones. There may be earlier children which are set to MATCHSOME

// because they *may* mark (since they match nodes which are only

// conditionally marked). But now we're looking for a child which

// *actually* marks under the current circumstances.

acceptChoice( ents );

}

if( viable == MATCHALL ) {

return getChild( choice1 )->viable;

// viable == MATCHALL because we found a MATCHALL sol'n along the way,

// but that wasn't necessarily the choice acceptChoice() took now.

// (See note above why we don't drop everything and just accept the

// MATCHALL.)

} else {

return viable;

}

}