/*輕型模板數組
  提供與VC CArray類相似的功能,
  可以自動增大,按下標訪問元素,
  符合數據結構--線性表規范,同時提供VC風格的編程接口*/

#ifndef DARRAY_H
#define DARRAY_H
template <class ADT/*元素數據類型*/>
class DArray 
{
protected:
	ADT *Head; //頭指針
	int Count; //有用元素個數
	int Size;  //數組容量
	int Addition; //超界增量
public:
	DArray(int size=10/*元素個數*/)
	{
		Size=size;
		Head=new ADT[Size];
		Count=0;
		Addition=(int)((double)Size/2+0.5);
	}
	~DArray()
	{
		delete []Head;
	}
/*添加元素*/
	void AddTail(ADT data/*待添加元素*/)
	{
		if(Count<Size) Head[Count]=data;
		else
		{
			int i;
			Size+=Addition;
			ADT *head=new ADT[Size];
			for(i=0;i<Count;i++)
				head[i]=Head[i];
			head[Count]=data;
			delete []Head;
			Head=head;
		}
		Count++;
	}

	void AddHead(ADT data)
	{
		int i;
		if(Count<Size)
		{
			for(i=Count;i>0;i--)
				Head[i]=Head[i-1];
		}
		else
		{
			Size+=Addition;
			ADT *head=new ADT[Size];
			for(i=Count;i>0;i--)
				head[i]=Head[i-1];
			delete []Head;
			Head=head;
		}
		Head[0]=data;
		Count++;
	}

	void InsertAt(int index,ADT data)
	{
		int i;
		if(Count<Size)
		{
			for(i=Count;i>index;i--)
				Head[i]=Head[i-1];
		}
		else
		{
			Size+=Addition;
			ADT *head=new ADT[Size];
			for(i=0;i<index;i++) head[i]=Head[i];
			for(i=Count;i>index;i--)
				head[i]=Head[i-1];
			delete []Head;
			Head=head;
		}
		Head[index]=data;
		Count++;
	}

	void Alloc(int size)
	{
		if(Size<size)
		{
			Size=size;
			delete []Head;
			Head=new ADT[Size];
		}
		Count=Size;
	}

/*刪除元素*/
	void RemoveTail()
	{
		Count--;
	}

	void RemoveHead()
	{
		int i;
        Count--;
		for(i=0;i<Count;i++)
			Head[i]=Head[i+1];
	}

	void RemoveAt(int index)
	{
		int i;
		Count--;
		for(i=index;i<Count;i++)
			Head[i]=Head[i+1];
	}

	void RemoveAll()
	{
		Count=0;
	}

	void Removes(int begin,int end)
	{
		int i,n=end-begin+1;
		Count-=n;
		for(i=begin;i<Count;i++) Head[i]=Head[i+n];
	}
/*設置/獲取元素*/
	void SetAt(int index,ADT data)
	{
		Head[index]=data;
	}

	ADT GetAt(int index)
	{
		return Head[index];
	}

	ADT & operator [](int index)
	{
		return Head[index];
	}
/*雜項*/
	int GetCount() 
	{
		return Count;
	}

	int GetSize()
	{
		return Size;
	}

	void SetSize(int size)
	{
		ADT *head=new ADT[size];
		int i;
		if(Count>size) Count=size;
		for(i=0;i<Count;i++)
			head[i]=Head[i];
		delete []Head;
		Head=head;
		Size=size;
	}

	void SetAddition(int addition)
	{
		Addition=addition;
	}

	void Copy(DArray<ADT> *src)
	{
		int i;
		Count=src->GetCount();
		if(Count>=Size)
		{
			Size=Count;
			ADT *head=new ADT[Size];
			delete []Head;
			Head=head;
		}
		for(i=0;i<Count;i++)
			Head[i]=src->GetAt(i);
	}
};
#endif