tlink.h

可能是能找到的处理速度最快

#ifndef TLINK_H_
#define TLINK_H_

#include<assert.h>
#include<stdio.h>
template<class T> class CLink;

template<class T> class CLinkNode
{
	T *data;
	CLinkNode<T> *next;
	int Own;
public:
	T &Data()	{	return *data;	}
	CLinkNode(int O,T *InitData=NULL,CLinkNode<T> *p=NULL):
	data(InitData),		next(p),	Own(O)	{	}

	CLinkNode(T &InitData,CLinkNode<T> *p=NULL):
					next(p),Own(1)
	{	data=new T(InitData);	}
	~CLinkNode()
	{
		if (Own&&data)
			delete data;
	}
	friend class CLink<T>;
};

template<class T> class CLink
{
	CLinkNode<T> *head;
	CLinkNode<T> *tail;
	CLinkNode<T> *CurrentNode;
	CLinkNode<T> *LoopMark;
	unsigned long count;
//	int Sort;
	int SortByData;
	int Increase;
	int NoDuplicate;
	int Own;
	CLinkNode<T> *Exist(CLinkNode<T> *t);
	CLinkNode<T> *Locate(T *t);
	CLinkNode<T> *Locate(T &t);
public:
	unsigned long Count()	{	return count;	}	// get the count of nodes

	CLinkNode<T> *Current()	{	return CurrentNode;	}	// get the current pointer 

	void Current(CLinkNode<T> *t)	{	CurrentNode=Exist(t);	}	// set the current pointer

	void Current(T *t)	{	CurrentNode=Locate(t);	}

	void Current(T &t)	{	CurrentNode=Locate(t);	}

	T *Push(T *item)	{	return Add(item);	}	// add a builded object to top

	T *Push(T &item)	{	return Add(item);	}	// build a new object and add  to top

	T *Pop()		// get the top object and delete it from the link, the object must be destroy by the other 
	{					// object
		T *t=head->data;
		Head();
		Delete();
		return t;
	}

	CLinkNode<T> *GotoNextOf(CLinkNode<T> *from)		// move current pointer to next node of this node
	{
		if ((!from)||(!Exist(from)))
		{
			if (CurrentNode)
				from=CurrentNode;
			else
				return NULL;				
		}
		CurrentNode=from->next;
		return CurrentNode;
	}

	CLinkNode<T> *Next()		// move current pointer to next node
	{
		if (CurrentNode)
		{
			CurrentNode=CurrentNode->next;
			return CurrentNode;
		}
		else
			return NULL;
	}
	CLinkNode<T> *NextIs()
	{
		if (CurrentNode)
			return CurrentNode->next;
		else
			return NULL;
	}
	T *GetData()				// get current data(object)
	{
		if (CurrentNode)
			return CurrentNode->data;
		else
			return NULL;
	}

	CLinkNode<T> *Head()					// move current pointer to begining of link
	{
		CurrentNode=head;
		return CurrentNode;
	}

	CLinkNode<T> *NewLoop()		// mark the current location as the border location of loop
	{
		if (CurrentNode)
			return (LoopMark=CurrentNode);
		else
		{
			CurrentNode=head;
			return (LoopMark=head);
		}
	}

	CLinkNode<T> *LoopNext()
	{
		if (CurrentNode->next)
			CurrentNode=CurrentNode->next;
		else
			CurrentNode=head;
		if (CurrentNode==LoopMark)	// when return to loop mark, a loop terminal
			return NULL;				// this function report terminal only one time, the next call will start another loop
	}

	CLinkNode<T> *Tail()		// move current pointer to end of link
	{
		if (!tail)			// the first time call this funtion , this section should be excuted
		{			
			CLinkNode<T> *p1=head,*p2=NULL;
			while(p1)
			{
				p2=p1;
				p1=p1->next;
			}
			tail=p2;
		}
		CurrentNode=tail;
		return tail;
	}
	
	CLink(int O,bool NoDupl=false, bool sortbydata=true,bool SortIncrease=true)
	{
		head=NULL;
		tail=NULL;
		CurrentNode=NULL;
		Own=O;
		count=0;
		NoDuplicate=NoDupl;
		Increase=SortIncrease;
		SortByData=sortbydata;
	}

	~CLink()	{	ClearAll();	}

	void ClearAll();			// clear the link( reset all )
	void Delete();		// delete the current node
	T *Search(T &t);		// compare the data
	T *Search(T *t);		// compare pointer only
	T *Append(T *item);	// Add a item to the end; point to version
	T *Append(T &item);	// Add a item to the end; copy version
	T *Insert(T *item);	// Insert an item behide CurrentNode;
	T *Insert(T &item);	// Insert an item behide CurrentNode;
	T *Add(T *item);		// Add an item to the head;
	T *Add(T &item);		// Add an item to the head;
	T *SortAdd(T *item);	// point to version , sort by data
	T *SortAdd(T &item);	// copy version , sort by data
	int operator==(CLink<T> &right);	// compare to judge if is equal
	int operator^(CLink<T> &right);		// subtrate function for sort
	unsigned long operator&&(CLink<T> &right);	// return the count of the same section, compare only by the pointer
	friend CLink operator&(CLink &link1,CLink &link2);			// return the same section of them, compare only by the pointer
	CLink &operator=(CLink &link2);		
	CLink(CLink &link2);			// copy constructor , copy pointer only, the data will not be copy
	T *operator->()
	{
		if (CurrentNode)
			return CurrentNode->data;
		else
			return NULL;
	}
};

