Buffer

Class Buffer<X> provides a mutable list of elements of type X. The class wraps and resizes an underyling array that holds the elements, and thus is comparable to ArrayLists or Vectors in other languages.

When required, the current state of a buffer object can be converted to a fixed-size array of its elements. This is recommended for example when storing a buffer to a stable variable.

Throughout this documentation, two terms come up that can be confused: size and capacity. size is the length of the list that the buffer represents. capacity is the length of the underyling array that backs this list. capacity >= size is an invariant for this class.

Like arrays, elements in the buffer are ordered by indices from 0 to size-1.

WARNING: Certain operations are amortized O(1) time, such as add, but run in worst case O(n) time. These worst case runtimes may exceed the cycles limit per message if the size of the buffer is large enough. Grow these structures with discretion. All amortized operations below also list the worst case runtime.

Constructor: The argument initCapacity determines the initial capacity of the array. The underlying array grows by a factor of 1.5 when its current capacity is exceeded. Further, when the size of the buffer shrinks to be less than 1/4th of the capacity, the underyling array is shrunk by a factor of 2.

Example:

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

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

Runtime: O(initCapacity)

Space: 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: O(1)

Space: 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]

Amortized Runtime: O(1), Worst Case Runtime: O(size)

Amortized Space: O(1), Worst Case Space: O(size)

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: O(1)

Space: 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: O(1)

Space: O(1)

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

Overwrites the current element at index with element. Traps if index >= size. Indexing is zero-based.

Example:

motoko include=initialize

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

Runtime: O(1)

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

Amortized Runtime: O(1), Worst Case Runtime: O(size)

Amortized Space: O(1), Worst Case Space: O(size)

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: Repeated removal of elements using this method is ineffecient and might be a sign that you should consider a different data-structure for 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: O(size)

Amortized Space: O(1), Worst Case Space: O(size)

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: O(1)

Space: 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: O(size)

Amortized Space: O(1), Worst Case Space: O(size)

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: O(1)

Space: 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: O(capacity)

Space: 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]

Amortized Runtime: O(size2), Worst Case Runtime: O(size1 + size2)

Amortized Space: O(1), Worst Case Space: O(size1 + size2)

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: O(size)

Amortized Space: O(1), Worst Case Space: O(size)

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: O(size)

Amortized Space: O(1), Worst Case Space: O(size1 + size2)

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: O(size * log(size))

Space: 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: O(1)

Space: O(1)

public func clone() : Buffer<X>

@deprecated Use static library function instead.

public func toArray() : [X]

@deprecated Use static library function instead.

public func toVarArray() : [var X]

@deprecated Use static library function instead.

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: O(1)

Space: O(1)

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

Returns true iff 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: O(size)

Space: O(1)

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

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: O(size)

Space: 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: O(size)

Space: O(1)

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

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: O(size)

Space: O(1)

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

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 iff 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: O(size)

Space: O(1)

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

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: O(size)

Space: O(1)

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

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: O(size)

Space: O(size)

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

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: O(size)

Space: O(1)

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

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: O(size)

Space: O(size)

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

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: O(size)

Space: O(size)

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

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: O(size of buffer + size of subBuffer)

Space: O(size of subBuffer)

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

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: O(log(size))

Space: O(1)

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

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: O(length)

Space: 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: O(size of subBuffer + size of buffer)

Space: O(size of subBuffer)

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

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: O(size of subBuffer + size of buffer)

Space: O(size of subBuffer)

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

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: O(length)

Space: 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: O(size of prefix)

Space: O(size of prefix)

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

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: O(size of prefix)

Space: O(size of prefix)

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

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: O(length)

Space: 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: O(length of suffix)

Space: O(length of suffix)

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

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: O(length of suffix)

Space: O(length of suffix)

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

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

Returns true iff 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: O(size)

Space: O(1)

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

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

Returns true iff 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: O(size)

Space: O(1)

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

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

Returns true iff 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: O(size)

Space: O(1)

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

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: O(size)

Space: 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: O(size)

Space: 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: O(size)

Space: 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: O(size)

Space: 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: O(size)

Space: 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: O(size)

Space: 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: O(size)

Space: O(size)

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

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: O(size)

Space: O(size)

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

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: O(size)

Space: O(size)

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

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: O(size)

Space: O(size)

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

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: O(size)

Space: O(size)

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

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: O(size)

Space: O(size)

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

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: O(size)

Space: O(1)

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

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: O(size)

Space: O(1)

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

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: O(1)

Space: 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: O(1)

Space: 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: O(1)

Space: 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: O(size)

Space: 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: O(size1 + size2)

Space: O(size1 + size2)

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

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: O(size * log(size))

Space: 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: O(size)

Space: O(size)

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

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: O(size)

Space: O(size)

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

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: O(number of elements in buffer)

Space: 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: O(size)

Space: O(size)

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

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: O(number of elements in buffer)

Space: 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: O(min(size1, size2))

Space: 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: O(min(size1, size2))

Space: O(min(size1, size2))

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

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: O(size)

Space: O(size)

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

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: O(size)

Space: O(size)

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