#ifndef __SQLLIST_H__
#define __SQLLIST_H__


#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLF -1
#define OVERFLOW -2

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef int Status;

typedef int ElemType;

typedef struct {
	ElemType *elem;
	ElemType length;
	ElemType listsize;
}SqList;

#endif

#include"SeqList.h"
#include<stdlib.h>
#include<stdio.h>

Status initList_Sq(SqList &L) {
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(!L.elem) {
		exit(OVERFLOW);
	}
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
	return OK;
}

Status listInsert(SqList &L, int i, ElemType e) {
	if(i < 1 || i > L.length + 1){
		return ERROR;
	}

	if(L.length > L.listsize) {
		ElemType *newbase = (ElemType *)realloc(L.elem,
			(L.listsize + LISTINCREMENT) * sizeof(ElemType));
		if(!newbase) {
			exit(OVERFLOW);
		}
		L.elem = newbase;
		L.listsize += LISTINCREMENT;
	}

	ElemType *q = &(L.elem[i - 1]);
	for(ElemType *p = &(L.elem[L.length - 1]); p >= q; --p) {
		*(p + 1) = *p;
	}

	*q = e;
	++L.length;
	return OK;
}

void pShow(SqList L){
	printf("=======  SqList   ======\n");
	if(L.length != 0) {

		ElemType *t = L.elem;
		for(int i = 0; i < L.length; i++) {
			printf("L.elem[%d] = %d\n", i, t[i]);
		}
	} else {

	}

	printf("L.length = %d\n", L.length);
	printf("L.listsize = %d\n", L.listsize);
}

Status GetElem(SqList &L, int i, ElemType &e) {
	if(i > L.length || i < 1) {
		exit(OVERFLOW);
	}

	e = L.elem[i - 1];
	return OK;
}

Status LocateElem_Sq(SqList L, ElemType e) {
	ElemType i = 1;
	ElemType *p = L.elem;

	while(i <= L.length && *p++ != e) {
		++i;
	}

	if(i <= L.length) {
		return i;
	} else{
		return 0;
	}
}

Status ListLength(SqList L) {
	return L.length;
}

void Union(SqList &a, SqList b) {
	ElemType a_len = ListLength(a);
	ElemType b_len = ListLength(b);
	ElemType e;
	for (int i = 1; i <= b_len; ++i)
	{
		/* code */
		GetElem(b, i, e);
		if(!LocateElem_Sq(a, e)) {
			listInsert(a, ++a_len, e);
		}
	}
}

void MergeList(SqList la, SqList lb, SqList &Lc) {
	initList_Sq(Lc);
	ElemType i = 1;
	ElemType j = 1;
	ElemType k = 0;

    ElemType La_len = ListLength(la);
    ElemType Lb_len = ListLength(lb);

    ElemType ai, bj;
    while((i <= La_len) && (j <= Lb_len)) {
    	GetElem(la, i, ai);
    	GetElem(lb, j, bj);
    	if(ai <= bj) {
    		listInsert(Lc, ++k, ai);
    		++i;
    	} else{
    		listInsert(Lc, ++k, bj);
    		++j;
    	}
    }

    while(i <= La_len) {
    	GetElem(la, i++, ai);
    	listInsert(Lc, ++k, ai);
    }

    while(j <= Lb_len) {
     	GetElem(lb, j++, bj);
    	listInsert(Lc, ++k, bj);   	
    }

}

Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
	if(i < 1 || (i > L.length)) {
		return ERROR;
	}

	ElemType *p = &(L.elem[i - 1]);
	e = *p;
	ElemType *q = L.elem + L.length - 1;
	for(++p; p <= q; ++p) {
		*(p -1) = *p;
	}
	--L.length;
	return OK;
}
 
int main() {

	ElemType e;

	SqList L;
	initList_Sq(L);
	for (int i = 0; i < 10; ++i)
	{
		/* code */
		listInsert(L, i + 1, i);
	}

	SqList t;
	initList_Sq(t);
	for (int i = 0; i < 10; ++i)
	{
		/* code */
		listInsert(t, i + 1, i + 10);
	}

	GetElem(L, 5, e);
	printf("l5 = %d\n", e);

	ElemType index = 6;
	ElemType value = LocateElem_Sq(L, index);
	printf("index = %d, value = %d\n", index, value);

	SqList r;
	MergeList(L, t, r);

	pShow(r);

	SqList a;
	initList_Sq(a);
	listInsert(a, 1, 3);
	listInsert(a, 2, 5);
	listInsert(a, 3, 8);
	listInsert(a, 4, 11);

	SqList b;
	initList_Sq(b);
	listInsert(b, 1, 2);
	listInsert(b, 2, 6);
	listInsert(b, 3, 8);
	listInsert(b, 4, 9);
	listInsert(b, 5, 11);
	listInsert(b, 6, 15);
	listInsert(b, 7, 20);

	SqList c;
	MergeList(a, b, c);
	pShow(c);

	Union(a, b);
	pShow(a);

	ListDelete_Sq(b, 6, e);
	pShow(b);
	return 0;
}