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

* entnode.cc \class EntNode *

* *

* Description: The EntNode class is used to store a collection of entity *

* names. It stores them in alphabetical order. It is the key *

* component of the EntList classes, which are used to store *

* information on the instantiable complex entity types. This *

* file contains EntNode member function definitions. *

* *

* Created by: David Rosenfeld *

* Date: 9/18/96 *

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

#include "clstepcore/complexSupport.h"

/**

* Given a list of entity names, creates a sorted linked list of EntNodes

* corresponding to the list. A name which = "*" is a dummy trailer

* implying the list has been completed. This function first builds the

* list, then sets this to the first element, and then deletes the first

* element. This ensures that `this' points to the start of the list.

*/

EntNode::EntNode( const char ** names ) {

int j = 1, comp;

EntNode * prev, *prev2 = NULL, // prev2 - the one before prev

*newnode, *firstnode;

const char * nm;

// Create a first EntNode:

firstnode = prev = new EntNode( names[0] );

while( names[j] && *names[j] != '*' ) {

nm = names[j];

while( prev != NULL && ( comp = StrCmpIns( 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.

firstnode = newnode;

} else {

prev2->next = newnode;

}

}

// Reset for next name:

prev = firstnode;

prev2 = NULL;

j++;

}

// Finally, place the contents of firstnode in 'this', and delete first-

// node. This ensures that 'this' is first.

*this = *firstnode;

firstnode->next = NULL;

// (Otherwise, deleting firstnode would delete entire list.)

delete firstnode;

}

/**

* Copies all of ent's values here.

*/

EntNode & EntNode::operator= ( EntNode & ent ) {

Name( ent.name );

setmark( ent.mark );

multSuprs( ent.multSupers );

next = ent.next;

return *this;

}

/**

* Marks/unmarks all the nodes in this's list (default is to mark).

*/

void EntNode::markAll( MarkType stamp ) {

EntNode * node = this;

while( node != NULL ) {

node->mark = stamp;

node = node->next;

}

}

/**

* Returns true if this and all nodes following it are marked.

*/

bool EntNode::allMarked() {

EntNode * node = this;

while( node != NULL ) {

if( node->mark == NOMARK ) {

return false;

}

node = node->next;

}

return true;

}

/**

* Returns the number of unmarked nodes in this's list.

*/

int EntNode::unmarkedCount() {

int count = 0;

EntNode * node = this;

while( node != NULL ) {

if( node->mark == NOMARK ) {

count++;

}

node = node->next;

}

return count;

}

/**

* Starting from `this', search for the last node (along our next's) which

* alphabetically precedes ent.

*/

EntNode * EntNode::lastSmaller( EntNode * ent ) {

EntNode * eptr = next, *prev = this;

if( *this > *ent ) {

return NULL;

}

while( eptr && *eptr > *prev && *eptr < *ent ) {

prev = eptr;

eptr = eptr->next;

}

return prev;

}

/**

* Check if our nodes are in order. If not, re-sort. The earlier part of

* the list has been sorted but not necessarily the remainder. This algo-

* rithm sorts our nodes in chunks, and is fairly efficient when we know

* our nodes are basically in order. (sort() is called from STEPcomplex::

* Initialize() when we are creating a complex entity and have renamed a

* few of the nodes. The nodes at first were in order; only the renamed

* ones may be out of place.)

*/

void EntNode::sort( EntNode ** first ) {

EntNode * eptr1, *eptr2, *temp1, *temp2;

while( next && *this > *next ) {

// Find the earliest node greater than next. (I.e., is not only this >

// next but also some of this's preceding nodes. Since the nodes

// earlier in the list are sorted already, we can easily determine the

// ordered chunk of nodes which next should precede.) (eptr1 is

// actually set to the one before, so that we'll know that eptr1->next

// should now be set to next.)

eptr1 = ( *first )->lastSmaller( next );

// Take the latest node eptr1 is greater than. (I.e., beyond next are

// there more nodes which should be immediately after eptr1.) (The

// succeeding nodes are not necessarily in order, so lastSmaller() also

// checks that nodes later than next are also > their prev's.)

if( eptr1 ) {

eptr2 = next->lastSmaller( eptr1->next );

} else {

eptr2 = next->lastSmaller( *first );

}

// Switch the two lists:

if( eptr1 ) {

temp1 = eptr1->next;

eptr1->next = next;

temp2 = eptr2->next;

eptr2->next = temp1;

next = temp2;

} else {

// `this' should be first in the list.

temp2 = eptr2->next;

eptr2->next = *first;

*first = next;

next = temp2;

}

}

if( next ) {

next->sort( first );

}

}