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]
```