#ifndef __Response_H__
#define __Response_H__

#define DEBUG_RESPONSE 0

// -----------------------------------
#include "Search.h"
#include "HashTable.h"
// -----------------------------------

template<class Automaton>
class Response : public Search<Automaton> {

private:
  int start;
  int newindex;
  int g, h, f;
  HashTable ht;
  PrioQueue pq;
  int bound_depth;
  int cycle_length;
  int maxf;
  State *seed,*aux_state;

public:
  
  Response (Automaton* aT, int max,int _maxf,
	   int applicability, int heuristic, int wg, int wh): 
    Search<Automaton>(aT,max,_maxf,maxmove,applicability,heuristic,wg,wh),
    ht(max), pq(max,_maxf)
    {
      maxf=_maxf;
    }

  search(int bound){
    State *index;
    State *found;
    State *newState;
    StateItem* newStateList,*aux_item;
    int newindex;
    int hashval;                                 
    int f;


    ht.init(); pq.init();
    bound_depth=bound;
    pq.bestf = wh * S.h; expanded=0;       // compute F value of initial state 
    expanded=sol_depth= 0;    
    if (!heuristic) S.h = 0;
    index=new State;
    *index=S;
    ht.insert(index); memory=1;    
    f = wg * index->g + wh * index->h;       // compute f value 
    pq.insert(index,f);      
    aT->dfa();

    // ------------------------- run -------------------------------
    int maxi = pq.bestf;

    while (1) {    // expand until goal found or hash table full
      while ((!pq.open[pq.bestf]) && (pq.bestf != maxf)) {
	pq.bestf++;                            // find best node on open lists
	if (pq.bestf > maxi) {
	  //cout << maxi << ":" << expanded << endl;
	  maxi = pq.bestf;
	}
      }
      if (pq.bestf == maxf || pq.bestf==bound) {
	//cout << "e:" << expanded << endl;
	//delete newState; ???
	return -1;
      }
      index = pq.open[pq.bestf]->the_state;  // new best state on open list 
      found = (State *)0;

      if (ot->goal(index)) {
	printf("\tclaim violated (at depth %d)\n",found->g);
	//build_rek_path(index,sol_depth,sol_move); // sol_depth--;
	return index->g;
      }

      newStateList = ot->expand(index); expanded++;
 
      while(newStateList){	
        newState=newStateList->the_state;
	aux_item=newStateList;
	newStateList=newStateList->next;
	delete aux_item;
	generated++;                                  // count nodes generated 
	if (!heuristic) newState->h = 0;

	found = ht.search(*(newState->ps)); // target loc.
       
	if (!found) {
	  found=newState;
	  f = wg * found->g + wh * found->h;
	  ht.insert(found); memory++;     // insert into hash list
#ifdef VERI
	  if(accpstate[VERI][((P0 *)hsf_pptr(found->ps,0))->_p]){ // Never claim in accepting state?
	    if(DEBUG_RESPONSE) printf("Accepting state found at depth %d (claim in state %d) by 1st Search\n",found->g,((P0 *)hsf_pptr(found->ps,0))->_p);
	    if(DEBUG_RESPONSE) printf("\tStarting 2nd nested search...\n");
	    //expanded=0; generated=0; memory=0;
	    if(Dfs2(found)!=-1){
	      //this->statistics();
	      return newState->g;
	    }
	    else{
	      if(DEBUG_RESPONSE) printf("\tno cycle found.\n");
	      //this->statistics();
	    }
	    newStateList=(StateItem *)0;
	  } else {
	    pq.insert(found,f);           // insert into open list
	  }
#endif //
	}
	else {
/* 	  if (found->g > newState->g) {     */
/* 	    f = wg * found->g + wh * found->h;  */
/* 	    pq.close(found,f);                  // remove node from open */
/* 	    found=newState; */
/* 	    f = wg * found->g + wh * found->h;  */
/* 	    pq.insert(found,f);                 // insert into open list  */
/* 	    ht.insert(found);                   // insert into hash table */
/* 	    reopened++;         // keep track of how many times this happens */
/* 	  } */
	  delete newState;
	}
      }
      f = wg * index->g + wh * index->h;     // compute f value
      pq.close(index,f);                     // move best state to closed list
    }
  }


