/* Copyright (c) 2001 by the Institute for Computer Science,               */
/* Alberts-Ludwigs-University of Freiburg, Germany.                        */
/* All Rights Reserved.  This software is for educational purposes only.   */
/* Permission is given to distribute this code provided that this intro-   */
/* ductory message is not removed and no monies are exchanged.             */
/* No guarantee is expressed or implied by the distribution of this code.  */
/* Software written by Alberto Lluch Lafuente and Stefan Edelkamp.         */
/* References:                                                             */
/* - Stefan Edelkamp, Alberto Lluch Lafuente and Stefan Leue,              */
/*   Directed Explicit Model Checking with HSF-SPIN, to appear in:         */
/*   Proc. 8th International SPIN Workshop on Model Checking Software,     */
/*   Springer LNCS 2057, Toronto, May 2001                                 */
/* - Stefan Edelkamp, Alberto Lluch Lafuente and Stefan Leue,              */
/*   Protocol Verification with Heuristic Search,                          */
/*   Proc. AAAI Spring Symposium on Model-Based Validation of Inteligence, */
/*   AAAI, Stanford, April 2001.                                           */
/* Send bug-reports or questions to: lafuente@informatik.uni-freiburg.de   */

#ifndef _GENETIC_
#define _GENETIC_

/* Includes */
#include "search.h"
#include <time.h>

/* Parameteres */
int population_size;
#define DEFAULT_POPULATION_SIZE 10
double mutation_probability;
#define DEFAULT_MUTATION_PROBABILITY 0.01
int chromosome_size; /* Size in bytes */
#define DEFAULT_CHROMOSOME_SIZE DEFAULT_DEPTH_BOUND
unsigned char elitism;
#define DEFAULT_ELITISM 0
unsigned char crossover_operator;
#define BIT_MASKING_CROSSOVER 0
#define BYTE_MASKING_CROSSOVER 1
#define ONE_POINT_CROSSOVER 2
#define TWO_POINT_CROSSOVER 3
#define DEFAULT_CROSSOVER ONE_POINT_CROSSOVER

#define FITNESS_AVERAGE 'a'
#define FITNESS_MINIMAL 'm'
#define FITNESS_ALBERTO 'n'

unsigned char fitness_function;


#define MUTATION_ALBERTO 'n'
#define MUTATION_SINGLEPOINT_DRIFT  'd'
#define MUTATION_SINGLEPOINT_RANDOMIZE  'r'
#define MUTATION_MULTIPOINT 'm'
#define MUTATION_ALLPOINT 'a'

unsigned char mutation_function;

#define SELECTION_ALBERTO 'n'
#define SELECTION_ONE_RANDOM  'o'
#define SELECTION_TWO_RANDOM  't'
#define SELECTION_RANDOMRANK  'r'
#define SELECTION_TWO_RANDOMRANK  'R'
#define SELECTION_BESTOF2 'b'
#define SELECTION_ROULETTE  'l'
#define SELECTION_ROULETTE_REBASED  'L'

unsigned char selection_function;

#define ENCODING_ALBERTO  'n'
#define ENCODING_PROCESS_TRANS 'p'

unsigned char encoding_method;

void print_fitness(){
  printf("Available Fitness Functions are:\n");
  printf("\t%c: Fitness Average\n",FITNESS_AVERAGE);
  printf("\t%c: Fitness Minimal\n",FITNESS_MINIMAL);
  printf("\t%c: Fitness by Alberto\n",FITNESS_ALBERTO);
}

void print_mutation(){
  printf("Available Mutation Functions are:\n");
  printf("\t%c: Mutation Function by Alberto\n", MUTATION_ALBERTO);
  printf("\t%c: Mutation Function of Single Point Drift\n", MUTATION_SINGLEPOINT_DRIFT);
  printf("\t%c: Mutation Function of Single Point Randomize\n", MUTATION_SINGLEPOINT_RANDOMIZE);
  printf("\t%c: Mutation Function of Multi Point\n", MUTATION_MULTIPOINT);
  printf("\t%c: Mutation Function of All Point\n", MUTATION_ALLPOINT);

}

void print_crossover(){
  printf("Available Crossover Functions are:\n");
  printf("\t%d: Bit Masking Crossover\n", BIT_MASKING_CROSSOVER);
  printf("\t%d: Byte Masking Crossover\n", BYTE_MASKING_CROSSOVER);
  printf("\t%d: One Point Crossover\n", ONE_POINT_CROSSOVER);
  printf("\t%d: Two Point Crossover\n", TWO_POINT_CROSSOVER);
}


