steady_vector (steady_vector v1.1.0)

A persistent vector: an array-like collection of values optimized for growth and shrinkage at the tail.

steady_vector optimizes the following operations:

getting the element count (size/1) — O(1);
looking up an element by its 0-based index (get/2, get/3, find/2);
updating an element by its 0-based index (set/3);
appending a new element to the end (append/2);
removing the last element (remove_last/1);
enumeration (foldl/3, foldr/3, foreach/2);
mapping (map/2) and filtering (filter/2).

Every operation other than size/1 is O(log32(N)).

It is implemented as a tree with 32-way branching at each level and uses structural sharing for updates, following the same design as Clojure's persistent vectors.

Summary

Types

index()

A 0-based index into a vector.

t()

A persistent vector, as returned by new/0.

Functions

append(Value, Vector1)

Appends Value to the end of Vector, returning the modified vector.

filter(Fun, Vector1)

Filters the elements of Vector using the predicate Fun, returning a new vector with the elements for which Fun(Index, Value) returned true.

find(Index, Vector)

Returns {ok, Value} for the element in Vector at 0-based Index, or error if the index is too large.

foldl(Fun, Acc0, Vector)

Calls Fun(Index, Value, AccIn) on successive elements of Vector, starting with AccIn =:= Acc0.

foldr(Fun, Acc0, Vector)

Like foldl/3, but Vector is traversed from right to left.

foreach(Fun, Vector)

Calls Fun(Index, Value) for each Value in Vector.

from_list(List)

Converts a proper list into a vector containing the same elements in the same order.

get(Index, Vector)

Returns the value of the element in Vector at 0-based Index.

get(Index, Vector, Default)

Returns the value of the element in Vector at 0-based Index, or Default if Index >= size(Vector).

is_empty(Vector)

Returns true if Vector is empty, false otherwise.

is_steady_vector(Term)

Returns true if Term is a steady_vector, false otherwise.

last(Vector)

Returns the last value of a non-empty Vector.

last(Vector, Default)

Returns the last value of Vector if it is not empty, Default otherwise.

map(Fun, Vector1)

Maps Fun(Index, Value) over every value of Vector, returning a new vector containing the mapped values.

new()

Returns a new, empty vector.

remove_last(Vector1)

Removes the last value of the non-empty vector Vector1 and returns Vector2 with that element removed.

set(Index, Value, Vector1)

Returns Vector2, a copy of Vector1 with the element at 0-based Index set to Value.

size(Vector)

Returns the number of elements in Vector.

to_list(Vector)

Returns a list with the elements of Vector in the same order.

Types

index()

-type index() :: non_neg_integer().

A 0-based index into a vector.

t()

-opaque t()

A persistent vector, as returned by new/0.

Functions

append(Value, Vector1)

-spec append(Value, Vector1) -> Vector2 when Value :: term(), Vector1 :: t(), Vector2 :: t().

Appends Value to the end of Vector, returning the modified vector.

Vector must be a valid vector or a {badvec, Vector} error is raised.

filter(Fun, Vector1)

-spec filter(Fun, Vector1) -> Vector2
                when
                    Fun :: fun((Index, Value) -> boolean()),
                    Index :: index(),
                    Value :: term(),
                    Vector1 :: t(),
                    Vector2 :: t().

Filters the elements of Vector using the predicate Fun, returning a new vector with the elements for which Fun(Index, Value) returned true.

Fun must be an arity-2 function or a badarg error is raised. Vector must be a valid vector or a {badvec, Vector} error is raised.

find(Index, Vector)

-spec find(Index, Vector) -> {ok, Value} | error when Index :: index(), Vector :: t(), Value :: term().

Returns {ok, Value} for the element in Vector at 0-based Index, or error if the index is too large.

Index must be a non-negative integer or a badarg error is raised. Vector must be a valid vector or a {badvec, Vector} error is raised.

foldl(Fun, Acc0, Vector)

-spec foldl(Fun, Acc0, Vector) -> AccN
               when
                   Fun :: fun((Index, Value, AccIn) -> AccOut),
                   Index :: index(),
                   Value :: term(),
                   AccIn :: Acc0 | AccOut,
                   AccOut :: term() | AccN,
                   Acc0 :: term(),
                   Vector :: t(),
                   AccN :: term().

Calls Fun(Index, Value, AccIn) on successive elements of Vector, starting with AccIn =:= Acc0.

Fun/3 must return a new accumulator, which is passed to the next call. The final value of the accumulator is returned; Acc0 is returned if the vector is empty.

Fun must be an arity-3 function or a badarg error is raised. Vector must be a valid vector or a {badvec, Vector} error is raised.

