#include<iostream>

#include<stdexcept>

using namespace std;

struct List{

     int *data;  //指向堆内存的指针，存储实际元素

     int size;   //当前元素个数

     int cap;     //当前已分配的内存容量（可容纳的元素个数）

};//创建数组

List *make(int cap=1){

    List*p=new List;                // 分配 List 结构体内存

    p->data=new int[cap];           // 分配元素存储空间

    p->size=0;

    p->cap=cap;                      // 记录容量

    return p;

}

//内存释放

void del(List* p){

    delete[]p-> data;

    delete p;

}

//扩容/缩容

void resize(List* p,int cap){

    if (cap<1) cap=1;                     //防止容量变为 0 避免后续 new int[0] 引发问题

    int *tmp=new int[cap];  //申请新数组

    int copySize=(p->size<cap)?p->size:cap;          // 拷贝时取最小值，防止越界

    for(int i=0;i<copySize;i++){ //拷贝

        tmp[i]=p->data[i];

    }

    delete[]p->data;  //释放旧数组内存

    p->data=tmp;

    p->cap=cap;

    if(p->size>cap)p->size=cap;

}

//push

void Mypush(List* p,int x){

    if(p->size==p->cap)resize(p,p->cap*2);

    p->data[p->size++]=x;

    // 等价于：

    // p->data[p->size] = x;

    // p->size++;

}

//指定位置插入

void Myinsert(List* p,int idx,int x){

    if(idx<0||idx>p->size){

        cerr<<"err;idx="<<idx<<" size="<<p->size<<endl;

        exit(1);

    }

    if(p->size==p->cap)resize(p,p->cap*2);

    for(int i=p->size;i>idx;i--){                   // 从后往前移动元素，腾出插入位置

        p->data[i]=p->data[i-1];

    }

    p->data[idx]=x;

    p->size++;

}

// 头部插入

void Myunshift(List* p,int x){

    Myinsert(p,0,x);

}

//尾部删除

int pop(List *p){

    if(p->size==0){

        cerr<<"err:empty"<<endl;

        exit(1);

    }

    if(p->size==p->cap/4&&p->cap>1) resize(p,p->cap/2);

    return p->data[--p->size];

   

}

int cut(List* p,int idx){

    if(idx<0||idx>=p->size){

        cerr<<"err:idx="<<idx<<" size="<<p->size<<endl;

        exit(1);

    }

    if(p->size==p->cap/4&&p->cap>1)resize(p,p->cap/2);

    int val=p->data[idx]; // ③ 保存要删除的值

    for(int i=idx;i<p->size-1;i++){//元素前移，覆盖被删位置

        p->data[i]=p->data[i+1];

    }

    p->size--;

    return val;

}

int shift(List* p){

    return cut(p,0);

}

int get(List*p,int idx){

       if(idx<0||idx>=p->size){

        cerr<<"err:idx="<<idx<<" size="<<p->size<<endl;

        exit(1);

       }

       return p->data[idx];

}

//修改

int put(List*p,int idx,int x){

    int old=get(p,idx);

    p->data[idx]=x;

    return old;

}

int len(List* p){

    return p->size;

}

bool empty(List *p){

    return p->size==0;

}

void show(List* p){

    cout<<"size="<<p->size<<" cap="<<p->cap<<endl;

    cout<<"[";

    for(int i=0;i<p->size;i++){

        if(i)cout<<" ,";

        cout<<p->data[i];

    }

    cout<<"]"<<endl;

}

int main(){

     

    List* list = make(2);    

   

    Mypush(list, 10);

    Mypush(list, 20);

    Mypush(list, 30);        

    show(list);              

   

    Myinsert(list, 1, 99);

    show(list);              

    

    pop(list);

    show(list);              

   

    cut(list, 1);            

    show(list);              

   

    shift(list);

    show(list);              

   

    del(list);

    return 0;

}