#ifndef __LtlDfsAStar_H__
#define __LtlDfsAStar_H__

#define DEBUG_NASTAR 0

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

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

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

public:
  
  LtlDfsAStar (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 = new HashTable(max);	
  }

  search(int bound) {
    bound_depth=bound;
    total = memory = 0;
    ht->init();
    
    expanded=sol_depth=0;
    if (!heuristic) S.h = 0;
    ht->insert(&S); memory++;
    return Dfs1(&S);
  }


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

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

    if(state->g==bound_depth) 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); 
	return newState->g;
      }
      
      // cout << "search in hash table" << endl;
      found = ht->search(*(newState->ps)); // target loc.
       
      if (found) {
	delete newState;
      } else {
	ht->insert(newState); memory++;
	rval = Dfs1(newState);
	if (rval != -1) return rval;
      }
    }
    
#ifdef VERI
    if(Selected_Goal==LTL && accpstate[VERI][((P0 *)hsf_pptr(state->ps,0))->_p]){ // Never claim in accepting state?
      if(DEBUG_NASTAR) printf("Accepting state found at depth %d (claim in state %d)\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_NASTAR) printf("\tStarting nested search...\n");
      //expanded=generated=0;
      rval=AStar2(seed);
      if(rval!=-1){
	return rval;
      }
      else{
	if(DEBUG_NASTAR) printf("\tno cycle found.\n");
	ot->My_Heuristic->unset_heuristic();
	//ot->My_Goal->unset_goal();
      }
    }
#endif //
    out_stack(state);
    return -1;
  }

  AStar2(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 2nd Dfs!\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 << "LTL AStar nested on Dfs"; }
};


#endif //
