/*********************** PGraphplan **************************************
  (C) Copyright 1999 Avrim Blum and John Langford,
  based on Graphplan code Copyright 1995 by Avrim Blum and Merrick Furst

  This software is made available AS IS, and neither the authors nor CMU make 
  any warranty about the software or its performance. 
*************************************************************************/

#include "graphplan.h"
#include <sys/time.h>

/* The code consists of the following main parts.

1. Reading in the operator and fact files. 

2. Creating the graph and performing instantiations

   (same as in Graphplan, but no longer using mutexs)

3. Propoagating "neededness" constraints and heuristic values

4. Doing forward chaining search with memoizing

 Note: can have planner minimize expected time to complete.  In this case,
 failure within the time window gives utility (negative of time to complete)
 of VERYBAD.

*/

/* GLOBAL VARIABLES */

char junk[100]; 
fact_list the_types;           /* list of all the different type decls */
probdef_list the_probs;        /* list of probability definitions */
fact_list initial_facts, the_goals; /* initial facts and goals */
hashtable_t *fact_table, *op_table;  /* the arrays of hash tables */
hashtable_t types_table;  /* holds the types */
int *value_of_null;    /* use for heuristic values */

extern int hash_hits, hash_inserts; /* entries in plan hash table */

/* these are defaults */
int MAXNODES = 256;  /* default MAX number of nodes at any given time step. */
int DEBUG_FLAG = 0, do_remove = 2, 
  do_heuristic_value = 1, debugging_mode = 0, 
  do_minexp = 0, print_horizon = -1, print_path = 0;
int done_creating_graph = 0;
int VERYBAD =  -100;   /* utility of failing when minimizing expectation */

int *utilities;      /* utility of solving goals at given time */
int util_of_failing; /* utility of not solving goals */

int do_completeness = 1; /* do completeness check */

/* other flags, counters, etc. */
int same_as_prev_flag = 0;  /* graph layer is same as previous time step */
extern int number_of_recursive_calls, number_of_actions_tried;
int bvec_len = 1;  /* max facts in a time step / 32 */
int num_goals;

int instrs(void)
{
  printf("command line args.  Use any of: \n \
          -h               for this list \n \
          -o <op file>     to specify operator file\n \
          -f <fact file>   to specify fact file\n \
          -t <integer>     to specify a fixed number of time steps\n \
          -i <info level>  to specify info level 1, 2, or 3 (default is 0)\n \
          -O <option list> to specify options you want\n \
          -M <integer>     to specify alternative max nodes in a time step\n \
                            (default is 256)\n \
          -d               give default values to everything not specified\n\
\n   for example: pgplan -o Domains/moat_ops -f Domains/moat2_facts -t 5 \n\
          \n\n");
  return 0;
}

struct timeval start, end;

int main(int argc, char *argv[])
{
  op_list ops;
  int i,max_time=AUTO, givedef=0;
  double result;
  FILE *fp;
  char opfile[50], factfile[50], option[10];

  if (argc == 1) {
    printf("Welcome to PGraphplan. 'pgplan -h' gives help on command-line args.\n\n");
  }
  option[0] = opfile[0] = factfile[0] = '\0';
  DEBUG_FLAG = 0;
  for(i = 1; i < argc; ++i) {
    if (argv[i][0] != '-') continue; 
    if (argv[i][1] == 'h') {instrs(); exit(0);}
    else if (argv[i][1] == 'd') givedef = 1;
    else if (i == argc - 1) do_error("command line args not in proper format");
    else if (argv[i][1] == 'o') strcpy(opfile,argv[i+1]);
    else if (argv[i][1] == 'f') strcpy(factfile,argv[i+1]);
    else if (argv[i][1] == 't') sscanf(argv[i+1],"%d",&max_time);
    else if (argv[i][1] == 'i') sscanf(argv[i+1],"%d",&DEBUG_FLAG);
    else if (argv[i][1] == 'O') strcpy(option,argv[i+1]);
    else if (argv[i][1] == 'M') sscanf(argv[i+1],"%d",&MAXNODES);
  }
  /* if (max_time < 1) do_error("please give legal max time"); */
  if (MAXNODES > MAXMAXNODES)
    do_error("Sorry, can't handle that large MAXNODES");


  /*LOAD IN OPS AND FACTS FILES. If ends in ".lisp", assume prodigy style*/
  if (!opfile[0]) {
    printf("give file name for operators: ");
    gets(opfile);
  }
  if ((fp = fopen(opfile,"r")) == NULL) do_error("cant load operator file");
  if (strcmp(opfile+max((strlen(opfile)-strlen(LISPEXT)),0),LISPEXT) == SAME)
    do_error("no longer allowing ops in prodigy format");
  else
    ops = load_ops(fp);
  if (!ops) do_error("illegal ops file");

  if (!factfile[0]) {
    printf("give file name for initial facts: ");
    gets(factfile); 
  }
  if ((fp = fopen(factfile,"r")) == NULL) do_error("cant load facts file");
  the_types = load_types(fp);  /* load in types.  Also sets up the_probs */
  load_fact_list(fp, &initial_facts);  /* load in actual facts */
  read_item(fp,junk); /* left paren */
  read_item(fp,junk); /* "effects" */
  num_goals = load_fact_list(fp, &the_goals);  /* load in the goals */
  if (num_goals > MAXGOALS) do_error("MAXGOALS too small");
  printf("facts loaded.\n");

  if (max_time == AUTO) {
    printf("number of time steps (automatic is disabled): ");
    scanf("%d",&max_time);
    gets(junk);  /* get the CR */
  }

  if (!givedef && DEBUG_FLAG == 0) {
    printf("Info type: (3 = max, 0 or <CR> = min): ");
    gets(junk);
    if (*junk == '3') DEBUG_FLAG = 3;
    else if (*junk == '2') DEBUG_FLAG = 2;
    else if (*junk == '1') DEBUG_FLAG = 1;
    else DEBUG_FLAG = 0;
  }

  /* OTHER OPTIONS */
  /* For instance, to simulate straight top-down dynamic programming, 
     using options VNN  */
  if (option[0] == '\0' && !givedef) {
    printf("other options (concatenate together for multiple):\n");
    printf("        'D' = debugging mode\n");
    printf("        'E' = minimize expected time to complete\n");
    printf("        'S' = don't print entire plan. Just one random path\n");
    printf("        'SS'= just two random paths, etc.\n");
    printf("        'P' = don't print entire plan. Just first action\n");
    printf("        'PP'= Just first 2 actions, etc.\n");
    printf("        'V' = don't propagate heuristic values\n");
    printf("        'N' = don't do 'pairwise neededness' relations\n");
    printf("        'NN'= N+don't even remove obviously unneeded vertices: ");
    gets(option);
  }

  for(i=0; option[i] != '\0'; ++i) {
    if (option[i] == 'D') debugging_mode = 1;
    if (option[i] == 'N') {--do_remove; if (do_remove < 0) do_remove = 0;}
    if (option[i] == 'S') ++print_path;
    if (option[i] == 'P') ++print_horizon;  /* just print up to horizon */
    if (option[i] == 'V') do_heuristic_value = 0;
    if (option[i] == 'E') do_minexp =1;
  }
  setup_utilities(do_minexp, max_time);

  /* BEGIN TIMING */
  gettimeofday(&start,0);

  /* MAKE GRAPH AND START PLANNING */
  max_time = create_graph(ops, initial_facts, max_time);
  if (max_time == -1) {
    if (same_as_prev_flag)
      printf("Problem not solvable: can't even reach goals.\n");
    else 
      printf("Can't get there from here in allotted time.\n");
  } else {
    if (do_remove) remove_unneeded_vertices(max_time);
    if (do_heuristic_value) propagate_heuristic_values(max_time);
    if (DEBUG_FLAG > 1) print_info(max_time);
    done_creating_graph = 1;
    if ((result = do_plan(max_time)) == util_of_failing) 
      print_cant_do(max_time);
  }
  gettimeofday(&end,0);
  if (end.tv_sec - start.tv_sec < 60)
    fprintf(stdout,"  %.2f secs\n",end.tv_sec + end.tv_usec/1000000.0 - 
	    (start.tv_sec + start.tv_usec/1000000.0));
  else
    fprintf(stdout,"  %d min, %d seconds\n",(int) (end.tv_sec - start.tv_sec)
	    / 60, (int) (end.tv_sec - start.tv_sec)%60);

  return 0;
}

