#define  TRUE   1
#define  FALSE  0
#define  OK     1
#define  ERROR  0
#define  INFEASIBLE  -1
#define  OVERFLOW    -2  
#define  errInt   -999
#define  errE     -999
#define  nullE    -999
typedef  int  Status;       
typedef  int  ElemType;      

typedef struct {
    ElemType * elem;
    int len;
    int size;
    int inc;    
} * SqList, *List;            

SqList InitList(int size, int inc) {
    SqList L;
    if(!(L = (SqList)malloc(sizeof(*L)))) exit(OVERFLOW);
    L->elem = (ElemType*)malloc(size*sizeof(ElemType));
    
    if(!L->elem) exit(OVERFLOW);
    L->len = 0;
    L->size = size;
    L->inc = inc;
    
    return L;    
}
SqList CreateList(ElemType es[], int n) {
    SqList L;
    if(!(L = (SqList)malloc(sizeof(*L)))) exit(OVERFLOW);
    if(!(L->elem = (ElemType*)malloc(n+5*sizeof(ElemType)))) exit(OVERFLOW);
    for(int i = 0; i < n; i++) L->elem[i] = es[i];
    L->size = n + 5; L->len = n; L->inc = 5;
    return L;
}


SqList FreeList(SqList L){
    if(L) {
        free(L->elem);
        free(L);
    }
    return NULL;
}

int ListLen(SqList L) {
    if(L) return L->len;
    else return errInt;
}

ElemType GetElem(SqList L, int i) {
    if(!L||i<1||i>L->len) return errE;
    return L->elem[i-1];
}

Status ListInsert(SqList L, int i, ElemType e) {
     if(!L||i<1||i>L->len+1) return ERROR;
     if(L->len >= L->size) {
        L->elem = (ElemType*)realloc(L->elem, (L->size+L->inc)*sizeof(ElemType));
        if(!L->elem) exit(OVERFLOW);
        L->size+=L->inc;
     }
     memmove(L->elem+i, L->elem+i-1, (L->len-i+1)*sizeof(ElemType));
     L->elem[i-1]=e; L->len++;
     return OK;
}

ElemType ListDelete(SqList L, int i) {
   if(!L||i<1||i>L->len) return errE;
   ElemType *p = &(L->elem[i-1]);
   ElemType e = *p;
   memmove(p, p+1, (L->len-i)*sizeof(ElemType));
   --L->len;
   return e;
}

int equal(ElemType a, ElemType b) {
    if(a==b) return TRUE;
    else return FALSE;
}
   
int LocateElem(SqList L, ElemType e, Status(*equal)(ElemType, ElemType)) {
    int i = 1;
    ElemType *p = L->elem;
    while(i <= L->len && !(*equal)(*p++, e)) ++i;
    if(i <= L->len) return i;
    else return 0;
}

int LocateElem_Sq(SqList L, ElemType e, Status(*equal)(ElemType, ElemType)) {
    if(!L) return 0;
    int i = 1;
    ElemType *p = L->elem; 
    while(i<=L->len && !equal(*p++, e)) ++i;
    if(i<=L->len) return i;
    else return 0;    
}


void Union(SqList La, SqList Lb) {
    int m = ListLen(La);
    int n = ListLen(Lb);
    for(int i = 1; i <= n; i++) {
        ElemType e = GetElem(Lb, i);
        if(0 == LocateElem(La, e, equal)) {
           ListInsert(La, ++m, e);
        }
    }
}

SqList MergeList_Sq(SqList La, SqList Lb) {
    SqList Lc;
    ElemType *pa, *pc, *pb, *pa_end, *pb_end; 
    if(!La || !Lb) return NULL;
    pa = La->elem; pb = Lb->elem;
    Lc = InitList(La->len + Lb->len, La->inc);
    Lc->len = Lc->size;
    pc = Lc->elem;
    pa_end = La->elem + La->len-1;
    pb_end = Lb->elem + Lb->len-1;
    while(pa<=pa_end && pb<=pb_end) {
        if(*pa<=*pb) *pc++=*pa++;
        else *pc++=*pb++;
    }
    if(pa<=pa_end) memcpy(pc, pa, (pa_end-pa+1)*sizeof(ElemType));
    if(pb<=pb_end) memcpy(pc, pb, (pb_end-pb+1)*sizeof(ElemType));
    
    return Lc;
}