VarArray

motoko name=import
import VarArray "mo:base/VarArray";

public func empty<T>() : [var T]

Creates an empty mutable array (equivalent to [var]).

motoko include=import
let array = VarArray.empty<Text>();
assert array.size() == 0;

Runtime: O(1)

Space: O(1)

public func repeat<T>(item : T, size : Nat) : [var T]

Creates a mutable array containing item repeated size times.

motoko include=import
import Text "mo:base/Text";

let array = VarArray.repeat<Text>("Echo", 3);
assert VarArray.equal(array, [var "Echo", "Echo", "Echo"], Text.equal);

Runtime: O(size)

Space: O(size)

public func clone<T>(array : [var T]) : [var T]

Duplicates array, returning a shallow copy of the original.

motoko include=import
import Nat "mo:base/Nat";

let array1 = [var 1, 2, 3];
let array2 = VarArray.clone<Nat>(array1);
array2[0] := 0;
assert VarArray.equal(array1, [var 1, 2, 3], Nat.equal);
assert VarArray.equal(array2, [var 0, 2, 3], Nat.equal);

Runtime: O(size)

Space: O(size)

public func tabulate<T>(size : Nat, generator : Nat -> T) : [var T]

Creates an immutable array of size size. Each element at index i is created by applying generator to i.

motoko include=import
import Nat "mo:base/Nat";

let array : [var Nat] = VarArray.tabulate<Nat>(4, func i = i * 2);
assert VarArray.equal(array, [var 0, 2, 4, 6], Nat.equal);

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that generator runs in O(1) time and space.

public func equal<T>(
  array1 : [var T],
  array2 : [var T],
  equal : (T, T) -> Bool
) : Bool

Tests if two arrays contain equal values (i.e. they represent the same list of elements). Uses equal to compare elements in the arrays.

motoko include=import
// Use the equal function from the Nat module to compare Nats
import Nat "mo:base/Nat";

let array1 = [var 0, 1, 2, 3];
let array2 = [var 0, 1, 2, 3];
assert VarArray.equal(array1, array2, Nat.equal);

Runtime: O(size1 + size2)

Space: O(1)

*Runtime and space assumes that equal runs in O(1) time and space.

public func find<T>(array : [var T], predicate : T -> Bool) : ?T

Returns the first value in array for which predicate returns true. If no element satisfies the predicate, returns null.

motoko include=import
let array = [var 1, 9, 4, 8];
let found = VarArray.find<Nat>(array, func x = x > 8);
assert found == ?9;

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that predicate runs in O(1) time and space.

public func concat<T>(array1 : [var T], array2 : [var T]) : [var T]

Create a new mutable array by concatenating the values of array1 and array2. Note that VarArray.concat copies its arguments and has linear complexity.

motoko include=import
import Nat "mo:base/Nat";

let array1 = [var 1, 2, 3];
let array2 = [var 4, 5, 6];
let result = VarArray.concat<Nat>(array1, array2);
assert VarArray.equal(result, [var 1, 2, 3, 4, 5, 6], Nat.equal);

Runtime: O(size1 + size2)

Space: O(size1 + size2)

public func sort<T>(array : [var T], compare : (T, T) -> Order.Order) : [var T]

Creates a new sorted copy of the mutable array according to compare. Sort is deterministic and stable.

motoko include=import
import Nat "mo:base/Nat";

let array = [var 4, 2, 6];
let sorted = VarArray.sort(array, Nat.compare);
assert VarArray.equal(sorted, [var 2, 4, 6], Nat.equal);

Runtime: O(size * log(size))

Space: O(size) *Runtime and space assumes that compare runs in O(1) time and space.

public func sortInPlace<T>(array : [var T], compare : (T, T) -> Order.Order) : ()

Sorts the elements in a mutable array in place according to compare. Sort is deterministic and stable. This modifies the original array.

motoko include=import
import Nat "mo:base/Nat";