/* setup util_of_failing and utilities[t] for each time-step t, so that
   maximizing expected utility does what we want.  For min expected time, 
   utility of failing is VERYBAD */
void  setup_utilities(int do_minexp, int max_time)
{
  int i;
  if (max_time == AUTO) do_error("automatic is disabled");
  utilities = (int *) calloc(max_time+1, sizeof(int));
  if (!do_minexp) {                     /* we want max prob of success */
    util_of_failing = 0;
    for(i=0; i<=max_time; ++i) utilities[i] = 1;
  } else {                              /* want to minimize expected time*/
    util_of_failing = VERYBAD;
    for(i=0; i<=max_time; ++i) utilities[i] = -i;
    printf("If solution not found, viewing as %d in calc of expected time\n",
	   -util_of_failing);
  }
}


/* speedup: propagate heuristic values backward.  The idea is that a state
   at time t must have value at least t in order for it to be possible
   to reach the goals using at most one operator per time step.
   Initially, we give each goal the value maxtime/(#goals).
   (these are ints so arbitrarily break ties)

   Then we use the following method to propagate values backwards:
   1. values on facts at time t are copied to time t-1.
   2. for each op at time t-1, for each "possibility" ("inclusion") of that op,
      (a) value of the inclusion = -1 + sum of values of add-effects of 
          that inclusion.  For this purpose, think of non-deleted preconditions
	  ("catalysts") as add-effects.

      (b) subtract value(p) for all preconditions p.  (This is the amount
          that can be given "for free").  Call the end result "val".

      (c) Now, distribute "val" among the preconditions.  From looking 
          at typical domains, it seems best is to give to precs that 
	  are deleted (think about what happens if same op appears
	  in several time steps in a row).  So, if any precs are deleted,
	  will spread evenly among them.  Else, spread evenly among all precs.

    Note: if op has no preconds, then view it as having a single "null"
          precond with value = value_of_null

    Note2: can think of the above method as imagining that the planner is
          able to choose which possibility of each op occurs.  So, 
	  when we say "impossible to solve goals" we mean that it is 
	  impossible even if the planner had that choice.

*/
void propagate_heuristic_values(int maxtime)
{
  int current_sum, inclval;
  fact_list temp;
  vertex_t vert, op;
  incl_list incl;
  edgelist_t edge, prec, del;
  char str[100];
  int t, total_precs, precs_deleted, prec_remaining, to_give, free_value,
    value_remaining = maxtime, goals_remaining = num_goals; 

  /* begin by setting values of goals (and for safety set all others to 0)*/
  get_next(fact_table[maxtime],0);
  while((vert = get_next(fact_table[maxtime],1)) != NULL)
    vert->heuristic_value = 0;
  for(temp=the_goals; temp; temp = temp->next) {
     instantiate_into_string(temp->item, NULL, str,1);
     if ((vert = lookup_from_table(fact_table[maxtime],str)) == NULL) 
       do_error("goal not found in output");
     vert->heuristic_value = value_remaining/goals_remaining;
     --goals_remaining;
     value_remaining -= vert->heuristic_value;
  }
  value_of_null[maxtime] = 0;   /* special for ops with no preconds */

  /* now propagate backwards */
  for(t = maxtime; t > 0; --t) {
    /* first, copy value of facts at time t to time t-1 */
    value_of_null[t-1] = value_of_null[t];
    get_next(fact_table[t],0);                 /* INIT */
    while((vert = get_next(fact_table[t],1)) != NULL) {
      if (!vert->prev_time) continue;
      if (do_remove && !vert->needed) continue;
      vert->prev_time->heuristic_value = vert->heuristic_value;

      /* for debugging */
      if (DEBUG_FLAG && vert->heuristic_value != 0)
	printf("%s has value %d at time %d\n",
	       vert->name,vert->heuristic_value, t);
    }
    /* now, do the non-noop ops */
    get_next(op_table[t-1], 0);
    while((op = get_next(op_table[t-1],1)) != NULL) {
      op->heuristic_value = -1;
      if (op->is_noop) continue;
      if (do_remove && !op->needed) continue;
      /* Do each inclusion.  value of inclusion = sum of values of add
	 effects, minus 1.  For this purpose, think of non-deleted preconds
	 as "add effects".  we subtract 1 for the "cost" of performing
	 the operator.  */
      for(incl = op->inclusions; incl; incl = incl->next) {
	current_sum = -1;
	for(edge = op->out_edges; edge; edge = edge->next) {
	  if (edge->incl != incl) continue;   /* a different outcome */
	  current_sum += edge->endpt->heuristic_value;
	}
	/* now do non-deleted preconds.  Also gather info about preconds */
	total_precs = precs_deleted = 0;
	for(prec = op->in_edges; prec; prec = prec->next) {
	  ++total_precs;
	  for(del = op->del_edges; del; del = del->next) {
	    if (del->incl != incl) continue;
	    if (prec->endpt == del->endpt->prev_time) break;
	  }
	  if (!del) {   /* was not deleted */
	    current_sum += prec->endpt->next_time->heuristic_value;
	  } else {
	    ++precs_deleted;
	  }
	}
	inclval =  current_sum; /* value of the inclusion */

	/* now compute the amount of value that can be given to preconds for
	   free.  Use value_of_null if no preconds.  */

	if (!op->in_edges) 
	  free_value = value_of_null[t-1] - value_of_null[t];
	else 
	  for(free_value = 0, prec = op->in_edges; prec; prec = prec->next)
	    free_value += prec->endpt->heuristic_value;
	
	/* for debugging */
	if (DEBUG_FLAG) {
	  printf("%s has value %d at time %d but giving %d for free\n",
		 op->name,inclval,t-1, free_value);
	}

	if (inclval > op->heuristic_value) op->heuristic_value = inclval;
	if (inclval > free_value) {
	  /* distribute value remaining */
	  value_remaining = inclval - free_value;
	  if (!op->in_edges) value_of_null[t-1] += value_remaining;
	  else if (precs_deleted == 0) {   /* distribute evenly */
	    prec_remaining = total_precs;
	    for (prec = op->in_edges; prec; prec = prec->next) {
	      to_give = value_remaining / prec_remaining;
	      prec->endpt->heuristic_value += to_give;
	      value_remaining -= to_give;
	      --prec_remaining;

	      /* for debugging */
	      if (DEBUG_FLAG) 
		printf("   giving %d to %s\n",to_give, prec->endpt->name);
	    }
	  } else {                         /* distribute among precs deleted*/
	    prec_remaining = precs_deleted;
	    for (prec = op->in_edges; prec; prec = prec->next) {
	      for(del = op->del_edges; del; del = del->next) {
		if (del->incl != incl) continue;
		if (prec->endpt == del->endpt->prev_time) { /* I am deleted */
		  to_give = value_remaining / prec_remaining;
		  prec->endpt->heuristic_value += to_give;
		  value_remaining -= to_give;
		  --prec_remaining;

		  /* for debugging */
		  if (DEBUG_FLAG) 
		    printf("   giving %d to %s\n",to_give, prec->endpt->name);

		  break;
		}
	      }
	    }
	  }
	}     /* done distributing values */
	/* done with the inclusion */
      }
    }
  }
  printf("done propagating heuristic values.\n");
}



