#ifndef _LineList
#define _LineList

#include "Error.h"
#include <iostream>
#include <time.h>
using namespace std;

template <class T>
class LineList
{
public:
	LineList();                              //构造函数,创建一个空表
	~LineList();                             //析构函数，删除表

	bool IsEmpty()const;                     //判断数组是否为空：是，则返回true
	int Length()const{return length;};       //返回表的长度，即表中元素个数 
	bool Find(int k,T &x) const;             //寻找表中第k个元素，并把它赋给x，若不存在第k个元素，则返回false
	int Search(const T &x) const;            //返回元素x在表中的位置；如果x 不在表中，则返回0
	LineList<T>& Delete(int k,T &x);         //删除表中第k 个元素，并把它保存到x 中；函数返回修改后的线性表
	LineList<T>& Insert(int k,const T &x);   //在第k个元素之后插入x；函数返回修改后的线性表
	LineList<T>& Change_Size_List(T *element_new,int l,int m);   //改变数组最大长度函数，l为数组长度，m为数组最大长度
	LineList<T>& Reverse();                  //将表中的数据反转，即element[k]=element[length-k]
	LineList<T>& Half();                     //数组元素减半函数

	//元素位置相关函数
	void Reset(){current=0;};                //置零current
	bool Current(T &x){                      //返回当前位置的元素，给x
		if(current<=0 || current>length) return false;
		else{  
			x=element[current-1];
			return true;
		}
	}
	bool End(){return current==length;};     //是否在最后
	bool Front(){return current==1;};        //是否在最前面
	void Next() {							 //移至下一个元素
		if(current<length)
			current++;
		else
			throw OutOfRange();
	};               
	void Previous(){                         //移至前一个元素
		if(current>1)
			current--;
		else
			throw OutOfRange();
	}

	//线性表的交叉组合
	LineList<T>& LineList<T>::Alternate(const LineList &A,const LineList& B); 

	//有规律（元素从小到大排列）线性表的组合
	LineList<T>& LineList<T>::Merge(const LineList &C,const LineList &D);

	//线性表分割函数
	void LineList<T>::Split(LineList &A,LineList &B);

	void Output(ostream &out) const;         //输出函数

private:
	T *element;      //模板类，动态一维数组
	int MaxL;        //最大长度
	int length;      //数组长度
	int current;     //元素当前位置
};
//构造函数,创建初始表
template <class T>
LineList<T>::LineList()
{
	MaxL=1;                //初始表长度最大容量为1
	element=new T[MaxL]; 
	length=0;              //长度为0
}

template <class T>
LineList<T>& LineList<T>::Change_Size_List(T *element_new,int l,int m)
{
	element=new T[m];
	for(int i=0;i<l;i++)
		element[i]=element_new[i];
	delete [] element_new;
	return *this;
}

//析构函数，删除表
template <class T>
LineList<T>::~LineList()
{
	delete [] element;
}

//判断数组是否为空：是，则返回true
template <class T>
bool LineList<T>::IsEmpty() const
{
	return length==0;
}

//寻找表中第k个元素，并把它赋给x，若不存在第k个元素，则返回false
template <class T>
bool LineList<T>::Find(int k,T &x) const
{
	if(k<0 || k>length)
		return false;
	else
		x=element[k-1];
}

//返回元素x在表中的位置；如果x 不在表中，则返回0
template <class T>
int LineList<T>::Search(const T &x) const
{
	for(int i=1;i<=length;i++)
	{
		if(element[i-1]==x)
			return i;
	}
	return 0;
}

//删除表中第k 个元素，并把它保存到x 中；函数返回修改后的线性表
template <class T>
LineList<T>& LineList<T>::Delete(int k,T &x) 
{
	if(Find(k,x))
	{
		for(int i=k-1;i<length;i++)
		element[i]=element[i+1];
		length--;		

		if(length==(MaxL/4) && length>0)
		{
			MaxL=MaxL/2;
			Change_Size_List(element,length,MaxL);
		}
		return *this;		
	}
	else
		throw OutOfRange();
}

