smart_vector - [mainnet]

public fun new<T: store>(): SmartVector<T> {
    empty()
}

public fun empty<T: store>(): SmartVector<T> {
    SmartVector {
        inline_vec: vector[],
        big_vec: option::none(),
        inline_capacity: option::none(),
        bucket_size: option::none(),
    }
}

public fun empty_with_config<T: store>(inline_capacity: u64, bucket_size: u64): SmartVector<T> {
    assert!(bucket_size > 0, error::invalid_argument(EZERO_BUCKET_SIZE));
    SmartVector {
        inline_vec: vector[],
        big_vec: option::none(),
        inline_capacity: option::some(inline_capacity),
        bucket_size: option::some(bucket_size),
    }
}

public fun singleton<T: store>(element: T): SmartVector<T> {
    let v = empty();
    v.push_back(element);
    v
}

public fun destroy_empty<T>(self: SmartVector<T>) {
    assert!(self.is_empty(), error::invalid_argument(EVECTOR_NOT_EMPTY));
    let SmartVector { inline_vec, big_vec, inline_capacity: _, bucket_size: _ } = self;
    inline_vec.destroy_empty();
    big_vec.destroy_none();
}

public fun destroy<T: drop>(self: SmartVector<T>) {
    self.clear();
    self.destroy_empty();
}

public fun clear<T: drop>(self: &mut SmartVector<T>) {
    self.inline_vec = vector[];
    if (self.big_vec.is_some()) {
        self.big_vec.extract().destroy();
    }
}

public fun borrow<T>(self: &SmartVector<T>, i: u64): &T {
    assert!(i < self.length(), error::invalid_argument(EINDEX_OUT_OF_BOUNDS));
    let inline_len = self.inline_vec.length();
    if (i < inline_len) {
        self.inline_vec.borrow(i)
    } else {
        self.big_vec.borrow().borrow(i - inline_len)
    }
}

public fun borrow_mut<T>(self: &mut SmartVector<T>, i: u64): &mut T {
    assert!(i < self.length(), error::invalid_argument(EINDEX_OUT_OF_BOUNDS));
    let inline_len = self.inline_vec.length();
    if (i < inline_len) {
        self.inline_vec.borrow_mut(i)
    } else {
        self.big_vec.borrow_mut().borrow_mut(i - inline_len)
    }
}