char foostring[NEEDVECLEN+1];
NeedVec global_needed_vec;

/* utility for printing needed_vec */
char *vecstr(int x)
{
  int i;
  for(i=0; i < NEEDVECLEN; ++i) {
    if ((x & (1 << i)) != 0) foostring[i] = 'x';
    else foostring[i] = '.';
  }
  for(i=NEEDVECLEN; i >= 0; --i) {
    foostring[i] = '\0';
    if (foostring[i-1] == 'x') break;
  }
  return foostring;
}

/* This routine takes in a count of the number of goals observed so far,
   and a new goal.  If this new goal can be created by only one non-noop
   action, then we "replace" that goal by the preconditions to that action,
   marking those preconditions as if they were the goals and giving the 
   real goal the union of those marks.

   Two caveats:
   (1) if a precond is already marked, we don't mark it again.
   (2) if a precond is actually a goal, we don't mark it.

   We don't continure recursively, because it is too messy.

   We return the new value of the count.
*/

int mark_and_check_preconds(int count, vertex_t goal, int time)
{
  edgelist_t edge;
  vertex_t action;
  int numactions = 0;

  goal->needed = 1;
  if (count >= NEEDVECLEN)
    do_error("sorry I lazily set up max goals to be 32");

  /* see if exactly one non-noop that creates goal */
  for(edge = goal->in_edges; edge; edge = edge->next) {
    if (edge->endpt->is_noop) continue;
    numactions++;
    action = edge->endpt;
  }
  if (numactions != 1) { /* we are *not* replacing this goal with preconds*/
    goal->needed_vec = (1 << count);
    global_needed_vec |= (1 << count);
    if (DEBUG_FLAG) printf("Marking %s at time %d as a basic goal\n",
			   goal->name, time);
    return count+1;
  }
  /* we *are* replacing the goal with the preconds to this action */
  for(edge = action->in_edges; edge; edge = edge->next) {
    /* check caveats (1) and (2) */
    if (edge->endpt->needed || edge->endpt->next_time->needed) continue;
    edge->endpt->needed = 1;
    edge->endpt->needed_vec = (1 << count);
    goal->needed_vec |= (1 << count);
    global_needed_vec |= (1 << count);
    ++count;
    if (DEBUG_FLAG) printf("%s inheriting from %s\n",
			   goal->name, edge->endpt->name);
  }
  return count;
}


/* if do_remove == 1:
    Simple speedup: removes vertices that could never be reached by planner.

    AND, mark down WHICH GOAL each vertex is needed for.  Then we can 
    backtrack from any state for which not all goals are represented.  In fact,
    for goals that can be created in only one (non noop) way, we can view
    the preconds to this action as goals too for this purpose.  This is
    handled by mark_and_check_preconds.  We could imagine doing this 
    recursively (in fact it seems very natural to do so) but for various
    reasons that gets messy, so we don't.

   if do_remove > 1:
    In addition, set up pairwise "A requires B" relations
     - a noop A requires op B if the add-effect F of A requires a fact G
       that can be created only through B.
     - a non-noop A requires noop B if the effect G of B is not an add-effect
       of A, and if all needed add-effects F of A require G.  In fact, if
       G has no in-edges (not even a noop) then A is unneeded after all.

     - fact F requires fact G if all needed ops A that F is a precondition to
       either (a) have G as a precondition, or (b) require an op B with G
       as a precondition

     - Base Case:  All goals need each other at the end.  This is equivalent 
       to having a final action that takes in all goals and outputs a 
       super-goal.

 */
