
/*********************************************************************
 * (C) Copyright 2001 Albert Ludwigs University Freiburg
 *     Institute of Computer Science
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 * 
 *********************************************************************/




/*
 * THIS SOURCE CODE IS SUPPLIED  ``AS IS'' WITHOUT WARRANTY OF ANY KIND, 
 * AND ITS AUTHOR AND THE JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH 
 * (JAIR) AND JAIR'S PUBLISHERS AND DISTRIBUTORS, DISCLAIM ANY AND ALL 
 * WARRANTIES, INCLUDING BUT NOT LIMITED TO ANY IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, AND
 * ANY WARRANTIES OR NON INFRINGEMENT.  THE USER ASSUMES ALL LIABILITY AND
 * RESPONSIBILITY FOR USE OF THIS SOURCE CODE, AND NEITHER THE AUTHOR NOR
 * JAIR, NOR JAIR'S PUBLISHERS AND DISTRIBUTORS, WILL BE LIABLE FOR 
 * DAMAGES OF ANY KIND RESULTING FROM ITS USE.  Without limiting the 
 * generality of the foregoing, neither the author, nor JAIR, nor JAIR's
 * publishers and distributors, warrant that the Source Code will be 
 * error-free, will operate without interruption, or will meet the needs 
 * of the user.
 */











/*********************************************************************
 *
 * File: search.c
 *
 * Description: implementation of routines that search the state space
 *
 *              ADL version, Goal Agenda driven
 *                           Enforced Hill-climbing enhanced with
 *                           informed Goal Added Deletion Heuristic,
 *
 *                           and, alternatively, standard Best First Search
 *
 *
 * Author: Joerg Hoffmann 2000
 *
 *********************************************************************/ 









#include "ff.h"

#include "output.h"
#include "memory.h"

#include "relax.h"
#include "search.h"
#include <string.h>













/*****************
 * LOCAL GLOBALS *
 *****************/









/* in agenda driven algorithm, the current set of goals is this
 */
State lcurrent_goals;


/* search space for EHC
 */
EhcNode *lehc_space_head, *lehc_space_end, *lehc_current_start, *lehc_current_end;



/* memory (hash table) for states that are already members
 * of the breadth - first search space in EHC
 */
EhcHashEntry_pointer lehc_hash_entry[EHC_HASH_SIZE];
int lnum_ehc_hash_entry[EHC_HASH_SIZE];
int lchanged_ehc_entrys[EHC_HASH_SIZE];
int lnum_changed_ehc_entrys;
Bool lchanged_ehc_entry[EHC_HASH_SIZE];



/* memory (hash table) for states that are already 
 * encountered by current serial plan
 */
PlanHashEntry_pointer lplan_hash_entry[PLAN_HASH_SIZE];



/* search space
 */
BfsNode *lbfs_space_head, *lbfs_space_had;



/* memory (hash table) for states that are already members
 * of the best first search space
 */
BfsHashEntry_pointer lbfs_hash_entry[BFS_HASH_SIZE];












/********************************
 * EHC FUNCTION, CALLED BY MAIN *
 ********************************/











Bool do_enforced_hill_climbing( State *start, State *end )

{

  static Bool first_call = TRUE;
  static State S, S_;
  int i, h, h_;

  if ( first_call ) {
    /* on first call, initialize plan hash table, search space, search hash table
     */
    for ( i = 0; i < PLAN_HASH_SIZE; i++ ) {
      lplan_hash_entry[i] = NULL;
    }
    /* on subsequent calls, the start is already hashed, as it's the end
     * of the previous calls
     */
    hash_plan_state( start, 0 );
    
    lehc_space_head = new_EhcNode();
    lehc_space_end = lehc_space_head;
    
    for ( i = 0; i < EHC_HASH_SIZE; i++ ) {
      lehc_hash_entry[i] = NULL;
      lnum_ehc_hash_entry[i] = 0;
      lchanged_ehc_entry[i] = FALSE;
    }
    lnum_changed_ehc_entrys = 0;

    make_state( &S, gnum_ft_conn ); 
    S.max_F = gnum_ft_conn;
    make_state( &S_, gnum_ft_conn );
    S_.max_F = gnum_ft_conn;

    make_state( &lcurrent_goals, gnum_ft_conn );
    lcurrent_goals.max_F = gnum_ft_conn;

    first_call = FALSE;
  }
  
  /* start enforced Hill-climbing
   */

  source_to_dest( &lcurrent_goals, end );  

  source_to_dest( &S, start );
  gexpanded_states++;
  h = get_1P_and_H( &S, &lcurrent_goals );

  if ( h == INFINITY ) {
    return FALSE;
  }
  if ( h == 0 ) {
    return TRUE;
  }  
  printf("\n\nCueing down from goal distance: %4d into depth ", h);

  while ( h != 0 ) {
    if ( !search_for_better_state( &S, h, &S_, &h_ ) ) {
      return FALSE;
    }
    source_to_dest( &S, &S_ );
    h = h_;
    if(h == 3)
	    printf("aho %d \n", gexpanded_states);
    printf("\n                                %4d            ", h);
  }

  return TRUE;

}











