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.

:::note Assumptions

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

:::

:::note Size vs capacity

The invariant capacity >= size always holds. :::

:::warning 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. :::

:::info Constructor behavior

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

Example:

motoko name=initialize
import Buffer "mo:base/Buffer";

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

| Runtime | Space | |-----------|-----------| | O(initCapacity) | O(initCapacity) |

class Buffer<X>(initCapacity : Nat)

public func size() : Nat

Returns the current number of elements in the buffer.

Example:

motoko include=initialize
buffer.size() // => 0

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

public 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:

motoko include=initialize
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) |

public func get(index : Nat) : X

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

Example:

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

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

public func getOpt(index : Nat) : ?X

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

Example:

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

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

public func put(index : Nat, element : X)

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

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

public func removeLast() : ?X

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

Example:

motoko include=initialize
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) |

public 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.

:::warning 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:

motoko include=initialize
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) |

public func clear()

Resets the buffer. Capacity is set to 8.

Example:

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

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

public 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:

motoko include=initialize
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) |

public func capacity() : Nat

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

Example:

motoko include=initialize
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) |

public func reserve(capacity : Nat)

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

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

| Runtime | Space | |-----------|-----------| | O(capacity) | O(capacity) |

public func append(buffer2 : Buffer<X>)

Adds all elements in buffer b to this buffer.

motoko include=initialize
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) |

public 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.

motoko include=initialize
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) |

public 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.

motoko include=initialize
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) |

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

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

motoko include=initialize
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) |

public 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.

motoko include=initialize
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) |

public func clone() : Buffer<X>

@deprecated Use the static library function instead of this instance method.

public func toArray() : [X]

@deprecated Use the static library function instead of this instance method.

public func toVarArray() : [var X]

@deprecated Use the static library function instead of this instance method.

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

Returns true if and only if the buffer is empty.

Example:

motoko include=initialize
buffer.add(2);
buffer.add(0);
buffer.add(3);
Buffer.isEmpty(buffer); // => false
motoko include=initialize
Buffer.isEmpty(buffer); // => true

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

public 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:

motoko include=initialize
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) |

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

Returns a copy of buffer, with the same capacity.

Example:

motoko include=initialize
buffer.add(1);

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

| Runtime | Space | |-----------|-----------| | O(size) | O(size) |

public 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:

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

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

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

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

public 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:

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

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

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

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

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

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

Returns true if every element in buffer satisfies predicate.

Example:

motoko include=initialize
buffer.add(2);
buffer.add(3);
buffer.add(4);

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

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

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

Returns true if some element in buffer satisfies predicate.

Example:

motoko include=initialize
buffer.add(2);
buffer.add(3);
buffer.add(4);

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

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

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

Returns true if no element in buffer satisfies predicate.

Example:

motoko include=initialize
buffer.add(2);
buffer.add(3);
buffer.add(4);

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

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

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

Creates an array containing elements from buffer.

Example:

motoko include=initialize
buffer.add(1);
buffer.add(2);
buffer.add(3);

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

| Runtime | Space | |-----------|-----------| | O(size) | O(size) |

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

Creates a mutable array containing elements from buffer.

Example:

motoko include=initialize
buffer.add(1);
buffer.add(2);
buffer.add(3);

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

| Runtime | Space | |-----------|-----------| | O(size) | O(size) |

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

Creates a buffer containing elements from array.

Example:

motoko include=initialize
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) |

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

Creates a buffer containing elements from array.

Example:

motoko include=initialize
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) |

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

Creates a buffer containing elements from iter.

Example:

motoko include=initialize
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) |

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

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

Example:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

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

Applies f to each element in buffer.

Example:

motoko include=initialize
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) |

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

Applies f to each element in buffer and its index.

Example:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

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

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

Example:

motoko include=initialize
buffer.add(1);
buffer.add(2);
buffer.add(3);

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

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

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

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

Example:

motoko include=initialize
buffer.add(1);
buffer.add(2);
buffer.add(3);

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

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

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

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

Example:

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

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

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

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

Reverses the order of elements in buffer.

Example:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |

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

Flattens the buffer of buffers into a single buffer.

Example:

motoko include=initialize
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) |

public 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:

motoko include=initialize

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)) |

public 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:

motoko include=initialize

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)) |

public 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:

motoko include=initialize
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) |

public 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:

motoko include=initialize
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) |