void remove_unneeded_vertices(int time)
{
  fact_list temp, temp2;
  vertex_t vert, vert2, a, ap, b, bp, f, g;
  edgelist_t edge, edge2, edge3, edge4, edge5, tempe;
  int count, flag, ok;
  char str[100];

  global_needed_vec = 0;
  /* begin by marking goals as needed at the end*/
  for(temp=the_goals; temp; temp = temp->next) {
     instantiate_into_string(temp->item, NULL, str,1);
     if ((vert = lookup_from_table(fact_table[time],str)) == NULL) 
       do_error("goal not found in remove_unneeded_vertices");
     vert->needed = 1;
  }
  /* now set up needed_vec and pairwise neededness for goals */
  for(count=0, temp=the_goals; temp; temp = temp->next) {
     instantiate_into_string(temp->item, NULL, str,1);
     vert = lookup_from_table(fact_table[time],str);
     count = mark_and_check_preconds(count, vert, time);

     if (do_remove > 1) {
       for(temp2 = temp->next; temp2; temp2 = temp2->next) { 
	 instantiate_into_string(temp2->item, NULL, str,1);
	 vert2 = lookup_from_table(fact_table[time],str); 
	 vert->requirements = insert_edge(vert->requirements,vert2,NULL);
	 vert2->requirements = insert_edge(vert2->requirements,vert,NULL);
	 if (DEBUG_FLAG) printf("%s requires %s and vice versa at time %d\n",
				vert->name, vert2->name, time);
       }
     }

  }
  /* now work backwards from end.  An operator is needed if it has a 
   * needed add-effect.   A fact is needed if it has an edge into
   * a needed operator or NOOP (if it's needed in a later time step). */
  for(--time; time >= 0; --time) {
    /* do ops */
    get_next(op_table[time],0);                   /* INIT */
    while((vert = get_next(op_table[time],1)) != NULL) {
      vert->needed = 0;
      for(edge = vert->out_edges; edge; edge = edge->next)
	if(edge->endpt->needed) {
	  vert->needed = 1;
	  vert->needed_vec |= edge->endpt->needed_vec;
	}
      if (DEBUG_FLAG && !vert->is_noop) {
	if (vert->needed == 0)
	  printf("discarding %s at time %d\n",vert->name, time);
	else
	  printf("%s at time %d has needed_vec %s\n",vert->name,
		 time, vecstr(vert->needed_vec));
      }
      /* special for op with no in-edges. Tricky, tricky */
      if (!vert->in_edges) global_needed_vec = 
		 (global_needed_vec | vert->needed_vec) ^ vert->needed_vec;

      /* do the pairwise relation if asked for */
      if (do_remove > 1 && vert->needed) { 
	if (vert->is_noop) {  /* do no-op case */
	  f = vert->out_edges->endpt;
	  for(edge=f->requirements; edge; edge=edge->next) {
	    g = edge->endpt;
	    if (g->in_edges->next == NULL) {
	      b = g->in_edges->endpt;
	      vert->requirements = insert_edge(vert->requirements,b,NULL);
	      if (DEBUG_FLAG) printf("%s requires %s at time %d\n",
				     vert->name, b->name,time); 
	    }
	  }
	} else {              /* do non-noop case */
	  for(edge=vert->out_edges; edge; edge = edge->next)
	    if (edge->endpt->needed) break;  /* find some needed add-effect */
	  for(edge2 = edge->endpt->requirements; edge2; edge2 = edge2->next) {
	    g = edge2->endpt;  /* g is a candidate */

	    /* step 1: check that g is not an add-effect */
	    for(edge3 = vert->out_edges; edge3; edge3 = edge3->next)
	      if (edge3->endpt == g) break; /* nope */
	    if (edge3) continue;            /* nope */

	    /* step 2: see if g is required by the rest of the add-effects */
	    for(edge3 = edge->next; edge3; edge3 = edge3->next) {
	      if (!edge3->endpt->needed) continue;
	      f = edge3->endpt;
	      for(edge4 = f->requirements; edge4; edge4 = edge4->next) {
		if (edge4->endpt == g) break; /* ok so far... */
	      }
	      if (!edge4) break;  /* nope */
	    }
	    if (edge3) continue;  /* nope */

	    /* yay. g's noop really is needed.  Set b to be this noop */
	    for(edge3 = g->in_edges; edge3; edge3 = edge3->next)
	      if (edge3->endpt->is_noop) break;
	    if (!edge3) { /* no noop into g */
	      vert->needed = 0;
	      printf("%s unneeded after all at time %d\n",vert->name,time);
	      continue;
	    } 
	    b = edge3->endpt;
	    vert->requirements = insert_edge(vert->requirements,b,NULL);
	    if (DEBUG_FLAG) printf("%s requires %s at time %d\n",
				   vert->name, b->name,time);
	  }
	}
      }
    }

    /*do facts */
    get_next(fact_table[time],0);                 /* INIT */
    while((vert = get_next(fact_table[time],1)) != NULL) {
      if (vert->needed == 0) { /* not already handled by mark_and_check */
	for(edge = vert->out_edges; edge; edge = edge->next) { /* incl' NOOP */
	  if(edge->endpt->needed) {
	    vert->needed = 1;
	    vert->needed_vec |= edge->endpt->needed_vec;
	  }
	}
      }
      /* do the pairwise relation if asked for */
      if (do_remove > 1 && vert->needed) {
	for(edge=vert->out_edges; edge; edge = edge->next)
	  if (edge->endpt->needed) break;
	a = edge->endpt;
	/* all required G's are either precond of A or precond of some B
	   required by A.  flag=0 means working on 1st case, flag=1 means
	   working on 2nd case */
	for(flag=0, edge2 = a->in_edges; 1 ; edge2 = edge2->next) {
	  if (!edge2) {
	    if (flag == 0) {
	      flag = 1;
	      tempe = a->requirements;
	    } else {
	      tempe = tempe->next;
	    }
	    if (!tempe) break;
	    b = tempe->endpt;
	    edge2 = b->in_edges;
	  }
	  g = edge2->endpt;
	  if (g == vert) continue;

	  /* g is a candidate. Check any remaining ops */
	  ok = 1;
	  for(edge5 = edge->next; edge5; edge5 = edge5->next) {
	    if (!edge5->endpt->needed) continue;
	    ok = 0;
	    ap = edge5->endpt;
	    for(edge3 = ap->in_edges; edge3; edge3 = edge3->next) {
	      if (edge3->endpt == g) ok = 1;
	    }
	    if (ok == 1) continue;
	    for(edge3 = ap->requirements; edge3; edge3 = edge3->next) {
	      bp = edge3->endpt;
	      for(edge4 =bp->in_edges; edge4; edge4 = edge4->next) {
		if (edge4->endpt == g) ok= 1;
	      }
	    }
	    if (ok == 0) break;
	  }
	  if (ok == 1) { /* g really is required */
	    vert->requirements = insert_edge(vert->requirements,g,NULL);
	    if (DEBUG_FLAG) printf("%s requires %s at time %d\n",
				   vert->name, g->name,time);
	  }
	}
      }
    }
  }
  printf("done removing unneeded vertices.\n");
  if (do_remove > 1) printf("done setting up pairwise relations\n");
}



/***********creating the graph*************************************
 ******************************************************************/


/* this routine makes a layer of noops.  Assumes next fact already in table.
 */
void make_noop_layer(int time)
{
  vertex_t noop,v,w;
  get_next(fact_table[time],0);  /**INIT**/
  while((v = get_next(fact_table[time],1)) != NULL) {
    w = v->next_time;
    noop = insert_into_table(op_table[time],make_noop_string(v->name));
    noop->is_noop = 1;  /* SAY THAT IT'S A NOOP */
    noop->in_edges = insert_edge(noop->in_edges, v,NULL);
    v->out_edges = insert_edge(v->out_edges,noop,NULL);
    noop->out_edges = insert_edge(noop->out_edges,w,NULL);
    w->in_edges = insert_edge(w->in_edges,noop,NULL);
  }
}