void print_selection(){
  printf("Available Selection Functions are:\n");
  printf("\t%c: Selection Function by Alberto\n", SELECTION_ALBERTO);
  printf("\t%c: Selection Function of father is randomly selected\n", SELECTION_ONE_RANDOM);
  printf("\t%c: Selection Function of parents are randomly selected\n", SELECTION_TWO_RANDOM);
  printf("\t%c: Selection Function of random rank\n", SELECTION_RANDOMRANK);
  printf("\t%c: Selection Function of parents random rank\n", SELECTION_TWO_RANDOMRANK);
  printf("\t%c: Selection Function of selection the best of two candidates\n", SELECTION_BESTOF2);
  printf("\t%c: Selection Function of Roulette\n", SELECTION_ROULETTE);
  printf("\t%c: Selection Function of Roulette rebased\n", SELECTION_ROULETTE_REBASED);  
}

void print_encoding(){
  printf("Available Encoding Methods are:\n");
  printf("\t%c: Encoding Method which is simply MODed to select successor\n", ENCODING_ALBERTO);
  printf("\t%c: Encoding Method which considers process and trans to select successor\n", ENCODING_PROCESS_TRANS);
}

typedef struct chromosome{
  unsigned char* genes;
  unsigned int fitness;
  unsigned int length;
} chromosome;
unsigned int total_fitness;

int ga_comp(const void* a, const void* b){
  return ((chromosome*)a)->fitness - ((chromosome*)b)->fitness;
}

class Genetic : public Search{
public:
  friend int ga_comp(void* a, void* b);
public:
  unsigned int bound_depth; /* Bound depth. States beyond the depth are not explored. */
  unsigned int maxf;            /* Maximum value for f. */
  int sol_depth;
  unsigned int worst_fit, best_fit, new_worst_fit;
  chromosome *child,*initial_population,*new_population, * aux_population;
  unsigned int actual_gen;
  unsigned int optimize; /* 0 is error search, 1 is optimal error search */
  unsigned int best_child;
  /* The folowing variables are used in function DFSsearch. Declared here for efficiency. */

  Genetic (int hash_size, int _maxf, int _optimize): Search() {
    ht = new HashTable(1<<hash_size);
    maxf=_maxf; /* Set maximal value for f. */
    optimize=_optimize;
    
#ifdef DEBUG_GLIVENESS
    printf("Maxf = %d\n", maxf);
#endif //
  }

  int search(int bound) {
    int father,mother;
    State *state,*old_goal_state;

    state = (State *)0;
    int iter = 0; /* Iteration Counter */
    unsigned int sol_found = (unsigned int)-1;

    sol_depth=-1; /* No solution found. */
    bound_depth=bound; /* Set bound depth. */
    if (Selected_Heuristic==BLIND) S.h=0;/* If not heuristic defined set h value to zero. */
    S.pred=(State *)0; /* Initial state has no predecessor. */
    if( (Selected_Goal==GIVEN_STATE || Selected_Goal==LTL) && proto->goal(&S,!optimize)){
      /* In some cases the initial state may be a goal state. */
      build_solution_path(&S);
      return S.g;
    }
    memory=1; generated=1; expanded=0; matched=0; open_size=max_open_size=1; /* Init statistics. */

    printf("Spawning first generation...\n");
    initial_population = new chromosome[population_size];
    for(int i=0; i<population_size; i++)
      initial_population[i].genes=new unsigned char[chromosome_size];
    new_population = new chromosome[population_size];
    for(int i=0; i<population_size; i++)
      new_population[i].genes=new unsigned char[chromosome_size];

    sol_depth=produce_initial_population(initial_population);
    if(sol_depth!=-1){         // get solution
#ifdef DEBUG_GA_ITERATIONBOUND
  printf("Here I found solution in the initial populaiton with depth %d", sol_depth);
#endif //    
      if(!optimize)            
        return sol_depth;
      else{                    // with the optimize option, we need continue for the best solution
         sol_found = sol_depth;
         build_solution_path(&S);
      }
    }
#ifdef DEBUGALBERTO
	printf("Preparing selection table...\n");
#endif //
    prepare_selection_table(initial_population);
//    printf("\tBest fitness is %d, Worst fitness is %d, Average is %f\n",best_fit, worst_fit,total_fitness/(float)population_size+worst_fit-1);

    while(1){ /* Loop until error found */
      if(iter++ >= Iteration_Bound){
        if(sol_found == (unsigned int)-1){
#ifdef DEBUG_GA_ITERATIONBOUND
          printf("No solution Found!\n");
#endif //
          return -1;
        }else{
#ifdef DEBUG_GA_ITERATIONBOUND
          printf("Found Solution with depth %d\n", sol_found);
#endif //
          return sol_found;
        }
      }
        

#ifdef DEBUG_GA_ITERATIONBOUND
        printf("Iter %d\n", iter);
#endif //
#ifdef DEBUGALBERTO
      printf("The next generation comes...\n");
      snapshot();
#endif //
      best_fit=maxf;
      new_worst_fit=0;

      /* Elitism */
      if(elitism){
        for(int i=0; elitism && i<chromosome_size; i++){
          new_population[0].genes[i]=initial_population[best_child].genes[i];
        }

        new_population[0].fitness=initial_population[best_child].fitness;
        new_population[0].length=initial_population[best_child].length;
        best_fit=new_population[0].fitness;
      }

      for(int i=elitism; i<population_size; i++){
        select(initial_population, i, father, mother);

        // father=select_chromosome(initial_population);
        // mother=select_chromosome(initial_population);
        child=&(new_population[i]);

        crossover(mother,father,child);

        mutate(child);

        /* Check if goal and set fitness */
	old_goal_state=state;
        sol_depth = check(child, &state);

        if(sol_depth!=-1){
#ifdef DEBUG_GA_ITERATIONBOUND
  printf("Here I found solution with depth %d at Iter %d\n", sol_depth, iter);
#endif //
          if(!optimize) /* Criterium?*/
            return sol_depth;
          else{
            if(sol_found > sol_depth){
#ifdef DEBUG_GA_ITERATIONBOUND
  printf("Here I found better solution with depth %d instead of %d at Iter %d\n", sol_depth, sol_found, iter);
#endif //
              
              sol_found = sol_depth;
              build_solution_path(state);
	      if(old_goal_state) remove_states(old_goal_state);
            } else{
	      remove_states(state);
	      state=old_goal_state;
	    }
          }
        }
        
        if(child->fitness<best_fit){
          best_child=i;
          best_fit=child->fitness;
        }

        if(child->fitness>new_worst_fit)
          new_worst_fit=child->fitness;
      }
      
      worst_fit=new_worst_fit;
      aux_population=new_population;
      new_population=initial_population;
      initial_population=aux_population;
      prepare_selection_table(initial_population);
//      printf("\tBest fitness is %d, Worst fitness is %d, Average is %f\n",best_fit, worst_fit,total_fitness/(float)population_size+worst_fit-1);
    }
  }

