// ..
// ..

#ifndef __BITSTATE_ASTAR_H__
#define __BITSTATE_ASTAR_H__

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

//#define DEBUG 1

#include "Search.h"
#include "BitStateHashTable.h"
#include "PrioQueue.h"
#ifdef DEBUG_HASHING
#include </home/proto/hspin/Include/universal_hashing_class.h>
#include "HashTable.h"
#endif //

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

public:
  BitStateHashTable ht;
#ifdef DEBUG_HASHING
  HashTable debug_ht;
  int debug_memory,debug_generated,debug_expanded,debug_reopened,debug_atomic;
  Hash_Function *debug_hash;
  int debug_hashval;
#endif //
  PrioQueue pq;

  BitStateAStar(Automaton* aT,int max,int maxf,int maxmove, 
	       int applicability,int heuristic,int wg,int wh) : 
    Search<Automaton>(aT,max,maxf,maxmove,applicability,heuristic,wg,wh), 
    ht(max), pq(max,maxf)
#ifdef DEBUG_HASHING
    ,debug_ht(max)
#endif //
    { }

  search(int bound){
    int r;

#ifdef DEBUG_HASHING
    State *start_state;
    debug_ht.init();
    debug_memory= debug_generated= debug_expanded= debug_reopened= debug_atomic= 0;
    debug_hash=new Hash_Function(HOLZMANN_NEW,1);
    debug_hash->rand();
    debug_hashval=debug_hash->hash((unsigned char*)(S.ps),S.ps->_vsz)%max;
    start_state=new State;
    *start_state=S;
    debug_ht.insert(start_state,debug_hashval);
#endif //

    for(r=0; r<Supertraces; r++){
      //printf("RUN %d\n",r+1);
      ht.init(); pq.init();
      sol_depth=supertrace_search(bound);
      if(sol_depth!=-1){
	printf("Solution found at depth %d\n",sol_depth);
	break;
      }
      if(r==Supertraces) break;
      this->statistics();
      //this->vinit(this->ot);
#ifdef DEBUG_HASHING
      debug_generated+=generated; debug_expanded+=expanded; debug_reopened+=reopened;
      debug_atomic+=ot->atomic_transitions;
#endif //
      sol_depth = expanded = generated = pruned = reopened = total = hash = 0;
      ot->atomic_transitions=0;
      the_hash_function->rand();
    }
#ifdef DEBUG_HASHING
    memory=debug_memory; generated=debug_generated; expanded=debug_expanded;
    reopened+=debug_reopened; ot->atomic_transitions=debug_atomic;
    printf("Debug Statistics of Supertrace\n");
    this->statistics();
#endif //
  }

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

    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 (index->h == 0) {
	if (ot->goal(index)) {          
	  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
#ifdef DEBUG_HASHING
	  debug_hashval=debug_hash->hash((unsigned char*)(newState->ps),newState->ps->_vsz)%max;
	  found = debug_ht.search(*(newState->ps),debug_hashval);
	  if(!found){
	    found=new State;
	    *found=*newState;
	    found->compress();
	    f = wg * found->g + wh * found->h;
	    debug_ht.insert(found, debug_hashval); debug_memory++;
	  }
#endif //
	}
	else {
	  if (found->g > newState->g) {    
	    f = wg * found->g + wh * found->h; 
	    pq.close(found,f);                  // remove node from open
	    delete found;
	    found=newState;
	    found->bitstate_compress(); // state in closed liste can be bitstated
	    f = wg * found->g + wh * found->h; 
	    pq.insert(found,f);                 // insert into open list 
	    ht.insert(found); memory++;           // insert into hash table
	    reopened++;         // keep track of how many times this happens
	  } else {
	    delete newState;
	  }
	}
      }
      f = wg * index->g + wh * index->h;     // compute f value 
      pq.close(index,f);                     // move best state to closed list
      index->bitstate_compress(); // state in closed liste can be bitstated
    }
   }

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

};

#endif //


