types.h

RoboCup仿真组世界冠军源代码

	OrderedList():head(NULL){}
	~OrderedList();
	virtual bool enqueue(Data& d);
	void cleanup();
	void Rewind(){ pcurrent = head;}
	bool IsEmpty(){return head == NULL;}
	bool IsTail(ListNode<Data> *p){ return p->next == NULL;}
	bool IsTail(){ return pcurrent->next == NULL;}
	bool IsEnd(){ return pcurrent == NULL;}
	bool IsHead(){ return pcurrent == head;}
	ListNode<Data> * Head(){ return head;}
	Data& NextElement(ListNode<Data>*& p);
	Data& NextElement(){ return NextElement(pcurrent);}
	Data& RetrElement(ListNode<Data>*& p);
	Data& RetrElement(){ return RetrElement(pcurrent);}
	void GotoNext(ListNode<Data>*& p);
};

template <class Data> OrderedList<Data>::~OrderedList(){
	cleanup();
}

template <class Data> bool OrderedList<Data>::enqueue(Data& d){
	ListNode<Data> superhead, *p = &superhead, *tmp;
	superhead.next = head;
	while(p->next){
		if (d > p->next->data){
			break;
		}
		p = p->next;
	}

	tmp = p->next;
	p->next = new ListNode<Data>(d);
	p->next->next = tmp;

	head = superhead.next;
	return true;
}

template <class Data> void OrderedList<Data>::cleanup(){
	ListNode<Data> *p = head, *tmp;
	while(p){
		tmp = p->next;
		delete p;
		p = tmp;
	}
	head = NULL;
}

template <class Data> Data& OrderedList<Data>::NextElement(ListNode<Data>*& p){
	GotoNext(p);
	return p->data;
}

template <class Data> Data& OrderedList<Data>::RetrElement(ListNode<Data>*& p){
	ListNode<Data>* tp = p;

	GotoNext(p);
	return tp->data;
}

template <class Data> void OrderedList<Data>::GotoNext(ListNode<Data>*& p){
	if (IsEmpty())
		return;
	if (IsTail(p)){
		p = head;		
	}
	else{
		p = p->next;
	}
}

template <class Data> class CounterOrderedList : public OrderedList<Data>{
public:
	bool enqueue(Data& d);
};

template <class Data> bool CounterOrderedList<Data>::enqueue(Data& d){
	ListNode<Data> superhead, *p = &superhead, *tmp;
	superhead.next = head;
	while(p->next){
		if (d < p->next->data){
			break;
		}
		p = p->next;
	}

	tmp = p->next;
	p->next = new ListNode<Data>(d);
	p->next->next = tmp;

	head = superhead.next;
	return true;
}


template <class T> class OptimalA;
template <class T> class OAlist;
template <class T> class OAnode{
	friend class OptimalA<T>;
	friend class OAlist<T>;
	friend class T;
public:
	OAnode():waypre(NULL){}
	OAnode(T item):waypre(NULL){data = item;}
	OAnode(T item, OAnode* wayprevious, float value){
		data = item; waypre = wayprevious; hvalue = value;}

	inline T GetData(){return data;}
	inline OAnode* Getwaypre(){return waypre;}
	inline void SetData(T item){data = item;}
	inline void Setwaypre(OAnode* p){waypre = p;}
	inline float GetValue(){return hvalue+cost;}
	inline void Sethvalue(float value){hvalue = value;}
	inline void Setcost(float value){cost = value;}
	inline float Gethvalue(){return hvalue;}
	inline float Getcost(){return cost;}
	
	T data;
	float hvalue,cost;
	OAnode* waypre;
private:
};