  int produce_initial_population(chromosome *population){
    int sol;
    State *state;

    best_fit=maxf;
    worst_fit=0;
    for(int i=0; i<population_size; i++){
      for(int j=0; j<chromosome_size; j++){
        population[i].genes[j]=(unsigned char)random();
      }

      sol = check(&(population[i]), &state);

      if(population[i].fitness<best_fit){
        best_fit=population[i].fitness;
        best_child=i;
      }

      if(population[i].fitness>worst_fit)
        worst_fit=population[i].fitness;

      if(sol!=-1 && !optimize)
        return sol;
      else if(sol!=-1)
        remove_states(state);

    }
    return -1;
  }

  void prepare_selection_table(chromosome *population){
    total_fitness=0;
    for(int i=0; i<population_size; i++)
      total_fitness+=(worst_fit-population[i].fitness)+1;
  }

  void select(chromosome* population, int pos, int& mother, int& father){
    mother = 0;
    father = 0;

    switch(selection_function){
      case SELECTION_ALBERTO:
        mother = select_chromosome(population);
        father = select_chromosome(population);
        return;
        break;
      case SELECTION_ONE_RANDOM:
        mother = pos;

        do{
          father = select_random();
        }while(mother == father);
        return;
        break;
      case SELECTION_TWO_RANDOM:
        mother = select_random();

        do{
          father = select_random();
        }while(mother == father);
        return;
        break;
      case SELECTION_TWO_RANDOMRANK:
        mother = select_randomrank(population, pos, true);
        father = select_randomrank(population, pos, false);
        return;
        break;
      case SELECTION_RANDOMRANK:
        mother = pos;
        father = select_randomrank(population, pos, true);
        return;
        break;
      case SELECTION_BESTOF2:
        mother = select_bestof2(population);

        do{
          father = select_bestof2(population);
        }while(mother == father);
        return;
        break;
      case SELECTION_ROULETTE:
        mother = select_roulette(population, pos);
        father = select_roulette(population, pos);
        return;
        break;
      case SELECTION_ROULETTE_REBASED:
        mother = select_roulette_rebased(population, pos);
        father = select_roulette_rebased(population, pos);
        return;
        break;
    }
  }

  int select_roulette(chromosome* population, int pos){
    static int marker;

    if(pos == 0){
      marker = random()% population_size;
    }

    int fit;

    fit=random()%total_fitness;

    //printf("\tFIT=%d, TOT=%d\n",fit,total_fitness);
    do{
      marker ++;

      if(marker >= population_size)
        marker = 0;

      fit -= population[marker].fitness;
      //printf("Loop pos = %d; maker = %d; fit = %d\n", pos, marker, fit);
    }while(fit > 0);

    return marker;
  }

