Vec

The Vec module contains the vector type, a container for a dynamically-allocated contiguous region of memory with constant time access and the ability to resize.

Types


Vec ’t

The main vector type exported by the module.

type Vec 't = 't* data, usz len cap

Examples

Creating a Vec and pushing to it:

mut v = Vec.empty ()
v.push 2
v.push 4

Creating a Vec from an array:

let v = Vec.of [1, 2, 3, 4]

Iterating through all elements of a Vec:

for elem in Vec.of [5, 6, 7] do
    print elem

Applying a function to every element of a Vec, and receiving a new Vec containing the new elements:

let v1 = Vec.of [1, 2, 3, 4]     //[1, 2, 3, 4]
let v2 = v1.map (fun x = x * 2)  //[2, 4, 6, 8]

fun square: x = x * x
let v3 = v2.map square           //[4, 16, 36, 64]          

Combining each element of the vector in some way. Eg. Summing them or finding the max element:

fun sum: vec =
    fold vec 0 (+)

fun max_elem: vec =
    fold vec None (fun cur_max, elem =
        match cur_max with
        | None -> elem
        | Some n -> max n elem)

//max_elem can alternatively be written using
//reduce, which enforces that the Vec is not empty
//and uses the first element as the initial value for cur_max
fun max_elem: vec =
    reduce vec max

VecIter ’t

An iterator for a Vec. These aren’t typically constructed directly. Instead, they are made from the into_iter function that is called automatically when a Vec is used in a for loop.

type VecIter 't = 't* view, usz idx len

Examples

Iterating through a Vec:

let vec = Vec.of ["bob", "marissa", "sandra"]

mut VecIter iter = into_iter vec
while has_next iter do
    let e = unwrap iter
    print e
    iter := next iter

//which is equivalent to the preferred form:
for e in vec do
    print e

Traits


Vec : Iterable

ext Vec : Iterable
    fun into_iter: Vec 't v -> VecIter 't

Allows the usage of Vec in a for loop.


VecIter : Iterator

ext VecIter : Iterator
    fun has_next: VecIter v -> bool

    fun unwrap: VecIter 't v -> 't

    fun next: VecIter 't v -> VecIter 't

Allows the usage of VecIter in a for loop.


Functions


empty

Initializes an empty vector of any element type. The vector has a default capacity of 0 elements.

fun empty: -> Vec 't

Examples

let v1 = Vec.empty ()
let v2 = Vec.empty ()

//pushing to the Vec determines its element type
v1.push 10     //v1 : Vec i32
v2.push "ten"  //v2 : Vec Str

v1.push "test" //error! cannot push Str to Vec of i32

of

Creates a vector of integers with all elements from the given iterable.

fun of: Iterable 'e i -> Vec 'e ret where len i = len ret

Examples

let v = Vec.of [1, 1, 2, 3, 5]

let one_to_one_hundred = Vec.of (1..101)

let evens = Vec.of <| (2,4)..101

let copy = Vec.of v

make

Creates a vector filled with count copies of the given argument e. This function is useful to create multi-dimensional vectors or vectors that need to be a certain length.

fun make: usz count, 'e elem -> Vec 'e ret where len ret = count

Examples

Vec.make 3 5.78  //=> [5.78, 5.78, 5.78]

Vec.make 4 (Vec.make 3 0)
/* =>  [[0, 0, 0],
        [0, 0, 0],
        [0, 0, 0],
        [0, 0, 0]] */

is_empty

Returns true if the vector is empty.

fun is_empty: Vec v -> bool ret where ret = (len v = 0)

Examples

Vec.empty () |> is_empty |> assert

let v1 = Vec.of [1]
let v2 = Vec.of [2, 3]
assert (not (Vec.empty v1))
assert (not (Vec.empty v2))

indices

Returns a Range that contains all the indices from the given vector.

fun indices: Vec v -> Range r  \
    where r.start = 0  \
      and r.step = 1   \
      and r.end = len v

Examples

let v = Vec.of ["zero", "one", "two"]