/*************************************
						Private use only
  ****************************************/
template<class T> CLinkNode<T> *CLink<T>::Locate(T *t)
{
	CLinkNode<T> *p=head;
	while(p)
	{
		if (p->data==t)
			return p;
		p=p->next;
	}
	return NULL;
}

/*************************************
						Private use only
  ****************************************/
template<class T> CLinkNode<T> *CLink<T>::Locate(T &t)
{
	CLinkNode<T> *p=head;
	while(p)
	{
		if (*(p->data)==t)
			return p;
		p=p->next;
	}
	return NULL;
}

/*************************************
						Private use only
  ****************************************/
template<class T> CLinkNode<T> *CLink<T>::Exist(CLinkNode<T> *t)
{
	CLinkNode<T> *p=head;
	while(p&&(p!=t))
	{
		p=p->next;
	}
	return p;
}

template<class T>T *CLink<T>::Search(T &t)		// compare the data
	{
		CLinkNode<T> *p=head;
		while(p)
		{
			if (*(p->data)==t)
				return p->data;
			p=p->next;
		}
		return NULL;
	}

template<class T>T *CLink<T>::Search(T *t)		// compare pointer only
	{
		CLinkNode<T> *p=head;
		while(p)
		{
			if (p->data==t)
				return p->data;
			p=p->next;
		}
		return NULL;
	}

/**************************************
				Functions to Add object to link
**************************************/
template<class T>T *CLink<T>::Append(T *item)	// Add a item to the end; point to version
	{
		if (NoDuplicate)
		{
			T *i=Search(*item);
			if (i)	return i;
		}
		register CLinkNode<T> *p=new CLinkNode<T>(Own,item);
		assert(p);
		if (!tail)	Tail();
		if (tail)	tail->next=p;
		if (!head)	head=p;
		tail=p;
		count++;
		return p->data;
	}

/**************************************
				Functions to Add object to link
**************************************/
template<class T>T *CLink<T>::Append(T &item)	// Add a item to the end; copy version
	{
		if (NoDuplicate)
		{
			T *i=Search(item);
			if (i)	return i;
		}
		register CLinkNode<T> *p=new CLinkNode<T>(item,NULL);
		assert(p);
		if (!tail)	Tail();
		if (tail)	tail->next=p;
		if (!head)	head=p;
		tail=p;
		count++;
		return p->data;
	}