let array = [var 4, 2, 6];
VarArray.sortInPlace(array, Nat.compare);
assert VarArray.equal(array, [var 2, 4, 6], Nat.equal);

Runtime: O(size * log(size))

Space: O(size) *Runtime and space assumes that compare runs in O(1) time and space.

public func reverse<T>(array : [var T]) : [var T]

Creates a new mutable array by reversing the order of elements in array. The original array is not modified.

motoko include=import
import Nat "mo:base/Nat";

let array = [var 10, 11, 12];
let reversed = VarArray.reverse(array);
assert VarArray.equal(reversed, [var 12, 11, 10], Nat.equal);

Runtime: O(size)

Space: O(1)

public func reverseInPlace<T>(array : [var T]) : ()

Reverses the order of elements in a mutable array in place. This modifies the original array.

motoko include=import
import Nat "mo:base/Nat";

let array = [var 10, 11, 12];
VarArray.reverseInPlace(array);
assert VarArray.equal(array, [var 12, 11, 10], Nat.equal);

Runtime: O(size)

Space: O(1)

public func forEach<T>(array : [var T], f : T -> ())

Calls f with each element in array. Retains original ordering of elements.

motoko include=import
var sum = 0;
let array = [var 0, 1, 2, 3];
VarArray.forEach<Nat>(array, func(x) {
  sum += x;
});
assert sum == 6;

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func map<T, R>(array : [var T], f : T -> R) : [var R]

Creates a new mutable array by applying f to each element in array. f "maps" each element it is applied to of type T to an element of type R. Retains original ordering of elements.

motoko include=import
import Nat "mo:base/Nat";

let array = [var 0, 1, 2, 3];
let array2 = VarArray.map<Nat, Nat>(array, func x = x * 2);
assert VarArray.equal(array2, [var 0, 2, 4, 6], Nat.equal);

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func mapInPlace<T>(array : [var T], f : T -> T)

Applies f to each element of array in place, retaining the original ordering of elements. This modifies the original array.

motoko include=import
import Nat "mo:base/Nat";

let array = [var 0, 1, 2, 3];
VarArray.mapInPlace<Nat>(array, func x = x * 3);
assert VarArray.equal(array, [var 0, 3, 6, 9], Nat.equal);

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func filter<T>(array : [var T], f : T -> Bool) : [var T]

Creates a new mutable array by applying predicate to every element in array, retaining the elements for which predicate returns true.

motoko include=import
import Nat "mo:base/Nat";

let array = [var 4, 2, 6, 1, 5];
let evenElements = VarArray.filter<Nat>(array, func x = x % 2 == 0);
assert VarArray.equal(evenElements, [var 4, 2, 6], Nat.equal);

Runtime: O(size)

Space: O(size) *Runtime and space assumes that predicate runs in O(1) time and space.

public func filterMap<T, R>(array : [var T], f : T -> ?R) : [var R]

Creates a new mutable array by applying f to each element in array, and keeping all non-null elements. The ordering is retained.

motoko include=import
import Nat "mo:base/Nat";
import Text "mo:base/Text";

let array = [var 4, 2, 0, 1];
let newArray =
  VarArray.filterMap<Nat, Text>( // mapping from Nat to Text values
    array,
    func x = if (x == 0) { null } else { ?Nat.toText(100 / x) } // can't divide by 0, so return null
  );
assert VarArray.equal(newArray, [var "25", "50", "100"], Text.equal);

Runtime: O(size)

Space: O(size) *Runtime and space assumes that f runs in O(1) time and space.

public func mapResult<T, R, E>(array : [var T], f : T -> Result.Result<R, E>) : Result.Result<[var R], E>

Creates a new mutable array by applying f to each element in array. If any invocation of f produces an #err, returns an #err. Otherwise returns an #ok containing the new array.

motoko include=import
import Result "mo:base/Result";