/*************************************************
 * FUNCTIONS FOR BREADTH FIRST SEARCH IN H SPACE *
 *************************************************/













Bool search_for_better_state( State *S, int h, State *S_, int *h_ )

{

  static Bool first_call = TRUE;
  static State S__;

  int i, h__, depth = 0, g;
  EhcNode *tmp;

  if ( first_call ) {
    make_state( &S__, gnum_ft_conn );
    S__.max_F = gnum_ft_conn;
    first_call = FALSE;
  }

  /* don't hash states, but search nodes.
   * this way, don't need to keep states twice in memory
   */
  tmp = new_EhcNode();
  copy_source_to_dest( &(tmp->S), S);
  hash_ehc_node( tmp );

  /*  printf("\nHelpful: ");*/
  lehc_current_end = lehc_space_head->next;
  for ( i = 0; i < gnum_H; i++ ) {
	  /*	  print_op_name(gH[i]);*/
	  g = result_to_dest( &S__, S, gH[i] );
	  add_to_ehc_space( &S__, gH[i], NULL, g );
  }
  lehc_current_start = lehc_space_head->next;

  while ( TRUE ) {  
	  if ( lehc_current_start == lehc_current_end ) {
      reset_ehc_hash_entrys();
      free( tmp );
      return FALSE;
      }
    if ( lehc_current_start->depth > depth ) {
      depth = lehc_current_start->depth;
      if ( depth > gmax_search_depth ) {
	gmax_search_depth = depth;
      }
      printf("[%d]", depth);
      fflush( stdout );
    }
  gexpanded_states++;
    h__ = expand_first_node( h );
    if ( LESS( h__, h ) ) {
      break;
    }
  }

  reset_ehc_hash_entrys();
  free( tmp );

  extract_plan_fragment( S );

  source_to_dest( S_, &(lehc_current_start->S) );
  *h_ = h__;

  return TRUE;

}



void add_to_ehc_space( State *S, int op, EhcNode *father, int new_goal )

{

  /* see if state is already a part of this search space
   */
  if ( ehc_state_hashed( S ) ) {
    return;
  }

  if ( !lehc_current_end ) {
    lehc_current_end = new_EhcNode();
    lehc_space_end->next = lehc_current_end;
    lehc_space_end = lehc_current_end;
  }

  copy_source_to_dest( &(lehc_current_end->S), S );
  lehc_current_end->op = op;
  lehc_current_end->father = father;
  if ( !father ) {
    lehc_current_end->depth = 1;
  } else {
    lehc_current_end->depth = father->depth + 1;
  }
  lehc_current_end->new_goal = new_goal;

  hash_ehc_node( lehc_current_end );

  lehc_current_end = lehc_current_end->next;

}

EhcNode* add_to_ehc_spaceB( State *S, int op, EhcNode *father, int new_goal )

{

  /* see if state is already a part of this search space
   */
  if ( ehc_state_hashed( S ) ) {
    return NULL;
  }

  if ( !lehc_current_end ) {
    lehc_current_end = new_EhcNode();
    lehc_space_end->next = lehc_current_end;
    lehc_space_end = lehc_current_end;
  }

  copy_source_to_dest( &(lehc_current_end->S), S );
  lehc_current_end->op = op;
  lehc_current_end->father = father;
  if ( !father ) {
    lehc_current_end->depth = 1;
  } else {
    lehc_current_end->depth = father->depth + 1;
  }
  lehc_current_end->new_goal = new_goal;

  EhcNode* node = lehc_current_end;

  hash_ehc_node( lehc_current_end );

  lehc_current_end = lehc_current_end->next;

  return node;
}