/***********create the graph************************************
* Given a list of ops, a list of initial facts and a length 
* of time, we create the graph.
*************************************/


/* This routine creates a single layer: op_table[time] and fact_table[time+1].
   Assumes is always called on consecutive time steps.  To make sure
   I don't forget this, "time" is a static variable.
 */
void create_graph_layer(op_list olist)
{
  static int time = 0;
  int i;
  static pair fact_summary, old_fact_summary;
  fact_list flist;
  op_ptr op;
  vertex_t v,w;
  if (time == 0) fact_summary.first = fact_summary.second = 0;
  if (same_as_prev_flag) make_copy(time);
  else {
    /* first copy facts over to next time step */
    get_next(fact_table[time],0);  /**INIT**/
    while((v = get_next(fact_table[time],1)) != NULL) {
      w = insert_into_table(fact_table[time+1],v->name);
      w->prev_time = v;
      v->next_time = w;
    }
    /* get fact list from the hash table (INEFFICIENT!) */
    flist = make_list_from_htable(fact_table[time]);
    /* do ops */
    for(op = olist; op != NULL; op = op->next)
      do_operator(fact_table[time], flist, op, op->preconds, time);
    completely_free_fact_list(flist);

    /* make the noop layer.  NOTE: doing it HERE so that the noops will be
     the first ones in the list.  Makes it easier for the planner to
     try them FIRST. */
    make_noop_layer(time);

    /* fact summary */
    old_fact_summary = fact_summary;
    fact_summary.first = 0;  /* how many facts */

    /* set up uids and rands*/
    get_next(op_table[time], 0);  /* INIT */
    for(i=0;  (v = get_next(op_table[time],1)) != NULL; ++i) {
      if (i >= MAXNODES) do_error("Too many ops. Need to increase MAXNODES");
      set_uid(v,i);
    }
    get_next(fact_table[time+1],0);  /**INIT**/
    for(i=0; (v = get_next(fact_table[time+1],1)) != NULL; ++i) {
      if (i >= MAXNODES) do_error("Too many ops. Need to increase MAXNODES");
      v->rand1 = random(); /* these are used in memoizing */
      set_uid(v,i);        /* everybody needs a unique ID */
      ++fact_summary.first;
    }

    /* put in delete edges */
    put_in_all_del_edges(op_table, time);

    if (fact_summary.first == old_fact_summary.first)
      same_as_prev_flag=1;
  }

  /* setting bit vector length */
  if (bvec_len * 32 < fact_summary.first) bvec_len = 1 + fact_summary.first/32;
  printf("time: %d, %d facts.\n",
	 time+1, fact_summary.first);
  ++time;  /* INCREMENT TIME... */
}

/* Keep going until "can_stop".
 * Returns max time used.
 * Returns -1 if can't get there from here (i.e., goals not in graph)
 */
int create_graph(op_list olist, fact_list flist, int maxtime)
{
  int time = 0, i, autostop = (maxtime == AUTO);
  vertex_t v;

  num_created = 0;  /* GLOBAL: how many nodes created */
  if (autostop) maxtime = max_auto;

  /* allocate space */
  fact_table = (hashtable_t *) calloc(maxtime+1,sizeof(hashtable_t));
  op_table = (hashtable_t *) calloc(maxtime,sizeof(hashtable_t));
  value_of_null = (int *) calloc(maxtime+1, sizeof(int));

  /* load in initial facts. */
  for(i=0; flist != NULL; flist = flist->next) {
    v = insert_token_list(fact_table[0],flist->item);
    v->rand1 = random();
    set_uid(v,i++);
  }
  /* make the graph */
  for(time=0; time < maxtime; ++time) { 
    /* for auto case, see if can stop */
    if (autostop && can_stop(time)) {
      printf("Goals first reachable in %d steps.\n",time);
      break;
    }
    if (autostop && same_as_prev_flag) break; /* Will never reach goals */
    create_graph_layer(olist);   /* CREATE LAYER OF GRAPH */
  }

  printf("%d nodes created.\n", num_created);
  if (can_stop(time)) return time;
  else return -1;
}

edgelist_t insert_edge_at_end(edgelist_t e, vertex_t v, incl_list with);

/*****copy op_table[time-1] to op_table[time] and fact_table[time] to 
  fact_table[time+1]. (not exactly copies of course since need to point to
  objects at subsequent time step.)   This is done in the case that 
  fact_table[time] was EXACTLY like fact_table[time-1], meaning that there
  were both the same number of ops and the same number of mutex's.

  Of course, rands are different.

  Also, the ordering of the exclusive lists gets reversed, but this shouldn't
  affect anything.
  *****/
void make_copy(int time)
{
  vertex_t u,v,w;
  edgelist_t e;

  /* first do the ops and connect to their preconditions */
  get_next(op_table[time-1],0);
  while((v = get_next(op_table[time-1],1)) != NULL) {
    w = insert_into_table(op_table[time],v->name);
    w->prev_time = v;
    v->next_time = w;
    w->uid_mask = v->uid_mask;
    w->uid = v->uid;
    w->uid_block = v->uid_block;
    w->is_noop = v->is_noop;
    w->inclusions=v->inclusions;

    /* in-edges of op */
    for(e = v->in_edges; e; e = e->next) {
      u = e->endpt->next_time;  /* the fact for OUR in-edge */
      w->in_edges = insert_edge_at_end(w->in_edges, u,e->incl);
      u->out_edges = insert_edge_at_end(u->out_edges, w,e->incl);
      /*the e->excl and e->incl should both be NULL at this time because
	only edges from an operator to a fact should have exclusions and
	inclusions.*/
    }
  }

  /* now do facts and connect them up.  Keep order the same */
  get_next(fact_table[time],0);
  while((v = get_next(fact_table[time],1)) != NULL) {
    w = insert_into_table(fact_table[time+1],v->name);
    w->prev_time = v;
    v->next_time = w;
    w->rand1 = random();
    w->uid_mask = v->uid_mask;
    w->uid_block = v->uid_block;
    w->uid = v->uid;

    /* in-edges */
    for(e = v->in_edges; e; e = e->next) {
      u = e->endpt->next_time;  /* the op for OUR in-edge */
      w->in_edges = insert_edge_at_end(w->in_edges, u,e->incl);
      u->out_edges = insert_edge_at_end(u->out_edges, w,e->incl);
    }
  }
 
  /* now do del_edges, exclusives (don't really need del_list) */
  get_next(fact_table[time+1],0);
  while((v = get_next(fact_table[time+1],1)) != NULL) {
    for(e = v->prev_time->exclusive; e; e = e->next) {
      v->exclusive = insert_edge(v->exclusive,e->endpt->next_time, e->incl);
      /*e->excl and e->incl should both be NULL*/
    }
    for(e = v->prev_time->del_edges; e; e = e->next) {
      v->del_edges = insert_edge(v->del_edges,e->endpt->next_time,e->incl);
    }
  }
  get_next(op_table[time],0);
  while((v = get_next(op_table[time],1)) != NULL) {
    for(e = v->prev_time->exclusive; e; e = e->next) {
      v->exclusive = insert_edge(v->exclusive,e->endpt->next_time,e->incl);
      /*e->excl and e->incl should both be NULL*/
    }
    for(e = v->prev_time->del_edges; e; e = e->next) {
      v->del_edges = insert_edge(v->del_edges,e->endpt->next_time,e->incl);
      /*e->excl and e->incl should both be NULL*/
    }
  }
}