/**************************************
				Functions to Add object to link
**************************************/
template<class T>T *CLink<T>::Insert(T *item)	// Insert an item behide CurrentNode;
	{
		if (NoDuplicate)
		{
			T *i=Search(*item);
			if (i)	return i;
		}
		if (!CurrentNode)
			CurrentNode=head;
		CLinkNode<T> *p;
		if (CurrentNode)
		{
			p=new CLinkNode<T>(Own,item,CurrentNode->next);
			assert(p);
			CurrentNode->next=p;
		}
		else		// if the link there is nothing 
		{
			p=new CLinkNode<T>(Own,item);
			assert(p);
			head=p;
			CurrentNode=p;
		}
		count++;
		return p->data;
	}

/**************************************
				Functions to Add object to link
**************************************/
template<class T>T *CLink<T>::Insert(T &item)	// Insert an item behide CurrentNode;
	{
		if (NoDuplicate)
		{
			T *i=Search(item);
			if (i)	return i;
		}
		if (!CurrentNode)
			CurrentNode=head;
		CLinkNode<T> *p;
		if (CurrentNode)
		{
			p=new CLinkNode<T>(item,CurrentNode->next);
			assert(p);
			CurrentNode->next=p;
		}
		else 
		{
			p=new CLinkNode<T>(item);
			assert(p);
			CurrentNode=p;
		}
		count++;
		return p->data;
	}

/**************************************
				Functions to Add object to link
**************************************/
template<class T>T *CLink<T>::Add(T *item)		// Add an item to the head;
	{
		if (NoDuplicate)
		{
			T *i=Search(*item);
			if (i)	return i;
		}
		head=new CLinkNode<T>(Own,item,head);	// use it directly
		assert(head);
		count++;
		return head->data;
	}

/**************************************
				Functions to Add object to link
**************************************/
template<class T>T *CLink<T>::Add(T &item)		// Add an item to the head;
	{
		if (NoDuplicate)
		{
			T *i=Search(item);
			if (i)	return i;
		}
		head=new CLinkNode<T>(item,head);	// use it directly
		assert(head);
		count++;
		return head->data;
	}

/**************************************
				Functions to Add object to link
**************************************/
template<class T>T *CLink<T>::SortAdd(T *item)	// point to version 
	{
		if (head==NULL)
		{
			return Add(item);
		}
		CLinkNode<T> *p=head;
		CLinkNode<T> *p2=NULL;
		while(p)
		{
			int b;
			if (SortByData)
				b=*(p->data)-*item;
			else
				b=p->data-item;// sort by pointer
			if ((NoDuplicate)&&(b==0))
				return p->data;
			if (!Increase)
				b=(b>0)?-1:1;
			if (b>0)
			{
				if (p2)
				{
					Current(p2);
					return 	Insert(item);
				}
				else
					return Add(item);
			}
			p2=p;
			p=p->next;
		}
		return Append(item);
	}

/**************************************
				Functions to Add object to link
**************************************/
template<class T>T *CLink<T>::SortAdd(T &item)	// copy version , add orderly by data 
	{
		CLinkNode<T> *p=head;
		CLinkNode<T> *p2=NULL;
		while(p)
		{
			int b=*(p->data)-item;			// compare by data
			if ((NoDuplicate)&&(b==0))
				return p->data;
			if (!Increase)
				b=(b>0)?-1:1;
			if (b>0)
			{
				if (p2)
				{
					Current(p2);
					return 	Insert(item);
				}
				else
					return Add(item);
			}
			p2=p;
			p=p->next;
		}
		return Append(item);
	}

/**************************************
				Destroy functions
**************************************/
template<class T>void CLink<T>::ClearAll()			// clear the link( reset all )
	{
		CLinkNode<T> *p1=head,*p2=head;
		while(p2!=NULL)
		{
			p1=p2->next;
			delete p2;
			p2=p1;
		}
		count=0;
		head=NULL;
		tail=NULL;
		CurrentNode=NULL;
		LoopMark=NULL;
	}

