vector - [mainnet]

native public fun empty<Element>(): vector<Element>;

native public fun length<Element>(self: &vector<Element>): u64;

native public fun borrow<Element>(self: &vector<Element>, i: u64): &Element;

native public fun push_back<Element>(self: &mut vector<Element>, e: Element);

native public fun borrow_mut<Element>(self: &mut vector<Element>, i: u64): &mut Element;

native public fun pop_back<Element>(self: &mut vector<Element>): Element;

native public fun destroy_empty<Element>(self: vector<Element>);

native public fun swap<Element>(self: &mut vector<Element>, i: u64, j: u64);

native public fun move_range<T>(
    from: &mut vector<T>,
    removal_position: u64,
    length: u64,
    to: &mut vector<T>,
    insert_position: u64
);

public fun singleton<Element>(e: Element): vector<Element> {
    let v = empty();
    v.push_back(e);
    v
}

public fun reverse<Element>(self: &mut vector<Element>) {
    let len = self.length();
    self.reverse_slice(0, len);
}

public fun reverse_slice<Element>(self: &mut vector<Element>, left: u64, right: u64) {
    assert!(left <= right, EINVALID_RANGE);
    if (left == right) return;
    right -= 1;
    while (left < right) {
        self.swap(left, right);
        left += 1;
        right -= 1;
    }
}

public fun append<Element>(self: &mut vector<Element>, other: vector<Element>) {
    if (USE_MOVE_RANGE) {
        let self_length = self.length();
        let other_length = other.length();
        move_range(&mut other, 0, other_length, self, self_length);
        other.destroy_empty();
    } else {
        other.reverse();
        self.reverse_append(other);
    }
}

public fun reverse_append<Element>(self: &mut vector<Element>, other: vector<Element>) {
    let len = other.length();
    while (len > 0) {
        self.push_back(other.pop_back());
        len -= 1;
    };
    other.destroy_empty();
}

public fun trim<Element>(self: &mut vector<Element>, new_len: u64): vector<Element> {
    let len = self.length();
    assert!(new_len <= len, EINDEX_OUT_OF_BOUNDS);

    let other = empty();
    if (USE_MOVE_RANGE) {
        move_range(self, new_len, len - new_len, &mut other, 0);
    } else {
        while (len > new_len) {
            other.push_back(self.pop_back());
            len -= 1;
        };
        other.reverse();
    };

    other
}

public fun trim_reverse<Element>(self: &mut vector<Element>, new_len: u64): vector<Element> {
    let len = self.length();
    assert!(new_len <= len, EINDEX_OUT_OF_BOUNDS);
    let result = empty();
    while (new_len < len) {
        result.push_back(self.pop_back());
        len -= 1;
    };
    result
}

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

public fun contains<Element>(self: &vector<Element>, e: &Element): bool {
    let i = 0;
    let len = self.length();
    while (i < len) {
        if (self.borrow(i) == e) return true;
        i += 1;
    };
    false
}

public fun index_of<Element>(self: &vector<Element>, e: &Element): (bool, u64) {
    let i = 0;
    let len = self.length();
    while (i < len) {
        if (self.borrow(i) == e) return (true, i);
        i += 1;
    };
    (false, 0)
}

public inline fun find<Element>(self: &vector<Element>, f: |&Element|bool): (bool, u64) {
    let find = false;
    let found_index = 0;
    let i = 0;
    let len = self.length();
    while (i < len) {
        // Cannot call return in an inline function so we need to resort to break here.
        if (f(self.borrow(i))) {
            find = true;
            found_index = i;
            break
        };
        i += 1;
    };
    (find, found_index)
}

public fun insert<Element>(self: &mut vector<Element>, i: u64, e: Element) {
    let len = self.length();
    assert!(i <= len, EINDEX_OUT_OF_BOUNDS);

    if (USE_MOVE_RANGE) {
        if (i + 2 >= len) {
            // When we are close to the end, it is cheaper to not create
            // a temporary vector, and swap directly
            self.push_back(e);
            while (i < len) {
                self.swap(i, len);
                i += 1;
            };
        } else {
            let other = singleton(e);
            move_range(&mut other, 0, 1, self, i);
            other.destroy_empty();
        }
    } else {
        self.push_back(e);
        while (i < len) {
            self.swap(i, len);
            i += 1;
        };
    };
}

