#include <iostream>
#include <cstdlib>
//#include <climits>
#include "seqlist.h"

using namespace std;

//////////////////////////////////////////////////////////
void InitList_sq(Sqlist& l)
{  //構(gòu)造一個(gè)空的線性表
	
	l.elem=new ElemType[List_Init_Size];
	if(!l.elem) 
	{
		cout<<"OVERFLOW"<<endl;
		exit(1);
	}//存儲(chǔ)空間分配失敗
	l.length=0;
	l.listsize= List_Init_Size;
	
}
//////////////////////////////////////////////////////////
void DestroyList_sq(Sqlist& l)
{ //銷毀順序表l
	
	delete []l.elem;
	l.elem=NULL;
	l.length=l.listsize=0;
}
/////////////////////////////////////////////////////////
void ClearList_sq(Sqlist& l)
{ //將線性表置為空表
	l.length=0;
}
/////////////////////////////////////////////////////////
bool ListEmpty_sq(Sqlist l)
{
	return(l.length==0);
}
///////////////////////////////////////////////////////////
int ListLength_sq(Sqlist l)
{
	return(l.length);
}
////////////////////////////////////////////////////////
void GetElem_sq(Sqlist l, int i, ElemType& e)
{  //若1≤i≤l.length, 則用e返回線性表的第i個(gè)數(shù)據(jù)元素
	if( ( i>=1)&&(i<=l.length) ) e=l.elem[i-1];
	else e=-1;
}
///////////////////////////////////////////////////////
int LocateElem_sq(Sqlist l, ElemType e)
{ // 在順序表l中查找第1個(gè)值與e滿足compare()的元素的位序, 若找到, 返回其在// l中的位序,否則返回0
	int i=1;
	ElemType *p;
	p=l.elem;
	while( (i<=l.length) && (!compare(*p,e)) )
	{
		p++;
		i++;
	}
	if(i<=l.length) return i;
	else return 0;
}
////////////////////////////////////////////////////////////
void PriorElem_sq(Sqlist l, ElemType cur_e, ElemType& Pre_e)
{//若cur_e是l的數(shù)據(jù)元素, 且不是第一個(gè), 則用pre_e返回它的直接前驅(qū), 
	//否則操作失敗, pre_e無(wú)定義
	int pos;

	pos= LocateElem_sq(l, cur_e);
	if(pos&&pos!=1) 
	{
		Pre_e=l.elem[pos-2];
	}
	else Pre_e=-1;
}
//////////////////////////////////////////////////////////////
void NextElem_sq(Sqlist l, ElemType cur_e, ElemType& Next_e)
{//若cur_e是l的數(shù)據(jù)元素, 且不是最后一個(gè), 則用next_e返回它的直接后繼, 否則操作失敗, next_e無(wú)定義
	int pos= LocateElem_sq(l, cur_e);
	if(pos && pos!=l.length) 
	{
		Next_e=l.elem[pos];
	}
	else Next_e=-1;
}
//////////////////////////////////////////////////////////////////
void ListInsert_sq(Sqlist& l, int i, ElemType e)
{// 在順序表l中第i個(gè)數(shù)據(jù)元素之前插入一個(gè)數(shù)據(jù)元素e,其中1<=i<=l.length+1
	ElemType* newbase;
	int j;

	if ( (i<1)||(i> l.length+1) ) 
	{
		cout<<"invalid i!"<<endl;
		exit(1);
	}
	if (l.length>=l.listsize)
	{
		//當(dāng)前存儲(chǔ)空間已滿,增加分配
		newbase=new ElemType[l.listsize+ ListIncrement];
		if(!newbase) 
		{
			cout<<"OVERFLOW"<<endl;
			exit(1);//存儲(chǔ)分配失敗
		}
		l.listsize+= ListIncrement;//增加存儲(chǔ)容量
		for(j=0; j<i-1; j++) newbase[j]=l.elem[j];
		newbase[j]=e;
		for(j=i; j<=l.length; j++) newbase[j]=l.elem[j-1];
		delete []l.elem;
		l.elem=newbase; //新基址
	}
	else
	{
		for(j=l.length;j>=i; j--) l.elem[j]=l.elem[j-1];
		l.elem[i-1]=e;
	}

	l.length++;//表長(zhǎng)增1
}//ListInsert_sq
///////////////////////////////////////////////////////////////////
void ListDelete_sq(Sqlist&l, int i, ElemType& e)
{ //在順序表l中刪除第i個(gè)數(shù)據(jù)元素,并用e返回其值,其中1<=i<=l.length
	ElemType *p,*q;
	
	if  ( (i<1)||(i>l.length) ) 
	{
		cout<<"invalid i"<<endl;//非法的i
		exit(1);
	}
	p=&(l.elem[i-1]); //p為被刪除元素的位置
	e=*p; //被刪除元素的賦給e
	q=l.elem+l.length-1;
	for(++p; p<=q; p++) *(p-1)=*p; //被刪除元素之后的元素前移
	l.length--;
}//ListDelete_sq
///////////////////////////////////////////////////////////////
void ListTraverse (Sqlist l)
{
	ElemType *p,*q;

	p=l.elem;
	q=l.elem+l.length;
	cout<<"here are the elements of L:"<<endl;
	while(p<q)
	{
		cout<<*p<<' ';
		p++;
	}
	cout<<endl<<"end of l"<<endl;
}
//////////////////////////////////////////////////////////
bool compare(ElemType x,ElemType y)
{
	if (x!=y) return false;
	else return true;
}