let array = [var 4, 3, 2, 1, 0];
// divide 100 by every element in the array
let result = VarArray.mapResult<Nat, Nat, Text>(array, func x {
  if (x > 0) {
    #ok(100 / x)
  } else {
    #err "Cannot divide by zero"
  }
});
assert Result.isErr(result);

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func mapEntries<T, R>(array : [var T], f : (T, Nat) -> R) : [var R]

Creates a new array by applying f to each element in array and its index. Retains original ordering of elements.

motoko include=import
import Nat "mo:base/Nat";

let array = [var 10, 10, 10, 10];
let newArray = VarArray.mapEntries<Nat, Nat>(array, func (x, i) = i * x);
assert VarArray.equal(newArray, [var 0, 10, 20, 30], Nat.equal);

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func flatMap<T, R>(array : [var T], k : T -> Types.Iter<R>) : [var R]

Creates a new mutable array by applying k to each element in array, and concatenating the resulting arrays in order.

motoko include=import
import Int "mo:base/Int"

let array = [var 1, 2, 3, 4];
let newArray = VarArray.flatMap<Nat, Int>(array, func x = [x, -x].vals());
assert VarArray.equal(newArray, [var 1, -1, 2, -2, 3, -3, 4, -4], Int.equal);

Runtime: O(size)

Space: O(size) *Runtime and space assumes that k runs in O(1) time and space.

public func foldLeft<T, A>(
  array : [var T],
  base : A,
  combine : (A, T) -> A
) : A

Collapses the elements in array into a single value by starting with base and progessively combining elements into base with combine. Iteration runs left to right.

motoko include=import
import {add} "mo:base/Nat";

let array = [var 4, 2, 0, 1];
let sum =
  VarArray.foldLeft<Nat, Nat>(
    array,
    0, // start the sum at 0
    func(sumSoFar, x) = sumSoFar + x // this entire function can be replaced with `add`!
  );
assert sum == 7;

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that combine runs in O(1) time and space.

public func foldRight<T, A>(
  array : [var T],
  base : A,
  combine : (T, A) -> A
) : A

Collapses the elements in array into a single value by starting with base and progessively combining elements into base with combine. Iteration runs right to left.

motoko include=import
import {toText} "mo:base/Nat";