  int select_roulette_rebased(chromosome* population, int pos){
    static int marker;
    static double mean;
    static double minval;
    
    if(pos == 0){
      marker = random()% population_size;

      mean = total_fitness / population_size;
      minval = population[population_size - 1].fitness;
      mean -= minval;
    }
    
    double val;

    val = (1.0 * random())/(RAND_MAX * population_size);
    //printf("\tFIT=%d, TOT=%d\n",fit,total_fitness);
    do{
      marker ++;

      if(marker >= population_size)
        marker = 0;

      val -= (population[marker].fitness - minval)/mean;
    }while(val > 0.0);

    return marker;    
  }
  
  int select_bestof2(chromosome* population){
    int one = random() % population_size;
    int two = random() % population_size;

    if(population[one].fitness >= population[two].fitness)
      return one;
    else
      return two;
  }
  
  int select_randomrank(chromosome* population, int pos, bool needSort){
    if(pos == 0){
      if(needSort){
        qsort(population, population_size, sizeof(chromosome), &ga_comp);

//        for(int i=0; i < population_size; i++)
//          printf("index: %d, fitness: %d\n", i, population[i].fitness);
      }

      return 0;
    }
      
    return random()%pos;
  }
  
  int select_random(){
    return random()%population_size;
  }
  
  int select_chromosome(chromosome *population){
    int fit;

    fit=random()%total_fitness;
    //printf("\tFIT=%d, TOT=%d\n",fit,total_fitness);
    for(int i=0; i<population_size; i++){
      if(fit<=0){
	//printf("Selected Child is %d\n",i);
	return i;
      }
      fit-=(((worst_fit+1)-population[i].fitness));
      //printf("\t\tworst=%d, chiuld=%d\n",worst_fit,population[i].fitness);
      //printf("\t\tfit=%d, tot=%d\n",fit,total_fitness);
    }
    return 0;
  }

  void crossover(int father, int mother, chromosome *child){
    /* At the moment equal probability */
    unsigned char mask, block1, block2;
    int min_length,point,i;
    int point2;

    switch(crossover_operator){
    case BIT_MASKING_CROSSOVER:
      for(i=0; i<chromosome_size; i++){
        mask=(unsigned char)random();
        block1=initial_population[father].genes[i]&mask;
        block2=initial_population[mother].genes[i]&~mask;
        child->genes[i]=block1|block2;
      }
      
      break;
    case BYTE_MASKING_CROSSOVER:
      for(i=0; i<chromosome_size; i++){
        if( (random()%(initial_population[father].fitness+initial_population[mother].fitness+2)) <= initial_population[mother].fitness)
          child->genes[i]=initial_population[father].genes[i];
        else
          child->genes[i]=initial_population[mother].genes[i];
      }
      
      break;
    case ONE_POINT_CROSSOVER:
      if(initial_population[father].length < initial_population[mother].length)
        min_length=initial_population[father].length;
      else
        min_length=initial_population[mother].length;

      if(min_length>0)
        point=random()%min_length;
        
      for(i=0; i<chromosome_size && i<point; i++)
        child->genes[i]=initial_population[father].genes[i];

      for(i; i<chromosome_size; i++)
        child->genes[i]=initial_population[mother].genes[i];

      break;
    case TWO_POINT_CROSSOVER:
      if(initial_population[father].length < initial_population[mother].length)
        min_length=initial_population[father].length;
      else
        min_length=initial_population[mother].length;

      if(min_length>0)
        point=random()%min_length;

      do{
        point2 = random()% min_length;
      } while (point2 == point);

      if (point > point2) 
      {
        int tmp = point; 
        point = point2;
        point2 = tmp;
      }

      for(i=0; i<chromosome_size && i<point; i++)
        child->genes[i]=initial_population[father].genes[i];

      for(i; i<chromosome_size && i < point2; i++)
        child->genes[i]=initial_population[mother].genes[i];

      for(i; i<chromosome_size; i++)
        child->genes[i]=initial_population[father].genes[i];

      break;
      
    }
  }

  void mutate(chromosome *child){
    switch(mutation_function){
      case MUTATION_ALBERTO:
        mutate_alberto(child);
        break;
      case MUTATION_SINGLEPOINT_DRIFT:
        mutate_singlepoint_drift(child);
        break;
      case MUTATION_SINGLEPOINT_RANDOMIZE:
        mutate_singlepoint_randomize(child);
        break;
      case MUTATION_MULTIPOINT:
        mutate_multipoint(child);
        break;
      case MUTATION_ALLPOINT:
        mutate_allpoint(child);
        break;
      }
  }
  
