big_vector - [mainnet]

friend fun empty<T: store>(bucket_size: u64): BigVector<T> {
    assert!(bucket_size > 0, error::invalid_argument(EZERO_BUCKET_SIZE));
    BigVector {
        buckets: table_with_length::new(),
        end_index: 0,
        bucket_size,
    }
}

friend fun singleton<T: store>(element: T, bucket_size: u64): BigVector<T> {
    let v = empty(bucket_size);
    v.push_back(element);
    v
}

public fun destroy_empty<T>(self: BigVector<T>) {
    assert!(self.is_empty(), error::invalid_argument(EVECTOR_NOT_EMPTY));
    let BigVector { buckets, end_index: _, bucket_size: _ } = self;
    buckets.destroy_empty();
}

public fun destroy<T: drop>(self: BigVector<T>) {
    let BigVector { buckets, end_index, bucket_size: _ } = self;
    let i = 0;
    while (end_index > 0) {
        let num_elements = buckets.remove(i).length();
        end_index -= num_elements;
        i += 1;
    };
    buckets.destroy_empty();
}

public fun borrow<T>(self: &BigVector<T>, i: u64): &T {
    assert!(i < self.length(), error::invalid_argument(EINDEX_OUT_OF_BOUNDS));
    self.buckets.borrow(i / self.bucket_size).borrow(i % self.bucket_size)
}

public fun borrow_mut<T>(self: &mut BigVector<T>, i: u64): &mut T {
    assert!(i < self.length(), error::invalid_argument(EINDEX_OUT_OF_BOUNDS));
    self.buckets.borrow_mut(i / self.bucket_size).borrow_mut(i % self.bucket_size)
}

public fun append<T: store>(self: &mut BigVector<T>, other: BigVector<T>) {
    let other_len = other.length();
    let half_other_len = other_len / 2;
    let i = 0;
    while (i < half_other_len) {
        self.push_back(other.swap_remove(i));
        i += 1;
    };
    while (i < other_len) {
        self.push_back(other.pop_back());
        i += 1;
    };
    other.destroy_empty();
}

public fun push_back<T: store>(self: &mut BigVector<T>, val: T) {
    let num_buckets = self.buckets.length();
    if (self.end_index == num_buckets * self.bucket_size) {
        self.buckets.add(num_buckets, vector::empty());
        self.buckets.borrow_mut(num_buckets).push_back(val);
    } else {
        self.buckets.borrow_mut(num_buckets - 1).push_back(val);
    };
    self.end_index += 1;
}

public fun pop_back<T>(self: &mut BigVector<T>): T {
    assert!(!self.is_empty(), error::invalid_state(EVECTOR_EMPTY));
    let num_buckets = self.buckets.length();
    let last_bucket = self.buckets.borrow_mut(num_buckets - 1);
    let val = last_bucket.pop_back();
    // Shrink the table if the last vector is empty.
    if (last_bucket.is_empty()) {
        move last_bucket;
        self.buckets.remove(num_buckets - 1).destroy_empty();
    };
    self.end_index -= 1;
    val
}

public fun remove<T>(self: &mut BigVector<T>, i: u64): T {
    let len = self.length();
    assert!(i < len, error::invalid_argument(EINDEX_OUT_OF_BOUNDS));
    let num_buckets = self.buckets.length();
    let cur_bucket_index = i / self.bucket_size + 1;
    let cur_bucket = self.buckets.borrow_mut(cur_bucket_index - 1);
    let res = cur_bucket.remove(i % self.bucket_size);
    self.end_index -= 1;
    move cur_bucket;
    while ({
        spec {
            invariant cur_bucket_index <= num_buckets;
            invariant table_with_length::spec_len(self.buckets) == num_buckets;
        };
        (cur_bucket_index < num_buckets)
    }) {
        // remove one element from the start of current vector
        let cur_bucket = self.buckets.borrow_mut(cur_bucket_index);
        let t = cur_bucket.remove(0);
        move cur_bucket;
        // and put it at the end of the last one
        let prev_bucket = self.buckets.borrow_mut(cur_bucket_index - 1);
        prev_bucket.push_back(t);
        cur_bucket_index += 1;
    };
    spec {
        assert cur_bucket_index == num_buckets;
    };

    // Shrink the table if the last vector is empty.
    let last_bucket = self.buckets.borrow_mut(num_buckets - 1);
    if (last_bucket.is_empty()) {
        move last_bucket;
        self.buckets.remove(num_buckets - 1).destroy_empty();
    };

    res
}