int get_Moves(State* s)
{
	int i, j;

	Action *a;
	for(i = 0; i < gnum_ft_conn; i++)
		in_s[i] = FALSE;

	for ( i = 0; i < s->num_F; i++ )
		in_s[s->F[i]] = TRUE; 

	for(i = 0; i < gnum_op_moves; i++)
		{				       
			a = gop_conn[ gop_moves[i] ].action;
			for(j = 0; j < a->num_preconds; j++)
				if(in_s[ a->preconds[j] ] == FALSE)
					break;

			if(j == a->num_preconds)
				return gop_moves[i];
		}

	return -1;
	
}

int expand_first_node( int h )

{

  static Bool fc = TRUE;
  static State S_;

  int h_, i, g;

  if ( fc ) {
    make_state( &S_, gnum_ft_conn );
    S_.max_F = gnum_ft_conn;
    fc = FALSE;
  }
  
  
  {
	  static State tmpS_;
	  /*	  copy_source_to_dest(&tmpS_, &lehc_current_start->S);*/

	  tmpS_ = lehc_current_start->S;
	  EhcNode* node = lehc_current_start;
	       				
	  /*	  get_A( &tmpS_ );*/
	  
	  int move_op=-1;
	  
	  int moves_op = get_Moves( &tmpS_ );
	  
	  while( moves_op != -1 )	 
		  {			
			  g = result_to_dest( &S_, &tmpS_, moves_op );   
			  move_op = moves_op;		
			  
			  copy_source_to_dest(&tmpS_, &S_);
				  /*tmpS_ = S_;*/
			  moves_op = get_Moves( &S_ );
			  /*			  get_A( &S_ );*/
			  /*  moves = TRUE;*/
		  }

	  /*	  if(move_op != -1)
		  {
			  add_to_ehc_space( &S_, move_op, lehc_current_start, g );
			  lehc_current_start = lehc_current_start->next;
			  return h;
		  }
	  */
	  if(move_op != -1)
		  {
			  copy_source_to_dest( &lehc_current_start->S, &S_);
		  }
			      /*	  Smove_ = S_;*/
	  

    }

  /*  
  get_A( &(lehc_current_start->S) ); 
  if( gop_conn[gA[0]].is_moveBA == TRUE)  {	  
	  for ( i = 0; i < gnum_A; i++ ) {
		  g = result_to_dest( &S_, &(lehc_current_start->S), gA[i] );
		  add_to_ehc_space( &S_, gA[i], lehc_current_start, g );

		  if(nir < gnum_A)
			  nir=gnum_A;
	  }
	  
	  lehc_current_start = lehc_current_start->next;
	  return h;
  }
  */	

  
  h_ = get_1P_and_H( &(lehc_current_start->S), &lcurrent_goals );
  	  
  if ( h_ == INFINITY ) {
    lehc_current_start = lehc_current_start->next;
    return h_;
  }
  /*NIR*/
  /*if ( lehc_current_start->new_goal != -1 &&
       new_goal_gets_deleted( lehc_current_start ) ) {
    lehc_current_start = lehc_current_start->next;
    return INFINITY;
  }
  */
  if ( h_ < h ) {
    return h_;
  }

  
  /*  printf("\nHelpful: ");*/
  for ( i = 0; i < gnum_H; i++ ) {
	  /*	      print_op_name(gH[i]);*/

	  g = result_to_dest( &S_, &(lehc_current_start->S), gH[i] );

	  /*
	      {
		    static State tmpS_;
		    source_to_dest(&tmpS_, &S_);		   
	       				
		  get_A( &tmpS_ );
					
		  while( gop_conn[gA[0]].is_moveBA == TRUE )	  
			{			
				g = result_to_dest( &S_, &tmpS_, gA[0] );									

				source_to_dest(&tmpS_, &S_);
				get_A( &S_ );
			}
	  
			}
	  */
    add_to_ehc_space( &S_, gH[i], lehc_current_start, g );
  }
    
  lehc_current_start = lehc_current_start->next;

  return h_;

}