  void mutate_alberto(chromosome *child){
    //return;
    //printf("v is %f, p is %f\n",((random()%100000))/100000.0,mutation_probability);

    for(int i=0; i<chromosome_size; i++){
      if( ((random()%100000)/100000.0) < mutation_probability){
	/*      child_genes[i]|1) = xxxxxxx1 */
	/*   ~(child_genes[i]&1)) = 1111111y */
	/*                      & = xxxxxxx1 */
	//printf("Mutated %d to",child->genes[i]);
	child->genes[i]=(child->genes[i]|1) & ~(child->genes[i]&1);
	//printf("%d\n",child->genes[i]);
      }
      if( ((random()%100000)/100000.0) < mutation_probability)
	child->genes[i]=(child->genes[i]|2) & ~(child->genes[i]&2);
      if( ((random()%100000)/100000.0) < mutation_probability)
	child->genes[i]=(child->genes[i]|4) & ~(child->genes[i]&4);
      if( ((random()%100000)/100000.0) < mutation_probability)
	child->genes[i]=(child->genes[i]|8) & ~(child->genes[i]&8);
      if( ((random()%100000)/100000.0) < mutation_probability)
	child->genes[i]=(child->genes[i]|16) & ~(child->genes[i]&16);
      if( ((random()%100000)/100000.0) < mutation_probability)
	child->genes[i]=(child->genes[i]|32) & ~(child->genes[i]&32);
      if( ((random()%100000)/100000.0) < mutation_probability)
	child->genes[i]=(child->genes[i]|64) & ~(child->genes[i]&64);
      if( ((random()%100000)/100000.0) < mutation_probability)
	child->genes[i]=(child->genes[i]|128) & ~(child->genes[i]&128);
    }
  }

  void mutate_singlepoint_drift(chromosome *child){
    child->genes[random()%chromosome_size] += random()%2?-1:1;    
  }

  void mutate_singlepoint_randomize(chromosome *child){
    child->genes[random()%chromosome_size] = random();
  }

  void mutate_multipoint(chromosome *child){
    for(int point = 0; point < chromosome_size; point++){
      if( ((random()%100000)/100000.0) < mutation_probability )
        child->genes[point] += random()%2?-1:1;
    }
  }

  void mutate_allpoint(chromosome *child){
    for(int point = 0; point < chromosome_size; point++){
      switch(random()%3){
        case 0:
          child->genes[point] += 1;
          break;
        case 1:
          child->genes[point] += -1;
          break;
        default:
          break;
      }
    }
  }