/* for auto case.  See if can stop expanding graph.  Can stop if (A)
 * all goals are reachable, and (B) they're not mutex of each other.
 */
int can_stop(int time)
{
  static int i,j,flag = 0;
  fact_list temp;
  char str[100];
  static vertex_t *v;   /* doing it this way since MAXGOALS not a constant */
  int num=0;
  if (flag == 0) { /* set up v */
    v = (vertex_t *) malloc(MAXGOALS*sizeof(vertex_t));
    flag = 1;
  }

  for(temp = the_goals; temp; temp = temp->next) {
    instantiate_into_string(temp->item, NULL, str,1);
    if ((v[num++] = lookup_from_table(fact_table[time],str)) == NULL) 
      return 0;
  }
  /* reached all goals, but check to make sure none are exclusive. */
  /* only doing exclusive testing if do_remove > 2 */
  if (do_remove > 2) {
  for(i=0; i < num; ++i)
    for(j=i+1; j < num; ++j)
      if (are_mutex(v[i],v[j])) {
	fprintf(stderr,"Goals reachable at %d steps but mutually exclusive.\n",
	       time);
	return 0;
      }
  }
  return 1;
}


/***********LOAD IN OPERATOR AND FACT FILES*****************************/
/*******fn prototypes needed for load_ops********/
op_list load_ops_recursive(FILE *fp);
void set_insts(op_ptr op);
/************************************************/


/* reads in operators into a big list and returns it. A hash mark "#"
   means old-style.  That means that preconditions are assumed to be
   deleted unless they are in the add-effects.  A precondition
   that wasn't deleted was called a "catalyst" in the old version.

   Not allowing this format any more.
*/
op_list load_ops(FILE *fp)
{
  int c;
  /* start with # if old style */
  if ((c = getc(fp)) == '#') do_error("no longer allowing old style format");
  ungetc(c, fp);
  return load_ops_recursive(fp);
}



op_list load_ops_recursive(FILE *fp)
{
  op_list op; char str[100];
  int result;
  /* first read up to left paren */
  do {
    result = read_item(fp,junk);
  } while ((result != LEFT_PAREN) && (result != EOF));
  if (result == EOF) return NULL;

  read_item(fp,junk); /* this should be OPR */

  if (read_item(fp,str) != TOKEN) do_error("error reading operator name");
  printf("%s\n",str);
  op = (op_list) malloc(sizeof(op_s));
  op->name = (char *) calloc(strlen(str) + 1, sizeof(char));
  strcpy(op->name, str);

  /* read in parameters */
  if (read_item(fp,junk) != LEFT_PAREN)
    do_error("expecting left paren before parameters");
  read_item(fp,junk);  /* PARAMS */
  load_fact_list(fp, &(op->params));

  /* read in preconditions. */
  if (read_item(fp,junk) != LEFT_PAREN)
    do_error("expecting left paren before preconds");
  read_item(fp,junk);  /* PRECOND */
  load_fact_list(fp, &(op->preconds));

  /* read in effects */
  if (read_item(fp,junk) != LEFT_PAREN)
    do_error("expecting left paren before effects");
  read_item(fp,junk);  /* EFFECT */
  op->effects = load_effect_list(fp);

  /* AB: getting rid of outer layer of parens... */
  /* read_item(fp,junk);  the final right parenthesis */

  /* set instantiation list */
  set_insts(op);
  op->next = load_ops_recursive(fp);
  return op;
}

int really_is_var(char *str) 
{ 
  return (str[strlen(str)-1] == '>');
}

/****have instantiation list associated to op.  Set all the var-parts.*****/
/** Changing this to allow the parameters to have some variables mentioned
 ** more than once.  Just makes a list of all of the different ones.
 ** This goes in reverse order. (Gets re-reversed when op-string is created)
 **/
void set_insts(op_ptr op)
{
  param_list pptr;
  token_list tptr;
  instantiation_list iptr;
  op->insts = NULL;
  for(pptr = op->params; pptr != NULL; pptr = pptr->next) {
    for(tptr = pptr->item; tptr; tptr = tptr->next) {
      if (!is_var(tptr->item)) continue;
      if (!really_is_var(tptr->item)) {
	sprintf(junk,"Badly-formed op: %s",op->name);
	do_error(junk);
      }
      /* it's a variable.  Check to make sure it's a new one */
      for(iptr = op->insts; iptr; iptr = iptr->next) {
	if (strcmp(iptr->var_part, tptr->item) == SAME) break;
      }
      if (iptr != NULL) continue;  /* did break above: not new */

      op->insts = insert_inst(tptr->item, NULL, op->insts);
    }
  }
}

token_list load_tokens(FILE *fp);

fact_list make_fact_list(token_list tlist, fact_list ptr)
{
  fact_list fptr = (fact_list) malloc(sizeof(fact_list_elt));
  fptr->item=tlist;
  fptr->next=ptr;
  return fptr;
}

/* returns number of facts loaded */
int load_fact_list(FILE *fp, fact_list *fptr)
{
  token_list tlist;
  /* if not left paren, then we're done. */
  if (read_item(fp, junk) != LEFT_PAREN) {
    *fptr = NULL;
    return 0;
  }
  if ((tlist = load_tokens(fp)) == NULL) do_error("bad input file");
  *fptr = make_fact_list(tlist,NULL);
  return 1 + load_fact_list(fp, &( (*fptr)->next ));
}

token_list token_list_constructor(char temp_token[MAX_TOKEN_LENGTH]);

effect_fact_list load_effect_fact_list(FILE *fp)
{
  effect_fact_list ret;
  char buffer[MAX_TOKEN_LENGTH];
  if (read_item(fp,buffer)==RIGHT_PAREN)
    return NULL;
  ret = (effect_fact_list) malloc(sizeof(effect_fact_list_elt));
  if(read_item(fp,buffer)!=TOKEN){/*this is an implicit add*/
    ret->action=add;
    push_back(buffer);
  }
  else
    if (strcmp(buffer,"del")==0)
      ret->action= del;
    else 
      ret->action=add;
  load_fact_list(fp,&(ret->facts));
  ret->next=load_effect_fact_list(fp);
  return ret;
}