//在第k个元素之后插入x；函数返回修改后的线性表
template <class T>
LineList<T>& LineList<T>::Insert(int k,const T &x) 
{
	//不存在第k个元素，抛出异常
	if(k<0 || k>length) throw OutOfRange();  
	if(length==MaxL) throw NoMem();
	
	for(int i=length-1;i>=k;i--)
		element[i+1]=element[i];
	element[k]=x;
	length++;

	if(length==MaxL)
	{
		MaxL=MaxL*2;
		Change_Size_List(element,length,MaxL);
	}
	
	return *this;
}

//数据反转函数
template <class T>
LineList<T>& LineList<T>::Reverse()
{
	for(int i=0;i<(length/2);i++)
	{
		int temp=element[i];
		element[i]=element[length-1-i];
		element[length-1-i]=temp;
	}
	return *this;
}

//数据减半函数
template <class T>
LineList<T>& LineList<T>::Half()
{
	length=(length+1)/2;	
	T *element_new=new T[length+1];
	for(int i=0;i<=length;i++)
		element_new[i]=element[2*i];
	delete [] element;
	element=new T [length+1];
	for(int i=0;i<=length;i++)
		element[i]=element_new[i];
	delete [] element_new;
	return *this;
}

//线性表的交叉组合
template <class T>
LineList<T>& LineList<T>::Alternate(const LineList &A,const LineList &B)
{
	length=A.Length()+B.Length();
	element=new T[length];
	A.Reset();                   //位置置0
	B.Reset();                   //位置置0
	int x;                       //当前位置上的元素
	int min_l=A.Length();        //A和B中的最小长度
	if(min_l>B.Length())
		min_l=B.Length();

	for(int i=0;i<min_l;i++)
	{
		A.Next();                //移至下一个元素
		if(A.Current(x))
			element[2*i]=x;

		B.Next();                //移至下一个元素
		if(B.Current(x))
			element[2*i+1]=x;
	}

	//经过上述current的移动，现在current在较短的线性表末端
	for(int i=2*min_l;i<length;i++)
	{
		if(!A.End())      //如果不是在A的末端，说明A线性表较长，则将A中后面元素依次赋给新线性表
		{
			A.Next();
			A.Current(x);
			element[i]=x;
		}
		else{            //否则，说明A线性表较短，则将B中后面元素依次赋给新线性表
			B.Next();
			B.Current(x);
			element[i]=x;
		}
	}
	return *this;
}

//有规律(元素从小到大排列)线性表的组合
template<class T>
LineList<T>& LineList<T>::Merge(const LineList &C,const LineList &D)
{
	length=C.Length()+D.Length();

	element=new T [length];

	int ca=0,cb=0,ct=0;     //A、B、L的索引值

	while (ca<C.Length() && cb<D.Length())
	{
		if(C.element[ca]>=D.element[cb])
			element[ct++]=D.element[cb++];
		else
			element[ct++]=C.element[ca++];
	}
	if(ca==C.Length())                     //说明A已经判断完
	{
		for(int i=cb;i<D.Length();i++)
		{
			element[ct]=D.element[i];
			ct++;
		}
	}
	else                                   //说明A没判断完
	{
		for(int i=ca;i<C.Length();i++)
		{
			element[ct]=C.element[i];
			ct++;
		}
	}
	return *this;
}

//线性表的分割
template<class T>
void LineList<T>::Split(LineList &A, LineList &B)
{
	int ca=0,cb=0,i;
	for(i=0;i<(length/2);i++)
	{
		B.Insert(cb,element[2*i]);
		cb++;
		A.Insert(ca,element[2*i+1]);
		ca++;
	}
	if((2*i-1)<=(length-1))   //原线性表有奇数个元素
		B.Insert(cb,element[length-1]);
}
//输出
template <class T>
void LineList<T>::Output(ostream &out) const
{//把表送至输出流
	for(int i=0;i<length;i++)
		out<<element[i]<<" ";
}

//重载<<
template <class T>
ostream & operator<<(ostream &out,const LineList<T>& x)
{
	x.Output(out);
	return out;
}
#endif