  int check(chromosome *child, State **goal_state){
    if(( Selected_Goal == LIVENESS )) /* When checking for cycles...*/
      ht->clean(); /* ...the hash table has to cleaned before decoding a chromosome. */
    switch(fitness_function)
    {
      case FITNESS_AVERAGE:
        return check_average(child, goal_state);
        break;
      case FITNESS_MINIMAL:
        return check_min(child, goal_state);
        break;
      case FITNESS_ALBERTO:
        return check_alberto(child, goal_state);
        break;
      }
  }

      
  int check_alberto(chromosome *child, State **goal_state){
    /* Returns -1 if no solution is found. */
    /* Sets the fitness of the chromosome. */
    State* state;
    State* newState = (State *)0; /* Successor of state. */
    StateItem* newStateList = (StateItem*)0; /* Successors list. */
    StateItem* aux_item;
    int best_value;

    int cycle_number = 0;
    int accepting_states_number = 0;
    int last_accepting_state = -1;
    
    state=new State;
    *state=S;
    state->ps=(PackedState *)new unsigned char[S.ps->_vsz];
    memcpy((void*)state->ps,(void*)S.ps,S.ps->_vsz);

    actual_gen=0;
    best_value=maxf;
    if(( Selected_Goal == LIVENESS ))
      ht->insert(state); /* Store states in hash table only for cycle detection. */
    while(true){
      /* Stack and depth issues */
      state->in_open(); /* Mark state as on dfs1 stack. */
      stack_height++;

      if(depth_reached<bound_depth && state->g>=bound_depth){
        printf("Warning: max search depth too small\n");
      }

      if(state->g > depth_reached)
        depth_reached=state->g;

      if(state->g>=bound_depth){
        if(!optimize){
          child->fitness=state->h+1;
        }else
          child->fitness=100*state->g;

        child->length=stack_height;
        remove_states(state);

        return -1; /* If depth bound is reached return -1 */
      }

      /* Expand state */
      newStateList = proto->expand(state,1,bound_depth); expanded++;
      /* Check if state is a deadlock */
      if(!newStateList && (Selected_Goal==DEADLOCK || Selected_Goal==SIMPLESAFETY || Selected_Goal==VALID_ENDSTATE)){
        /* If state is an endstate and we are checking for deadlocks or valid endstates,
	      then check if state is a goal state. */
        if(proto->goal(state,!optimize)){
         (*goal_state)=state;
          build_solution_path(state);

          if(!optimize)
            child->fitness=state->h+1;
          else
            child->fitness=state->g;

          child->length=stack_height;

          return state->g;
        }
      }
      
      if(!newStateList){
        if( Selected_Goal == LIVENESS ){
          child->fitness = ga_fitness(accepting_states_number, last_accepting_state, cycle_number, stack_height);
        }else if(!optimize){
          child->fitness=state->h+1;
        }
        //child->fitness=maxf;
        else
          child->fitness=state->g*100;

        remove_states(state);
        child->length=stack_height;

        return -1; /* If no successors return -1 */
      }

      /* Select successor according to genes. */
      newState=select_successor(newStateList,child);
      
#ifdef VERI
      if(( Selected_Goal == LIVENESS )){
      //            printf("Leave at %d %d\n", ht, newState);
	if(accpstate[VERI][((P0 *)hsf_pptr(newState->ps,0))->_p]){
	  accepting_states_number ++;
	  last_accepting_state = newState->g;
	}
        State* found = ht->search(newState);
        if(found){
          if((int)found->g <= last_accepting_state){
            (*goal_state) = state;
	    printf("\tacceptance cycle found (at depth %d, length %d)\n",found->g,state->g-found->g);
	    
	    sol_depthfound=found->g+1;
            child->length = stack_height;
  //                printf("Leave at %d\n", __LINE__);
            return newState->g;
          }else 
              cycle_number ++;
        }else{
//          printf("Not found\n");
#ifdef DEBUG_GLIVENESS
          printf("Insert %d; ps: %d\n", newState, newState->ps);
#endif //
          ht->insert(newState);
        }
      }
#endif // VERI
    //            printf("Leave at %d\n", __LINE__);
      
//      /* Check if goal */
//      if( Selected_Goal && Selected_Goal!=DEADLOCK && Selected_Goal!=VALID_ENDSTATE && proto->goal(newState,!optimize) ){
//        /* Check for errors, but not in the case of deadlocks and valid endstates */
//        /* Also a duplicate could be an error (only by checking assertions violations). */
//        (*goal_state)=state;
//        build_solution_path(newState);
//
//        if(!optimize)
//          child->fitness=state->h+1;
//        else
//          child->fitness=state->g;
//
//        child->length=stack_height;
//
//        return newState->g;
//      }

      /*
      if( Selected_Goal == LTL ){
        (*goal_state)=state;
        build_solution_path(newState);

        if(!optimize)
          child->fitness=state->h+1;
        else
          child->fitness=state->g;

        child->length=stack_height;

        return newState->g;
      }
      */
      
      state=newState;

      if(state->h<best_value)
        best_value=state->h+1;

        //   printf("stack_height: %d\n", stack_height);
        //   printf("state->g: %d\n", state->g);
        //   printf("state->h: %d\n", state->h);
        //   printf("child->fitness: %d\n", child->fitness);
        //    printf("i: %d\tstate->g: %d\tstate->h: %d\tfitness: %d\n", stack_height, state->g, state->h, child->fitness);
//        printf("[%s]%d\tstack %d, ps = %d\n", __FILE__, __LINE__, stack_height, ((State*)XXXX)->ps);
    }

   // printf("Leave at %d\n", __LINE__);

  }
  
//  int check(chromosome *child, State **goal_state){
//    /* Returns -1 if no solution is found. */
//    /* Sets the fitness of the chromosome. */
//    State* state;
//    State* newState = (State *)0; /* Successor of state. */
//    StateItem* newStateList = (StateItem*)0; /* Successors list. */
//    StateItem* aux_item;
//    int best_value;
//
//    state=&S; actual_gen=0;
//    best_value=maxf;
//    while(true){
//      /* Stack and depth issues */
//      state->in_open(); /* Mark state as on dfs1 stack. */
//      stack_height++;
//      if(depth_reached<bound_depth && state->g>=bound_depth)
//	printf("Warning: max search depth too small\n");
//      if(state->g > depth_reached)
//	depth_reached=state->g;
//      if(state->g>=bound_depth){
//	if(!optimize){
//	  child->fitness=state->h+1;
//	}
//	else
//	  child->fitness=100*state->g;
//	child->length=stack_height;
//	remove_states(state);
//	return -1; /* If depth bound is reached return -1 */
//      }
//
//      /*if(state->g==6){
//      printf("Expanding at depth%d...\n",state->g);
//      //for(double i=0; state->g>38 && i<100000; i++){
//      while(1){
//      newStateList = proto->expand(state); expanded++;
//      //proto->print_successors(newStateList);
//      while(newStateList) {
//	delete newStateList->the_state;
//	aux_item = newStateList;
//	newStateList = newStateList->next;
//	delete aux_item;
//      }
//      }
//      }*/
//
//      /* Expand state */
//      newStateList = proto->expand(state,1,bound_depth); expanded++;
//
//      /* Check if state is a deadlock */
//      if(!newStateList && (Selected_Goal==DEADLOCK || Selected_Goal==SIMPLESAFETY || Selected_Goal==VALID_ENDSTATE)){
//	/* If state is an endstate and we are checking for deadlocks or valid endstates,
//	   then check if state is a goal state. */
//	if(proto->goal(state,!optimize)){
//	  (*goal_state)=state;
//	  build_solution_path(state);
//	  if(!optimize)
//	    child->fitness=state->h+1;
//	  else
//	    child->fitness=state->g;
//	  child->length=stack_height;
//	  return state->g;
//	}
//      }
//      if(!newStateList){
//	if(!optimize){
//	  child->fitness=state->h+1;
//	}
//	//child->fitness=maxf;
//	else
//	  child->fitness=state->g*100;
//	remove_states(state);
//	child->length=stack_height;
//	return -1; /* If no successors return -1 */
//      }
//
//      /* Select successor according to genes. */
//      newState=select_successor(newStateList,child);
//
//      /* Check if goal */
//      if( Selected_Goal && Selected_Goal!=DEADLOCK && Selected_Goal!=VALID_ENDSTATE && proto->goal(newState,!optimize) ){
//	/* Check for errors, but not in the case of deadlocks and valid endstates */
//	/* Also a duplicate could be an error (only by checking assertions violations). */
//	(*goal_state)=state;
//	build_solution_path(newState);
//	if(!optimize)
//	  child->fitness=state->h+1;
//	else
//	  child->fitness=state->g;
//	child->length=stack_height;
//	return newState->g;
//      }
//      state=newState;
//      if(state->h<best_value) best_value=state->h+1;
//    }
//  }


