#include "searcher.h"

#ifndef _BDFS_H_
#define _BDFS_H_

class BDFS: public searcher{
private:
	int maxstep;
public:
	virtual CString getIntroduction();
	virtual int search(int begin, int end, int &stop, int val = 0);
	virtual CString getResult();
};



class HASH_BDFS{
private:
	struct Node{
		int data;
		int index;
		int step;
		struct Node *next;
	};
	const static int MAXSIZE= 70001, ALL = 182000;	
	int ID;
	struct Node *hash[MAXSIZE], node[ALL];
public:
	void reset(){
		memset(hash, 0, sizeof(hash) );
		ID = 0;
	}
	int add(const int &m_data, const int &m_index, const int &step){
		int mod = (m_data << 1) % MAXSIZE;
		for(struct Node * p = hash[mod]; p; p = p->next){
			if(m_data == p->data){
				if(step < p->step){
					p->step = step;
					return p->index;
				}else
					return -1;
			}
		}
		if(ID >= ALL) return -1;		
		node[ID].data = m_data;		
		node[ID].index = m_index;
		node[ID].step = step;
		node[ID].next = hash[mod];
		hash[mod] = &node[ID];
		++ID;
		return 0;
	}
};

#endif