// ..
// ..

#ifndef __PROVAT_SEARCH_H__
#define __PROVAT_SEARCH_H__

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

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

public:
  HashTable ht;
  PrioQueue pq;
  int sb,tb; // state-base, transition-based

  ProvatSearch(Automaton* aT,int max,int maxf,int maxmove, 
	       int applicability,int heuristic,int wg,int wh,int _sb, int _tb) : 
    Search<Automaton>(aT,max,maxf,maxmove,applicability,heuristic,wg,wh), 
    ht(max), pq(max,maxf) {
    sb=_sb; tb=_sb;
    if(!sb) wh=0;
  }

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

    ht.init(); pq.init();
    
    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
      flag = 0;
      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 = 0;

      if(!partially_expanded(index))
	if (ot->goal(index)) { // check if goal found
	  //sol_depth=index->g;
	  build_rek_path(index,sol_depth,sol_move); // sol_depth--;
	  return index->g;
	}

      if(!tb)
	newStateList = ot->expand(index);
      else
	newStateList = ot->partially_expand(index);
      if(!partially_expanded(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) {
	    if(!partially_expanded(found)){
	      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;
	}
      }
      if(!partially_expanded(index)){
	f = wg * index->g + wh * index->h;     // compute f value
	pq.close(index,f);                     // move best state to closed list
      }
    }
  }

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

};

#endif //


