BufferDeque

A Buffer that with an amortized time of O(1) additions at both ends

class BufferDeque<A>(init_capacity : Nat)

public func size() : Nat

Returns the number of items in the buffer

public func capacity() : Nat

Returns the capacity of the deque.

public func internal_array() : [?A]

for debugging purposes

public func internal_start() : Nat

public func get(i : Nat) : A

Retrieves the element at the given index. Traps if the index is out of bounds.

public func getOpt(i : Nat) : ?A

Retrieves an element at the given index, if it exists. If not it returns null.

public func put(i : Nat, elem : A)

Overwrites the element at the given index.

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)

Adapted from the base implementation of the Buffer class

public func addFront(elem : A)

Adds an element to the start of the buffer.

public func addBack(elem : A)

Adds an element to the end of the buffer

public func popFront() : ?A

Removes an element from the start of the buffer and returns it if it exists. If the buffer is empty, it returns null.

public func popBack() : ?A

Removes an element from the end of the buffer and returns it if it exists. If the buffer is empty, it returns null. Runtime: O(1) amortized

public func clear()

Removes all elements from the buffer and resizes it to the default capacity.

public func append(other : BufferInterface<A>)

Adds all the elements in the given buffer to the end of this buffer. The BufferInterface<A> type is used to allow for any type that has a size and get method.

public func prepend(other : BufferInterface<A>)

Adds all the elements in the given buffer to the start of this buffer.

public func remove(i : Nat) : A

Removes an element at the given index and returns it. Traps if the index is out of bounds. Runtime: O(min(i, size - i))

public func removeRange(_start : Nat, end : Nat) : [A]

Removes a range of elements from the buffer and returns them as an array. Traps if the range is out of bounds.

public func range(start : Nat, end : Nat) : Iter.Iter<A>

Returns an iterator over the elements of the buffer. Note: The values in the iterator will change if the buffer is modified before the iterator is consumed.

public func swap(i : Nat, j : Nat)

Swaps the elements at the given indices.

public func rotateLeft(n : Nat)

Rotates the buffer to the left by the given amount. Runtime: O(min(n, size - n))

public func rotateRight(n : Nat)

Rotates the buffer to the right by the given amount. Runtime: O(min(n, size - n))

public func vals() : Iter.Iter<A>

Returns an iterator over the elements of the buffer.

public func new<A>() : BufferDeque<A>

Creates an empty buffer.

public func init<A>(capacity : Nat, val : A) : BufferDeque<A>

Creates a buffer with the given capacity and initializes all elements to the given value.

public func tabulate<A>(capacity : Nat, f : Nat -> A) : BufferDeque<A>

Creates a buffer with the given capacity and initializes all elements using the given function.

public func peekFront<A>(buffer : BufferDeque<A>) : ?A

Returns the element at the front of the buffer, or null if the buffer is empty.

public func peekBack<A>(buffer : BufferDeque<A>) : ?A

Returns the element at the back of the buffer, or null if the buffer is empty.

public func isEmpty<A>(buffer : BufferDeque<A>) : Bool

Checks if the buffer is empty.

public func fromArray<A>(arr : [A]) : BufferDeque<A>

Creates a buffer from the given array.

public func toArray<A>(buffer : BufferDeque<A>) : [A]

Returns the buffer as an array.