#ifndef VECTOR_H
#define VECTOR_H

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

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

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

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

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

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

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

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

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

// 將數(shù)組的元素從指定下標位置依次向后挪動
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)建一個空的Vector時分配內(nèi)存失敗");
        exit(-1);
    }
    // 給Vector的成員變量賦值
    v->data = c1alloc(DEFAULT_CAPACITY, sizeof(Element));
    if (v->data == NULL) {
        puts("error：創(chuàng)建一個空的Vector時分配內(nèi)存失敗");
        free(v); // 因為下面一行是直接退出程序，free(v)意義不大，但最好還是寫上，養(yǎng)成習慣
        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) { // 容量不足，擴容
        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) { // 容量不足，擴容
        vector_rsize(v);
    }
    // 從下標0向后移動并在0下標位置賦值
    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，索引位置不能為負且不能越界
        return;
    }
    if (v->size == v->capacity) { // 容量不足，擴容
        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ōu)先級比位運算符‘>>'高，要用括號括起來
    int new_capacity = v->size < HIGHT_SIZE ? old_capacity << 1 : old_capacity + (old_capacity >> 1);
    // tips：用realloc擴容，不能用calloc和malloc，數(shù)據(jù)會丟失！
    // tips：擴容的是v->data，而不是v
    Element *temp = realloc(v->data, new_capacity * sizeof(Element));
    if (temp == NULL) {
        puts("error：給Vector的動態(tài)數(shù)組擴容失敗");
        exit(-1);
    }
    // tips：v->data擴容部分附上初值
    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;
}