public fun swap_remove<T>(self: &mut BigVector<T>, i: u64): T {
    assert!(i < self.length(), error::invalid_argument(EINDEX_OUT_OF_BOUNDS));
    let last_val = self.pop_back();
    // if the requested value is the last one, return it
    if (self.end_index == i) {
        return last_val
    };
    // because the lack of mem::swap, here we swap remove the requested value from the bucket
    // and append the last_val to the bucket then swap the last bucket val back
    let bucket = self.buckets.borrow_mut(i / self.bucket_size);
    let bucket_len = bucket.length();
    let val = bucket.swap_remove(i % self.bucket_size);
    bucket.push_back(last_val);
    bucket.swap(i % self.bucket_size, bucket_len - 1);
    val
}

public fun swap<T>(self: &mut BigVector<T>, i: u64, j: u64) {
    assert!(i < self.length() && j < self.length(), error::invalid_argument(EINDEX_OUT_OF_BOUNDS));
    let i_bucket_index = i / self.bucket_size;
    let j_bucket_index = j / self.bucket_size;
    let i_vector_index = i % self.bucket_size;
    let j_vector_index = j % self.bucket_size;
    if (i_bucket_index == j_bucket_index) {
        self.buckets.borrow_mut(i_bucket_index).swap(i_vector_index, j_vector_index);
        return
    };
    // If i and j are in different buckets, take the buckets out first for easy mutation.
    let bucket_i = self.buckets.remove(i_bucket_index);
    let bucket_j = self.buckets.remove(j_bucket_index);
    // Get the elements from buckets by calling `swap_remove`.
    let element_i = bucket_i.swap_remove(i_vector_index);
    let element_j = bucket_j.swap_remove(j_vector_index);
    // Swap the elements and push back to the other bucket.
    bucket_i.push_back(element_j);
    bucket_j.push_back(element_i);
    let last_index_in_bucket_i = bucket_i.length() - 1;
    let last_index_in_bucket_j = bucket_j.length() - 1;
    // Re-position the swapped elements to the right index.
    bucket_i.swap(i_vector_index, last_index_in_bucket_i);
    bucket_j.swap(j_vector_index, last_index_in_bucket_j);
    // Add back the buckets.
    self.buckets.add(i_bucket_index, bucket_i);
    self.buckets.add(j_bucket_index, bucket_j);
}

public fun reverse<T>(self: &mut BigVector<T>) {
    let new_buckets = vector[];
    let push_bucket = vector[];
    let num_buckets = self.buckets.length();
    let num_buckets_left = num_buckets;

    while (num_buckets_left > 0) {
        let pop_bucket = self.buckets.remove(num_buckets_left - 1);
        pop_bucket.for_each_reverse(|val| {
            push_bucket.push_back(val);
            if (push_bucket.length() == self.bucket_size) {
                new_buckets.push_back(push_bucket);
                push_bucket = vector[];
            };
        });
        num_buckets_left -= 1;
    };

    if (push_bucket.length() > 0) {
        new_buckets.push_back(push_bucket);
    } else {
        push_bucket.destroy_empty();
    };

    new_buckets.reverse();
    assert!(self.buckets.length() == 0, 0);
    for (i in 0..num_buckets) {
        self.buckets.add(i, new_buckets.pop_back());
    };
    new_buckets.destroy_empty();
}

public fun index_of<T>(self: &BigVector<T>, val: &T): (bool, u64) {
    let num_buckets = self.buckets.length();
    let bucket_index = 0;
    while (bucket_index < num_buckets) {
        let cur = self.buckets.borrow(bucket_index);
        let (found, i) = cur.index_of(val);
        if (found) {
            return (true, bucket_index * self.bucket_size + i)
        };
        bucket_index += 1;
    };
    (false, 0)
}

public fun contains<T>(self: &BigVector<T>, val: &T): bool {
    if (self.is_empty()) return false;
    let (exist, _) = self.index_of(val);
    exist
}

public fun to_vector<T: copy>(self: &BigVector<T>): vector<T> {
    let res = vector[];
    let num_buckets = self.buckets.length();
    for (i in 0..num_buckets) {
        res.append(*self.buckets.borrow(i));
    };
    res
}

public fun length<T>(self: &BigVector<T>): u64 {
    self.end_index
}

public fun is_empty<T>(self: &BigVector<T>): bool {
    self.length() == 0
}