/********************************************************
 * HASHING ALGORITHM FOR RECOGNIZING REPEATED STATES IN *
 * EHC BREADTH FIRST SEARCH                             *
 ********************************************************/












void hash_ehc_node( EhcNode *n )

{

  int i, sum, index;
  EhcHashEntry *h, *prev = NULL;

  sum = state_sum( &(n->S) );
  index = sum & EHC_HASH_BITS;

  h = lehc_hash_entry[index];
  if ( !h ) {
    h = new_EhcHashEntry();
    h->sum = sum;
    h->ehc_node = n;
    lehc_hash_entry[index] = h;
    lnum_ehc_hash_entry[index]++;
    if ( !lchanged_ehc_entry[index] ) {
      lchanged_ehc_entrys[lnum_changed_ehc_entrys++] = index;
      lchanged_ehc_entry[index] = TRUE;
    }
    return;
  }
  i = 0;
  while ( h ) {
    if ( i == lnum_ehc_hash_entry[index] ) {
      break;
    }
    i++;
    prev = h;
    h = h->next;
  }

  if ( h ) {
    /* current list end is still in allocated list of hash entrys
     */
    h->sum = sum;
    h->ehc_node = n;
    lnum_ehc_hash_entry[index]++;
    if ( !lchanged_ehc_entry[index] ) {
      lchanged_ehc_entrys[lnum_changed_ehc_entrys++] = index;
      lchanged_ehc_entry[index] = TRUE;
    }
    return;
  }
  /* allocated list ended; connect a new hash entry to it.
   */
  h = new_EhcHashEntry();
  h->sum = sum;
  h->ehc_node = n;
  prev->next = h;
  lnum_ehc_hash_entry[index]++;
  if ( !lchanged_ehc_entry[index] ) {
    lchanged_ehc_entrys[lnum_changed_ehc_entrys++] = index;
    lchanged_ehc_entry[index] = TRUE;
  }
  return;
      
}



Bool ehc_state_hashed( State *S )

{

  int i, sum, index;
  EhcHashEntry *h;

  sum = state_sum( S );
  index = sum & EHC_HASH_BITS;

  h = lehc_hash_entry[index];
  for ( i = 0; i < lnum_ehc_hash_entry[index]; i++ ) {
    if ( h->sum != sum ) {
      h = h->next;
      continue;
    }
    if ( same_state( &(h->ehc_node->S), S ) ) {
      return TRUE;
    }
    h = h->next;
  }

  return FALSE;

}



Bool same_state( State *S1, State *S2 ) 

{

  int i, j;

  if ( S2->num_F != S1->num_F ) {
    return FALSE;
  }

  for ( i = 0; i < S2->num_F; i++ ) {
    for ( j = 0; j < S1->num_F; j++ ) {
      if ( S1->F[j] == S2->F[i] ) {
	break;
      }
    }
    if ( j == S1->num_F ) {
      return FALSE;
    }
  }

  return TRUE;

}



int state_sum( State *S )

{

  int i, sum = 0;

  for ( i = 0; i < S->num_F; i++ ) {
    sum += gft_conn[S->F[i]].rand;
  }

  return sum;

}



void reset_ehc_hash_entrys( void )

{

  int i;

  for ( i = 0; i < lnum_changed_ehc_entrys; i++ ) {
    lnum_ehc_hash_entry[lchanged_ehc_entrys[i]] = 0;
    lchanged_ehc_entry[lchanged_ehc_entrys[i]] = FALSE;
  }
  lnum_changed_ehc_entrys = 0;

}











/***************************************************
 * FUNCTIONS FOR UPDATING THE CURRENT SERIAL PLAN, *
 * BASED ON SEARCH SPACE INFORMATION .             *
 *                                                 *
 * EMPLOY SOMEWHAT TEDIOUS HASHING PROCEDURE TO    *
 * AVOID REPEATED STATES IN THE PLAN               *
 ***************************************************/












void extract_plan_fragment( State *S )