for i in indices v do
    print (v#i)

for (e, i) in (v, indices v) do
    print "element ${i} is ${e}"

len

Returns the length of the vector.

fun len: Vec v = v.len

Examples

Checking if a given index is valid:

mut v = Vec.make (random u8) 3.14

if 50 < len v then
    print (v#50)

capacity

Returns the capacity of the vector. This can be useful in determining when a push will need to reallocate the vector’s contents. The capacity is usually a power of two, although if all the elements were allocated in one operation (eg. in Vec.of or Vec.make) then the capacity will more generally be initial_length * 2^n for some n, provided the initial_length is greater than zero.

fun capacity: Vec v = v.cap

Examples

mut v1 = Vec.empty ()
v1.push 1
v1.push 2
v1.push 3

mut v2 = Vec.of [1, 2, 3]

assert (capacity v1 = 4)  // = 2^2
assert (capacity v2 = 3)  // = len v2 * 2^0

v1.push 4
let v3 = Vec.of v2
v3.push 4

assert (capacity v1 = 4)  // = 2^2
assert (capacity v3 = 6)  // = len v2 * 2^1

push

Pushes an element onto the end of the vector. Resizes the vector automatically if the length is equal to the capacity. When resizing occurs, the capacity of the vector is doubled.

fun push: mut Vec 't v, 't elem where len v += 1

Examples

Appending to an existing vector:

mut v = Vec.empty ()  //=> []
v.push 3              //=> [3]
v.push 5              //=> [3, 5]
v.push 8              //=> [3, 5, 8]

Cannot push to an immutable vector:

let v = Vec.empty ()
v.push 3   // error: v is immutable!

An immutable vector can be copied, and the copy can be pushed to:

let v = Vec.of [1, 2]

mut cpy = Vec.of v  // same as copy v
cpy.push 3

print cpy  //=> [1, 2, 3]
print v    //=> [1, 2]

push_all

Push all elements, copying from the given iterable to the end of the vector.

fun push_all: mut Vec 't v, Iterable 't it where len v += len it

Examples

mut v = Vec.of [1, 2, 3]

v.push_all [4, 5, 6]

print v  //=> [1, 2, 3, 4, 5, 6]

reserve

Reserve space for numElements additional elements in the given vector. The newly reserved elements will be uninitialized. Note that this function just allocates the space for new elements, it does not actually fill it with any values or change the length of the vector.

fun reserve: mut Vec 't v, usz numElems where capacity v += numElements

Examples

mut buf = Vec.empty ()  //capacity = 0
buf.reserve 100         //capacity = 100

//no re-allocations occur:
for e in 0..100 do
    buf.push e

//note that the following is preferred over the above
let buf = Vec.of (0..100)

Newly allocated space is outside the length and is thus inaccessible initailly:

mut v = Vec.empty () //=> (buf = [], len = 0, cap = 0)
v.reserve 5          //=> (buf = [], len = 0, cap = 5)

v#0        //=> error: 0 >= len v
v.push 3   //=> (buf = [3], len = 1, cap = 5)
v#0        //=> ok: v#0 = 3

pop

Pops the last element off and returns it. This will never resize the vector.

fun pop: mut Vec 't v -> 't where len v > 0

Examples

mut queue = Vec.of [3, 4]
queue.pop ()   //=> 4
queue          //=> [3]

queue.pop ()   //=> 3
queue.pop ()   //error: len queue > 0
queue          //=> []

try_pop

Pops the last element off and returns it if it exists. This will never resize the vector.

fun pop: mut Vec 't v -> Maybe 't

Examples

mut queue = Vec.of [3, 4]
queue.try_pop ()   //=> Some 4
queue              //=> [3]

queue.try_pop ()   //=> Some 3
queue.try_pop ()   //=> None
queue              //=> []

remove_index

Removes the element at the given index and return it.

fun remove_index: mut Vec 't v, usz idx -> 't where idx < len v and len v -= 1

Examples

mut v = Vec.of (10..14)  //=> [10, 11, 12, 13]
v.remove_index 1         //=> 11
v                        //=> [10, 12, 13]

v.remove_index 4         //=> error: 4 >= len v

remove_indices

Removes the given indices from the vector. This function expects the indices to be in sorted order and will error if any index is out of bounds.

fun remove_indices: mut Vec v, Vec usz indices  \
    where is_sorted indices    \
      and max indices < len v  \
      and len v -= len indices

Examples

mut v = Vec.of [5, 6, 7, 8, 9]
v.remove_indices (Vec.of [1, 2, 4])
v  //=> [5, 7, 8]

remove_first

Remove the first instance of the given element from the vector or none if the element was not found. Uses = to determine element equality. returns the index where the element was found.

fun remove_first: mut Vec 't v, 't elem -> Maybe usz where len v -= 0 or len v -= 1

Examples

mut v = Vec.of [1, 1, 0, 2, 3, 0, 0]
v.remove_first 0   //=> Some 2
v.remove_first 1   //=> Some 0
v                  //=> [1, 2, 3, 0, 0]

v.remove_first 2   //=> Some 1
v.remove_first 4   //=> None
v                  //=> [1, 3, 0, 0]

remove_all

Remove all matching elements from the vector and return the number of elements removed. Uses = to determine element equality.

fun remove_all: mut Vec 't v, 't elem -> usz ret where len v -= ret

Examples

mut v = Vec[1, 2, 1, 5, 3, 1]
v.remove_all 1  //=> 3

assert <| v = Vec[2, 5, 3]