/**************************************
				Destroy functions
**************************************/
template<class T> void CLink<T>::Delete()		// this function is not a effective function because of the
{															// structure of link , don't use it frequently 
	CLinkNode<T> *p1=head,*p2=NULL;
	while(p1&&(p1!=CurrentNode))
	{
		p2=p1;
		p1=p1->next;
	}
	if (p1&&p2)		// if found the node
	{
		p2->next=p1->next;	// get rid of the node
		if (p2->next)
			CurrentNode=p2->next;	// adjust current location to the next
		else
			CurrentNode=p2;			// if reach the tail 
		count--;
		delete p1;
	}
	else if (p1)
	{
		head=p1->next;
		count--;
		delete p1;
	}
	else
		head=tail=CurrentNode=NULL;
}

/**************************************
				Compare functions
**************************************/
template<class T>int CLink<T>::operator==(CLink<T> &right)
	{
		if (SortByData)
		{
			CLinkNode<T> *p1=head,*p2=right.head;
			while(p1&&p2&&(*(p1->data)==*(p2->data)))		// compare by data
			{
				p1=p1->next;
				p2=p2->next;
			}
			return ((p1)&&(p2));
		}
		else
		{
			CLinkNode<T> *p1=head,*p2=right.head;
			while(p1&&p2&&(p1->data==p2->data))						// and here is "compare by pointer"
			{
				p1=p1->next;
				p2=p2->next;
			}
			return ((p1)&&(p2));
		}
	}


/**************************************
				Compare functions
**************************************/
template<class T>int CLink<T>::operator^(CLink<T> &right)
{
		int a=0;
		if (SortByData)
		{
			CLinkNode<T> *p1=head,*p2=right.head;
			while(p1&&p2&&(!(a=*(p1->data)-*(p2->data))))
			{
				p1=p1->next;
				p2=p2->next;
			}
			return a;
		}
		else
		{
			CLinkNode<T> *p1=head,*p2=right.head;
			while(p1&&p2&&(!(a=p1->data-p2->data)))
			{
				p1=p1->next;
				p2=p2->next;
			}
			return a;
		}
}

template<class T> unsigned long CLink<T>::operator&&(CLink<T> &right)		// get the same part of the two link and return the count, compared by pointers
{
	CLinkNode<T> *p=head;
	unsigned long count=0;
	while(p)
	{
		if (right.Search(p->data))
			count++;
		p=p->next;
	}
	return count;
}

template<class T> CLink<T>::CLink<T>(CLink<T> &link2)	// copy constructor , copy pointer only , the data will not be duplicated
{
	head=NULL;
	tail=NULL;
	CurrentNode=NULL;
	Own=0;
	count=0;
	NoDuplicate=link2.NoDuplicate;
	Increase=link2.Increase;
	SortByData=link2.SortByData;
	for (CLinkNode<T> *p=link2.head;p;p=p->next)
	{
		Append(p->data);
	}
}

template<class T>CLink<T> &CLink<T>::operator=(CLink<T> &link2)
{
	ClearAll();
	head=NULL;
	tail=NULL;
	CurrentNode=NULL;
	Own=0;
	count=0;
	NoDuplicate=link2.NoDuplicate;
	Increase=link2.Increase;
	SortByData=link2.SortByData;
	for (CLinkNode<T> *p=link2.head;p;p=p->next)
	{
		Append(p->data);
	}
	return *this;
}

template<class T>CLink<T> operator&(CLink<T> &link1,CLink<T> &link2)			// return the same section of them, compare only by the pointer
{																				// it's a friend function 
	CLink<T> result(/*own=*/false);
	link2.Head();
	T *data;
	for (data=link2.GetData();data;link2.Next(),data=link2.GetData())
	{
		if (link1.Search(data))
			result.Append(data);
	}
	return result;
}

#endif