public fun remove<Element>(self: &mut vector<Element>, i: u64): Element {
    let len = self.length();
    // i out of bounds; abort
    if (i >= len) abort EINDEX_OUT_OF_BOUNDS;

    if (USE_MOVE_RANGE) {
        // When we are close to the end, it is cheaper to not create
        // a temporary vector, and swap directly
        if (i + 3 >= len) {
            len -= 1;
            while (i < len) self.swap(i, { i += 1; i });
            self.pop_back()
        } else {
            let other = empty();
            move_range(self, i, 1, &mut other, 0);
            let result = other.pop_back();
            other.destroy_empty();
            result
        }
    } else {
        len -= 1;
        while (i < len) self.swap(i, { i += 1; i });
        self.pop_back()
    }
}

public fun remove_value<Element>(self: &mut vector<Element>, val: &Element): vector<Element> {
    // This doesn't cost a O(2N) run time as index_of scans from left to right and stops when the element is found,
    // while remove would continue from the identified index to the end of the vector.
    let (found, index) = self.index_of(val);
    if (found) {
        vector[self.remove(index)]
    } else {
       vector[]
    }
}

public fun swap_remove<Element>(self: &mut vector<Element>, i: u64): Element {
    assert!(!self.is_empty(), EINDEX_OUT_OF_BOUNDS);
    let last_idx = self.length() - 1;
    self.swap(i, last_idx);
    self.pop_back()
}

public fun replace<Element>(self: &mut vector<Element>, i: u64, val: Element): Element {
    let last_idx = self.length();
    assert!(i < last_idx, EINDEX_OUT_OF_BOUNDS);
    if (USE_MOVE_RANGE) {
        mem::replace(self.borrow_mut(i), val)
    } else {
        self.push_back(val);
        self.swap(i, last_idx);
        self.pop_back()
    }
}