  // added by liujun
	int check_min(chromosome *child, State **goal_state){
		/* Returns -1 if no solution is found. */
		/* Sets the fitness of the chromosome. */
		State* state;
		State* newState = (State *)0; /* Successor of state. */
		StateItem* newStateList = (StateItem*)0; /* Successors list. */
		StateItem* aux_item;
		int best_value;

		state=&S; /* First state */
		actual_gen=0;
		best_value = maxf;

		child->fitness = state->h;

		while(true){
			/* Stack and depth issues */
			state->in_open(); /* Mark state as on dfs1 stack. */
			stack_height++;

			if(depth_reached<bound_depth && state->g>=bound_depth)
				printf("Warning: max search depth too small\n");

			if(state->g > depth_reached)
				depth_reached=state->g;

			if(child->fitness > state->h)
				child->fitness = state->h;

			if(state->g >= bound_depth){

				child->length=stack_height;
				remove_states(state);
				return -1; /* If depth bound is reached return -1 */
			}

			/* Expand state */
			newStateList = proto->expand(state,1,bound_depth); expanded++;

			/* Check if state is a deadlock */
			if(!newStateList && (Selected_Goal==DEADLOCK || Selected_Goal==SIMPLESAFETY || Selected_Goal==VALID_ENDSTATE)){
			/* If state is an endstate and we are checking for deadlocks or valid endstates,
				then check if state is a goal state. */
				if(proto->goal(state,!optimize)){
					(*goal_state)=state;
					build_solution_path(state);

					child->length=stack_height;
					return state->g;
				}
			}

			if(!newStateList){
				remove_states(state);
				child->length=stack_height;
				return -1; /* If no successors return -1 */
			}

			/* Select successor according to genes. */
			newState=select_successor(newStateList,child);

			/* Check if goal */
			if( Selected_Goal && Selected_Goal!=DEADLOCK && Selected_Goal!=VALID_ENDSTATE && proto->goal(newState,!optimize) ){
				/* Check for errors, but not in the case of deadlocks and valid endstates */
				/* Also a duplicate could be an error (only by checking assertions violations). */
				(*goal_state)=state;
				build_solution_path(newState);

				child->length=stack_height;

				return newState->g;
			}

			state=newState;

			if(state->h<best_value)
				best_value=state->h+1;
		}
	}

  unsigned int ga_fitness_help(int n, int shift){
    unsigned int m = 0xF;

    if(n > m)
      n = m;
    else
      n = n & m;

    n = n << shift * 4;
                  
    return n;
  }

  /*
  calculate fitness value.
  four parts: type, # of accepting states, # of cycle, pos of last accepting state
  type:
    1 : found acception states and cycles
    2 : found cycles
    3 : found accepting states
    4 : nothing found
  */
  unsigned int ga_fitness(int accepting_states_number, int last_accepting_state, int cycle_number, int depth){
    unsigned int ret;
    unsigned int pos;

    if(last_accepting_state == -1){
      pos = 0;
      if(cycle_number == 0)
        ret = 4;
      else
        ret = 2;
    }else{
      pos = ((last_accepting_state * 1.0 * 0xF)/ depth);
      if(cycle_number == 0)
        ret = 3;
      else
        ret = 1;
    }

    ret = ret << 3 * 4;

    return ret + pos + ga_fitness_help(accepting_states_number, 2) + ga_fitness_help(cycle_number, 1);
  }