public fun append<T: store>(self: &mut SmartVector<T>, other: SmartVector<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 add_all<T: store>(self: &mut SmartVector<T>, vals: vector<T>) {
    vals.for_each(|val| { self.push_back(val); })
}

public fun to_vector<T: store + copy>(self: &SmartVector<T>): vector<T> {
    let res = self.inline_vec;
    if (self.big_vec.is_some()) {
        let big_vec = self.big_vec.borrow();
        res.append(big_vec.to_vector());
    };
    res
}

public fun push_back<T: store>(self: &mut SmartVector<T>, val: T) {
    let len = self.length();
    let inline_len = self.inline_vec.length();
    if (len == inline_len) {
        let bucket_size = if (self.inline_capacity.is_some()) {
            if (len < *self.inline_capacity.borrow()) {
                self.inline_vec.push_back(val);
                return
            };
            *self.bucket_size.borrow()
        } else {
            let val_size = size_of_val(&val);
            if (val_size * (inline_len + 1) < 150 /* magic number */) {
                self.inline_vec.push_back(val);
                return
            };
            let estimated_avg_size = max((size_of_val(&self.inline_vec) + val_size) / (inline_len + 1), 1);
            max(1024 /* free_write_quota */ / estimated_avg_size, 1)
        };
        self.big_vec.fill(big_vector::empty(bucket_size));
    };
    self.big_vec.borrow_mut().push_back(val);
}

public fun pop_back<T>(self: &mut SmartVector<T>): T {
    assert!(!self.is_empty(), error::invalid_state(EVECTOR_EMPTY));
    let big_vec_wrapper = &mut self.big_vec;
    if (big_vec_wrapper.is_some()) {
        let big_vec = big_vec_wrapper.extract();
        let val = big_vec.pop_back();
        if (big_vec.is_empty()) {
            big_vec.destroy_empty()
        } else {
            big_vec_wrapper.fill(big_vec);
        };
        val
    } else {
        self.inline_vec.pop_back()
    }
}

public fun remove<T>(self: &mut SmartVector<T>, i: u64): T {
    let len = self.length();
    assert!(i < len, error::invalid_argument(EINDEX_OUT_OF_BOUNDS));
    let inline_len = self.inline_vec.length();
    if (i < inline_len) {
        self.inline_vec.remove(i)
    } else {
        let big_vec_wrapper = &mut self.big_vec;
        let big_vec = big_vec_wrapper.extract();
        let val = big_vec.remove(i - inline_len);
        if (big_vec.is_empty()) {
            big_vec.destroy_empty()
        } else {
            big_vec_wrapper.fill(big_vec);
        };
        val
    }
}

public fun swap_remove<T>(self: &mut SmartVector<T>, i: u64): T {
    let len = self.length();
    assert!(i < len, error::invalid_argument(EINDEX_OUT_OF_BOUNDS));
    let inline_len = self.inline_vec.length();
    let big_vec_wrapper = &mut self.big_vec;
    let inline_vec = &mut self.inline_vec;
    if (i >= inline_len) {
        let big_vec = big_vec_wrapper.extract();
        let val = big_vec.swap_remove(i - inline_len);
        if (big_vec.is_empty()) {
            big_vec.destroy_empty()
        } else {
            big_vec_wrapper.fill(big_vec);
        };
        val
    } else {
        if (inline_len < len) {
            let big_vec = big_vec_wrapper.extract();
            let last_from_big_vec = big_vec.pop_back();
            if (big_vec.is_empty()) {
                big_vec.destroy_empty()
            } else {
                big_vec_wrapper.fill(big_vec);
            };
            inline_vec.push_back(last_from_big_vec);
        };
        inline_vec.swap_remove(i)
    }
}

public fun swap<T: store>(self: &mut SmartVector<T>, i: u64, j: u64) {
    if (i > j) {
        return self.swap(j, i)
    };
    let len = self.length();
    assert!(j < len, error::invalid_argument(EINDEX_OUT_OF_BOUNDS));
    let inline_len = self.inline_vec.length();
    if (i >= inline_len) {
        self.big_vec.borrow_mut().swap(i - inline_len, j - inline_len);
    } else if (j < inline_len) {
        self.inline_vec.swap(i, j);
    } else {
        let big_vec = self.big_vec.borrow_mut();
        let inline_vec = &mut self.inline_vec;
        let element_i = inline_vec.swap_remove(i);
        let element_j = big_vec.swap_remove(j - inline_len);
        inline_vec.push_back(element_j);
        inline_vec.swap(i, inline_len - 1);
        big_vec.push_back(element_i);
        big_vec.swap(j - inline_len, len - inline_len - 1);
    }
}

public fun reverse<T: store>(self: &mut SmartVector<T>) {
    let inline_len = self.inline_vec.length();
    let new_inline_vec = vector[];
    // Push the last `inline_len` Ts into a temp vector.
    for (i in 0..inline_len) {
        new_inline_vec.push_back(self.pop_back());
    };
    new_inline_vec.reverse();
    // Reverse the big_vector left if exists.
    if (self.big_vec.is_some()) {
        self.big_vec.borrow_mut().reverse();
    };
    // Mem::swap the two vectors.
    let temp_vec = vector[];
    while (!self.inline_vec.is_empty()) {
        temp_vec.push_back(self.inline_vec.pop_back());
    };
    temp_vec.reverse();
    while (!new_inline_vec.is_empty()) {
        self.inline_vec.push_back(new_inline_vec.pop_back());
    };
    new_inline_vec.destroy_empty();
    // Push the rest Ts originally left in inline_vector back to the end of the smart vector.
    while (!temp_vec.is_empty()) {
        self.push_back(temp_vec.pop_back());
    };
    temp_vec.destroy_empty();
}

public fun index_of<T>(self: &SmartVector<T>, val: &T): (bool, u64) {
    let (found, i) = self.inline_vec.index_of(val);
    if (found) {
        (true, i)
    } else if (self.big_vec.is_some()) {
        let (found, i) = self.big_vec.borrow().index_of(val);
        (found, i + self.inline_vec.length())
    } else {
        (false, 0)
    }
}

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

public fun length<T>(self: &SmartVector<T>): u64 {
    self.inline_vec.length() + if (self.big_vec.is_none()) {
        0
    } else {
        self.big_vec.borrow().length()
    }
}

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

public inline fun for_each<T: store>(self: SmartVector<T>, f: |T|) {
    self.reverse(); // We need to reverse the vector to consume it efficiently
    self.for_each_reverse(|e| f(e));
}

public inline fun for_each_reverse<T>(self: SmartVector<T>, f: |T|) {
    let len = self.length();
    while (len > 0) {
        f(self.pop_back());
        len -= 1;
    };
    self.destroy_empty()
}

public inline fun for_each_ref<T>(self: &SmartVector<T>, f: |&T|) {
    let len = self.length();
    for (i in 0..len) {
        f(self.borrow(i));
    }
}

public inline fun for_each_mut<T>(self: &mut SmartVector<T>, f: |&mut T|) {
    let len = self.length();
    for (i in 0..len) {
        f(self.borrow_mut(i));
    }
}

public inline fun enumerate_ref<T>(self: &SmartVector<T>, f: |u64, &T|) {
    let len = self.length();
    for (i in 0..len) {
        f(i, self.borrow(i));
    };
}

public inline fun enumerate_mut<T>(self: &mut SmartVector<T>, f: |u64, &mut T|) {
    let len = self.length();
    for (i in 0..len) {
        f(i, self.borrow_mut(i));
    };
}

public inline fun fold<Accumulator, T: store>(
    self: SmartVector<T>,
    init: Accumulator,
    f: |Accumulator, T|Accumulator
): Accumulator {
    let accu = init;
    self.for_each(|elem| accu = f(accu, elem));
    accu
}

public inline fun foldr<Accumulator, T>(
    self: SmartVector<T>,
    init: Accumulator,
    f: |T, Accumulator|Accumulator
): Accumulator {
    let accu = init;
    self.for_each_reverse(|elem| accu = f(elem, accu));
    accu
}

public inline fun map_ref<T1, T2: store>(
    self: &SmartVector<T1>,
    f: |&T1|T2
): SmartVector<T2> {
    let result = aptos_std::smart_vector::new<T2>();
    self.for_each_ref(|elem| result.push_back(f(elem)));
    result
}

public inline fun map<T1: store, T2: store>(
    self: SmartVector<T1>,
    f: |T1|T2
): SmartVector<T2> {
    let result = aptos_std::smart_vector::new<T2>();
    self.for_each(|elem| result.push_back(f(elem)));
    result
}

public inline fun filter<T: store + drop>(
    self: SmartVector<T>,
    p: |&T|bool
): SmartVector<T> {
    let result = aptos_std::smart_vector::new<T>();
    self.for_each(|elem| {
        if (p(&elem)) result.push_back(elem);
    });
    result
}

public inline fun zip<T1: store, T2: store>(self: SmartVector<T1>, v2: SmartVector<T2>, f: |T1, T2|) {
    // We need to reverse the vectors to consume it efficiently
    self.reverse();
    v2.reverse();
    self.zip_reverse(v2, |e1, e2| f(e1, e2));
}

public inline fun zip_reverse<T1, T2>(
    self: SmartVector<T1>,
    v2: SmartVector<T2>,
    f: |T1, T2|,
) {
    let len = self.length();
    // We can't use the constant ESMART_VECTORS_LENGTH_MISMATCH here as all calling code would then need to define it
    // due to how inline functions work.
    assert!(len == v2.length(), 0x20005);
    while (len > 0) {
        f(self.pop_back(), v2.pop_back());
        len -= 1;
    };
    self.destroy_empty();
    v2.destroy_empty();
}

public inline fun zip_ref<T1, T2>(
    self: &SmartVector<T1>,
    v2: &SmartVector<T2>,
    f: |&T1, &T2|,
) {
    let len = self.length();
    // We can't use the constant ESMART_VECTORS_LENGTH_MISMATCH here as all calling code would then need to define it
    // due to how inline functions work.
    assert!(len == v2.length(), 0x20005);
    for (i in 0..len) {
        f(self.borrow(i), v2.borrow(i));
    }
}

public inline fun zip_mut<T1, T2>(
    self: &mut SmartVector<T1>,
    v2: &mut SmartVector<T2>,
    f: |&mut T1, &mut T2|,
) {
    let len = self.length();
    // We can't use the constant ESMART_VECTORS_LENGTH_MISMATCH here as all calling code would then need to define it
    // due to how inline functions work.
    assert!(len == v2.length(), 0x20005);
    for (i in 0..len) {
        f(self.borrow_mut(i), v2.borrow_mut(i));
    }
}

public inline fun zip_map<T1: store, T2: store, NewT: store>(
    self: SmartVector<T1>,
    v2: SmartVector<T2>,
    f: |T1, T2|NewT
): SmartVector<NewT> {
    // We can't use the constant ESMART_VECTORS_LENGTH_MISMATCH here as all calling code would then need to define it
    // due to how inline functions work.
    assert!(self.length() == v2.length(), 0x20005);

    let result = aptos_std::smart_vector::new<NewT>();
    self.zip(v2, |e1, e2| result.push_back(f(e1, e2)));
    result
}

public inline fun zip_map_ref<T1, T2, NewT: store>(
    self: &SmartVector<T1>,
    v2: &SmartVector<T2>,
    f: |&T1, &T2|NewT
): SmartVector<NewT> {
    // We can't use the constant ESMART_VECTORS_LENGTH_MISMATCH here as all calling code would then need to define it
    // due to how inline functions work.
    assert!(self.length() == v2.length(), 0x20005);

    let result = aptos_std::smart_vector::new<NewT>();
    self.zip_ref(v2, |e1, e2| result.push_back(f(e1, e2)));
    result
}