public inline fun for_each<Element>(self: vector<Element>, f: |Element|) {
    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<Element>(self: vector<Element>, f: |Element|) {
    let len = self.length();
    while (len > 0) {
        f(self.pop_back());
        len -= 1;
    };
    self.destroy_empty()
}

public inline fun for_each_ref<Element>(self: &vector<Element>, f: |&Element|) {
    let i = 0;
    let len = self.length();
    while (i < len) {
        f(self.borrow(i));
        i += 1
    }
}

public inline fun zip<Element1, Element2>(self: vector<Element1>, v2: vector<Element2>, f: |Element1, Element2|) {
    // 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<Element1, Element2>(
    self: vector<Element1>,
    v2: vector<Element2>,
    f: |Element1, Element2|,
) {
    let len = self.length();
    // We can't use the constant EVECTORS_LENGTH_MISMATCH here as all calling code would then need to define it
    // due to how inline functions work.
    assert!(len == v2.length(), 0x20002);
    while (len > 0) {
        f(self.pop_back(), v2.pop_back());
        len -= 1;
    };
    self.destroy_empty();
    v2.destroy_empty();
}

public inline fun zip_ref<Element1, Element2>(
    self: &vector<Element1>,
    v2: &vector<Element2>,
    f: |&Element1, &Element2|,
) {
    let len = self.length();
    // We can't use the constant EVECTORS_LENGTH_MISMATCH here as all calling code would then need to define it
    // due to how inline functions work.
    assert!(len == v2.length(), 0x20002);
    let i = 0;
    while (i < len) {
        f(self.borrow(i), v2.borrow(i));
        i += 1
    }
}

public inline fun enumerate_ref<Element>(self: &vector<Element>, f: |u64, &Element|) {
    let i = 0;
    let len = self.length();
    while (i < len) {
        f(i, self.borrow(i));
        i += 1;
    };
}

public inline fun for_each_mut<Element>(self: &mut vector<Element>, f: |&mut Element|) {
    let i = 0;
    let len = self.length();
    while (i < len) {
        f(self.borrow_mut(i));
        i += 1
    }
}

public inline fun zip_mut<Element1, Element2>(
    self: &mut vector<Element1>,
    v2: &mut vector<Element2>,
    f: |&mut Element1, &mut Element2|,
) {
    let i = 0;
    let len = self.length();
    // We can't use the constant EVECTORS_LENGTH_MISMATCH here as all calling code would then need to define it
    // due to how inline functions work.
    assert!(len == v2.length(), 0x20002);
    while (i < len) {
        f(self.borrow_mut(i), v2.borrow_mut(i));
        i += 1
    }
}

public inline fun enumerate_mut<Element>(self: &mut vector<Element>, f: |u64, &mut Element|) {
    let i = 0;
    let len = self.length();
    while (i < len) {
        f(i, self.borrow_mut(i));
        i += 1;
    };
}

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

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

public inline fun map_ref<Element, NewElement>(
    self: &vector<Element>,
    f: |&Element|NewElement
): vector<NewElement> {
    let result = vector<NewElement>[];
    self.for_each_ref(|elem| result.push_back(f(elem)));
    result
}

public inline fun zip_map_ref<Element1, Element2, NewElement>(
    self: &vector<Element1>,
    v2: &vector<Element2>,
    f: |&Element1, &Element2|NewElement
): vector<NewElement> {
    // We can't use the constant EVECTORS_LENGTH_MISMATCH here as all calling code would then need to define it
    // due to how inline functions work.
    assert!(self.length() == v2.length(), 0x20002);

    let result = vector<NewElement>[];
    self.zip_ref(v2, |e1, e2| result.push_back(f(e1, e2)));
    result
}

public inline fun map<Element, NewElement>(
    self: vector<Element>,
    f: |Element|NewElement
): vector<NewElement> {
    let result = vector<NewElement>[];
    self.for_each(|elem| result.push_back(f(elem)));
    result
}

public inline fun zip_map<Element1, Element2, NewElement>(
    self: vector<Element1>,
    v2: vector<Element2>,
    f: |Element1, Element2|NewElement
): vector<NewElement> {
    // We can't use the constant EVECTORS_LENGTH_MISMATCH here as all calling code would then need to define it
    // due to how inline functions work.
    assert!(self.length() == v2.length(), 0x20002);

    let result = vector<NewElement>[];
    self.zip(v2, |e1, e2| result.push_back(f(e1, e2)));
    result
}

public inline fun filter<Element:drop>(
    self: vector<Element>,
    p: |&Element|bool
): vector<Element> {
    let result = vector<Element>[];
    self.for_each(|elem| {
        if (p(&elem)) result.push_back(elem);
    });
    result
}

public inline fun partition<Element>(
    self: &mut vector<Element>,
    pred: |&Element|bool
): u64 {
    let i = 0;
    let len = self.length();
    while (i < len) {
        if (!pred(self.borrow(i))) break;
        i += 1;
    };
    let p = i;
    i += 1;
    while (i < len) {
        if (pred(self.borrow(i))) {
            self.swap(p, i);
            p += 1;
        };
        i += 1;
    };
    p
}

public fun rotate<Element>(
    self: &mut vector<Element>,
    rot: u64
): u64 {
    let len = self.length();
    self.rotate_slice(0, rot, len)
}

public fun rotate_slice<Element>(
    self: &mut vector<Element>,
    left: u64,
    rot: u64,
    right: u64
): u64 {
    self.reverse_slice(left, rot);
    self.reverse_slice(rot, right);
    self.reverse_slice(left, right);
    left + (right - rot)
}

public inline fun stable_partition<Element>(
    self: &mut vector<Element>,
    p: |&Element|bool
): u64 {
    let len = self.length();
    let t = empty();
    let f = empty();
    while (len > 0) {
        let e = self.pop_back();
        if (p(&e)) {
            t.push_back(e);
        } else {
            f.push_back(e);
        };
        len -= 1;
    };
    let pos = t.length();
    self.reverse_append(t);
    self.reverse_append(f);
    pos
}

public inline fun any<Element>(
    self: &vector<Element>,
    p: |&Element|bool
): bool {
    let result = false;
    let i = 0;
    while (i < self.length()) {
        result = p(self.borrow(i));
        if (result) {
            break
        };
        i += 1
    };
    result
}

public inline fun all<Element>(
    self: &vector<Element>,
    p: |&Element|bool
): bool {
    let result = true;
    let i = 0;
    while (i < self.length()) {
        result = p(self.borrow(i));
        if (!result) {
            break
        };
        i += 1
    };
    result
}

public inline fun destroy<Element>(
    self: vector<Element>,
    d: |Element|
) {
    self.for_each_reverse(|e| d(e))
}

public fun range(start: u64, end: u64): vector<u64> {
    range_with_step(start, end, 1)
}

public fun range_with_step(start: u64, end: u64, step: u64): vector<u64> {
    assert!(step > 0, EINVALID_STEP);

    let vec = vector[];
    while (start < end) {
        vec.push_back(start);
        start += step;
    };
    vec
}

public fun slice<Element: copy>(
    self: &vector<Element>,
    start: u64,
    end: u64
): vector<Element> {
    assert!(start <= end && end <= self.length(), EINVALID_SLICE_RANGE);

    let vec = vector[];
    while (start < end) {
        vec.push_back(self[start]);
        start += 1;
    };
    vec
}