{

  EhcNode *i;
  int ops[MAX_PLAN_LENGTH], num_ops;
  State_pointer states[MAX_PLAN_LENGTH];
  int j;
  PlanHashEntry *start = NULL, *i_ph;

  num_ops = 0;
  for ( i = lehc_current_start; i; i = i->father ) {
    if ( (start = plan_state_hashed( &(i->S) )) != NULL ) {
      for ( i_ph = start->next_step; i_ph; i_ph = i_ph->next_step ) {
	i_ph->step = -1;
      }
      gnum_plan_ops = start->step;
      break;
    }
    if ( num_ops == MAX_PLAN_LENGTH ) {
      printf("\nincrease MAX_PLAN_LENGTH! currently %d\n\n",
	     MAX_PLAN_LENGTH);
      exit( 1 );
    }
    states[num_ops] = &(i->S);
    ops[num_ops++] = i->op;
  }
  if ( !start ) {
    start = plan_state_hashed( S );
    if ( !start ) {
      printf("\n\ncurrent start state not hashed! debug me!\n\n");
      exit( 1 );
    }
    if ( start->step == -1 ) {
      printf("\n\ncurrent start state marked removed from plan! debug me!\n\n");
      exit( 1 );
    }
  }

  for ( j = num_ops - 1; j > -1; j-- ) {
    if ( gnum_plan_ops == MAX_PLAN_LENGTH ) {
      printf("\nincrease MAX_PLAN_LENGTH! currently %d\n\n",
	     MAX_PLAN_LENGTH);
      exit( 1 );
    }
    start->next_step = hash_plan_state( states[j], gnum_plan_ops + 1 );
    start = start->next_step;
    source_to_dest( &(gplan_states[gnum_plan_ops+1]), states[j] );
    gplan_ops[gnum_plan_ops++] = ops[j];
  }

}




PlanHashEntry *hash_plan_state( State *S, int step )

{

  int sum, index;
  PlanHashEntry *h, *tmp;

  sum = state_sum( S );
  index = sum & PLAN_HASH_BITS;

  for ( h = lplan_hash_entry[index]; h; h = h->next ) {
    if ( h->sum != sum ) continue;
    if ( same_state( S, &(h->S) ) ) break;
  }

  if ( h ) {
    if ( h->step != -1 ) {
      printf("\n\nreencountering a state that is already in plan! debug me\n\n");
      exit( 1 );
    }
    h->step = step;
    return h;
  }

  for ( h = lplan_hash_entry[index]; h && h->next; h = h->next );

  tmp = new_PlanHashEntry();
  tmp->sum = sum;
  copy_source_to_dest( &(tmp->S), S );
  tmp->step = step;

  if ( h ) {
    h->next = tmp;
  } else {
    lplan_hash_entry[index] = tmp;
  }

  return tmp;

}
  

 
PlanHashEntry *plan_state_hashed( State *S )

{

  int sum, index;
  PlanHashEntry *h;

  sum = state_sum( S );
  index = sum & PLAN_HASH_BITS;

  for ( h = lplan_hash_entry[index]; h; h = h->next ) {
    if ( h->sum != sum ) continue;
    if ( same_state( S, &(h->S) ) ) break;
  }

  if ( h && h->step != -1 ) {
    return h;
  }

  return NULL;

}














/*********************************
 * ADDED GOAL DELETION HEURISTIC *
 *********************************/













Bool new_goal_gets_deleted( EhcNode *n )

{

  int i, j, ef, new_goal = n->new_goal;

  for ( i = 0; i < gnum_in_plan_E; i++ ) {
    ef = gin_plan_E[i];
    for ( j = 0; j < gef_conn[ef].num_D; j++ ) {
      if ( gef_conn[ef].D[j] == new_goal ) {
	return TRUE;
      }
    }
  }

  return FALSE;

}















/************************************
 * BEST FIRST SEARCH IMPLEMENTATION *
 ************************************/














Bool do_best_first_search( void )