  //---------------------------------------------------------------------------

  Dfs2(State* state) { 
    StateItem 
      *newStateList = (StateItem*) 0,  
      *aux_item = (StateItem*) 0;
    State* found;
    State* newState = (State *)0;
    int rval;

    if(state->g==bound_depth){
      if(DEBUG_RESPONSE) printf("\tbound reached by 2nd search\n");
      return -1;
    }
    on_stack(state); /* Mark state as in Dfs1 stack */
    unflag(state); /* Mark state as not visited in the 2nd search */
    newStateList = ot->expand(state); expanded++;  
    if(Selected_Heuristic && newStateList) reorder(newStateList);
    while(newStateList) {
      newState = newStateList->the_state;
      aux_item = newStateList;
      newStateList = newStateList->next;
      delete aux_item;
      generated++;
      //   cout << " successor:" << ot->print(newState) << endl;

      if (ot->goal(*newState)) {          
	//build_rek_path(newState,sol_depth,sol_move);
	printf("claim violated in 2nd search!\n");
	return newState->g;
      }
      
      // cout << "search in hash table" << endl;
      found = ht.search(*(newState->ps)); // target loc.
       
      if (found) {
	if (is_on_stack(found)){
	  printf("t'e pilllau (cycle beginnig at %d, length is %d\n",found->g,newState->g-found->g);
	  depthfound=found->g;
	  sol_depth=0;
	  build_rek_path(newState,sol_depth,sol_move);
	  cycle_length=newState->g-found->g;
	  printf("\tacceptance cycle (at depth %d, length %d)\n",found->g,cycle_length);
	  return sol_depth;
	}
	delete newState;
      } else {
	ht.insert(newState); memory++;
	rval = Dfs2(newState);
	if (rval != -1) return rval;
      }
    }
    
/* #ifdef VERI */
/*     if(Selected_Goal==LTL && !(accpstate[VERI][((P0 *)hsf_pptr(state->ps,0))->_p])){ */
/*       printf("Error! Are you checking for a non response property???\n"); */
/*       exit(0); */
/*     } */
/*     if(Selected_Goal==LTL && accpstate[VERI][((P0 *)hsf_pptr(state->ps,0))->_p]){ // Never claim in accepting state? */
/*       if(DEBUG_RESPONSE) printf("\tAccepting state found at depth %d (claim in state %d) in postorder by 2nd search\n",state->g,((P0 *)hsf_pptr(state->ps,0))->_p); */
/*       //ot->My_Goal->set_goal(state); */
/*       seed=state; */
/*       ot->My_Heuristic->set_goal_state(state); */
/*       ot->My_Heuristic->set_heuristic(Selected_Nested_Heuristic); */
/*       if(DEBUG_RESPONSE) printf("\tStarting 3rd nested search...\n"); */
/*       rval=AStar3(seed); */
/*       if(rval!=-1){ */
/* 	return rval; */
/*       } */
/*       else{ */
/* 	if(DEBUG_RESPONSE) printf("\tno cycle found by 2nd search.\n"); */
/* 	ot->My_Heuristic->unset_heuristic(); */
/* 	//ot->My_Goal->unset_goal(); */
/*       } */
/*     } */
/* #endif // */

    out_stack(state);
    return -1;
  }