	int check_average(chromosome *child, State **goal_state){
		/* Returns -1 if no solution is found. */
		/* Sets the fitness of the chromosome. */
		State* state;
		State* newState = (State *)0; /* Successor of state. */
		StateItem* newStateList = (StateItem*)0; /* Successors list. */
		StateItem* aux_item;
		int best_value;

		int fitness_sum = 0;
		int states_count = 0;

		state=&S; /* First state */
		actual_gen=0;
		best_value = maxf;

		child->fitness = state->h;

		while(true){
			/* Stack and depth issues */
			state->in_open(); /* Mark state as on dfs1 stack. */
			stack_height++;

			if(depth_reached<bound_depth && state->g>=bound_depth)
				printf("Warning: max search depth too small\n");

			if(state->g > depth_reached)
				depth_reached=state->g;

			fitness_sum += state->h;
			states_count ++;
			child->fitness = fitness_sum / states_count;

			if(state->g >= bound_depth){
				child->length=stack_height;
				remove_states(state);
				return -1; /* If depth bound is reached return -1 */
			}

			/* Expand state */
			newStateList = proto->expand(state,1,bound_depth); expanded++;

			/* Check if state is a deadlock */
			if(!newStateList && (Selected_Goal==DEADLOCK || Selected_Goal==SIMPLESAFETY || Selected_Goal==VALID_ENDSTATE)){
			/* If state is an endstate and we are checking for deadlocks or valid endstates,
				then check if state is a goal state. */
				if(proto->goal(state,!optimize)){
					(*goal_state)=state;
					build_solution_path(state);
					child->length=stack_height;
					return state->g;
				}
			}

			if(!newStateList){
				remove_states(state);
				child->length=stack_height;
				return -1; /* If no successors return -1 */
			}

			/* Select successor according to genes. */
			newState=select_successor(newStateList,child);

			/* Check if goal */
			if( Selected_Goal && Selected_Goal!=DEADLOCK && Selected_Goal!=VALID_ENDSTATE && proto->goal(newState,!optimize) ){
				/* Check for errors, but not in the case of deadlocks and valid endstates */
				/* Also a duplicate could be an error (only by checking assertions violations). */
				(*goal_state)=state;
				build_solution_path(newState);

				child->length=stack_height;

				return newState->g;
			}

			state=newState;

			if(state->h<best_value)
				best_value=state->h+1;
		}
	}

  State* select_successor(StateItem *newStateList,chromosome *child){
    /* static implementation at the moment */
    int successors, successor;
    int process, trans;
    StateItem *aux_item, *aux_item2;
    State *newState;

    if(actual_gen == (chromosome_size - 1)){
      printf("Warning! Larger chromosome size needed. Actual is %d\n",actual_gen);
    } else{
          actual_gen++;
    }

    /* Select successor according to genes. */
    successors=0;
    for(aux_item = newStateList; aux_item; aux_item = aux_item->next)
      successors++;
    generated += successors;
    //printf("TOTAL SUCCESSORS ARE %d!\n",successors);
    if(encoding_method == ENCODING_ALBERTO){
      successor= (child->genes[actual_gen] % successors)+1;
    }else
      {
        process=child->genes[actual_gen]&15;
        trans=child->genes[actual_gen]>>4;
        successor=1;

        for(aux_item = newStateList; aux_item; aux_item = aux_item->next){
          if( aux_item->the_state->move.pr >= process)
            break;

          successor++;
        }

        if(!aux_item){
          aux_item = newStateList;
          successor=1;
        }
        /* Now aux_item corresponds to the designated process. */

        successors = 0;
        for(aux_item2 = aux_item; aux_item2 && aux_item2->the_state->move.pr == aux_item->the_state->move.pr;  aux_item2 = aux_item2->next)
          successors++; /* successors of the designated process. */
        successor+=(trans%successors);
      }

    //printf("Successor is number %d!\n",successor);
    successors=1;
    while(newStateList) { /* For all successors... */
      if(successors == successor)
        newState = newStateList->the_state; /* newState is the selected successor */
      else
        delete newStateList->the_state;

      aux_item = newStateList;
      newStateList = newStateList->next;
      delete aux_item; /* Delete item in list */
      successors++;
    }
    
    return newState;
  }

  void remove_states(State *state){
    //    if(( Selected_Goal == LIVENESS )){
    //  return; /* When checking cycles, states are stored in hash table and will be deleted in by ht->init() */
    //}

    /* Must be done recursively and in postorder. */
    if(state->g==0) return;
    remove_states(state->pred);
    //printf("Removing state at depth %d\n",state->g);
    state->pred=(State *)0; /* To avoid propagation of delete. */
    delete state;
  }

  void print_name() {
    /* Auxiliary function used in main programm for visualizing the algorithm's name*/
    printf("Genetic Search");
    if(optimize) printf(" (optimizing error trail)");
  }
};
#endif // _GENETIC_
