/*************************************************************************//** * complexlist.cc \class ComplexList * * * * Description: ComplexList is a class type which represents inheritance * * information for a set of entities related through supertype * * and subtype information. This file contains many of the * * ComplexList member functions. * * * * Created by: David Rosenfeld * * Date: 01/07/97 * *****************************************************************************/ #include "clstepcore/complexSupport.h" /** * Destructor for ComplexList. */ ComplexList::~ComplexList() { if( next ) { delete next; } delete head; delete list; } /** * Delete myself but don't take my sublist too. Done when a ComplexList * was temporarily created to represent a complex structure which later * became a subtype of other supertypes. After being incorporated into * the supertypes' ComplexLists, this temp one can be deleted. Its sub- * structure, however, cannot be deleted since it's still being used. */ void ComplexList::remove() { head = NULL; // Only the overall AND will be deleted. delete this; } /** * Returns true if name is already contained at the top level of our * EntList hierarchy. By top level, we mean the level under head. This * is a highly specialized function which is used during the building of * a temporary CList to test entities which are subtypes of >1 supertype. */ bool ComplexList::toplevel( const char * name ) { EntList * slist = head->childList; while( slist ) { if( * dynamic_cast< SimpleList * >(slist) == name ) { return true; } slist = slist->next; if( slist ) { slist = slist->next; } } return false; } /** * Constructs this's list member. Contains an alphabetically-ordered * linked list of EntNodes corresponding to all the leaf nodes in this. * Used as a quick method of determining if this *may* allow a complex * entity to be instantiated. If the user wants to construct a complex * entity which contains an entity which is not contained in list, this * ComplexList certainly can't support it. */ void ComplexList::buildList() { EntList * sibling = head->childList->next; // sibling = the first EntList (below the overall AND) after the supertype. // If there was a list before, delete it: if( list ) { delete list; } // Add first node based on supertype: list = new EntNode( ( dynamic_cast< SimpleList * >(head->childList ))->name ); // Recursively add all descendents: while( sibling ) { addChildren( sibling ); sibling = sibling->next; // Note - a CList usually has no more than 1 sibling, corresponding to // the subtype info of a supertype. But this may be a combo-CList used // to test sub's with >1 supertype. If so, there will be more siblings. } } /** * Recursive function to add all the SimpleList descendents of ent into * this's list. */ void ComplexList::addChildren( EntList * ent ) { EntList * child; char * nm; EntNode * prev = list, *prev2 = NULL, *newnode; int comp = 0; if( ent->multiple() ) { child = ( ( MultList * )ent )->childList; while( child ) { addChildren( child ); child = child->next; } } else { nm = ( dynamic_cast(ent) )->name; while( prev != NULL && ( comp = strcmp( prev->name, nm ) ) < 0 ) { prev2 = prev; prev = prev->next; } // One exceptional case: If new name is same as prev, skip it: if( comp != 0 ) { // At this point, we know the new node belongs between prev2 and // prev. prev or prev2 may = NULL if newnode belongs at the end // of the list or before the beginning, respectively. newnode = new EntNode( nm ); newnode->next = prev; if( prev2 == NULL ) { // This will be the case if the inner while was never entered. // That happens when newnode belonged at the beginning of the // list. If so, reset firstnode. list = newnode; } else { prev2->next = newnode; } } } } /** * Does a simple search to determine if this contains all the nodes of an * EntNode list. If not, there's no way this will match ents. If so, * we'll have to run matches() (below) to check more closely. This func- * tion is simplified greatly because both EntNodes are ordered alphabeti- * cally. */ bool ComplexList::contains( EntNode * ents ) { EntNode * ours = list, *theirs = ents; while( theirs != NULL ) { while( ours != NULL && *ours < *theirs ) { ours = ours->next; } if( ours == NULL || *ours > *theirs ) { // If either of these occurred, we couldn't find one of ours which // matched the current "theirs". return false; } theirs = theirs->next; ours = ours->next; } // At this point we must have matched them all. (We may have extra, but // there's nothing wrong with that.) return true; } /** * Receives as input an EntNode list, corresponding to a user request to * instantiate the corresponding complex type. Returns true if such a list * can be instantiated based on the list of EntLists which were generated * when the schema was read; false otherwise. */ bool ComplexList::matches( EntNode * ents ) { MatchType retval; int result = false; // First check if this ComplexList at least contains all the nodes of ents. // If it does, we'll search in detail. If not, we're done. if( ! contains( ents ) ) { return false; } // Now start a thorough search through this ComplexList: if( ( retval = head->matchNonORs( ents ) ) == MATCHALL ) { result = true; } else if( retval != UNKNOWN ) { result = false; // UNKNOWN is the return val if there are ORs matchNonORs can't // analyze. Unless we got a MATCHALL already, that's our only hope. } else { if( ( ( retval = head->matchORs( ents ) ) == MATCHALL ) && ( hitMultNodes( ents ) ) ) { // hitMultNodes() checks that in case we're a combo-CList (see // CColect->supports()) we have a legal choice (see comments in // hitMultNodes()). result = true; } else if( retval >= MATCHSOME ) { // We have a partial answer. Check if other solutions exist (i.e., // if there are OR's with other choices): MatchType otherChoices = NEWCHOICE; while( otherChoices == NEWCHOICE ) { otherChoices = head->tryNext( ents ); if( otherChoices == MATCHALL ) { if( hitMultNodes( ents ) ) { result = true; } else { otherChoices = NEWCHOICE; } } } } } head->reset(); // This recursively sets all EntLists in our list. ents->unmarkAll(); // NOTE - may want to put this at ComplexCollect level. return result; } /** * This function has a specialized application. If the user wants to * instantiate a complex type containing an entity with >1 supertype (call * it C), we temporarily join all the ComplexLists together corresponding * to the supertypes of C into a big CList (this). We then test the user * request as normal. If the regular matches() functions return MATCHALL, * we must check if each MultList corresponding to a CList hit C. If not, * we do not have a valid match. We only have the right to join the CLists * together (and make use of all the matching they afford) in order to * create a complete instance of C. Matches which do not contain C are not * valid. (This function is actually slightly more complicated because it * also deals with the possibility that >1 entities like C exist.) */ bool ComplexList::hitMultNodes( EntNode * ents ) { EntNode * node; EntList * child; // First get rid of the trivial case: If this is not a combo-CList at all, // we have nothing to check for. (CList::matches() routinely checks for // hitMultNodes in case we're a combo.) if( !multSupers ) { return true; } for( node = ents; node != NULL; node = node->next ) { if( node->multSuprs() ) { child = head->childList->next; // child points to the sublist of the first CList. (head is the // AndList which AND's them all together.) while( child ) { // child is one of the EntList members of this which corre- // sponds to one of the combined CLists. If child has node as // a member, it must have matched node, or we do not have a // legal match (see function header comments). We check this // below. if( child->contains( node->name ) ) { if( ! child->hit( node->name ) ) { return false; } } child = child->next; if( child ) { child = child->next; } // We increment child twice. We know this is how CLists are // joined: super1 -> sublist1 -> super2 -> sublist2 -> ... } } } return true; // If we got here, we didn't find any unmatched complex subtypes. }