inherpsr.c

NASA 开发使用的一个专家系统

                 Shown below is the table above after each class is
                 entered onto the precedence list:
                 
                 Precedence list: C
                                     A      USER    OBJECT    B
                 Predecessor Count   0       2        1       1
                 Successor List     B,USER  OBJECT   <NIL>    USER
                 
                 Precedence list: C A
                                    USER    OBJECT    B
                 Predecessor Count   1        1       0
                 Successor List     OBJECT   <NIL>   USER
                 
                 Precedence list: C A B
                                    USER    OBJECT
                 Predecessor Count   0        1
                 Successor List     OBJECT   <NIL>
                 
                 Precedence list: C A B USER
                                    OBJECT
                 Predecessor Count   0
                 Successor List     <NIL>
                 
                 Precedence List: C A B USER OBJECT
                 
                 And since the table is now empty we are done!
  INPUTS       : 1) The old class definition (NULL if it is new)
                 2) The list of direct superclasses
  RETURNS      : The address of the precedence list if successful,
                 NULL otherwise
  SIDE EFFECTS : Precedence list allocated
  NOTES        : WARNING!! - This routine assumes that there are no
                 cyclic dependencies in the given superclass list, i.e.
                 none of the superclasses inherit from the class for
                 which the precedence list is being defined.  (This
                 is verified in ParseDefclasses() in CLASSCOM.C)
  
                 Every class-precedence list has the class itself on it
                 (implicitly) and a built-in system class on it explicitly
                 (except for the built-in classes).
                 
                 The precedence determination algorithm is a variation on
                 the topological sorting algorithm given in The Art of
                 Computer Programming - Vol. I (Fundamental Algorithms) by
                 Donald Knuth.
 ***************************************************************************/
globle PACKED_CLASS_LINKS *FindPrecedenceList(cls,supers)
  DEFCLASS *cls;
  PACKED_CLASS_LINKS *supers;
  {
   PARTIAL_ORDER *po_table = NULL,*start,*pop,*poprv,*potmp;
   SUCCESSOR *stmp;
   CLASS_LINK *ptop,*pbot,*ptmp;
   PACKED_CLASS_LINKS *plinks;
   register unsigned i;
   
   /* =====================================================================
      Recursively add all superclasses in a pre-order depth-first traversal
      to the partial order table.  There should be only one node per class.
      ===================================================================== */
   po_table = InitializePartialOrderTable(po_table,supers);
   
   /* =============================================================
      If the class already exists, record the rule 1 partial orders
      with the new superclass lists.  This is so that cyclic
      dependencies can be detected.
      ============================================================= */
   if (cls != NULL)
     {
      pop = get_struct(partialOrder);
      pop->cls = cls;
      pop->pre = 0;
      pop->suc = NULL;
      pop->nxt = po_table;
      po_table = pop;
      pop = po_table->nxt;
      RecordPartialOrders(po_table,cls,supers,0);
     }
   else
     pop = po_table;
     
   /* ==================================================================
      Record the rule 1 and rule 2 partial orders given by the direct
      superclass lists of the classes in the table.  There is no need to
      recurse since all possible classes have been entered already.
      
      Be sure to skip the class itself if it was added to the front of
      the table.
      ================================================================== */
   for ( ; pop != NULL ; pop = pop->nxt)
     {
      RecordPartialOrders(po_table,pop->cls,&pop->cls->directSuperclasses,0);
      for (i = 0 ; i < pop->cls->directSuperclasses.classCount ; i++)
        RecordPartialOrders(po_table,pop->cls->directSuperclasses.classArray[i],
                            &pop->cls->directSuperclasses,i+1);
     }
   
   /* =============================================================
      Record the rule 2 partial orders given by the superclass list
      ============================================================= */
   for (i = 0 ; i < supers->classCount ; i++)
     RecordPartialOrders(po_table,supers->classArray[i],supers,i+1);
     
   start = NULL;
   poprv = NULL;
   pop = po_table;
   ptop = pbot = NULL;
   while (pop != start)
     {
      /* ==============================================================
         Allow wraparound - happens when the search for a 0 node begins
         somewhere in the middle of the sequence table
         ============================================================== */
      if (pop == NULL)
        {
         poprv = NULL;
         pop = po_table;
         start = start->nxt;
        }
        
      /* =========================================================
         Search for the first class with no remaining predecessors
         ========================================================= */
      if (pop->pre == 0)
        {
         /* =================================================
            Decrement the predecessor count for all the
            successors of this class and delete the list.
            
            This is the variation on Knuth's algorithm which
            allows us to preserve the "family" heuristic.
            Since we will pick up scanning for 0's from
            this point, we will be able to keep "family"
            trees together, if possible. BuildPartialOrders()
            entered the classes into the sequence table
            in a pre-order depth traversal order.
            ================================================= */
         while (pop->suc != NULL)
           {
            stmp = pop->suc;
            pop->suc = stmp->nxt;
            stmp->po->pre--;
            rtn_struct(successor,stmp);
           }
           
         /* =============================================
            Append the class to the precedence list and
            remove its entry from the partial order table
            ============================================= */
         potmp = pop;
         if (poprv == NULL)
           po_table = pop->nxt;
         else
           poprv->nxt = pop->nxt;
         pop = pop->nxt;
         start = poprv;
         ptmp = get_struct(classLink);
         ptmp->cls = potmp->cls;
         ptmp->nxt = NULL;
         rtn_struct(partialOrder,potmp);
         if (ptop == NULL)
           ptop = ptmp;
         else
           pbot->nxt = ptmp;
         pbot = ptmp;
        }
      else
        {
         poprv = pop;
         pop = pop->nxt;
        }
     }
   
   /* ======================================================================
      If the table of partial orders is not empty and we were unable to find
      a class with no predecessors, then there is no solution! Print out the
      precedence loop in the partial orders. Delete the remaining partial
      order table and the partial precedence list.
      ====================================================================== */
   if (po_table != NULL)
     {
      PrintErrorID("INHERPSR",5,CLIPS_FALSE);
      PrintClassLinks(WERROR,"Partial precedence list formed:",ptop);
      PrintPartialOrderLoop(po_table);
      while (po_table != NULL)
        {
         while (po_table->suc != NULL)
           {
            stmp = po_table->suc;
            po_table->suc = stmp->nxt;
            rtn_struct(successor,stmp);
           }
         potmp = po_table;
         po_table = po_table->nxt;
         rtn_struct(partialOrder,potmp);
        }
      DeleteClassLinks(ptop);
      return(NULL);
     }
     
   /* =============================================================================
      If the class already existed, be sure and remove it from its own precedence
      list.  Remember that we stuck it on the table artificially to catch cycles.
      It was first in the table, and, since it started with a predecessor count
      of zero (given that there were no loops), it is first in the precedence list.
      
      We will leave the dummy node there so that functions which wish to iterate
      over a class and its superclasses may easily do so.
      ============================================================================= */
   if (cls == NULL)
     {
      ptmp = get_struct(classLink);
      ptmp->nxt = ptop;
      ptop = ptmp;
     }
      
   /* ============================================================
      The class pointer will be filled in later by ParseDefclass()
      ============================================================ */
   ptop->cls = NULL;
   
   plinks = get_struct(packedClassLinks);
   PackClassLinks(plinks,ptop);
   return(plinks);
  }

