list.h

2002年

#ifndef __LIST_H__
#define __LIST_H__


#ifndef NULL
#define NULL 0
#endif
/*************	Ordered List	**********************/
template <class Data> class ListNode{
public:
	ListNode():next(NULL){}
	ListNode(Data d):next(NULL){data = d;}
	Data data;
	ListNode* next;
};

template <class Data> class List{
protected:
	ListNode<Data> * head, *pcurrent;
public:
	List():head(NULL), pcurrent(NULL){}
	~List(){
		cleanup();
	}
	virtual bool enqueue(Data& d){
		ListNode<Data> superhead, *p = &superhead, *tmp;
		superhead.next = head;
		
		tmp = p->next;
		p->next = new ListNode<Data>(d);
		p->next->next = tmp;

		head = superhead.next;
		return true;
	}
	virtual void cleanup(){
		ListNode<Data> *p = head, *tmp;
		while(p){
			tmp = p->next;
			delete p;
			p = tmp;
		}
		head = NULL;
	}
	void Rewind(){ pcurrent = head;}

	bool IsEmpty(){return head == NULL;}
	inline bool IsTail(ListNode<Data> *p){ return p->next == NULL;}
	inline bool IsTail(){ return IsTail(pcurrent);}
	bool IsEnd(){ return pcurrent == NULL;}
	bool IsHead(){ return pcurrent == head;}
	
	ListNode<Data> * Head(){ return head;}
	void GotoNext(ListNode<Data>*& p){
		if(p != NULL)
			p= p->next ;
	}

	Data& NextElement(ListNode<Data>*& p){//取下一元素值
		GotoNext(p);
		return p->data;
	}
	Data& NextElement(){ return NextElement(pcurrent);}
	Data& RetrElement(ListNode<Data>*& p){//取当前元素值,并将指针后移
		ListNode<Data>* tp = p;
		
		GotoNext(p);
		return tp->data;
	}
	Data& RetrElement(){ return RetrElement(pcurrent);}	
};

/*Note: Maximum cell is on the top*/
template <class Data> class OrderedList : public List<Data>{
public:
	bool enqueue(Data& d){
		ListNode<Data> superhead, *p = &superhead, *tmp;
		superhead.next = head;
		while(p->next){
			if (d < p->next->data){
				p = p->next;
			}else{
				break;
			}
		}

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

		head = superhead.next;
		return true;
	}
};

/* Pointer List (special list used in class SceneManager
 *	Inherit class should overload operator > as this form
 *		operator <(class* p)
*/
template <class Data> class OrderedPointList : public List<Data>{
public:
	bool enqueue(Data& d){
		ListNode<Data> superhead, *p = &superhead, *tmp;
		superhead.next = head;
		while(p->next){
			if ((*d) < p->next->data){
				p = p->next;
			}else{
				break;
			}
		}

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

		head = superhead.next;
		return true;
	}
};

template <class Data> class CounterOrderedList : public OrderedList<Data>{
public:
	bool 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;
	}
};

/*	Soft List */
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;		//num of data
	int head, tail;
public:
	DoubleLinked_Soft_List(){
		head = size;
		tail = size;
		num_nodes = 0;
	}
	int NumDatas(){return num_nodes;}

	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;
	}

/*In dynamic method, data may be reordered which means the index you got may become invalid.
 *In non-dynamic method, data's index are kept, but you can't add data more unless cleanup.
 * 
 * A patch added by yjy.
 */
	bool Delete(int p, bool dynamic = false){
#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;
			if(dynamic){
			/*move data in last node to p in order to 
			 * make sure the Node[num_nodes] is empty
			*/
				int lastnode = num_nodes - 1;
				if(p != lastnode){
					Nodes[p] = Nodes[lastnode];
					Nodes[Nodes[lastnode].prev].next = p;
					if(lastnode == tail) tail = p;
				}
				Nodes[lastnode].next = Nodes[lastnode].prev = -1;
			}else{
				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 ListSize(){
		return size;
	}

	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:
public:
	Ordered_Soft_Queue(){}
	void cleanup(){
		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_nodes >= size || num_nodes < 0)
			return false;
#endif
		Nodes[num_nodes].data = data;
		return enqueue(num_nodes);
	}

	int GetLastNode(){return num_nodes-1;}

	int lnearest(const Data& data){
		int q = head;
		while(IsValid(Nodes[q].next)){
			if (data > Nodes[Nodes[q].next].data)
				break;
			q = Nodes[q].next;
		}
		return q;
	}
};

/***********************双向链表******************************/
template <class Data> class BiListNode{
public:
	BiListNode():next(NULL), prev(NULL){}
	BiListNode(Data d):next(NULL), prev(NULL){data = d;}
	Data data;
	BiListNode* next;
	BiListNode* prev;
};

template <class Data> class BiList{
protected:
	BiListNode<Data> *head, *pcurrent;
public:
	BiList():head(NULL), pcurrent(NULL){}
	~BiList(){
		cleanup();
	}

	BiListNode<Data> * Head(){ return head;}
	void Rewind(){ pcurrent = head;}
	void Next(){
		pcurrent = pcurrent->next;
	}
	bool IsEmpty(){return head == NULL;}
	bool IsEnd(){ return pcurrent == NULL;}
	bool IsHead(){ return pcurrent == head;}
	bool IsTail(){ return bool(pcurrent->next == NULL);}
	Data& GetData(){ return pcurrent->data;}

	//delete current node, and set pcurrent to its next.
	void Remove(){
		if(pcurrent == NULL) return;

		if(pcurrent == head){
			head = head->next;
			delete pcurrent;
			pcurrent = head;
			if(head != NULL)
				head->prev = NULL;
		}else{
			BiListNode<Data> *tmp = pcurrent->next;
			pcurrent->prev->next = tmp;
			if(tmp != NULL)
				tmp->prev = pcurrent->prev;
			delete pcurrent;
			pcurrent = tmp;
		}
	}
	//insert data after pcurrent, and set pcurrent point to it.
	virtual void Insert(const Data& d){
		BiListNode<Data> *node = new BiListNode<Data>(d);
		if(IsEmpty()){
			node->prev = NULL;
			node->next = NULL;
			head = node;
		}else{
			if(pcurrent == NULL)
				pcurrent = head;

			BiListNode<Data> *tmp = pcurrent->next;
			pcurrent->next = node;
			node->prev = pcurrent;
			node->next = tmp;
			if(tmp != NULL)
				tmp->prev = node;
		}
		pcurrent = node;
	}

	virtual void cleanup(){
		BiListNode<Data> *p = head, *tmp;
		while(p){
			tmp = p->next;
			delete p;
			p = tmp;
		}
		head = NULL;
	}
};

template <class Data> class OrderedBiList : public BiList<Data>{
	void Insert(const Data& d){
		BiListNode<Data> *node = new BiListNode<Data>(d);

		BiListNode<Data> superhead, *p = &superhead, *tmp;
		superhead.next = head;
		while(p->next){
			if (d < p->next->data){
				p = p->next;
			}else{
				break;
			}
		}

		node->prev = p;
		node->next = p->next;
		if(node->next != NULL){
			node->next->prev = node;
		}
		p->next = node;

		head = superhead.next;
		head->prev = NULL;
		return true;
	}
};

#endif //__LIST_H__