#ifndef VECTOR_H
#define VECTOR_H

// 數(shù)組默認(rèn)容量設(shè)置為10
#define DEFAULT_CAPACITY 10 
// 數(shù)組長(zhǎng)度低于 HIGHT_SIZE 時(shí)，每次按照原長(zhǎng)度翻倍擴(kuò)容
// 數(shù)組長(zhǎng)度高于 HIGHT_SIZE 時(shí)，擴(kuò)充原容量的1/2
#define HIGHT_SIZE 1000 

// 定義存儲(chǔ)的數(shù)據(jù)類(lèi)型
typedef char* Element;

// 定義Vector的數(shù)據(jù)結(jié)構(gòu)
typedef struct vector_s {
    Element *data; // 用于存儲(chǔ)數(shù)據(jù)的動(dòng)態(tài)數(shù)組的指針
    int size; // 數(shù)組長(zhǎng)度
    int capacity; // 容量
} Vector;

// 創(chuàng)建一個(gè)空的Vector
Vector* vector_create();

// 銷(xiāo)毀釋放Vector
void vector_destroy(Vector *v);

// 向動(dòng)態(tài)數(shù)組的末尾新增一個(gè)元素
void vector_push_back(Vector *v, Element val);

// 向數(shù)組的前面插入一個(gè)元素
void vector_push_front(Vector *v, Element val);

// 將元素val添加到索引為idx的位置，idx后面的元素依次后移
void vector_insert(Vector *v, int idx, Element val);

// 給Vector的動(dòng)態(tài)數(shù)組擴(kuò)容
static void vector_rsize(Vector *v);

// 將數(shù)組的元素從指定下標(biāo)位置依次向后挪動(dòng)
static void move_data(Vector *v, int idx);


#endif

Vector* vector_create() {
    Vector *v = (Vector*)calloc(1, sizeof(Vector));
    if (v == NULL) {
        puts("error：創(chuàng)建一個(gè)空的Vector時(shí)分配內(nèi)存失敗");
        exit(-1);
    }
    // 給Vector的成員變量賦值
    v->data = c1alloc(DEFAULT_CAPACITY, sizeof(Element));
    if (v->data == NULL) {
        puts("error：創(chuàng)建一個(gè)空的Vector時(shí)分配內(nèi)存失敗");
        free(v); // 因?yàn)橄旅嬉恍惺侵苯油顺龀绦?，free(v)意義不大，但最好還是寫(xiě)上，養(yǎng)成習(xí)慣
        exit(-1);
    }
    v->capacity = DEFAULT_CAPACITY;
    return v;
}

void vector_destroy(Vector *v) {
    if (v == NULL) { // Vector不能是NULL
        return;
    }
    free(v->data);
    free(v);
}

void vector_push_back(Vector *v, Element val) {
    if (v == NULL) { // Vector不能是NULL
        return;
    }
    if (v->size == v->capacity) { // 容量不足，擴(kuò)容
        vector_rsize(v);
    }
    v->data[v->size] = val;
    v->size++;
}

void vector_push_front(Vector *v, Element val) {
    if (v == NULL) { // Vector不能是NULL
        return;
    }
    if (v->size == v->capacity) { // 容量不足，擴(kuò)容
        vector_rsize(v);
    }
    // 從下標(biāo)0向后移動(dòng)并在0下標(biāo)位置賦值
    move_data(v, 0);
    v->data[0] = val;
    v->size++;
}

void vector_insert(Vector *v, int idx, Element val) {
    if (v == NULL || idx < 0 || idx > v->size) { // Vector不能是NULL，索引位置不能為負(fù)且不能越界
        return;
    }
    if (v->size == v->capacity) { // 容量不足，擴(kuò)容
        vector_rsize(v);
    }
    move_data(v, idx);
    v->data[idx] = val;
    v->size++;
}

static void vector_rsize(Vector *v) {
    int old_capacity = v->capacity;
    // tips：算術(shù)運(yùn)算‘+'的優(yōu)先級(jí)比位運(yùn)算符‘>>'高，要用括號(hào)括起來(lái)
    int new_capacity = v->size < HIGHT_SIZE ? old_capacity << 1 : old_capacity + (old_capacity >> 1);
    // tips：用realloc擴(kuò)容，不能用calloc和malloc，數(shù)據(jù)會(huì)丟失！
    // tips：擴(kuò)容的是v->data，而不是v
    Element *temp = realloc(v->data, new_capacity * sizeof(Element));
    if (temp == NULL) {
        puts("error：給Vector的動(dòng)態(tài)數(shù)組擴(kuò)容失敗");
        exit(-1);
    }
    // tips：v->data擴(kuò)容部分附上初值
    memset(v->data + v->size, 0, (v->capacity - v->size) * sizeof(Element));
    v->data = temp;
    v->capacity = new_capacity;
}

static void move_data(Vector *v, int idx) {
    for (int i = v->size - 1; i >= idx; i--) {
        v->data[i+1] = v->data[i];
    }
    v->data[idx] = 0;
}