template <class T> class OAlist : public OrderedList<OAnode<T>*>{
	friend class OptimalA<T>;
private:
	int tmp;
public:
	bool enqueue(OAnode<T>*& d){
		ListNode<OAnode<T>*> superhead, *p = &superhead, *tmp;
		superhead.next = head;
		while(p->next){
			if (d->GetValue() > p->next->data->GetValue()){
				break;
			}
			p = p->next;
		}

		tmp = p->next;
		p->next = new ListNode<OAnode<T>*>(d);
		p->next->next = tmp;

		head = superhead.next;
		return true;
	}

	OAnode<T>* FindNode(T data){
		Rewind();
		if(pcurrent == NULL) return NULL;
		if(pcurrent->data->data == data){
			return pcurrent->data;	
		}
		while(!IsTail()){
			if(NextElement()->data == data){
				return pcurrent->data;
			}
		}
		return NULL;
	}

	OAnode<T>* FindNode(OAnode<T>* data){
		Rewind();
		if(pcurrent == NULL) return NULL;
		if(pcurrent->data == data){
			return pcurrent->data;
		}

		while(!IsTail()){
			if(NextElement() == data){
				return pcurrent->data;
			}
		}
		return NULL;
	}

	ListNode<OAnode<T>*>* RmNode(OAnode<T>* data){
		Rewind();
		ListNode<OAnode<T>*>* phead;		
		if(pcurrent == NULL) return NULL;
		if(pcurrent->data == data){
			head = pcurrent->next;
			return pcurrent;
		}
		while(!IsTail()){
			phead = pcurrent;
			if(NextElement() == data){
				if(IsTail()) phead->next = NULL;
				else phead->next = pcurrent->next;
				return pcurrent;
			}
		}
		return NULL;
	}
	void cleanup(){
		ListNode<OAnode<T>*> *p = head, *tmp;
		while(p){
			tmp = p->next;
			delete p->data;
			delete p;
			p = tmp;
		}
		head = NULL;
	}
};

template <class T> class OptimalA{
protected:
	OAlist<T> openlist,closelist;
	OAnode<T>* curnode;
	int maxscounts,scounts;
private:
	bool SelectCurnode();
public:
	OptimalA():curnode(NULL){maxscounts = 100;};
	void Reset(){openlist.cleanup(); closelist.cleanup(); curnode = NULL;}
	void SetMaxScounts(int value){maxscounts = value;}
	virtual void SetInitial(T data, float hvalue, float cost=0){
		Reset();
		curnode = new OAnode<T>(data);
		curnode->Sethvalue(hvalue);
		curnode->Setcost(cost);
		closelist.enqueue(curnode);
	}

	virtual float Hestimate(T data){return 0;}
	virtual void Extendcurnode(){};
	virtual bool IsTargetState(){return false;}

	bool Findoptimalway(){
		if(curnode==NULL) return false;
		scounts = 0;
		while(scounts++ < maxscounts){
			Extendcurnode();
			if(!SelectCurnode() || curnode == NULL) return false;
			if(IsTargetState()) return true;
		}
		return false;
	}
};

template <class T> bool OptimalA<T>::SelectCurnode(){ 
	if(openlist.IsEmpty())	return false;
	curnode = openlist.Head()->data;
	openlist.RmNode(curnode);
	closelist.enqueue(curnode);
	return true;
}

template<class Data> class DoubleLinked_Soft_ListNode{
public:
	DoubleLinked_Soft_ListNode(){ next = -1; prev = -1;}
	int next;
	int prev;
	Data data;
};