{

  static Bool fc = TRUE;
  static State S;

  BfsNode *first;
  int i, min = INFINITY;
  Bool start = TRUE;

  if ( fc ) {
    make_state( &S, gnum_ft_conn );
    S.max_F = gnum_ft_conn;
    fc = FALSE;
  }

  lbfs_space_head = new_BfsNode();
  lbfs_space_had = NULL;

  for ( i = 0; i < BFS_HASH_SIZE; i++ ) {
    lbfs_hash_entry[i] = NULL;
  }

  add_to_bfs_space( &ginitial_state, -1, NULL );

  while ( TRUE ) {
    if ( (first = lbfs_space_head->next) == NULL ) {
      printf("\n\nbest first search space empty! problem proven unsolvable.\n\n");
      return FALSE;
    }

    lbfs_space_head->next = first->next;
    if ( first->next ) {
      first->next->prev = lbfs_space_head;
    }

    if ( LESS( first->h, min ) ) {
      min = first->h;
      if ( start ) {
	printf("\nadvancing to distance : %4d", min);
	start = FALSE;
      } else {
	printf("\n                        %4d", min);
      }
    }

    if ( first->h == 0 ) {
      break;
    }
    gexpanded_states++;
    get_A( &(first->S) );
    for ( i = 0; i < gnum_A; i++ ) {
      result_to_dest( &S, &(first->S), gA[i] );
      add_to_bfs_space( &S, gA[i], first );
    }

    first->next = lbfs_space_had;
    lbfs_space_had = first;
  }

  extract_plan( first );
  return TRUE;

}



void add_to_bfs_space( State *S, int op, BfsNode *father )

{

  BfsNode *new, *i;
  int h;

  /* see if state is already a part of this search space
   */
  if ( bfs_state_hashed( S ) ) {
    return;
  }

  h = get_1P( S, &ggoal_state );

  if ( h == INFINITY ) {
    return;
  }

  for ( i = lbfs_space_head; i->next; i = i->next ) {
    if ( i->next->h > h ) break;
  }

  new = new_BfsNode();
  copy_source_to_dest( &(new->S), S );
  new->op = op;
  new->h = h;
  new->father = father;
  
  new->next = i->next;
  new->prev = i;
  i->next = new;
  if ( new->next ) {
    new->next->prev = new;
  }
  
  hash_bfs_node( new );

}



void extract_plan( BfsNode *last )

{

  BfsNode *i;
  int ops[MAX_PLAN_LENGTH], num_ops;
  int j;

  num_ops = 0;
  for ( i = last; i->op != -1; i = i->father ) {
    if ( num_ops == MAX_PLAN_LENGTH ) {
      printf("\nincrease MAX_PLAN_LENGTH! currently %d\n\n",
	     MAX_PLAN_LENGTH);
      exit( 1 );
    }
    ops[num_ops++] = i->op;
  }

  gnum_plan_ops = 0;
  for ( j = num_ops - 1; j > -1; j-- ) {
    gplan_ops[gnum_plan_ops++] = ops[j];
  }

}












/************************************************************
 * HASHING ALGORITHM FOR RECOGNIZING REPEATED STATES IN BFS *
 ************************************************************/












void hash_bfs_node( BfsNode *n )

{

  int sum, index;
  BfsHashEntry *h, *tmp;

  sum = state_sum( &(n->S) );
  index = sum & BFS_HASH_BITS;

  h = lbfs_hash_entry[index];
  if ( !h ) {
    h = new_BfsHashEntry();
    h->sum = sum;
    h->bfs_node = n;
    lbfs_hash_entry[index] = h;
    return;
  }
  for ( ; h->next; h = h->next );

  tmp = new_BfsHashEntry();
  tmp->sum = sum;
  tmp->bfs_node = n;
  h->next = tmp;
      
}



Bool bfs_state_hashed( State *S )

{

  int sum, index;
  BfsHashEntry *h;

  sum = state_sum( S );
  index = sum & BFS_HASH_BITS;

  h = lbfs_hash_entry[index];
  for ( h = lbfs_hash_entry[index]; h; h = h->next ) {
    if ( h->sum != sum ) {
      continue;
    }
    if ( same_state( &(h->bfs_node->S), S ) ) {
      return TRUE;
    }
  }

  return FALSE;

}












/****************************
 * STATE HANDLING FUNCTIONS *
 ****************************/












/* function that computes state transition as induced by a
 * normalized ADL action. Adds go before deletes!
 *
 * a bit odd in implementation:
 * function returns number of new goal that came in when applying
 * op to source; needed for Goal Added Deletion Heuristic
 */
int result_to_dest( State *dest, State *source, int op )

