Buffer

Class Buffer<X> provides a mutable list of elements of type X. It wraps a resizable underlying array and is comparable to ArrayList or Vector in other languages.

You can convert a buffer to a fixed-size array using Buffer.toArray, which is recommended for storing data in stable variables.

Like arrays, buffer elements are indexed from 0 to size - 1.

[Assumptions]

Runtime and space complexity assumes that combine, equal, and other functions execute in O(1) time and space.

[Size vs capacity]

size: Number of elements in the buffer.
capacity: Length of the underlying array.

The invariant capacity >= size always holds.

[Performance caveat]

Operations like add are amortized O(1) but can take O(n) in the worst case. For large buffers, these worst cases may exceed the cycle limit per message. Use with care when growing buffers dynamically.

[Constructor behavior]

The initCapacity argument sets the initial capacity of the underlying array.

When the capacity is exceeded, the array grows by a factor of 1.5.
When the buffer size drops below 1/4 of the capacity, it shrinks by a factor of 2.

Example:

import Buffer "mo:base/Buffer";

let buffer = Buffer.Buffer<Nat>(3); // Creates a new Buffer

Runtime	Space
`O(initCapacity)`	`O(initCapacity)`

Class `Buffer<X>`

class Buffer<X>(initCapacity : Nat)

Function `size`

func size() : Nat

Returns the current number of elements in the buffer.

Example:

buffer.size() // => 0

Runtime	Space
`O(1)`	`O(1)`

Function `add`

func add(element : X)

Adds a single element to the end of the buffer, doubling the size of the array if capacity is exceeded.

Example:

buffer.add(0); // add 0 to buffer
buffer.add(1);
buffer.add(2);
buffer.add(3); // causes underlying array to increase in capacity
Buffer.toArray(buffer) // => [0, 1, 2, 3]

Runtime (worst)	Runtime (amortized)	Space (worst)	Space (amortized)
`O(size)`	`O(1)`	`O(size)`	`O(1)`

Function `get`

func get(index : Nat) : X

Returns the element at index index. Traps if index >= size. Indexing is zero-based.

Example:

buffer.add(10);
buffer.add(11);
buffer.get(0); // => 10

Runtime	Space
`O(1)`	`O(1)`

Function `getOpt`

func getOpt(index : Nat) : ?X

Returns the element at index index as an option. Returns null when index >= size. Indexing is zero-based.

Example:

buffer.add(10);
buffer.add(11);
let x = buffer.getOpt(0); // => ?10
let y = buffer.getOpt(2); // => null

Runtime	Space
`O(1)`	`O(1)`

Function `put`

func put(index : Nat, element : X)

buffer.add(10); buffer.put(0, 20); // overwrites 10 at index 0 with 20 Buffer.toArray(buffer) // => [20]

| Runtime   | Space     |
|-----------|-----------|
| `O(1)` | `O(1)` |