  AStar3(State *state) {
    State *index;
    State *found;
    State *newState;
    StateItem* newStateList,*aux_item;
    int newindex;
    int hashval;                                 
    int f;
    PrioQueue *pq;

    pq=new PrioQueue(max,maxf);
    pq->init();
    
    pq->bestf = wg* state->g + wh * state->h;       // compute F value of initial state 
    pq->insert(state,pq->bestf);

    int maxi = pq->bestf;
    while (1) {    // expand until goal found or hash table full
      while ((!pq->open[pq->bestf]) && (pq->bestf != maxf)) {
	pq->bestf++;                            // find best node on open lists
	if (pq->bestf > maxi) {
	  //cout << maxi << ":" << expanded << endl;
	  maxi = pq->bestf;
	}
      }
      if (pq->bestf == maxf || pq->bestf==bound_depth) {
	//cout << "e:" << expanded << endl;
	//delete newState; ???
	return -1;
      }
      index = pq->open[pq->bestf]->the_state;  // new best state on open list
      flag(index);
      f=pq->bestf;

      newStateList = ot->expand(index); expanded++;
      while(newStateList){
	newState=newStateList->the_state;
	aux_item=newStateList;
	newStateList=newStateList->next;
	delete aux_item;
	generated++;                                  // count nodes generated 

	if (!heuristic) newState->h = 0;
	found = ht.search(*(newState->ps)); // target loc.
	if(!found){
	  printf("\tError! Found new state in 3nd Search!\n");
	  exit(0);
	}
	newState->cycle_pred=found->cycle_pred=index;
	if(found==seed || is_on_stack(found)){
	  depthfound=found->g;
	  sol_depth=0;
	  build_rek_path(found,sol_depth,sol_move);
	  cycle_length=0;
	  for(aux_state=newState; aux_state!=seed; aux_state=aux_state->cycle_pred){
	    cycle_length++;
	  }
	  for(aux_state; aux_state!=found; aux_state=aux_state->pred){
	    cycle_length++;
	  }
	  sol_depth+=cycle_length;
	  f=sol_depth;
	  printf("\tacceptance cycle (at depth %d (seed at %d), length %d)\n",found->g,seed->g,cycle_length);
	  for(aux_state=newState; aux_state!=seed; aux_state=aux_state->cycle_pred){
	    sol_ind[f--]=aux_state;
	  }
	  for(aux_state; aux_state!=found; aux_state=aux_state->pred){
	    sol_ind[f--]=aux_state;
	  }
	  return sol_depth;
	}
	if(flagged(found)){
	  delete newState;
	  continue;
	}
	pq->insert(found,wg * newState->g + wh * newState->h); // insert into open list
	delete newState;
      }
      pq->close(index,f);                     // move best state to closed list
    }
    delete pq;
  }

  void on_stack(State *S){ /* Marks state as on stack of the 1st search */
    S->move.o_tt|=1;  /* Warning: using a field with other use*/
  }

  void out_stack(State *S){ /* Marks state as not on stack of the 1st search */
    S->move.o_tt&=~1; /* Warning: using a field with other use*/
  }

  int is_on_stack(State *S){ /* Is the state in the 1st stack? */
    return S->move.o_tt&1; /* Warning: using a field with other use*/
  }

  void flag(State *S){ /* Marks state as visited in the 2nd search */
    S->move.o_tt|=2;  /* Warning: using a field with other use*/
  }

  void unflag(State *S){ /* Marks state as not visited in the 2nd search */
    S->move.o_tt&=~2; /* Warning: using a field with other use*/
  }

  int flagged(State *S){ /* Has been visited in the 2nd search? */
    return S->move.o_tt&2; /* Warning: using a field with other use*/
  }

  reorder(StateItem *list){
    StateItem **aux_table;
    StateItem *current_item;
    int i;

    /* Init table */
    aux_table=new StateItem*[maxf+1];
    for(i=0; i<=maxf; i++) aux_table[i]=(StateItem*)0;

    /* Move from list to table in linear time*/
    while(list){
      current_item=list;
      list=current_item->next;
      current_item->next=aux_table[current_item->the_state->h];
      aux_table[current_item->the_state->h]=current_item;
    }
    
    /* Move from table to list in linear time */
    list=(StateItem*)0; //it should be already so
    for(i=0; i<=maxf; i++){
      while(aux_table[i]){
	current_item=aux_table[i];
	aux_table[i]=current_item->next;
	current_item->next=list;
	list=current_item;
      }
    }
    delete aux_table;
  }

  print_name() { cout << "Response AStar + Dfs";}

};

#endif //