let array = [var 1, 9, 4, 8];
let bookTitle = VarArray.foldRight<Nat, Text>(array, "", func(x, acc) = toText(x) # acc);
assert bookTitle == "1948";

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that combine runs in O(1) time and space.

public func join<T>(arrays : Types.Iter<[var T]>) : [var T]

Combines an iterator of mutable arrays into a single mutable array. Retains the original ordering of the elements.

Consider using VarArray.flatten() for better performance.

motoko include=import
import Nat "mo:base/Nat";

let arrays : [[var Nat]] = [[var 0, 1, 2], [var 2, 3], [var], [var 4]];
let joinedArray = VarArray.join<Nat>(arrays.vals());
assert VarArray.equal(joinedArray, [var 0, 1, 2, 2, 3, 4], Nat.equal);

Runtime: O(number of elements in array)

Space: O(number of elements in array)

public func flatten<T>(arrays : [var [var T]]) : [var T]

Combines a mutable array of mutable arrays into a single mutable array. Retains the original ordering of the elements.

This has better performance compared to VarArray.join().

motoko include=import
import Nat "mo:base/Nat";

let arrays : [var [var Nat]] = [var [var 0, 1, 2], [var 2, 3], [var], [var 4]];
let flatArray = VarArray.flatten<Nat>(arrays);
assert VarArray.equal(flatArray, [var 0, 1, 2, 2, 3, 4], Nat.equal);

Runtime: O(number of elements in array)

Space: O(number of elements in array)

public func singleton<T>(element : T) : [var T]

Create an array containing a single value.

motoko include=import
import Nat "mo:base/Nat";

let array = VarArray.singleton<Nat>(2);
assert VarArray.equal(array, [var 2], Nat.equal);

Runtime: O(1)

Space: O(1)

public func size<T>(array : [var T]) : Nat

Returns the size of a mutable array. Equivalent to array.size().

public func isEmpty<T>(array : [var T]) : Bool

Returns whether a mutable array is empty, i.e. contains zero elements.

public func fromIter<T>(iter : Types.Iter<T>) : [var T]

Converts an iterator to a mutable array.

public func keys<T>(array : [var T]) : Types.Iter<Nat>

Returns an iterator (Iter) over the indices of array. An iterator provides a single method next(), which returns indices in order, or null when out of index to iterate over.

NOTE: You can also use array.keys() instead of this function. See example below.

motoko include=import
let array = [var 10, 11, 12];

var sum = 0;
for (element in array.keys()) {
  sum += element;
};
assert sum == 3; // 0 + 1 + 2

Runtime: O(1)

Space: O(1)

public func values<T>(array : [var T]) : Types.Iter<T>

Iterator provides a single method next(), which returns elements in order, or null when out of elements to iterate over.

Note: You can also use array.values() instead of this function. See example below.

motoko include=import
let array = [var 10, 11, 12];

var sum = 0;
for (element in array.values()) {
  sum += element;
};
assert sum == 33; // 10 + 11 + 12

Runtime: O(1)

Space: O(1)

public func enumerate<T>(array : [var T]) : Types.Iter<(Nat, T)>

Returns an iterator that provides pairs of (index, element) in order, or null when out of elements to iterate over.

motoko include=import
let array = [var 10, 11, 12];

var sum = 0;
for ((index, element) in VarArray.enumerate(array)) {
  sum += element;
};
assert sum == 33;

Runtime: O(1)

Space: O(1)

public func all<T>(array : [var T], predicate : T -> Bool) : Bool

Returns true if all elements in array satisfy the predicate function.

motoko include=import
let array = [var 1, 2, 3, 4];
assert VarArray.all<Nat>(array, func x = x > 0);

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that predicate runs in O(1) time and space.

public func any<T>(array : [var T], predicate : T -> Bool) : Bool

Returns true if any element in array satisfies the predicate function.

motoko include=import
let array = [var 1, 2, 3, 4];
assert VarArray.any<Nat>(array, func x = x > 3);

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that predicate runs in O(1) time and space.

public func indexOf<T>(
  element : T,
  array : [var T],
  equal : (T, T) -> Bool
) : ?Nat

Returns the index of the first element in the array.

motoko include=import
import Char "mo:base/Char";

let array = [var 'c', 'o', 'f', 'f', 'e', 'e'];
assert VarArray.indexOf<Char>('c', array, Char.equal) == ?0;
assert VarArray.indexOf<Char>('f', array, Char.equal) == ?2;
assert VarArray.indexOf<Char>('g', array, Char.equal) == null;

Runtime: O(array.size())

Space: O(1)

public func nextIndexOf<T>(
  element : T,
  array : [var T],
  fromInclusive : Nat,
  equal : (T, T) -> Bool
) : ?Nat

Returns the index of the next occurence of element in the array starting from the from index (inclusive).

motoko include=import
import Char "mo:base/Char";

let array = [var 'c', 'o', 'f', 'f', 'e', 'e'];
assert VarArray.nextIndexOf<Char>('c', array, 0, Char.equal) == ?0;
assert VarArray.nextIndexOf<Char>('f', array, 0, Char.equal) == ?2;
assert VarArray.nextIndexOf<Char>('f', array, 2, Char.equal) == ?2;
assert VarArray.nextIndexOf<Char>('f', array, 3, Char.equal) == ?3;
assert VarArray.nextIndexOf<Char>('f', array, 4, Char.equal) == null;

Runtime: O(array.size())

Space: O(1)

public func lastIndexOf<T>(
  element : T,
  array : [var T],
  equal : (T, T) -> Bool
) : ?Nat

Returns the index of the last element in the array.

motoko include=import
import Char "mo:base/Char";

let array = [var 'c', 'o', 'f', 'f', 'e', 'e'];
assert VarArray.lastIndexOf<Char>('c', array, Char.equal) == ?0;
assert VarArray.lastIndexOf<Char>('f', array, Char.equal) == ?3;
assert VarArray.lastIndexOf<Char>('e', array, Char.equal) == ?5;
assert VarArray.lastIndexOf<Char>('g', array, Char.equal) == null;

Runtime: O(array.size())

Space: O(1)

public func prevIndexOf<T>(
  element : T,
  array : [var T],
  fromExclusive : Nat,
  equal : (T, T) -> Bool
) : ?Nat

Returns the index of the previous occurence of element in the array starting from the from index (exclusive).

motoko include=import
import Char "mo:base/Char";
let array = [var 'c', 'o', 'f', 'f', 'e', 'e'];
assert VarArray.prevIndexOf<Char>('c', array, array.size(), Char.equal) == ?0;
assert VarArray.prevIndexOf<Char>('e', array, array.size(), Char.equal) == ?5;
assert VarArray.prevIndexOf<Char>('e', array, 5, Char.equal) == ?4;
assert VarArray.prevIndexOf<Char>('e', array, 4, Char.equal) == null;

Runtime: O(array.size()); Space: O(1);

public func range<T>(
  array : [var T],
  fromInclusive : Int,
  toExclusive : Int
) : Types.Iter<T>

Returns an iterator over a slice of array starting at fromInclusive up to (but not including) toExclusive.

Negative indices are relative to the end of the array. For example, -1 corresponds to the last element in the array.

If the indices are out of bounds, they are clamped to the array bounds. If the first index is greater than the second, the function returns an empty iterator.

motoko include=import
let array = [var 1, 2, 3, 4, 5];
let iter1 = VarArray.range<Nat>(array, 3, array.size());
assert iter1.next() == ?4;
assert iter1.next() == ?5;
assert iter1.next() == null;

let iter2 = VarArray.range<Nat>(array, 3, -1);
assert iter2.next() == ?4;
assert iter2.next() == null;

let iter3 = VarArray.range<Nat>(array, 0, 0);
assert iter3.next() == null;

Runtime: O(1)

Space: O(1)

public func sliceToArray<T>(
  array : [var T],
  fromInclusive : Int,
  toExclusive : Int
) : [T]

Returns a new array containing elements from array starting at index fromInclusive up to (but not including) index toExclusive. If the indices are out of bounds, they are clamped to the array bounds.

motoko include=import
let array = [var 1, 2, 3, 4, 5];

let slice1 = VarArray.sliceToArray<Nat>(array, 1, 4);
assert slice1 == [2, 3, 4];

let slice2 = VarArray.sliceToArray<Nat>(array, 1, -1);
assert slice2 == [2, 3, 4];

Runtime: O(toExclusive - fromInclusive)

Space: O(toExclusive - fromInclusive)

public func toText<T>(array : [var T], f : T -> Text) : Text

Converts the mutable array to its textual representation using f to convert each element to Text.

motoko include=import
import Nat "mo:base/Nat";

let array = [var 1, 2, 3];
assert VarArray.toText<Nat>(array, Nat.toText) == "[var 1, 2, 3]";

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func compare<T>(
  array1 : [var T],
  array2 : [var T],
  compare : (T, T) -> Order.Order
) : Order.Order

Compares two mutable arrays using the provided comparison function for elements. Returns #less, #equal, or #greater if array1 is less than, equal to, or greater than array2 respectively.

If arrays have different sizes but all elements up to the shorter length are equal, the shorter array is considered #less than the longer array.

motoko include=import
import Nat "mo:base/Nat";
let array1 = [var 1, 2, 3];
let array2 = [var 1, 2, 4];
assert VarArray.compare<Nat>(array1, array2, Nat.compare) == #less;

let array3 = [var 1, 2];
let array4 = [var 1, 2, 3];
assert VarArray.compare<Nat>(array3, array4, Nat.compare) == #less;

Runtime: O(min(size1, size2))

Space: O(1)

*Runtime and space assumes that compare runs in O(1) time and space.