// ..
// ..

#ifndef __LIVENESS_ASTAR_H__
#define __LIVENESS_ASTAR_H__

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

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

public:
  HashTable ht;
  PrioQueue pq;
  int hash_size;
  int maxf;
  int bound_depth;

  LivenessAStar(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;
      hash_size=max;
    }

  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;
	  pq.insert(found,f);           // insert into open list
	  ht.insert(found); memory++;     // insert into hash list
	}
	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;
	}
      }
#ifdef VERI
      //if(index->move.o_pm&2){ //does not work. 
      if(accpstate[VERI][((P0 *)hsf_pptr(index->ps,0))->_p] && index->g>26){ // Never claim in accepting state?
	printf("Accepting state found at depth %d (claim in state %d)\n",index->g,((P0 *)hsf_pptr(index->ps,0))->_p);
	ot->My_Goal->set_goal(index);
	ot->My_Heuristic->set_goal_state(index);
	ot->My_Heuristic->set_heuristic(Selected_Nested_Heuristic);
	printf("\tStarting nested search...\n");
	//printf("Before...\n"); scanf("%d",&f);
	//expanded=0; generated=0; memory=0;
	if(AStar2(index)!=-1){
	  return index->g;
	}
	else{
	  printf("\tno cycle.\n");
	  //this->statistics();
	  ot->My_Heuristic->unset_heuristic();
	  ot->My_Goal->unset_goal();
	}
	
      }
#endif //
      f = wg * index->g + wh * index->h;     // compute f value
      pq.close(index,f);                     // move best state to closed list
    }
  }

  AStar2(State *seed) {
    State *index;
    State *found;
    State *newState;
    StateItem* newStateList,*aux_item;
    int newindex;
    int hashval;                                 
    int f;
    PrioQueue *pq2;
    HashTable *ht2;
    int cycle_length;

    pq2=new PrioQueue(hash_size,maxf);
    pq2->init();
    ht2=new HashTable(hash_size);
    ht2->init();
    
    newState=new State;
    *newState->ps=*seed->ps;
    newState->g=0; newState->h=0; newState->pred=(State *)0;
    pq2->bestf = wg* newState->g + wh *newState->h;       // compute F value of initial state 
    pq2->insert(newState,pq2->bestf);
    ht2->insert(newState); memory++;
    int maxi = pq2->bestf;
    while (1) {    // expand until goal found or hash table full
      while ((!pq2->open[pq2->bestf]) && (pq2->bestf != maxf)) {
	pq2->bestf++;                            // find best node on open lists
	if (pq2->bestf > maxi) {
	  //cout << maxi << ":" << expanded << endl;
	  maxi = pq2->bestf;
	}
      }
      if (pq2->bestf == maxf || pq2->bestf==bound_depth) {
	//cout << "e:" << expanded << endl;
	//delete newState; ???
	if(pq2->bestf==bound_depth)
	  printf("\tBound reached\n");
	else
	  printf("\tmaxf reached\n");
	delete pq2; delete ht2;
	return -1;
      }
      index = pq2->open[pq2->bestf]->the_state;  // new best state on open list
      f=pq2->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 = ht2->search(*(newState->ps)); // target loc.
	if(!found){
	  ht2->insert(newState); //memory++;
	  pq2->insert(newState,wg * newState->g + wh * newState->h); // insert into open list
	} else{
	  //printf("Found with depth %d\n",found->g);
	  if(found->g==0){
	    depthfound=seed->g;
	    sol_depth=0;
	    cycle_length=newState->g;
	    delete newState;
	    for(newState=newState; newState!=found; newState=newState->pred){
	      sol_ind[seed->g+newState->g]=newState; sol_depth++;
	    }
	    for(newState=seed; newState->g!=0; newState=newState->pred){
	      sol_ind[newState->g]=newState; sol_depth++;
	    }
	    sol_ind[newState->g]=newState;
	    printf("\tacceptance cycle (at depth %d, length %d)\n",seed->g,cycle_length);
	    return sol_depth;
	  }
	  delete newState;
	}
      }
      pq2->close(index,f);                     // move best state to closed list
    }
    delete pq2; delete ht2;
  }

  print_name() { cout << "LivenessA* with Dynamic State Allocation"; }

};

#endif //