/***************************************************
  NAME         : PackClassLinks
  DESCRIPTION  : Writes a list of class links into
                 a contiguous section of memory to
                 reduce overhead (the original list
                 is deleted)
  INPUTS       : 1) The packed list structure to use 
                 2) The top of the original list
  RETURNS      : Nothing useful
  SIDE EFFECTS : Packed list allocated and old list
                 deleted
  NOTES        : None
 ***************************************************/
globle VOID PackClassLinks(plinks,lptop)
  PACKED_CLASS_LINKS *plinks;
  CLASS_LINK *lptop;
  {
   register unsigned count;
   register CLASS_LINK *lp;
   
   for (count = 0 , lp = lptop ; lp != NULL ; lp = lp->nxt)
     count++;
   if (count > 0)
     plinks->classArray = (DEFCLASS **) gm2((int) (sizeof(DEFCLASS *) * count));
   else
     plinks->classArray = NULL;
   for (count = 0 , lp = lptop ; lp != NULL ; lp = lp->nxt , count++)
     plinks->classArray[count] = lp->cls;
   DeleteClassLinks(lptop);
   plinks->classCount = (unsigned short) count;
  }
  
/* =========================================
   *****************************************
          INTERNALLY VISIBLE FUNCTIONS
   =========================================
   ***************************************** */
  
/**************************************************************************
  NAME         : InitializePartialOrderTable
  DESCRIPTION  : This function recursively enters the classes
                 that will be used in a precedence list
                 determination in depth-first pre-order traversal.
                 The predecessor counts and successor list are initialized.
                 
  INPUTS       : 1) The partial order table
                 2) A list of direct superclasses
                 3) The class for which a precedence class is being
                    determined (NULL for new class)
                 4) The class which superclass list is being processed
  RETURNS      : The top of partial order table
  SIDE EFFECTS : The partial order table is initialized.
  NOTES        : None
 **************************************************************************/
static PARTIAL_ORDER *InitializePartialOrderTable(po_table,supers)
  PARTIAL_ORDER *po_table;
  PACKED_CLASS_LINKS *supers;
  {
   register PARTIAL_ORDER *pop,*poprv;
   register unsigned i;
   
   for (i = 0 ; i < supers->classCount ; i++)
     {
      /* =================================================