/*******************************************************/   /*      "C" Language Integrated Production System      */   /*                                                     */   /*             CLIPS Version 6.30  10/19/06            */   /*                                                     */   /*         CONFLICT RESOLUTION STRATEGY MODULE         */   /*******************************************************//*************************************************************//* Purpose: Used to determine where a new activation is      *//*   placed on the agenda based on the current conflict      *//*   resolution strategy (depth, breadth, mea, lex,          *//*   simplicity, or complexity). Also provides the           *//*   set-strategy and get-strategy commands.                 *//*                                                           *//* Principal Programmer(s):                                  *//*      Gary D. Riley                                        *//*                                                           *//* Contributing Programmer(s):                               *//*                                                           *//* Revision History:                                         *//*      6.23: Corrected compilation errors for files         *//*            generated by constructs-to-c. DR0861           *//*                                                           *//*      6.24: Removed CONFLICT_RESOLUTION_STRATEGIES         *//*            compilation flag.                              *//*                                                           *//*      6.30: Added salience groups to improve performance   *//*            with large numbers of activations of different *//*            saliences.                                     *//*                                                           *//*            Removed pseudo-facts used for not CEs.         *//*                                                           *//*************************************************************/#define _CRSTRTGY_SOURCE_#include <stdio.h>#define _STDIO_INCLUDED_#include <string.h>#include "setup.h"#if DEFRULE_CONSTRUCT#include "constant.h"#include "pattern.h"#include "reteutil.h"#include "argacces.h"#include "agenda.h"#include "envrnmnt.h"#include "memalloc.h"#include "crstrtgy.h"#define GetMatchingItem(x,i) ((x->basis->binds[i].gm.theMatch != NULL) ? \                              (x->basis->binds[i].gm.theMatch->matchingItem) : NULL)/***************************************//* LOCAL INTERNAL FUNCTION DEFINITIONS *//***************************************/   static ACTIVATION             *PlaceDepthActivation(ACTIVATION *,struct salienceGroup *);   static ACTIVATION             *PlaceBreadthActivation(ACTIVATION *,struct salienceGroup *);   static ACTIVATION             *PlaceLEXActivation(void *,ACTIVATION *,struct salienceGroup *);   static ACTIVATION             *PlaceMEAActivation(void *,ACTIVATION *,struct salienceGroup *);   static ACTIVATION             *PlaceComplexityActivation(ACTIVATION *,struct salienceGroup *);   static ACTIVATION             *PlaceSimplicityActivation(ACTIVATION *,struct salienceGroup *);   static ACTIVATION             *PlaceRandomActivation(ACTIVATION *,struct salienceGroup *);   static int                     ComparePartialMatches(void *,ACTIVATION *,ACTIVATION *);   static char                   *GetStrategyName(int);   static unsigned long long     *SortPartialMatch(void *,struct partialMatch *);   /******************************************************************//* PlaceActivation: Coordinates placement of an activation on the *//*   Agenda based on the current conflict resolution strategy.    *//******************************************************************/globle void PlaceActivation(  void *theEnv,  ACTIVATION **whichAgenda,  ACTIVATION *newActivation,  struct salienceGroup *theGroup)  {   ACTIVATION *placeAfter = NULL;   /*================================================*/   /* Set the flag which indicates that a change has */   /* been made to the agenda.                       */   /*================================================*/   EnvSetAgendaChanged(theEnv,TRUE);   /*=============================================*/   /* Determine the location where the activation */   /* should be placed in the agenda based on the */   /* current conflict resolution strategy.       */   /*==============================================*/   if (*whichAgenda != NULL)      {      switch (AgendaData(theEnv)->Strategy)        {         case DEPTH_STRATEGY:           placeAfter = PlaceDepthActivation(newActivation,theGroup);           break;         case BREADTH_STRATEGY:           placeAfter = PlaceBreadthActivation(newActivation,theGroup);           break;         case LEX_STRATEGY:           placeAfter = PlaceLEXActivation(theEnv,newActivation,theGroup);           break;         case MEA_STRATEGY:           placeAfter = PlaceMEAActivation(theEnv,newActivation,theGroup);           break;         case COMPLEXITY_STRATEGY:           placeAfter = PlaceComplexityActivation(newActivation,theGroup);           break;         case SIMPLICITY_STRATEGY:           placeAfter = PlaceSimplicityActivation(newActivation,theGroup);           break;         case RANDOM_STRATEGY:           placeAfter = PlaceRandomActivation(newActivation,theGroup);           break;        }     }    else     {      theGroup->first = newActivation;      theGroup->last = newActivation;     }   /*==============================================================*/   /* Place the activation at the appropriate place in the agenda. */   /*==============================================================*/   if (placeAfter == NULL) /* then place it at the beginning of then agenda. */     {      newActivation->next = *whichAgenda;      *whichAgenda = newActivation;      if (newActivation->next != NULL) newActivation->next->prev = newActivation;     }   else /* insert it in the agenda. */     {      newActivation->next = placeAfter->next;      newActivation->prev = placeAfter;      placeAfter->next = newActivation;      if (newActivation->next != NULL)        { newActivation->next->prev = newActivation; }     }  }/*******************************************************************//* PlaceDepthActivation: Determines the location in the agenda     *//*    where a new activation should be placed for the depth        *//*    strategy. Returns a pointer to the activation after which    *//*    the new activation should be placed (or NULL if the          *//*    activation should be placed at the beginning of the agenda). *//*******************************************************************/static ACTIVATION *PlaceDepthActivation(  ACTIVATION *newActivation,  struct salienceGroup *theGroup)  {   ACTIVATION *lastAct, *actPtr;   unsigned long long timetag;        /*============================================*/   /* Set up initial information for the search. */   /*============================================*/   timetag = newActivation->timetag;   if (theGroup->prev == NULL)     { lastAct = NULL; }   else     { lastAct = theGroup->prev->last; }   /*=========================================================*/   /* Find the insertion point in the agenda. The activation  */   /* is placed before activations of lower salience and      */   /* after activations of higher salience. Among activations */   /* of equal salience, the activation is placed before      */   /* activations with an equal or lower timetag (yielding    */   /* depth first traversal).                                 */   /*=========================================================*/   actPtr = theGroup->first;   while (actPtr != NULL)     {      if (timetag < actPtr->timetag)        {         lastAct = actPtr;         if (actPtr == theGroup->last)           { break; }         else            { actPtr = actPtr->next; }        }      else        { break; }     }   /*========================================*/   /* Update the salience group information. */   /*========================================*/      if ((lastAct == NULL) ||        ((theGroup->prev != NULL) && (theGroup->prev->last == lastAct)))     { theGroup->first = newActivation; }        if ((theGroup->last == NULL) || (theGroup->last == lastAct))     { theGroup->last = newActivation; }   /*===========================================*/   /* Return the insertion point in the agenda. */   /*===========================================*/   return(lastAct);  }/*******************************************************************//* PlaceBreadthActivation: Determines the location in the agenda   *//*    where a new activation should be placed for the breadth      *//*    strategy. Returns a pointer to the activation after which    *//*    the new activation should be placed (or NULL if the          *//*    activation should be placed at the beginning of the agenda). *//*******************************************************************/static ACTIVATION *PlaceBreadthActivation(  ACTIVATION *newActivation,  struct salienceGroup *theGroup)  {   unsigned long long timetag;   ACTIVATION *lastAct, *actPtr;   /*============================================*/   /* Set up initial information for the search. */   /*============================================*/   timetag = newActivation->timetag;   if (theGroup->last == NULL)     {          if (theGroup->prev == NULL)        { lastAct = NULL; }      else        { lastAct = theGroup->prev->last; }     }   else     { lastAct = theGroup->last; }   /*=========================================================*/   /* Find the insertion point in the agenda. The activation  */   /* is placed before activations of lower salience and      */   /* after activations of higher salience. Among activations */   /* of equal salience, the activation is placed after       */   /* activations with a lessor timetag (yielding breadth     */   /* first traversal).                                       */   /*=========================================================*/   actPtr = theGroup->last;   while (actPtr != NULL)     {      if (timetag < actPtr->timetag)        {         if (actPtr == theGroup->first)           {            if (theGroup->prev == NULL)              { lastAct = NULL; }            else              { lastAct = theGroup->prev->last; }            break;           }         else            { actPtr = actPtr->prev; }        }      else        {         lastAct = actPtr;          break;         }     }        /*========================================*/   /* Update the salience group information. */   /*========================================*/      if ((lastAct == NULL) ||        ((theGroup->prev != NULL) && (theGroup->prev->last == lastAct)))     { theGroup->first = newActivation; }        if ((theGroup->last == NULL) || (theGroup->last == lastAct))     { theGroup->last = newActivation; }   /*===========================================*/   /* Return the insertion point in the agenda. */   /*===========================================*/   return(lastAct);  }/*******************************************************************//* PlaceLEXActivation: Determines the location in the agenda       *//*    where a new activation should be placed for the lex          *//*    strategy. Returns a pointer to the activation after which    *//*    the new activation should be placed (or NULL if the          *//*    activation should be placed at the beginning of the agenda). *//*******************************************************************/static ACTIVATION *PlaceLEXActivation(  void *theEnv,  ACTIVATION *newActivation,  struct salienceGroup *theGroup)  {   unsigned long long timetag;   ACTIVATION *lastAct, *actPtr;   int flag;   /*============================================*/   /* Set up initial information for the search. */   /*============================================*/   timetag = newActivation->timetag;   if (theGroup->prev == NULL)     { lastAct = NULL; }   else     { lastAct = theGroup->prev->last; }   /*================================================*/   /* Look first at the very end of the group to see */   /* if the activation should be placed there.      */   /*================================================*/      actPtr = theGroup->last;   if (actPtr != NULL)     {      flag = ComparePartialMatches(theEnv,actPtr,newActivation);            if ((flag == LESS_THAN) ||          ((flag == EQUAL) &&  (timetag > actPtr->timetag)))        {         theGroup->last = newActivation;                   return(actPtr);        }     }        /*=========================================================*/   /* Find the insertion point in the agenda. The activation  */   /* is placed before activations of lower salience and      */   /* after activations of higher salience. Among activations */   /* of equal salience, the OPS5 lex strategy is used for    */   /* determining placement.                                  */   /*=========================================================*/   actPtr = theGroup->first;   while (actPtr != NULL)     {      flag = ComparePartialMatches(theEnv,actPtr,newActivation);