{

  static Bool first_call = TRUE;
  static Bool *in_source, *in_dest, *in_del, *true_ef;
  static int *del, num_del;

  int i, j, ef;
  int r = -1;
  
  if ( first_call ) {
    in_source = ( Bool * ) calloc( gnum_ft_conn, sizeof( Bool ) );
    in_dest = ( Bool * ) calloc( gnum_ft_conn, sizeof( Bool ) );
    in_del = ( Bool * ) calloc( gnum_ft_conn, sizeof( Bool ) );
    true_ef = ( Bool * ) calloc( gnum_ef_conn, sizeof( Bool ) );
    del = ( int * ) calloc( gnum_ft_conn, sizeof( int ) );
    for ( i = 0; i < gnum_ft_conn; i++ ) {
      in_source[i] = FALSE;
      in_dest[i] = FALSE;
      in_del[i] = FALSE;
    }
    for ( i = 0; i < gnum_ef_conn; i++ ) {
      true_ef[i] = FALSE;
    }
    first_call = FALSE;
  }

  /* setup true facts for effect cond evaluation
   */
  for ( i = 0; i < source->num_F; i++ ) {
    in_source[source->F[i]] = TRUE;
  }

  /* setup deleted facts
   */
  num_del = 0;
  for ( i = 0; i < gop_conn[op].num_E; i++ ) {
    ef = gop_conn[op].E[i];
    for ( j = 0; j < gef_conn[ef].num_PC; j++ ) {
      if ( !in_source[gef_conn[ef].PC[j]] ) break;
    }
    if ( j < gef_conn[ef].num_PC ) continue;
    true_ef[i] = TRUE;
    for ( j = 0; j < gef_conn[ef].num_D; j++ ) {
      if ( in_del[gef_conn[ef].D[j]] ) continue;
      in_del[gef_conn[ef].D[j]] = TRUE;
      del[num_del++] = gef_conn[ef].D[j];
    }
  }

  /* put all non-deleted facts from source into dest.
   * need not check for put-in facts here,
   * as initial state is made doubles-free, and invariant keeps
   * true through the transition procedure
   */
  dest->num_F = 0;
  for ( i = 0; i < source->num_F; i++ ) {
    if ( in_del[source->F[i]] ) {
      continue;
    }
    dest->F[dest->num_F++] = source->F[i];
    in_dest[source->F[i]] = TRUE;
  }

  /* now, finally, add all fullfilled effect adds to dest; 
   * each fact at most once!
   */
  for ( i = 0; i < gop_conn[op].num_E; i++ ) {
    if ( !true_ef[i] ) continue;
    ef = gop_conn[op].E[i];
    for ( j = 0; j < gef_conn[ef].num_A; j++ ) {
      if ( in_dest[gef_conn[ef].A[j]] ) {
	continue;
      }
      dest->F[dest->num_F++] = gef_conn[ef].A[j];
      in_dest[gef_conn[ef].A[j]] = TRUE;
      if ( gft_conn[gef_conn[ef].A[j]].is_global_goal ) {
	r = gef_conn[ef].A[j];
      }
    }
  }

  /* unset infos
   */
  for ( i = 0; i < source->num_F; i++ ) {
    in_source[source->F[i]] = FALSE;
  }
  for ( i = 0; i < dest->num_F; i++ ) {
    in_dest[dest->F[i]] = FALSE;
  }
  for ( i = 0; i < num_del; i++ ) {
    in_del[del[i]] = FALSE;
  }
  for ( i = 0; i < gop_conn[op].num_E; i++ ) {
    true_ef[i] = FALSE;
  }

  return r;

}



void source_to_dest( State *dest, State *source )

{

  int i;

  for ( i = 0; i < source->num_F; i++ ) {
    dest->F[i] = source->F[i];
  }
  dest->num_F = source->num_F;

}



void copy_source_to_dest( State *dest, State *source )

{

  int i, m;

  if ( dest->max_F < source->num_F ) {
    if ( dest->F ) {
      free( dest->F );
      dest->F =NULL;
    }
    if ( source->num_F + 50 > gnum_ft_conn ) {
      m = gnum_ft_conn;
    } else {
      m = source->num_F + 50;
    }
    dest->F = ( int * ) calloc( m, sizeof( int ) );
    dest->max_F = m;
  }

  for ( i = 0; i < source->num_F; i++ ) {
    dest->F[i] = source->F[i];
  }
  dest->num_F = source->num_F;

}



void print_state( State S )

{

  int i;
  
  for ( i = 0; i < S.num_F; i++ ) {
    printf("\n");
    print_ft_name( S.F[i] );
  }

}