### Function `removeLast`
``` motoko no-repl
func removeLast() : ?X

Removes and returns the last item in the buffer or null if the buffer is empty.

Example:

buffer.add(10);
buffer.add(11);
buffer.removeLast(); // => ?11

Runtime (worst)	Runtime (amortized)	Space (worst)	Space (amortized)
`O(size)`	`O(1)`	`O(size)`	`O(1)`

Function `remove`

func remove(index : Nat) : X

Removes and returns the element at index from the buffer. All elements with index > index are shifted one position to the left. This may cause a downsizing of the array.

Traps if index >= size.

[Inefficient pattern]

Repeated removal of elements using this method is inefficient and may indicate that a different data structure would better suit your use case.

Example:

buffer.add(10);
buffer.add(11);
buffer.add(12);
let x = buffer.remove(1); // evaluates to 11. 11 no longer in list.
Buffer.toArray(buffer) // => [10, 12]

Runtime (worst)	Runtime (amortized)	Space (worst)	Space (amortized)
`O(size)`	-	`O(size)`	`O(1)`

Function `clear`

func clear()

Resets the buffer. Capacity is set to 8.

Example:

buffer.add(10);
buffer.add(11);
buffer.add(12);
buffer.clear(); // buffer is now empty
Buffer.toArray(buffer) // => []

Runtime	Space
`O(1)`	`O(1)`

Function `filterEntries`

func filterEntries(predicate : (Nat, X) -> Bool)

Removes all elements from the buffer for which the predicate returns false. The predicate is given both the index of the element and the element itself. This may cause a downsizing of the array.

Example:

buffer.add(10);
buffer.add(11);
buffer.add(12);
buffer.filterEntries(func(_, x) = x % 2 == 0); // only keep even elements
Buffer.toArray(buffer) // => [10, 12]

Runtime (worst)	Runtime (amortized)	Space (worst)	Space (amortized)
`O(size)`	-	`O(size)`	`O(1)`

Function `capacity`

func capacity() : Nat

Returns the capacity of the buffer (the length of the underlying array).

Example:

let buffer = Buffer.Buffer<Nat>(2); // underlying array has capacity 2
buffer.add(10);
let c1 = buffer.capacity(); // => 2
buffer.add(11);
buffer.add(12); // causes capacity to increase by factor of 1.5
let c2 = buffer.capacity(); // => 3

Runtime	Space
`O(1)`	`O(1)`

Function `reserve`

func reserve(capacity : Nat)

Changes the capacity to capacity. Traps if capacity < size.

buffer.reserve(4);
buffer.add(10);
buffer.add(11);
buffer.capacity(); // => 4

Runtime	Space
`O(capacity)`	`O(capacity)`

Function `append`

func append(buffer2 : Buffer<X>)

Adds all elements in buffer b to this buffer.

let buffer1 = Buffer.Buffer<Nat>(2);
let buffer2 = Buffer.Buffer<Nat>(2);
buffer1.add(10);
buffer1.add(11);
buffer2.add(12);
buffer2.add(13);
buffer1.append(buffer2); // adds elements from buffer2 to buffer1
Buffer.toArray(buffer1) // => [10, 11, 12, 13]

Runtime (worst)	Runtime (amortized)	Space (worst)	Space (amortized)
`O(size1 + size2)`	`O(size2)`	`O(size1 +size2)`	`O(1)`

Function `insert`

func insert(index : Nat, element : X)

Inserts element at index, shifts all elements to the right of index over by one index. Traps if index is greater than size.

let buffer1 = Buffer.Buffer<Nat>(2);
let buffer2 = Buffer.Buffer<Nat>(2);
buffer.add(10);
buffer.add(11);
buffer.insert(1, 9);
Buffer.toArray(buffer) // => [10, 9, 11]

Runtime (worst)	Runtime (amortized)	Space (worst)	Space (amortized)
`O(size)`	-	`O(size)`	`O(1)`

Function `insertBuffer`

func insertBuffer(index : Nat, buffer2 : Buffer<X>)

Inserts buffer2 at index, and shifts all elements to the right of index over by size2. Traps if index is greater than size.

let buffer1 = Buffer.Buffer<Nat>(2);
let buffer2 = Buffer.Buffer<Nat>(2);
buffer1.add(10);
buffer1.add(11);
buffer2.add(12);
buffer2.add(13);
buffer1.insertBuffer(1, buffer2);
Buffer.toArray(buffer1) // => [10, 12, 13, 11]

Runtime (worst)	Runtime (amortized)	Space (worst)	Space (amortized)
`O(size)`	-	`O(size1 +size2)`	`O(1)`

Function `sort`

func sort(compare : (X, X) -> Order.Order)

Sorts the elements in the buffer according to compare. Sort is deterministic, stable, and in-place.

import Nat "mo:base/Nat";

buffer.add(11);
buffer.add(12);
buffer.add(10);
buffer.sort(Nat.compare);
Buffer.toArray(buffer) // => [10, 11, 12]

Runtime	Space
`O(size * log(size))`	`O(size)`

Function `vals`

func vals() : { next : () -> ?X }

Returns an Iterator (Iter) over the elements of this buffer. Iterator provides a single method next(), which returns elements in order, or null when out of elements to iterate over.

buffer.add(10);
buffer.add(11);
buffer.add(12);

var sum = 0;
for (element in buffer.vals()) {
  sum += element;
};
sum // => 33

Runtime	Space
`O(1)`	`O(1)`

Function `clone`

func clone() : Buffer<X>

[Deprecated function]

Use the static library function instead of this instance method.

Function `toArray`

func toArray() : [X]

[Deprecated function]

Use the static library function instead of this instance method.

Function `toVarArray`

func toVarArray() : [var X]

[Deprecated function]

Use the static library function instead of this instance method.

Function `isEmpty`

func isEmpty<X>(buffer : Buffer<X>) : Bool

Returns true if and only if the buffer is empty.

Example:

buffer.add(2);
buffer.add(0);
buffer.add(3);
Buffer.isEmpty(buffer); // => false

Buffer.isEmpty(buffer); // => true

Runtime	Space
`O(1)`	`O(1)`

Function `contains`

func contains<X>(buffer : Buffer<X>, element : X, equal : (X, X) -> Bool) : Bool

Returns true if buffer contains element with respect to equality defined by equal.

Example:

import Nat "mo:base/Nat";

buffer.add(2);
buffer.add(0);
buffer.add(3);
Buffer.contains<Nat>(buffer, 2, Nat.equal); // => true

Runtime	Space
`O(size)`	`O(1)`

Function `clone`

func clone<X>(buffer : Buffer<X>) : Buffer<X>

Returns a copy of buffer, with the same capacity.

Example:

buffer.add(1);

let clone = Buffer.clone(buffer);
Buffer.toArray(clone); // => [1]

Runtime	Space
`O(size)`	`O(size)`

Function `max`

func max<X>(buffer : Buffer<X>, compare : (X, X) -> Order) : ?X

Finds the greatest element in buffer defined by compare. Returns null if buffer is empty.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);

Buffer.max(buffer, Nat.compare); // => ?2

Runtime	Space
`O(size)`	`O(1)`

Function `min`

func min<X>(buffer : Buffer<X>, compare : (X, X) -> Order) : ?X

Finds the least element in buffer defined by compare. Returns null if buffer is empty.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);

Buffer.min(buffer, Nat.compare); // => ?1

Runtime	Space
`O(size)`	`O(1)`

Function `equal`

func equal<X>(buffer1 : Buffer<X>, buffer2 : Buffer<X>, equal : (X, X) -> Bool) : Bool

Defines equality for two buffers, using equal to recursively compare elements in the buffers. Returns true if the two buffers are of the same size, and equal evaluates to true for every pair of elements in the two buffers of the same index.

Example:

import Nat "mo:base/Nat";

let buffer1 = Buffer.Buffer<Nat>(2);
buffer1.add(1);
buffer1.add(2);

let buffer2 = Buffer.Buffer<Nat>(5);
buffer2.add(1);
buffer2.add(2);

Buffer.equal(buffer1, buffer2, Nat.equal); // => true

Runtime	Space
`O(size)`	`O(1)`

Function `compare`

func compare<X>(buffer1 : Buffer<X>, buffer2 : Buffer<X>, compare : (X, X) -> Order.Order) : Order.Order

Defines comparison for two buffers, using compare to recursively compare elements in the buffers. Comparison is defined lexicographically.

Example:

import Nat "mo:base/Nat";

let buffer1 = Buffer.Buffer<Nat>(2);
buffer1.add(1);
buffer1.add(2);

let buffer2 = Buffer.Buffer<Nat>(3);
buffer2.add(3);
buffer2.add(4);

Buffer.compare<Nat>(buffer1, buffer2, Nat.compare); // => #less

Runtime	Space
`O(size)`	`O(1)`

Function `toText`

func toText<X>(buffer : Buffer<X>, toText : X -> Text) : Text

Creates a textual representation of buffer, using toText to recursively convert the elements into Text.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);

Buffer.toText(buffer, Nat.toText); // => "[1, 2, 3, 4]"

Runtime	Space
`O(size)`	`O(size)`

Function `hash`

func hash<X>(buffer : Buffer<X>, hash : X -> Nat32) : Nat32

Hashes buffer using hash to hash the underlying elements. The deterministic hash function is a function of the elements in the buffer, as well as their ordering.

Example:

import Hash "mo:base/Hash";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(1000);

Buffer.hash<Nat>(buffer, Hash.hash); // => 2_872_640_342

Runtime	Space
`O(size)`	`O(1)`

Function `indexOf`

func indexOf<X>(element : X, buffer : Buffer<X>, equal : (X, X) -> Bool) : ?Nat

Finds the first index of element in buffer using equality of elements defined by equal. Returns null if element is not found.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);

Buffer.indexOf<Nat>(3, buffer, Nat.equal); // => ?2

Runtime	Space
`O(size)`	`O(size)`

Function `lastIndexOf`

func lastIndexOf<X>(element : X, buffer : Buffer<X>, equal : (X, X) -> Bool) : ?Nat

Finds the last index of element in buffer using equality of elements defined by equal. Returns null if element is not found.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);
buffer.add(2);
buffer.add(2);

Buffer.lastIndexOf<Nat>(2, buffer, Nat.equal); // => ?5

Runtime	Space
`O(size)`	`O(size)`

Function `indexOfBuffer`

func indexOfBuffer<X>(subBuffer : Buffer<X>, buffer : Buffer<X>, equal : (X, X) -> Bool) : ?Nat

Searches for subBuffer in buffer, and returns the starting index if it is found.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);
buffer.add(5);
buffer.add(6);

let sub = Buffer.Buffer<Nat>(2);
sub.add(4);
sub.add(5);
sub.add(6);

Buffer.indexOfBuffer<Nat>(sub, buffer, Nat.equal); // => ?3

Runtime	Space
`O(size of buffer + size of subBuffer)`	`O(size of subBuffer)`

Function `binarySearch`

func binarySearch<X>(element : X, buffer : Buffer<X>, compare : (X, X) -> Order.Order) : ?Nat

Similar to indexOf, but runs in logarithmic time. Assumes that buffer is sorted. Behavior is undefined if buffer is not sorted. Uses compare to perform the search. Returns an index of element if it is found.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(4);
buffer.add(5);
buffer.add(6);

Buffer.binarySearch<Nat>(5, buffer, Nat.compare); // => ?2

Runtime	Space
`O(log(size))`	`O(1)`

Function `subBuffer`

func subBuffer<X>(buffer : Buffer<X>, start : Nat, length : Nat) : Buffer<X>

Returns the sub-buffer of buffer starting at index start of length length. Traps if start is out of bounds, or start + length is greater than the size of buffer.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);
buffer.add(5);
buffer.add(6);

let sub = Buffer.subBuffer(buffer, 3, 2);
Buffer.toText(sub, Nat.toText); // => [4, 5]

Runtime	Space
`O(length)`	`O(length)`

Function `isSubBufferOf`

func isSubBufferOf<X>(subBuffer : Buffer<X>, buffer : Buffer<X>, equal : (X, X) -> Bool) : Bool

Checks if subBuffer is a sub-Buffer of buffer. Uses equal to compare elements.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);
buffer.add(5);
buffer.add(6);

let sub = Buffer.Buffer<Nat>(2);
sub.add(2);
sub.add(3);
Buffer.isSubBufferOf(sub, buffer, Nat.equal); // => true

Runtime	Space
`O(size of subBuffer + size of buffer)`	`O(size of subBuffer)`

Function `isStrictSubBufferOf`

func isStrictSubBufferOf<X>(subBuffer : Buffer<X>, buffer : Buffer<X>, equal : (X, X) -> Bool) : Bool

Checks if subBuffer is a strict subBuffer of buffer, i.e. subBuffer must be strictly contained inside both the first and last indices of buffer. Uses equal to compare elements.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);

let sub = Buffer.Buffer<Nat>(2);
sub.add(2);
sub.add(3);
Buffer.isStrictSubBufferOf(sub, buffer, Nat.equal); // => true

Runtime	Space
`O(size of subBuffer + size of buffer)`	`O(size of subBuffer)`

Function `prefix`

func prefix<X>(buffer : Buffer<X>, length : Nat) : Buffer<X>

Returns the prefix of buffer of length length. Traps if length is greater than the size of buffer.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);

let pre = Buffer.prefix(buffer, 3); // => [1, 2, 3]
Buffer.toText(pre, Nat.toText);

Runtime	Space
`O(length)`	`O(length)`

Function `isPrefixOf`

func isPrefixOf<X>(prefix : Buffer<X>, buffer : Buffer<X>, equal : (X, X) -> Bool) : Bool

Checks if prefix is a prefix of buffer. Uses equal to compare elements.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);

let pre = Buffer.Buffer<Nat>(2);
pre.add(1);
pre.add(2);
Buffer.isPrefixOf(pre, buffer, Nat.equal); // => true

Runtime	Space
`O(size of prefix)`	`O(size of prefix)`

Function `isStrictPrefixOf`

func isStrictPrefixOf<X>(prefix : Buffer<X>, buffer : Buffer<X>, equal : (X, X) -> Bool) : Bool

Checks if prefix is a strict prefix of buffer. Uses equal to compare elements.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);

let pre = Buffer.Buffer<Nat>(3);
pre.add(1);
pre.add(2);
pre.add(3);
Buffer.isStrictPrefixOf(pre, buffer, Nat.equal); // => true

Runtime	Space
`O(size of prefix)`	`O(size of prefix)`

Function `suffix`

func suffix<X>(buffer : Buffer<X>, length : Nat) : Buffer<X>

Returns the suffix of buffer of length length. Traps if lengthis greater than the size of buffer.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);

let suf = Buffer.suffix(buffer, 3); // => [2, 3, 4]
Buffer.toText(suf, Nat.toText);

Runtime	Space
`O(length)`	`O(length)`

Function `isSuffixOf`

func isSuffixOf<X>(suffix : Buffer<X>, buffer : Buffer<X>, equal : (X, X) -> Bool) : Bool

Checks if suffix is a suffix of buffer. Uses equal to compare elements.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);

let suf = Buffer.Buffer<Nat>(3);
suf.add(2);
suf.add(3);
suf.add(4);
Buffer.isSuffixOf(suf, buffer, Nat.equal); // => true

Runtime	Space
`O(length of suffix)`	`O(length of suffix)`

Function `isStrictSuffixOf`

func isStrictSuffixOf<X>(suffix : Buffer<X>, buffer : Buffer<X>, equal : (X, X) -> Bool) : Bool

Checks if suffix is a strict suffix of buffer. Uses equal to compare elements.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);

let suf = Buffer.Buffer<Nat>(3);
suf.add(2);
suf.add(3);
suf.add(4);
Buffer.isStrictSuffixOf(suf, buffer, Nat.equal); // => true

Runtime	Space
`O(length)`	`O(length)`

Function `forAll`

func forAll<X>(buffer : Buffer<X>, predicate : X -> Bool) : Bool

Returns true if every element in buffer satisfies predicate.

Example:

buffer.add(2);
buffer.add(3);
buffer.add(4);

Buffer.forAll<Nat>(buffer, func x { x > 1 }); // => true

Runtime	Space
`O(size)`	`O(1)`

Function `forSome`

func forSome<X>(buffer : Buffer<X>, predicate : X -> Bool) : Bool

Returns true if some element in buffer satisfies predicate.

Example:

buffer.add(2);
buffer.add(3);
buffer.add(4);

Buffer.forSome<Nat>(buffer, func x { x > 3 }); // => true

Runtime	Space
`O(size)`	`O(1)`

Function `forNone`

func forNone<X>(buffer : Buffer<X>, predicate : X -> Bool) : Bool

Returns true if no element in buffer satisfies predicate.

Example:

buffer.add(2);
buffer.add(3);
buffer.add(4);

Buffer.forNone<Nat>(buffer, func x { x == 0 }); // => true

Runtime	Space
`O(size)`	`O(1)`

Function `toArray`

func toArray<X>(buffer : Buffer<X>) : [X]

Creates an array containing elements from buffer.

Example:

buffer.add(1);
buffer.add(2);
buffer.add(3);

Buffer.toArray<Nat>(buffer); // => [1, 2, 3]

Runtime	Space
`O(size)`	`O(size)`

Function `toVarArray`

func toVarArray<X>(buffer : Buffer<X>) : [var X]

Creates a mutable array containing elements from buffer.

Example:

buffer.add(1);
buffer.add(2);
buffer.add(3);

Buffer.toVarArray<Nat>(buffer); // => [1, 2, 3]

Runtime	Space
`O(size)`	`O(size)`

Function `fromArray`

func fromArray<X>(array : [X]) : Buffer<X>

Creates a buffer containing elements from array.

Example:

import Nat "mo:base/Nat";

let array = [2, 3];

let buf = Buffer.fromArray<Nat>(array); // => [2, 3]
Buffer.toText(buf, Nat.toText);

Runtime	Space
`O(size)`	`O(size)`

Function `fromVarArray`

func fromVarArray<X>(array : [var X]) : Buffer<X>

Creates a buffer containing elements from array.

Example:

import Nat "mo:base/Nat";

let array = [var 1, 2, 3];

let buf = Buffer.fromVarArray<Nat>(array); // => [1, 2, 3]
Buffer.toText(buf, Nat.toText);

Runtime	Space
`O(size)`	`O(size)`

Function `fromIter`

func fromIter<X>(iter : { next : () -> ?X }) : Buffer<X>

Creates a buffer containing elements from iter.

Example:

import Nat "mo:base/Nat";

let array = [1, 1, 1];
let iter = array.vals();

let buf = Buffer.fromIter<Nat>(iter); // => [1, 1, 1]
Buffer.toText(buf, Nat.toText);

Runtime	Space
`O(size)`	`O(size)`

Function `trimToSize`

func trimToSize<X>(buffer : Buffer<X>)

Reallocates the array underlying buffer such that capacity == size.

Example:

let buffer = Buffer.Buffer<Nat>(10);
buffer.add(1);
buffer.add(2);
buffer.add(3);

Buffer.trimToSize<Nat>(buffer);
buffer.capacity(); // => 3

Runtime	Space
`O(size)`	`O(size)`

Function `map`

func map<X, Y>(buffer : Buffer<X>, f : X -> Y) : Buffer<Y>

Creates a new buffer by applying f to each element in buffer.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);

let newBuf = Buffer.map<Nat, Nat>(buffer, func (x) { x + 1 });
Buffer.toText(newBuf, Nat.toText); // => [2, 3, 4]

Runtime	Space
`O(size)`	`O(size)`

Function `iterate`

func iterate<X>(buffer : Buffer<X>, f : X -> ())

Applies f to each element in buffer.

Example:

import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

buffer.add(1);
buffer.add(2);
buffer.add(3);

Buffer.iterate<Nat>(buffer, func (x) {
  Debug.print(Nat.toText(x)); // prints each element in buffer
});

Runtime	Space
`O(size)`	`O(size)`

Function `mapEntries`

func mapEntries<X, Y>(buffer : Buffer<X>, f : (Nat, X) -> Y) : Buffer<Y>

Applies f to each element in buffer and its index.

Example:

import Nat "mo:base/Nat";
buffer.add(1);
buffer.add(2);
buffer.add(3);

let newBuf = Buffer.mapEntries<Nat, Nat>(buffer, func (x, i) { x + i + 1 });
Buffer.toText(newBuf, Nat.toText); // => [2, 4, 6]

Runtime	Space
`O(size)`	`O(size)`

Function `mapFilter`

func mapFilter<X, Y>(buffer : Buffer<X>, f : X -> ?Y) : Buffer<Y>

Creates a new buffer by applying f to each element in buffer, and keeping all non-null elements.

Example:

import Nat "mo:base/Nat";
buffer.add(1);
buffer.add(2);
buffer.add(3);

let newBuf = Buffer.mapFilter<Nat, Nat>(buffer, func (x) {
  if (x > 1) {
    ?(x * 2);
  } else {
    null;
  }
});
Buffer.toText(newBuf, Nat.toText); // => [4, 6]

Runtime	Space
`O(size)`	`O(size)`

Function `mapResult`

func mapResult<X, Y, E>(buffer : Buffer<X>, f : X -> Result.Result<Y, E>) : Result.Result<Buffer<Y>, E>

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

Example:

import Result "mo:base/Result";
buffer.add(1);
buffer.add(2);
buffer.add(3);

let result = Buffer.mapResult<Nat, Nat, Text>(buffer, func (k) {
  if (k > 0) {
    #ok(k);
  } else {
    #err("One or more elements are zero.");
  }
});

Result.mapOk<Buffer.Buffer<Nat>, [Nat], Text>(result, func buffer = Buffer.toArray(buffer)) // => #ok([1, 2, 3])

Runtime	Space
`O(size)`	`O(size)`

Function `chain`

func chain<X, Y>(buffer : Buffer<X>, k : X -> Buffer<Y>) : Buffer<Y>

Creates a new buffer by applying k to each element in buffer, and concatenating the resulting buffers in order. This operation is similar to what in other functional languages is known as monadic bind.

Example:

import Nat "mo:base/Nat";
buffer.add(1);
buffer.add(2);
buffer.add(3);

let chain = Buffer.chain<Nat, Nat>(buffer, func (x) {
  let b = Buffer.Buffer<Nat>(2);
  b.add(x);
  b.add(x * 2);
  return b;
});
Buffer.toText(chain, Nat.toText); // => [1, 2, 2, 4, 3, 6]

Runtime	Space
`O(size)`	`O(size)`

Function `foldLeft`

func foldLeft<A, X>(buffer : Buffer<X>, base : A, combine : (A, X) -> A) : A

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

Example:

import Nat "mo:base/Nat";
buffer.add(1);
buffer.add(2);
buffer.add(3);

Buffer.foldLeft<Text, Nat>(buffer, "", func (acc, x) { acc # Nat.toText(x)}); // => "123"

Runtime	Space
`O(size)`	`O(1)`

Function `foldRight`

func foldRight<X, A>(buffer : Buffer<X>, base : A, combine : (X, A) -> A) : A

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

Example:

import Nat "mo:base/Nat";
buffer.add(1);
buffer.add(2);
buffer.add(3);

Buffer.foldRight<Nat, Text>(buffer, "", func (x, acc) { Nat.toText(x) # acc }); // => "123"

Runtime	Space
`O(size)`	`O(1)`

Function `first`

func first<X>(buffer : Buffer<X>) : X

Returns the first element of buffer. Traps if buffer is empty.

Example:

buffer.add(1);
buffer.add(2);
buffer.add(3);

Buffer.first(buffer); // => 1

Runtime	Space
`O(1)`	`O(1)`

Function `last`

func last<X>(buffer : Buffer<X>) : X

Returns the last element of buffer. Traps if buffer is empty.

Example:

buffer.add(1);
buffer.add(2);
buffer.add(3);

Buffer.last(buffer); // => 3

Runtime	Space
`O(1)`	`O(1)`

Function `make`

func make<X>(element : X) : Buffer<X>

Returns a new buffer with capacity and size 1, containing element.

Example:

import Nat "mo:base/Nat";

let buffer = Buffer.make<Nat>(1);
Buffer.toText(buffer, Nat.toText); // => [1]

Runtime	Space
`O(1)`	`O(1)`

Function `reverse`

func reverse<X>(buffer : Buffer<X>)

Reverses the order of elements in buffer.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);

Buffer.reverse(buffer);
Buffer.toText(buffer, Nat.toText); // => [3, 2, 1]

Runtime	Space
`O(size)`	`O(1)`

Function `merge`

func merge<X>(buffer1 : Buffer<X>, buffer2 : Buffer<X>, compare : (X, X) -> Order) : Buffer<X>

Merges two sorted buffers into a single sorted buffer, using compare to define the ordering. The final ordering is stable. Behavior is undefined if either buffer1 or buffer2 is not sorted.

Example:

import Nat "mo:base/Nat";

let buffer1 = Buffer.Buffer<Nat>(2);
buffer1.add(1);
buffer1.add(2);
buffer1.add(4);

let buffer2 = Buffer.Buffer<Nat>(2);
buffer2.add(2);
buffer2.add(4);
buffer2.add(6);

let merged = Buffer.merge<Nat>(buffer1, buffer2, Nat.compare);
Buffer.toText(merged, Nat.toText); // => [1, 2, 2, 4, 4, 6]

Runtime	Space
`O(size1 + size2)`	`O(size1 + size2)`

Function `removeDuplicates`

func removeDuplicates<X>(buffer : Buffer<X>, compare : (X, X) -> Order)

Eliminates all duplicate elements in buffer as defined by compare. Elimination is stable with respect to the original ordering of the elements.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(1);
buffer.add(2);
buffer.add(3);

Buffer.removeDuplicates<Nat>(buffer, Nat.compare);
Buffer.toText(buffer, Nat.toText); // => [1, 2, 3]

Runtime	Space
`O(size * log(size))`	`O(size)`

Function `partition`

func partition<X>(buffer : Buffer<X>, predicate : X -> Bool) : (Buffer<X>, Buffer<X>)

Splits buffer into a pair of buffers where all elements in the left buffer satisfy predicate and all elements in the right buffer do not.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);
buffer.add(5);
buffer.add(6);

let partitions = Buffer.partition<Nat>(buffer, func (x) { x % 2 == 0 });
(Buffer.toArray(partitions.0), Buffer.toArray(partitions.1)) // => ([2, 4, 6], [1, 3, 5])

Runtime	Space
`O(size)`	`O(size)`

Function `split`

func split<X>(buffer : Buffer<X>, index : Nat) : (Buffer<X>, Buffer<X>)

Splits the buffer into two buffers at index, where the left buffer contains all elements with indices less than index, and the right buffer contains all elements with indices greater than or equal to index. Traps if index is out of bounds.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);
buffer.add(5);
buffer.add(6);

let split = Buffer.split<Nat>(buffer, 3);
(Buffer.toArray(split.0), Buffer.toArray(split.1)) // => ([1, 2, 3], [4, 5, 6])

Runtime	Space
`O(size)`	`O(size)`

Function `chunk`

func chunk<X>(buffer : Buffer<X>, size : Nat) : Buffer<Buffer<X>>

Breaks up buffer into buffers of size size. The last chunk may have less than size elements if the number of elements is not divisible by the chunk size.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);
buffer.add(5);
buffer.add(6);

let chunks = Buffer.chunk<Nat>(buffer, 3);
Buffer.toText<Buffer.Buffer<Nat>>(chunks, func buf = Buffer.toText(buf, Nat.toText)); // => [[1, 2, 3], [4, 5, 6]]

Runtime	Space
`O(number of elements in buffer)`	`O(number of elements in buffer)`

Function `groupBy`

func groupBy<X>(buffer : Buffer<X>, equal : (X, X) -> Bool) : Buffer<Buffer<X>>

Groups equal and adjacent elements in the list into sub lists.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(2);
buffer.add(4);
buffer.add(5);
buffer.add(5);

let grouped = Buffer.groupBy<Nat>(buffer, func (x, y) { x == y });
Buffer.toText<Buffer.Buffer<Nat>>(grouped, func buf = Buffer.toText(buf, Nat.toText)); // => [[1], [2, 2], [4], [5, 5]]

Runtime	Space
`O(size)`	`O(size)`

Function `flatten`

func flatten<X>(buffer : Buffer<Buffer<X>>) : Buffer<X>

Flattens the buffer of buffers into a single buffer.

Example:

import Nat "mo:base/Nat";

let buffer = Buffer.Buffer<Buffer.Buffer<Nat>>(1);

let inner1 = Buffer.Buffer<Nat>(2);
inner1.add(1);
inner1.add(2);

let inner2 = Buffer.Buffer<Nat>(2);
inner2.add(3);
inner2.add(4);

buffer.add(inner1);
buffer.add(inner2);
// buffer = [[1, 2], [3, 4]]

let flat = Buffer.flatten<Nat>(buffer);
Buffer.toText<Nat>(flat, Nat.toText); // => [1, 2, 3, 4]

Runtime	Space
`O(number of elements in buffer)`	`O(number of elements in buffer)`

Function `zip`

func zip<X, Y>(buffer1 : Buffer<X>, buffer2 : Buffer<Y>) : Buffer<(X, Y)>

Combines the two buffers into a single buffer of pairs, pairing together elements with the same index. If one buffer is longer than the other, the remaining elements from the longer buffer are not included.

Example:

let buffer1 = Buffer.Buffer<Nat>(2);
buffer1.add(1);
buffer1.add(2);
buffer1.add(3);

let buffer2 = Buffer.Buffer<Nat>(2);
buffer2.add(4);
buffer2.add(5);

let zipped = Buffer.zip(buffer1, buffer2);
Buffer.toArray(zipped); // => [(1, 4), (2, 5)]

Runtime	Space
`O(min(size1, size2))`	`O(min(size1, size2))`

Function `zipWith`

func zipWith<X, Y, Z>(buffer1 : Buffer<X>, buffer2 : Buffer<Y>, zip : (X, Y) -> Z) : Buffer<Z>

Combines the two buffers into a single buffer, pairing together elements with the same index and combining them using zip. If one buffer is longer than the other, the remaining elements from the longer buffer are not included.

Example:

let buffer1 = Buffer.Buffer<Nat>(2);
buffer1.add(1);
buffer1.add(2);
buffer1.add(3);

let buffer2 = Buffer.Buffer<Nat>(2);
buffer2.add(4);
buffer2.add(5);
buffer2.add(6);

let zipped = Buffer.zipWith<Nat, Nat, Nat>(buffer1, buffer2, func (x, y) { x + y });
Buffer.toArray(zipped) // => [5, 7, 9]

Runtime	Space
`O(min(size1, size2))`	`O(min(size1, size2))`

Function `takeWhile`

func takeWhile<X>(buffer : Buffer<X>, predicate : X -> Bool) : Buffer<X>

Creates a new buffer taking elements in order from buffer until predicate returns false.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);

let newBuf = Buffer.takeWhile<Nat>(buffer, func (x) { x < 3 });
Buffer.toText(newBuf, Nat.toText); // => [1, 2]

Runtime	Space
`O(size)`	`O(size)`

Function `dropWhile`

func dropWhile<X>(buffer : Buffer<X>, predicate : X -> Bool) : Buffer<X>

Creates a new buffer excluding elements in order from buffer until predicate returns false.

Example:

import Nat "mo:base/Nat";

buffer.add(1);
buffer.add(2);
buffer.add(3);

let newBuf = Buffer.dropWhile<Nat>(buffer, func x { x < 3 }); // => [3]
Buffer.toText(newBuf, Nat.toText);

Runtime	Space
`O(size)`	`O(size)`

Class Buffer<X>
- Function size
- Function add
- Function get
- Function getOpt
- Function put
- Function remove
- Function clear
- Function filterEntries
- Function capacity
- Function reserve
- Function append
- Function insert
- Function insertBuffer
- Function sort
- Function vals
- Function clone
- Function toArray
- Function toVarArray
Function isEmpty
Function contains
Function clone
Function max
Function min
Function equal
Function compare
Function toText
Function hash
Function indexOf
Function lastIndexOf
Function indexOfBuffer
Function binarySearch
Function subBuffer
Function isSubBufferOf
Function isStrictSubBufferOf
Function prefix
Function isPrefixOf
Function isStrictPrefixOf
Function suffix
Function isSuffixOf
Function isStrictSuffixOf
Function forAll
Function forSome
Function forNone
Function toArray
Function toVarArray
Function fromArray
Function fromVarArray
Function fromIter
Function trimToSize
Function map
Function iterate
Function mapEntries
Function mapFilter
Function mapResult
Function chain
Function foldLeft
Function foldRight
Function first
Function last
Function make
Function reverse
Function merge
Function removeDuplicates
Function partition
Function split
Function chunk
Function groupBy
Function flatten
Function zip
Function zipWith
Function takeWhile
Function dropWhile

Buffer

Class Buffer<X>​

Function size​

Function add​

Function get​

Function getOpt​

Function put​

Function remove​

Function clear​

Function filterEntries​

Function capacity​

Function reserve​

Function append​

Function insert​

Function insertBuffer​

Function sort​

Function vals​

Function clone​

Function toArray​

Function toVarArray​

Function isEmpty​

Function contains​

Function clone​

Function max​

Function min​

Function equal​

Function compare​

Function toText​

Function hash​

Function indexOf​

Function lastIndexOf​

Function indexOfBuffer​

Function binarySearch​

Function subBuffer​

Function isSubBufferOf​

Function isStrictSubBufferOf​

Function prefix​

Function isPrefixOf​

Function isStrictPrefixOf​

Function suffix​

Function isSuffixOf​

Function isStrictSuffixOf​

Function forAll​

Function forSome​

Function forNone​

Function toArray​

Function toVarArray​

Function fromArray​

Function fromVarArray​

Function fromIter​

Function trimToSize​

Function map​

Function iterate​

Function mapEntries​

Function mapFilter​

Function mapResult​

Function chain​

Function foldLeft​

Function foldRight​

Function first​

Function last​

Function make​

Function reverse​

Function merge​

Function removeDuplicates​

Function partition​

Function split​

Function chunk​

Function groupBy​

Function flatten​

Function zip​

Function zipWith​

Function takeWhile​

Function dropWhile​

Class `Buffer<X>`

Function `size`

Function `add`

Function `get`

Function `getOpt`

Function `put`

Function `remove`

Function `clear`

Function `filterEntries`

Function `capacity`

Function `reserve`

Function `append`

Function `insert`

Function `insertBuffer`

Function `sort`

Function `vals`

Function `clone`

Function `toArray`

Function `toVarArray`

Function `isEmpty`

Function `contains`

Function `clone`

Function `max`

Function `min`

Function `equal`

Function `compare`

Function `toText`

Function `hash`

Function `indexOf`

Function `lastIndexOf`

Function `indexOfBuffer`

Function `binarySearch`

Function `subBuffer`

Function `isSubBufferOf`

Function `isStrictSubBufferOf`

Function `prefix`

Function `isPrefixOf`

Function `isStrictPrefixOf`

Function `suffix`

Function `isSuffixOf`

Function `isStrictSuffixOf`

Function `forAll`

Function `forSome`

Function `forNone`

Function `toArray`

Function `toVarArray`

Function `fromArray`

Function `fromVarArray`

Function `fromIter`

Function `trimToSize`

Function `map`

Function `iterate`

Function `mapEntries`

Function `mapFilter`

Function `mapResult`

Function `chain`

Function `foldLeft`

Function `foldRight`

Function `first`

Function `last`

Function `make`

Function `reverse`

Function `merge`

Function `removeDuplicates`

Function `partition`

Function `split`

Function `chunk`

Function `groupBy`

Function `flatten`

Function `zip`

Function `zipWith`

Function `takeWhile`

Function `dropWhile`