template<class Data, int size> class DoubleLinked_Soft_List{
protected:
	DoubleLinked_Soft_ListNode<Data> Nodes[size + 1];
	int num_nodes;
	int head, tail;
public:
	DoubleLinked_Soft_List(){
		head = size;
		tail = size;
		num_nodes = 0;
	}

	bool Insert(int p, int insert_node){
#ifdef _DEBUG_MOD
		if (!IsValid(p) || !IsValid(insert_node) || p == insert_node)
			return false;
		if (Nodes[p].prev == -1 && p != head)
			return false;
#endif
		if (p == tail){
			tail = insert_node;
			Nodes[p].next = insert_node;
			Nodes[insert_node].prev = p;
			Nodes[insert_node].next = -1;
		}
		else{
			Nodes[Nodes[p].next].prev = insert_node;
			Nodes[insert_node].next = Nodes[p].next;
			Nodes[insert_node].prev = p;
			Nodes[p].next = insert_node;
		}
		num_nodes ++;
		return true;
	}

	bool Delete(int p){
#ifdef _DEBUG_MOD
		if (!IsValid(p)) return false;
		if (Nodes[p].prev == -1) return false;
#endif
		if (p == tail){
			tail = Nodes[p].prev;
			Nodes[tail].next = -1;
		}
		else{
			Nodes[Nodes[p].prev].next = Nodes[p].next;
			Nodes[Nodes[p].next].prev = Nodes[p].prev;
			Nodes[p].next = Nodes[p].prev = -1;
		}
		num_nodes --;
		return true;
	}

	int Prev(int p){
#ifdef _DEBUG_MOD
		if (p < 0 || p > size)
			return -1;
#endif
		return Nodes[p].prev;
	}

	int Next(int p){
#ifdef _DEBUG_MOD
		if (p < 0 || p > size)
			return -1;
#endif
		return Nodes[p].next;
	}

	int Head(){
		return head;
	}

	int ActualHead(){
		return Nodes[head].next;
	}

	int Tail(){
		return tail;
	}

	int CircularNext(int p){
#ifdef _DEBUG_MOD
		if (p < 0 || p > size )
			return -1;
#endif
		if (IsEmpty()) return -1;
		if(p == tail)
			return Nodes[head].next;
		return Nodes[p].next;
	}

	int CircularPrev(int p){
#ifdef _DEBUG_MOD
		if (p < 0 || p > size )
			return -1;
#endif
		if (IsEmpty() || p == head) return -1;
		if (Nodes[p].prev == head)
			return tail;
		return Nodes[p].prev;
	}

	bool IsHead(int p){
		return head == p;
	}

	bool IsTail(int p){
		return tail == p;
	}

	bool IsValid(int p){
		return (p >= 0 && p <= size);
	}

	virtual void cleanup(){
		Nodes[head].next = -1;
		num_nodes = 0;
		tail = head;
	}

	bool SetData(const Data& data, int p){
#ifdef _DEBUG_MOD
		if (p < 0 || p >= size)
			return false;
#endif
		Nodes[p].data = data;
	}

	int AddData(const Data& data, int num_data){
		return SetData(data, num_data) ? num_data : num_data + 1;
	}

	int ListSize(){
		return num_nodes;
	}

	int IsEmpty(){
		return Nodes[head].next == -1;
	}

	DoubleLinked_Soft_ListNode<Data>& GetHead(){
		return Nodes[head];
	}

	DoubleLinked_Soft_ListNode<Data>& GetElement(int p){
#ifdef _DEBUG_MOD
		if (p < 0 || p >= size)
			return Nodes[head];
#endif
		return Nodes[p];
	}

	Data& GetData(int p){
#ifdef _DEBUG_MOD
		if (p < 0 || p >= size)
			return Nodes[head].data;
#endif
		return Nodes[p].data;
	}
};

template<class Data, int size> class Ordered_Soft_Queue : public DoubleLinked_Soft_List<Data, size>{
private:
	int num_datas;
public:
	Ordered_Soft_Queue(){ num_datas = 0;}
	int NumDatas(){ return num_datas;}
	void cleanup(){
		num_datas = 0;
		DoubleLinked_Soft_List<Data, size>::cleanup();
	}

	bool enqueue(int p){
#ifdef _DEBUG_MOD
		if (p < 0 || p >= size) return false;
#endif
		int q = head;
		while(IsValid(Nodes[q].next)){
			if (Nodes[p].data > Nodes[Nodes[q].next].data)
				break;
			q = Nodes[q].next;
		}
		return Insert(q, p);
	}

	bool enqueue(const Data& data){
#ifdef _DEBUG_MOD
		if(num_datas >= size || num_datas < 0)
			return false;
#endif
		Nodes[num_datas].data = data;
		return enqueue(num_datas ++);
	}
};
#endif