/* special for loading in types. 
   Reads up to and including next left paren.  Also, sets up
   types_table and sets up the_probs */
fact_list load_types(FILE *fp)
{
  char temp_token[100];
  double prob;
  fact_list f;
  probdef_list p;

  while(read_item(fp, junk) != LEFT_PAREN); /* get left paren */
  read_item(fp, temp_token); /* first in list: see if it is "preconds" */
  if (strcmp(temp_token, PRECOND) == SAME) return NULL; /* at end */

  /* if temp_token is a real number, then view as a probability definition */
  if (sscanf(temp_token, "%lf", &prob) == 1) {
    if (prob < 0.0 || prob > 1.0) do_error("illegal probability");
    p = (probdef_list) malloc(sizeof(probdef_list_elt));
    p->prob = prob;
    instantiate_into_string(load_tokens(fp), NULL, p->str, 1);/* load p->str */
    p->next = the_probs;
    the_probs = p;
    return load_types(fp);
  }
  
  f = (fact_list) malloc(sizeof(fact_list_elt));
  f->item = (token_list) malloc(sizeof(token_list_elt));
  f->item->item = strdup(temp_token);   /* first token */
  f->item->next = load_tokens(fp);      /* remaining tokens */
  insert_token_list(types_table, f->item);
  f->next = load_types(fp);
  return f;
}

token_list token_list_constructor(char temp_token[MAX_TOKEN_LENGTH])
{
  token_list ret=(token_list) malloc(sizeof(token_list_elt));
  ret->item = (char *) calloc(1 + strlen(temp_token),sizeof(char));
  strcpy(ret->item, temp_token);
  ret->next=NULL;
  return ret;
}

/* if next word is a right paren, returns NULL. Otherwise, read in tokens up
   to right parenthesis and return the list of tokens.  */
token_list load_tokens(FILE *fp)
{
  char temp_token[MAX_TOKEN_LENGTH];
  int result;
  token_list_elt *current;
  result = read_item(fp, temp_token);
  if (result == RIGHT_PAREN) return NULL;
  current = token_list_constructor(temp_token);
  current->next = load_tokens(fp);
  return current;
}


effect_list load_effect_list(FILE *fp)
{
  char temp_prob[MAX_TOKEN_LENGTH];
  effect_list ret;
  int prob_result;

  if (read_item(fp, junk) != LEFT_PAREN) return NULL; /* done */

  ret=(effect_list) calloc(1, sizeof(effect_list_elt));
  prob_result = read_item(fp, temp_prob);
  if (prob_result == PROB) {             /* read in a probability */
    ret->prob=atof(temp_prob);
    printf("read in probability of %.3f\n", ret->prob);
  } else if (prob_result == LEFT_PAREN) {/* reading a define'd probability */
    printf("read in a defined probability\n");
    ret->prob = -1.0; /* for safety */
    ret->defined_prob = load_tokens(fp);
  } else do_error("unknown format of effect list");

  ret->effects = load_effect_fact_list(fp);
  ret->next=load_effect_list(fp);
  return ret;
}

/*************************END OF STUFF FOR LOADING IN OPS,FACTS**********/
/************************************************************************/



/********* ROUTINES FOR TAKING THE OPS AND A LIST OF FACTS AND ***********
 *********     INSTANTIATING TO CREATE NODES IN THE GRAPH      ***********/

/* These routines create nodes in the graph by instantiating operators  */
/* This part is kindof messy, but conceptually it's not bad            */

/* see if match different var names to same constant */
int illegal_match(instantiation_list insts)
{
  instantiation_list i,j;
  for(i = insts; i; i = i->next)
    for(j = i->next; j; j = j->next)
      if (strcmp(i->var_part,j->var_part) != SAME &&
	  strcmp(i->const_part,j->const_part) == SAME)
	return 1;
  return 0;
}

void insert_node(token_list tlist,instantiation_list insts, int time, vertex_t 
		 op_vert, incl_list with)
{
  char str[100];
  vertex_t fact_vert;
  instantiate_into_string(tlist, insts, str,1);
  fact_vert = lookup_from_table(fact_table[time+1], str);
  if (fact_vert == NULL)                     /* wasn't there */
    fact_vert = insert_into_table(fact_table[time+1],str);
  op_vert->out_edges = insert_edge(op_vert->out_edges, fact_vert,with);
  fact_vert->in_edges = insert_edge(fact_vert->in_edges, op_vert,with);
}

void put_in_del_list(token_list tlist, op_ptr op,  vertex_t op_vert, incl_list with)
{
  delete_list temp;
  char str[100];
  instantiate_into_string(tlist, op->insts, str,1);
  temp = (delete_list) malloc(sizeof(delete_list_elt));
  temp->item = (char *) calloc(strlen(str) + 1, sizeof(char));
  strcpy(temp->item, str);
  temp->with=with;
  temp->next = op_vert->del_list;
  op_vert->del_list = temp;
}

incl_list add_incl(incl_list list,double prob)
{
  incl_list new_incl=(incl_list)malloc(sizeof(incl_list_ele));
  new_incl->prob=prob;
  new_incl->next=list;
  return new_incl;
}

/****************here's the important one for making the graph*************/
/* this takes in an operator and an instantiation list, and a time.
   Inserts the operators and new facts and connects them appropriately.

   Inserts op into op_table[time]. attaches edges to fact_table[i] and
   fact_table[i+1].

   If op has effects with "define'd probabilities", need to deal with that too.
 */
