#define PROVAT_STATE_BASED 5
#define PROVAT_TRANSITION_BASED 6
#define PROVAT 7
  int provat_transition_based(State &S);
  int provat_state_based(State &S);
  int provat(State &S);

/***** BEGIN PROVAT STRATEGY FOR DEADLOCKS *****/

int Protocol_Heuristic::provat_transition_based(State &S){
  /* If it is the root or it is not a real state, but a rendezvous try, return 0 */
  if(S.ps->boq!=-1 || !S.move.o_t){ 
    return 0;
  }
  if(is_dangerous(S.move.o_t)) return 0;
  else return 1;
}

int Protocol_Heuristic::provat_state_based(State &S){
  int w1,w2,N1,N2,q;
  Destination_Entity *de;
  
  w1=1; w2=1; N1=N2=0;
  if((old_nr_pr)!=S.ps->_nr_pr){
    if(S.ps->_nr_pr>1) delete destination_entities_list;
    //printf("Constructing destination list (%d procs)...\n",S.ps->_nr_pr);
    construct_destination_entities_lists(S);
    old_nr_pr=S.ps->_nr_pr;
  }
  //printf("Computing h...\n");
  for(q=0; q<S.ps->_nr_qs; q++){
    for(de=destination_entities_list[q].list; de; de=de->next){
      if( (de->op_typ=='r' && q_len(q+1)==0) ||
	  (de->op_typ=='s' && q_len(q+1)==q_max[q+1])){
	if( (((P0 *)hsf_pptr(S.ps,de->p))->_p==de->s)) N1++;
	else if ( (!de->next) || (de->next->p!=de->p) ) N2++;
      }
    }
  }
  //printf("h is maxh-%d\n",w1*N1+w2*N2);
  return maxh-(w1*N1+w2*N2);
}

int Protocol_Heuristic::provat(State &S){
  int sbh,tbh;
  sbh=provat_state_based(S);
  tbh=provat_transition_based(S);
  return sbh+tbh*sbh;
}

void Protocol_Heuristic::search_destinations(State &S, int p, int s){
  Trans *t;
  unsigned short is_destination;
  int i,q;
  Destination_Entity *aux_destination_entity;
  
  if(!visited[s]){
    for(i=0; i<S.ps->_nr_qs; i++) destination_entities_list[i].aux=0;
    visited[s]=1;
    t=trans[((P0 *)hsf_pptr(S.ps,p))->_t][s];
    if (!t) is_destination=0;
    for(t;t;t=t->nxt){
      if( (!is_dangerous(t)) ||
	  (is_destination && is_destination!=t->lextok_tree->ntyp)){
	is_destination=0;
	break;
      }
      else{
	is_destination=t->lextok_tree->ntyp;
	this_p=hsf_pptr(S.ps,p);
	destination_entities_list[(t->lextok_tree->lft->val())-1].aux=1;
      }
    }
    if(is_destination){
      //printf("\t\tFound %c state %d in process %d\n",is_destination,s,p);
      for(q=0; q<S.ps->_nr_qs; q++){
	if(destination_entities_list[q].aux){
	  //printf("\t\t\tFrom Q%d\n",q);
	  aux_destination_entity=destination_entities_list[q].list;
	  destination_entities_list[q].list=new Destination_Entity;
	  destination_entities_list[q].list->p=p;
	  destination_entities_list[q].list->s=s;
	  destination_entities_list[q].list->op_typ=is_destination;
	  destination_entities_list[q].list->next=aux_destination_entity;
	}
      }
    }
    for(t=trans[((P0 *)hsf_pptr(S.ps,p))->_t][s];t;t=t->nxt)
      if(!visited[t->st]) search_destinations(S,p,t->st);
  }
}

void Protocol_Heuristic::construct_destination_entities_lists(State &S){
  int i,j;
  
  //printf("\tInitializing...\n");
  destination_entities_list=new Destination_Entity_List[S.ps->_nr_qs];
  for(i=0; i<S.ps->_nr_pr; i++){
    visited=new int[nstates_proc[((P0 *)hsf_pptr(S.ps,i))->_t]];
    for(j=0; j<nstates_proc[((P0 *)hsf_pptr(S.ps,i))->_t];j++) visited[j]=0;
    //printf("\tSearching for dest in process %d(%d)...\n",i,((P0 *)hsf_pptr(S.ps,i))->_t);
    search_destinations(S,i,start_proc[((P0 *)hsf_pptr(S.ps,i))->_t]);
    delete visited;
  }
}

/***** END PROVAT STRATEGY *****/
