#include<iostream.h>
#include"listnode.hpp"

#ifndef LIST_H
#define LIST_H
//////////////////////////////////////////////////////////////////////////
//有序單鏈表類定義開始,實(shí)現(xiàn)與課本基本一樣，不作多余注釋
//////////////////////////////////////////////////////////////////////////
template<class Type>
class List
{
public:	
	List();//構(gòu)造函數(shù)
	List(const List<Type>& list);//拷貝構(gòu)造函數(shù)
	~List();      //析構(gòu)函數(shù)
	List<Type> operator =(const List<Type>& list);
	void Clear();//將鏈表置為空表
	int Length() const;//計(jì)算鏈表中的元素個(gè)數(shù)
	ListNode<Type>* Find(Type& value);//在單鏈表中搜索含數(shù)據(jù)value的結(jié)點(diǎn),搜索成功則返回該節(jié)點(diǎn)的地址,否則返回NULL
	ListNode<Type>* Find(int i);//定位函數(shù),函數(shù)返回鏈表中的第i個(gè)元素的地址
	bool Insert(Type& value);//將新元素value插入在鏈表中,鏈表元素按有小到大的順序排列
	Type* Remove(int i);//將鏈表中的第i個(gè)元素刪去
	Type* Get(int i);//取出鏈表中第i個(gè)元素
private:
	friend class ListNode<Type>;
	friend class ListIterator<Type>;
	ListNode<Type> *first,*last;//鏈表的表頭表尾指針
};
//////////////////////////////////////////////////////////////////////////
template<class Type>
List<Type>::List()
{
	last=first=new ListNode<Type>();
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
List<Type>::List(const List<Type>& list)
{
	first=new ListNode<Type>();
	ListNode<Type> *p=list.first->link;
	while(p!=NULL)
	{
		Insert(p->data);
		p=p->link;
	}
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
List<Type>::~List()
{
	Clear();
	delete first;
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
List<Type> List<Type>::operator =(const List<Type>&list)
{
	Clear();
	ListNode<Type>* p=list.first->link;
	while(p!=NULL)
	{
		Insert(p->data);
		p=p->link;
	}
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
void List<Type>::Clear()
{
	ListNode<Type>* q;
	while(first->link!=NULL)
	{
		q=first->link;
		first->link=q->link;
		delete q;
	}
	last=first;
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
int List<Type>::Length()const
{
	ListNode<Type>* p=first->link;
	int count=0;
	while(p!=NULL)
	{
		p=p->link;
		count++;
	}
	return count;
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
ListNode<Type>* List<Type>::Find(Type& value)
{
	ListNode<Type>* p=first->link;
	while(p!=NULL && p->data!=value)
		p=p->link;
	return p;
}
//////////////////////////////////////////////////////////////////////////	
template<class Type>
ListNode<Type>* List<Type>::Find(int i)
{
	if(i<-1)
		return NULL;
	if(i==-1)
		return first;
	ListNode<Type>* p=first->link;
	int j=0;
	while(p!=NULL && j<i)
	{
		p=p->link;
		j++;
	}
	return p;
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
bool List<Type>::Insert(Type& value)
{
	if(first->link == NULL)
	{
		first->link =new ListNode<Type>(value,NULL);
		last=first->link;
	}
	else
	{
		ListNode<Type> *previous=first,*current=first->link;
		while(current!=NULL && current->data < value)
		{
			current=current->link;
			previous=previous->link;
		}
		ListNode<Type>* newnode=new ListNode<Type>(value,current);
		if(current==NULL)
			last=newnode;
		previous->link=newnode;
	}
	return true;
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
Type* List<Type>::Remove(int i)
{
	ListNode<Type>* p=Find(i-1),*q;
	if(p==NULL || p->link==NULL)
		return NULL;
	q=p->link;
	p->link=q->link;
	Type value=new Type(q->data);
	if(q==last)
		last=p;
	delete q;
	return &value;
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
Type* List<Type>::Get(int i)
{
	ListNode<Type>* p=Find(i);
	if(p==NULL || p==first)//參數(shù)不合理或欲取的元素是頭節(jié)點(diǎn)
		return NULL;
	else 
		return &p->data;
}
//////////////////////////////////////////////////////////////////////////
//有序單鏈表類定義結(jié)束
//////////////////////////////////////////////////////////////////////////
#endif