void make_graph_piece(op_ptr op, int time)
{
  vertex_t op_vert, fact_vert, fv2;
  effect_list elist; 
  precond_list plist, p2;
  double test, prob;
  effect_fact_list eflist;
  fact_list flist;
  probdef_list pdl;
  char str[100], str2[100];

  /* get op name */
  make_op_string(op, str);
  /* NEW: need to make sure that vars of different names match to different
     constants.  Otherwise can get into trouble. */
  if (illegal_match(op->insts)) {
    if (DEBUG_FLAG > 2) printf("discarding %s.\n",str);
    return;
  }

  /* first, insert the operator and get a pointer to it */
  op_vert = insert_into_table(op_table[time], str);

  
  /* if op can be avoided then return now */
  for(plist = op->preconds; plist; plist = plist->next) {
    instantiate_into_string(plist->item, op->insts, str,1);
    fact_vert = lookup_from_table(fact_table[time], str);
    for(p2 = plist->next; p2; p2 = p2->next) {
      instantiate_into_string(p2->item, op->insts, str2,1);
      fv2 = lookup_from_table(fact_table[time], str2);
      if (fact_vert == NULL || fv2 == NULL) {      /* wasn't there */
	do_error("didn't find precondition. Shouldn't happen");
      }
      if (are_mutex(fact_vert, fv2)) { /* DONT NEED TO PUT OP IN */
	if (DEBUG_FLAG) printf("Avoiding %s, time %d\n",op_vert->name, time);
	return;
      }
    }
  }

  /* set up the connections to the preconditions */
  for(plist = op->preconds; plist; plist = plist->next) {
    instantiate_into_string(plist->item, op->insts, str,1);
    fact_vert = lookup_from_table(fact_table[time], str);
    op_vert->in_edges = insert_edge(op_vert->in_edges, fact_vert,NULL);
    fact_vert->out_edges = insert_edge(fact_vert->out_edges, op_vert,NULL);
  }

  /* set up the connections to effects. Now allowing deletes */
  for(elist = op->effects, test=0.0; elist; elist = elist->next) {
    /* find the probability for this list of effects */
    if (elist->defined_prob == NULL) { /* easy case */
      prob = elist->prob;
    } else {                           /* need to look it up */
      instantiate_into_string(elist->defined_prob, op->insts, str, 1);
      for(pdl = the_probs; pdl; pdl = pdl->next)
	if (strcmp(str, pdl->str) == SAME) break;
      if (!pdl) do_error("couldn't find the defined probability for this op");
      prob = pdl->prob;
    }
    test += prob;  /* check that things sum up to 1 */
    op_vert->inclusions = add_incl(op_vert->inclusions, prob);
    for (eflist=elist->effects; eflist; eflist=eflist->next)
      for (flist=eflist->facts;flist;flist=flist->next)
	if (eflist->action!=del)  /* it's an add */
	  insert_node(flist->item,op->insts,time,op_vert,op_vert->inclusions);
	else  /* just put into del list.  Don't try creating new node */
	  put_in_del_list(flist->item, op, op_vert,op_vert->inclusions);
  }
  if (test<1-epsilon || test>1+epsilon) {
    printf("-> For %s, your probabilities don't sum to 1.\n",op_vert->name);
    do_error("Exiting");
  }
}

/*** do one of the operators ***/
/* The do_operator_rec routine can be used to do forwards or backwards, 
   but is written using variable names as if going in forwards direction.

   This routine takes the list of facts true at current time, a ptr to an
   operator, a list of preconditions to go, and some instantiations.
   It calls make_graph_piece for each new node that needs to be created.

   --> Also takes in hash table.  For speedup...

   When d_o_rec matches, it calls itself recursively with
   flag=1 and replacing current facts by the types list, to make sure that
   those get matched.  Should now handle correctly the case where there
   is a parameter that is not one of the preconditions.
*/
void do_operator_rec(hashtable_t, fact_list, op_ptr, precond_list, int, int);

void do_operator(hashtable_t htable, fact_list current_facts, op_ptr op, 
		 precond_list p, int time)
{
  do_operator_rec(htable, current_facts,op,p,time,0);
}

void do_operator_rec(hashtable_t htable, fact_list current_facts, op_ptr op, 
                     precond_list precs_to_go, int time, int flag)
{
  fact_list factptr;
  token_list prec;
  int result;
  int i, old_matched[MAX_TOKENS]; /* 0 if const_part is NULL. Else 1 */
  instantiation_list iptr;
  char str[100];

  if (precs_to_go == NULL) { 
    /* if flag is 1, that means we're done. Otherwise, call recursively 
        * using the_types. */
    if (flag == 1) make_graph_piece(op,time);
    else do_operator_rec(types_table, the_types, op, op->params, time, 1);
    return;
  }
  for(i=0, iptr = op->insts; iptr!= NULL; iptr = iptr->next, i++) {
    if (iptr->const_part == NULL) old_matched[i]=0;
    else old_matched[i] = 1;
  }
  prec =  precs_to_go->item;

  /* first see if it's fully instantiated.  If so, it's lots faster */
  if (instantiate_into_string(prec, op->insts, str,0)) { /* YAY! */
    if (lookup_from_table(htable, str))           /* found it */
      do_operator_rec(htable, current_facts, op, precs_to_go->next, time,flag);
    return;
  }
  /* now we know that it is NOT fully instantiated */

  for(factptr = current_facts; factptr != NULL; factptr = factptr->next) {
    result = compare_and_instantiate(prec, factptr->item, op->insts);
    if (result == NO) continue;  /* No match.  Most common */
    if (result == YES) do_error("bug in do_operator_rec");
    do_operator_rec(htable, current_facts, op,  precs_to_go->next, time, flag);
    /* now, un-instantiate the new ones */
    for(i=0,iptr=op->insts; iptr!=NULL; iptr = iptr->next, i++)
      if (old_matched[i] == 0) iptr->const_part = NULL;
  }
}

/* this routine takes an uninstantiated pattern, a fact, and a list of
   partially made instantiations.
   Sees if the precondition matches the fact given the
   instantiations so far.  Returns YES if exact match NO if no exact match
   and NEW_INSTS if new instantiations were needed.
 */
int compare_and_instantiate(token_list patt, token_list fact,
                            instantiation_list insts)
{
  token_list p,f;          /* p,f,iptr are pointers to go down the lists */
  instantiation_list iptr;
  int temp_arr[MAX_TOKENS]; /* temp_arr[i] = NO or NEW_INSTS */
  int i=0,result = YES;  /* change result to NEW_INSTS when add instantiatons*/

  /* Check the constant parts.  If any fail to match,  we can return.  */
  for(p = patt, f = fact; p && f; p = p->next, f = f->next)
    if (is_const(p->item) && !equal_tokens(p->item,f->item)) return NO;

  /* check they're the same length */
  if (p || f) return NO;

  /* initialize temp_arr */
  for(i=0,iptr=insts; iptr !=NULL; i++,iptr=iptr->next) temp_arr[i] = NO;

  for(p = patt, f = fact; p && f; p = p->next, f = f->next) {
    if (is_const(p->item)) continue;    /* we already know this matches */
    for(i=0,iptr = insts; iptr != NULL; i++, iptr = iptr->next)
      if (equal_tokens(p->item,iptr->var_part)) {  /* matched */
        if (iptr->const_part == NULL) {          /* need new inst */
          iptr->const_part = f->item;            /* so, do it */
          temp_arr[i] = NEW_INSTS;               /* and remember it */
          result = NEW_INSTS;                    /* and change result */
        } else if (!equal_tokens(f->item,iptr->const_part)) { /* not equal*/
          result=NO;
	}
	break;
      }
    if (iptr == NULL) {
      sprintf(junk,"Badly formed operator: '%s' not a parameter",p->item);
      do_error(junk);
    }
    if (result == NO) break;
  }

  /* if result is NO, then reset insts */
  if (result == NO)
    for(i=0,iptr=insts; iptr !=NULL; i++,iptr=iptr->next) {
      if (temp_arr[i] == NEW_INSTS) iptr->const_part = NULL;
    }
  return result;
}

/*************************END OF OP->PART_OF_GRAPH section***************/