foldr(Fun, Acc0, Vector)

-spec foldr(Fun, Acc0, Vector) -> AccN
               when
                   Fun :: fun((Index, Value, Acc1) -> Acc2),
                   Index :: index(),
                   Value :: term(),
                   Acc1 :: Acc0 | Acc2,
                   Acc2 :: term() | AccN,
                   Acc0 :: term(),
                   Vector :: t(),
                   AccN :: term().

Like foldl/3, but Vector is traversed from right to left.

foreach(Fun, Vector)

-spec foreach(Fun, Vector) -> ok
                 when
                     Fun :: fun((Index, Value) -> term()),
                     Index :: index(),
                     Value :: term(),
                     Vector :: t().

Calls Fun(Index, Value) for each Value in Vector.

This function is used for its side effects, and the evaluation order is the same as the order of the elements in the vector.

Fun must be an arity-2 function or a badarg error is raised. Vector must be a valid vector or a {badvec, Vector} error is raised.

from_list(List)

-spec from_list(List) -> Vector when List :: list(), Vector :: t().

Converts a proper list into a vector containing the same elements in the same order.

List must be a list or a badarg error is raised.

get(Index, Vector)

-spec get(Index, Vector) -> Value | no_return() when Index :: index(), Vector :: t(), Value :: term().

Returns the value of the element in Vector at 0-based Index.

Index must be an integer satisfying 0 =< Index < size(Vector) or a badarg error is raised. Vector must be a valid vector or a {badvec, Vector} error is raised.

get(Index, Vector, Default)

-spec get(Index, Vector, Default) -> Value | Default
             when Index :: index(), Vector :: t(), Default :: term(), Value :: term().

Returns the value of the element in Vector at 0-based Index, or Default if Index >= size(Vector).

Index must be a non-negative integer or a badarg error is raised. Vector must be a valid vector or a {badvec, Vector} error is raised.

is_empty(Vector)

-spec is_empty(Vector) -> boolean() when Vector :: t().

Returns true if Vector is empty, false otherwise.

Vector must be a valid vector or a {badvec, Vector} error is raised.

is_steady_vector(Term)

-spec is_steady_vector(Term) -> boolean() when Term :: term().

Returns true if Term is a steady_vector, false otherwise.

last(Vector)

-spec last(Vector) -> Value | no_return() when Vector :: t(), Value :: term().

Returns the last value of a non-empty Vector.

If Vector is empty, an emptyvec error is raised. Vector must be a valid vector or a {badvec, Vector} error is raised.

last(Vector, Default)

-spec last(Vector, Default) -> Value | Default when Vector :: t(), Default :: term(), Value :: term().

Returns the last value of Vector if it is not empty, Default otherwise.

Vector must be a valid vector or a {badvec, Vector} error is raised.

map(Fun, Vector1)

-spec map(Fun, Vector1) -> Vector2
             when
                 Fun :: fun((Index, Value1) -> Value2),
                 Index :: index(),
                 Value1 :: term(),
                 Value2 :: term(),
                 Vector1 :: t(),
                 Vector2 :: t().

Maps Fun(Index, Value) over every value of Vector, returning a new vector containing the mapped values.

Fun must be an arity-2 function or a badarg error is raised. Vector must be a valid vector or a {badvec, Vector} error is raised.

new()

-spec new() -> Vector when Vector :: t().

Returns a new, empty vector.

remove_last(Vector1)

-spec remove_last(Vector1) -> Vector2 | no_return() when Vector1 :: t(), Vector2 :: t().

Removes the last value of the non-empty vector Vector1 and returns Vector2 with that element removed.

If the vector is empty, an emptyvec error is raised. Vector1 must be a valid vector or a {badvec, Vector1} error is raised.

set(Index, Value, Vector1)

-spec set(Index, Value, Vector1) -> Vector2 | no_return()
             when Index :: index(), Value :: term(), Vector1 :: t(), Vector2 :: t().

Returns Vector2, a copy of Vector1 with the element at 0-based Index set to Value.

Index must be an integer satisfying 0 =< Index < size(Vector) or a badarg error is raised. If Index equals size(Vector), this function behaves like append/2. Vector1 must be a valid vector or a {badvec, Vector1} error is raised.

size(Vector)

-spec size(Vector) -> non_neg_integer() when Vector :: t().

Returns the number of elements in Vector.

Vector must be a valid vector or a {badvec, Vector} error is raised.

to_list(Vector)

-spec to_list(Vector) -> list() when Vector :: t().

Returns a list with the elements of Vector in the same order.

Vector must be a valid vector or a {badvec, Vector} error is raised.