steady_vector

%% Copyright (c) 2017 Dmitry Kakurin
%% Copyright (c) 2017 Guilherme Andrade <steady_vector@gandrade.net>
%%
%% Permission is hereby granted, free of charge, to any person obtaining a
%% copy  of this software and associated documentation files (the "Software"),
%% to deal in the Software without restriction, including without limitation
%% the rights to use, copy, modify, merge, publish, distribute, sublicense,
%% and/or sell copies of the Software, and to permit persons to whom the
%% Software is furnished to do so, subject to the following conditions:
%%
%% The above copyright notice and this permission notice shall be included in
%% all copies or substantial portions of the Software.
%%
%% THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
%% IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
%% FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
%% AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
%% LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
%% FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
%% DEALINGS IN THE SOFTWARE.

-module(steady_vector).

-ifdef(TEST).
-include_lib("eunit/include/eunit.hrl").
-endif.

-compile({no_auto_import,[{size,1}]}).
-compile(inline_list_funcs).

%% ------------------------------------------------------------------
%% API Function Exports
%% ------------------------------------------------------------------

-export([append/2]).                -ignore_xref({append,2}).
-export([get/2]).                   -ignore_xref({get,2}).
-export([get/3]).                   -ignore_xref({get,3}).
-export([filter/2]).                -ignore_xref({filter,2}).
-export([find/2]).                  -ignore_xref({find,2}).
-export([foldl/3]).                 -ignore_xref({foldl,3}).
-export([foldr/3]).                 -ignore_xref({foldr,3}).
-export([foreach/2]).               -ignore_xref({foreach,2}).
-export([from_list/1]).             -ignore_xref({from_list,1}).
-export([is_empty/1]).              -ignore_xref({is_empty,1}).
-export([is_steady_vector/1]).      -ignore_xref({is_steady_vector,1}).
-export([last/1]).                  -ignore_xref({last,1}).
-export([last/2]).                  -ignore_xref({last,2}).
-export([map/2]).                   -ignore_xref({map,2}).
-export([new/0]).                   -ignore_xref({new,0}).
-export([remove_last/1]).           -ignore_xref({remove_last,1}).
-export([set/3]).                   -ignore_xref({set,3}).
-export([size/1]).                  -ignore_xref({size,1}).
-export([to_list/1]).               -ignore_xref({to_list,1}).

%% ------------------------------------------------------------------
%% Macro Definitions
%% ------------------------------------------------------------------

-ifdef(TEST).
-define(shift, 2).
-else.
-define(shift, 5).
-endif.

-define(block_size, (1 bsl ?shift)).
-define(mask, (?block_size - 1)).

-define(is_index(I), (is_integer((I)) andalso (I) >= 0)).
-define(is_existing_index(I, V), (?is_index((I)) andalso (I) < (V)#steady_vector.count)).
-define(is_next_index(I, V), ((I) =:= (V)#steady_vector.count)).
-define(is_vector(V), (is_record(V, steady_vector))).

-define(arg_error, (error(badarg))).
-define(vec_error(Vector), (error({badvec,Vector}))).
-define(empty_vec_error, (error(emptyvec))).

%% ------------------------------------------------------------------
%% Record and Type Definitions
%% ------------------------------------------------------------------

-type shift() :: pos_integer().

-type index() :: non_neg_integer().
-export_type([index/0]).

-record(steady_vector, {
          count = 0 :: index(),
          shift = ?shift :: shift(),
          root = {} :: tuple(),
          tail = {} :: tuple()
         }).
-opaque t() :: #steady_vector{}.
-export_type([t/0]).

%% ------------------------------------------------------------------
%% API Function Definitions
%% ------------------------------------------------------------------

-spec append(Value, Vector1) -> Vector2
            when Value :: term(),
                 Vector1 :: t(),
                 Vector2 :: t().
%% @doc Appends `Value' to the end of `Vector'.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
%% @see set/3
%% @returns Modified `Vector'
append(Value, #steady_vector{ tail = Tail } = Vector) when tuple_size(Tail) < ?block_size ->
    Vector#steady_vector{
      count = Vector#steady_vector.count + 1,
      tail = tuple_append(Value, Tail)
     };
append(NewValue, #steady_vector{} = Vector) ->
    #steady_vector{ count = Count, shift = Shift, root = Root, tail = Tail } = Vector,
    NewCount = Count + 1,
    NewTail = {NewValue},
    case append_recur(Root, Shift, Tail) of
        {ok, NewRoot} ->
            Vector#steady_vector{ count = NewCount, root = NewRoot, tail = NewTail };
        {overflow, TailPath} ->
            NewShift = Shift + ?shift,
            NewRoot = {Root, TailPath},
            Vector#steady_vector{ count = NewCount, shift = NewShift, root = NewRoot, tail = NewTail }
    end;
append(_NewValue, Vector) ->
    ?vec_error(Vector).

-spec get(Index, Vector) -> Value | no_return()
            when Index :: index(),
                 Vector :: t(),
                 Value :: term().
%% @doc Returns value of element in `Vector' at `0'-based `Index'.
%% `Index' must be an integer and satisfy condition `0 =< Index =< size(Vector)' or a `badarg' error will be raised.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
%% @see get/3
%% @see find/2
get(Index, Vector) when ?is_existing_index(Index, Vector) ->
    fast_get(Index, Vector);
get(_Index, Vector) when ?is_vector(Vector) ->
    ?arg_error;
get(_Index, Vector) ->
    ?vec_error(Vector).

%% @doc Returns value of element in `Vector' at `0'-based `Index' or `Default' if `Index >= size(Vector)'.
%% `Index' must be a non-negative integer or a `badarg' error will be raised.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
%% @see get/2
%% @see find/2
-spec get(Index, Vector, Default) -> Value | Default
            when Index :: index(),
                 Vector :: t(),
                 Default :: term(),
                 Value :: term().
get(Index, Vector, Default) when ?is_index(Index), ?is_vector(Vector) ->
    case Index < Vector#steady_vector.count of
        true -> fast_get(Index, Vector);
        _ -> Default
    end;
get(_Index, Vector, _Default) when ?is_vector(Vector) ->
    ?arg_error;
get(_Index, Vector, _Default) ->
    ?vec_error(Vector).

%% @doc Filters `Vector' elements using predicate `Fun'.
%% `Fun' must be an arity-2 function or a `badarg' error will be raised.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
%% @returns The modified vector containing the filtered elements.
-spec filter(Fun, Vector1) -> Vector2
            when Fun :: fun((Index, Value) -> boolean()),
                 Index :: index(),
                 Value :: term(),
                 Vector1 :: t(),
                 Vector2 :: t().
filter(Fun, Vector) when is_function(Fun, 2) ->
    foldl(
      fun (Index, Value, Acc) ->
              case Fun(Index, Value) of
                  true -> append(Value, Acc);
                  false -> Acc
              end
      end,
      new(), Vector);
filter(_Fun, Vector) when ?is_vector(Vector) ->
    ?arg_error;
filter(_Fun, Vector) ->
    ?vec_error(Vector).

%% @doc Returns success-wrapped value of 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 will be raised.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
%% @see get/2
%% @see get/3
-spec find(Index, Vector) -> {ok, Value} | error
            when Index :: index(),
                 Vector :: t(),
                 Value :: term().
find(Index, Vector) when ?is_index(Index), ?is_vector(Vector) ->
    case Index < Vector#steady_vector.count of
        true -> {ok, fast_get(Index, Vector)};
        _ -> error
    end;
find(_Index, Vector) when ?is_vector(Vector) ->
    ?arg_error;
find(_Index, Vector) ->
    ?vec_error(Vector).

%% @doc 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 function returns the final value of the accumulator. `Acc0' is returned if the vector is empty.
%% `Fun' must be an arity-3 function or a `badarg' error will be raised.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
%% @see foldr/3
-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().
foldl(Fun, Acc0, Vector) when is_function(Fun, 3), ?is_vector(Vector) ->
    countfoldl_leaves(Fun, Acc0, Vector);
foldl(_Fun, _Acc0, Vector) when ?is_vector(Vector) ->
    ?arg_error;
foldl(_Fun, _Acc0, Vector) ->
    ?vec_error(Vector).

%% @doc Like `foldl/3' but `Vector' is traversed from right to left.
%% @see foldl/3
-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().
foldr(Fun, Acc0, Vector) when is_function(Fun, 3), ?is_vector(Vector) ->
    countfoldr_leaves(Fun, Acc0, Vector);
foldr(_Fun, _Acc0, Vector) when ?is_vector(Vector) ->
    ?arg_error;
foldr(_Fun, _Acc0, Vector) ->
    ?vec_error(Vector).

%% @doc Calls `Fun(Index, Value)' for each `Value' in `Vector'.
%% This function is used for its side effects and the evaluation order
%% is defined to be the same as the order of the elements in the vector.
%% `Fun' must be an arity-2 function or a `badarg' error will be raised.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
-spec foreach(Fun, Vector) -> ok
            when Fun :: fun((Index, Value) -> term()),
                 Index :: index(),
                 Value :: term(),
                 Vector :: t().
foreach(Fun, Vector) when is_function(Fun, 2) ->
    counteach_leaves(Fun, Vector);
foreach(_Fun, Vector) when ?is_vector(Vector) ->
    ?arg_error;
foreach(_Fun, Vector) ->
    ?vec_error(Vector).

%% @doc Converts a proper `List' of elements to a `Vector' containing them in the same order.
%% `List' must be a list or a `{badvec,Vector}' error will be raised.
%% @see to_list/1
-spec from_list(List) -> Vector
            when List :: list(),
                 Vector :: t().
from_list(List) when is_list(List) ->
    lists:foldl(fun append/2, new(), List);
from_list(_List) ->
    ?arg_error.

%% @doc Returns `true' if `Vector' is empty, `false' otherwise.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
%% @see size/1
-spec is_empty(Vector) -> boolean()
            when Vector :: t().
is_empty(Vector) when ?is_vector(Vector) ->
    Vector#steady_vector.count =:= 0;
is_empty(Vector) ->
    ?vec_error(Vector).

%% @doc Returns `true' if `Term' is a `steady_vector', `false' otherwise.
-spec is_steady_vector(Term) -> boolean()
            when Term :: term().
is_steady_vector(Term) ->
    ?is_vector(Term).

%% @doc Returns the last value of a non-empty `Vector'.
%% If `Vector' is empty, an `emptyvec' error will be raised.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
-spec last(Vector) -> Value | no_return()
            when Vector :: t(),
                 Value :: term().
last(#steady_vector{ count = Count } = Vector) ->
    case Count > 0 of
        true -> fast_get(Count - 1, Vector);
        _ -> ?empty_vec_error(Vector)
    end;
last(Vector) ->
    ?vec_error(Vector).

%% @doc Returns the last value `Vector' if it's not empty, `Default' otherwise.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
-spec last(Vector, Default) -> Value | Default
            when Vector :: t(),
                 Default :: term(),
                 Value :: term().
last(#steady_vector{ count = Count } = Vector, Default) ->
    case Count > 0 of
        true -> fast_get(Count - 1, Vector);
        _ -> Default
    end;
last(Vector, _Default) ->
    ?vec_error(Vector).

%% @doc Maps function `Fun(Index, Value)' to all values of vector `Vector'.
%% Returns a new vector containing the mapped values.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
-spec map(Fun, Vector1) -> Vector2
            when Fun :: fun((Index, Value1) -> Value2),
                 Index :: index(),
                 Value1 :: term(),
                 Value2 :: term(),
                 Vector1 :: t(),
                 Vector2 :: t().
map(Fun, Vector) when is_function(Fun, 2) ->
    countmap_leaves(Fun, Vector);
map(_Fun, Vector) when ?is_vector(Vector) ->
    ?arg_error;
map(_Fun, Vector) ->
    ?vec_error(Vector).

%% @doc Returns an empty vector.
-spec new() -> Vector
            when Vector :: t().
new() ->
    #steady_vector{}.

%% @doc Removes the last value of non-empty `Vector1' and returns `Vector2' with the element removed.
%% If `Vector' is empty, an `emptyvec' error will be raised.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
-spec remove_last(Vector1) -> Vector2 | no_return()
            when Vector1 :: t(),
                 Vector2 :: t().
remove_last(#steady_vector{ tail = Tail } = Vector) when tuple_size(Tail) > 1 ->
    NewTail = tuple_delete_last(Tail),
    Vector#steady_vector{
      count = Vector#steady_vector.count - 1,
      tail = NewTail };
remove_last(#steady_vector{ count = Count } = Vector) when Count > 1 ->
    #steady_vector{ shift = Shift, root = Root } = Vector,
    NewCount = Count - 1,
    {NewRoot, NewTail} = remove_last_recur(Root, Shift),
    if tuple_size(NewRoot) =:= 1 andalso Shift > ?shift ->
           NewShift = Shift - ?shift,
           {InnerNewRoot} = NewRoot, % remove topmost tree level
           Vector#steady_vector{ count = NewCount, root = InnerNewRoot,
                                 shift = NewShift, tail = NewTail };
       true ->
           Vector#steady_vector{ count = NewCount, root = NewRoot, tail = NewTail }
    end;
remove_last(#steady_vector{ count = 1 }) ->
    new();
remove_last(Vector) when ?is_vector(Vector) ->
    ?empty_vec_error;
remove_last(Vector) ->
    ?vec_error(Vector).

%% @doc Returns updated `Vector2' with element at `0'-based `Index' set to `Value'.
%% `Index' must be an integer and satisfy condition `0 =< Index < size(Vector)'
%% or a `badarg' error will be raised. If `Index' equals `size(Vector)', this
%% function will behave like append/2.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
%% @see append/2
-spec set(Index, Value, Vector1) -> Vector2 | no_return()
            when Index :: index(),
                 Value :: term(),
                 Vector1 :: t(),
                 Vector2 :: t().
set(Index, Value, Vector) when ?is_existing_index(Index, Vector) ->
    case Index >= tail_start(Vector) of
        true ->
            Tail = Vector#steady_vector.tail,
            ValueIndex = Index band ?mask,
            NewTail = tuple_set(ValueIndex, Value, Tail),
            Vector#steady_vector{ tail = NewTail };
        _ ->
            Root = Vector#steady_vector.root,
            NewRoot = set_recur(Root, Vector#steady_vector.shift, Index, Value),
            Vector#steady_vector{ root = NewRoot }
    end;
set(Index, Value, Vector) when ?is_next_index(Index, Vector) ->
    append(Value, Vector);
set(_Index, _Value, Vector) when ?is_vector(Vector) ->
    ?arg_error;
set(_Index, _Value, Vector) ->
    ?vec_error(Vector).

%% @doc Returns number of elements in `Vector'.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
%% @see is_empty/1
-spec size(Vector) -> non_neg_integer()
            when Vector :: t().
size(#steady_vector{ count = Count }) ->
    Count;
size(Vector) ->
    ?vec_error(Vector).

%% @doc Returns list with `Vector''s elements in the same order.
%% `Vector' must be a valid vector or a `{badvec,Vector}' error will be raised.
%% @see from_list/1
-spec to_list(Vector) -> list()
            when Vector :: t().
to_list(Vector) ->
    foldr_leaf_blocks(
      fun (Block, Acc) -> tuple_to_list(Block) ++ Acc end,
      [], Vector).

%% ------------------------------------------------------------------
%% Internal Function Definitions - Appending
%% ------------------------------------------------------------------

append_recur(Node, Level, Tail) when Level > ?shift ->
    LastChildIndex = tuple_size(Node) - 1,
    LastChild = tuple_get(LastChildIndex, Node),
    case append_recur(LastChild, Level - ?shift, Tail) of
        {ok, NewChild} ->
            {ok, tuple_set(LastChildIndex, NewChild, Node)};
        {overflow, TailPath} ->
            append_here(Node, TailPath)
    end;
append_recur(Node, _Level, Tail) ->
    append_here(Node, Tail).

append_here(Node, TailPath) ->
    case tuple_size(Node) < ?block_size of
        true ->
            {ok, tuple_append(TailPath, Node)};
        _ ->
            {overflow, {TailPath}}
    end.

%% ------------------------------------------------------------------
%% Internal Function Definitions - Fetching
%% ------------------------------------------------------------------

fast_get(Index, Vector) ->
    ValueIndex = Index band ?mask,
    case Index >= tail_start(Vector) of
        true ->
            tuple_get(ValueIndex, Vector#steady_vector.tail);
        _ ->
            Node = get_recur(Vector#steady_vector.root, Vector#steady_vector.shift, Index),
            tuple_get(ValueIndex, Node)
    end.

get_recur(Node, Level, Index) when Level > 0 ->
    ChildIndex = (Index bsr Level) band ?mask,
    Child = tuple_get(ChildIndex, Node),
    get_recur(Child, Level - ?shift, Index);
get_recur(Leaf, _Level, _Index) ->
    Leaf.

%% ------------------------------------------------------------------
%% Internal Function Definitions - Folding Left
%% ------------------------------------------------------------------

countfoldl_leaves(Fun, Acc1, Vector) ->
    #steady_vector{ shift = Shift, root = Root, tail = Tail } = Vector,
    Counter1 = 0,
    {Counter2, Acc2} = countfoldl_descendant_leaf_blocks(Fun, Counter1, Acc1, Root, Shift),
    {_Counter3, Acc3} = countfoldl_node_leaves(Fun, Counter2, Acc2, Tail),
    Acc3.

countfoldl_descendant_leaf_blocks(Fun, Counter, Acc, Node, Level) when Level =:= 0 ->
    % leaf node
    countfoldl_node_leaves(Fun, Counter, Acc, Node);
countfoldl_descendant_leaf_blocks(Fun, Counter0, Acc0, Node, Level) ->
    ChildrenLevel = Level - ?shift,
    tuple_foldl(
      fun (Child, Counter, Acc) ->
              countfoldl_descendant_leaf_blocks(Fun, Counter, Acc, Child, ChildrenLevel)
      end,
      Counter0, Acc0, Node).

countfoldl_node_leaves(Fun, Counter, Acc, Node) ->
    tuple_countfoldl(Fun, Counter, Acc, Node).

%% ------------------------------------------------------------------
%% Internal Function Definitions - Folding Right
%% ------------------------------------------------------------------

foldr_leaf_blocks(Fun, Acc1, Vector) ->
    #steady_vector{ shift = Shift, root = Root, tail = Tail } = Vector,
    Acc2 = Fun(Tail, Acc1),
    foldr_descendant_leaf_blocks(Fun, Acc2, Root, Shift).

foldr_descendant_leaf_blocks(Fun, Acc, Node, Level) when Level =:= ?shift ->
    % leaf node
    tuple_foldr(Fun, Acc, Node);
foldr_descendant_leaf_blocks(Fun, Acc0, Node, Level) ->
    ChildrenLevel = Level - ?shift,
    tuple_foldr(
      fun (Child, Acc) ->
              foldr_descendant_leaf_blocks(Fun, Acc, Child, ChildrenLevel)
      end,
      Acc0, Node).

countfoldr_leaves(Fun, Acc1, Vector) ->
    #steady_vector{ count = Size, shift = Shift, root = Root, tail = Tail } = Vector,
    Counter1 = Size - 1,
    {Counter2, Acc2} = countfoldr_node_leaves(Fun, Counter1, Acc1, Tail),
    {_Counter3, Acc3} = countfoldr_descendant_leaf_blocks(Fun, Counter2, Acc2, Root, Shift),
    Acc3.

countfoldr_descendant_leaf_blocks(Fun, Counter, Acc, Node, Level) when Level =:= 0 ->
    % leaf node
    countfoldr_node_leaves(Fun, Counter, Acc, Node);
countfoldr_descendant_leaf_blocks(Fun, Counter0, Acc0, Node, Level) ->
    ChildrenLevel = Level - ?shift,
    tuple_foldr(
      fun (Child, Counter, Acc) ->
              countfoldr_descendant_leaf_blocks(Fun, Counter, Acc, Child, ChildrenLevel)
      end,
      Counter0, Acc0, Node).

countfoldr_node_leaves(Fun, Counter, Acc, Node) ->
    tuple_countfoldr(Fun, Counter, Acc, Node).

%% ------------------------------------------------------------------
%% Internal Function Definitions - Iterating
%% ------------------------------------------------------------------

counteach_leaves(Fun, Vector) ->
    #steady_vector{ shift = Shift, root = Root, tail = Tail } = Vector,
    Counter1 = 0,
    Counter2 = counteach_descendant_leaf_blocks(Fun, Counter1, Root, Shift),
    _Counter3 = counteach_node_leaves(Fun, Counter2, Tail),
    ok.

counteach_descendant_leaf_blocks(Fun, Counter, Node, Level) when Level =:= 0 ->
    % leaf node
    counteach_node_leaves(Fun, Counter, Node);
counteach_descendant_leaf_blocks(Fun, Counter0, Node, Level) ->
    ChildrenLevel = Level - ?shift,
    tuple_foldl(
      fun (Child, Counter) ->
              counteach_descendant_leaf_blocks(Fun, Counter, Child, ChildrenLevel)
      end,
      Counter0, Node).

counteach_node_leaves(Fun, Counter0, Node) ->
    tuple_foldl(
      fun (Value, Counter) ->
              _ = Fun(Counter, Value),
              Counter + 1
      end,
      Counter0, Node).

%% ------------------------------------------------------------------
%% Internal Function Definitions - Mapping
%% ------------------------------------------------------------------

countmap_leaves(Fun, Vector) ->
    #steady_vector{ shift = Shift, root = Root1, tail = Tail1 } = Vector,
    Counter1 = 0,
    {Counter2, Root2} = countmap_descendant_leaf_blocks(Fun, Counter1, Root1, Shift),
    {_Counter3, Tail2} = countmap_node_leaves(Fun, Counter2, Tail1),
    Vector#steady_vector{ root = Root2, tail = Tail2 }.

countmap_descendant_leaf_blocks(Fun, Counter, Node, Level) when Level =:= 0 ->
    % leaf node
    countmap_node_leaves(Fun, Counter, Node);
countmap_descendant_leaf_blocks(Fun, Counter0, Node, Level) ->
    ChildrenLevel = Level - ?shift,
    tuple_map(
      fun (Counter, Child) ->
              countmap_descendant_leaf_blocks(Fun, Counter, Child, ChildrenLevel)
      end,
      Counter0, Node).

countmap_node_leaves(Fun, Counter0, Node) ->
    tuple_countmap(Fun, Counter0, Node).

%% ------------------------------------------------------------------
%% Internal Function Definitions - Removing
%% ------------------------------------------------------------------

remove_last_recur(Node, Level) when Level > ?shift ->
    ChildIndex = tuple_size(Node) - 1,
    Child = tuple_get(ChildIndex, Node),
    case remove_last_recur(Child, Level - ?shift) of
        {{}, LastBlock} ->
            NewNode = tuple_delete(ChildIndex, Node),
            {NewNode, LastBlock};
        {NewChild, LastBlock} ->
            NewNode = tuple_set(ChildIndex, NewChild, Node),
            {NewNode, LastBlock}
    end;
remove_last_recur(Node, _Level) ->
    ChildIndex = tuple_size(Node) - 1,
    Child = tuple_get(ChildIndex, Node),
    NewNode = tuple_delete(ChildIndex, Node),
    {NewNode, Child}.

%% ------------------------------------------------------------------
%% Internal Function Definitions - Setting
%% ------------------------------------------------------------------

set_recur(Node, Level, Index, Val) when Level > 0 ->
    ChildIndex = (Index bsr Level) band ?mask,
    Child = tuple_get(ChildIndex, Node),
    NewChild = set_recur(Child, Level - ?shift, Index, Val),
    tuple_set(ChildIndex, NewChild, Node);
set_recur(Leaf, _Level, Index, Val) ->
    ValueIndex = Index band ?mask,
    tuple_set(ValueIndex, Val, Leaf).

%% ------------------------------------------------------------------
%% Internal Function Definitions - Utilities
%% ------------------------------------------------------------------

tail_start(#steady_vector{} = Vector) ->
    Vector#steady_vector.count - tuple_size(Vector#steady_vector.tail).

-compile({inline,{tuple_append,2}}).
tuple_append(Value, Tuple) ->
    erlang:append_element(Tuple, Value).

-compile({inline,{tuple_delete,2}}).
tuple_delete(Index, Tuple) ->
    erlang:delete_element(Index + 1, Tuple).

-compile({inline,{tuple_delete_last,1}}).
tuple_delete_last(Tuple) ->
    erlang:delete_element(tuple_size(Tuple), Tuple).

-compile({inline,{tuple_get,2}}).
tuple_get(Index, Tuple) ->
    element(Index + 1, Tuple).

-compile({inline,{tuple_foldl,3}}).
tuple_foldl(Fun, Acc, Tuple) ->
    lists:foldl(Fun, Acc, tuple_to_list(Tuple)).

-compile({inline,{tuple_foldl,4}}).
tuple_foldl(Fun, Counter, Acc, Tuple) ->
    List = tuple_to_list(Tuple),
    tuple_foldl_recur(Fun, Counter, Acc, List).

-compile({inline,{tuple_foldl_recur,4}}).
tuple_foldl_recur(_Fun, Counter, Acc, []) ->
    {Counter, Acc};
tuple_foldl_recur(Fun, Counter1, Acc1, [H|T]) ->
    {Counter2, Acc2} = Fun(H, Counter1, Acc1),
    tuple_foldl_recur(Fun, Counter2, Acc2, T).

-compile({inline,{tuple_countfoldl,4}}).
tuple_countfoldl(Fun, Counter, Acc, Tuple) ->
    List = tuple_to_list(Tuple),
    tuple_countfoldl_recur(Fun, Counter, Acc, List).

-compile({inline,{tuple_countfoldl_recur,4}}).
tuple_countfoldl_recur(_Fun, Counter, Acc, []) ->
    {Counter, Acc};
tuple_countfoldl_recur(Fun, Counter, Acc1, [H|T]) ->
    Acc2 = Fun(Counter, H, Acc1),
    tuple_countfoldl_recur(Fun, Counter + 1, Acc2, T).

-compile({inline,{tuple_foldr,3}}).
tuple_foldr(Fun, Acc, Tuple) ->
    lists:foldr(Fun, Acc, tuple_to_list(Tuple)).

-compile({inline,{tuple_foldr,4}}).
tuple_foldr(Fun, Counter, Acc, Tuple) ->
    List = lists:reverse(tuple_to_list(Tuple)),
    tuple_foldr_recur(Fun, Counter, Acc, List).

-compile({inline,{tuple_foldr_recur,4}}).
tuple_foldr_recur(_Fun, Counter, Acc, []) ->
    {Counter, Acc};
tuple_foldr_recur(Fun, Counter1, Acc1, [H|T]) ->
    {Counter2, Acc2} = Fun(H, Counter1, Acc1),
    tuple_foldr_recur(Fun, Counter2, Acc2, T).

-compile({inline,{tuple_countfoldr,4}}).
tuple_countfoldr(Fun, Counter, Acc, Tuple) ->
    List = lists:reverse(tuple_to_list(Tuple)),
    tuple_countfoldr_recur(Fun, Counter, Acc, List).

-compile({inline,{tuple_countfoldr_recur,4}}).
tuple_countfoldr_recur(_Fun, Counter, Acc, []) ->
    {Counter, Acc};
tuple_countfoldr_recur(Fun, Counter, Acc1, [H|T]) ->
    Acc2 = Fun(Counter, H, Acc1),
    tuple_countfoldr_recur(Fun, Counter - 1, Acc2, T).

-compile({inline,{tuple_map,3}}).
tuple_map(Fun, Counter, Tuple) ->
    List = tuple_to_list(Tuple),
    tuple_map_recur(Fun, Counter, List, []).

-compile({inline,{tuple_map_recur,4}}).
tuple_map_recur(_Fun, Counter, [], Acc) ->
    Tuple = list_to_tuple(lists:reverse(Acc)),
    {Counter, Tuple};
tuple_map_recur(Fun, Counter1, [Value1 | T], Acc) ->
    {Counter2, Value2} = Fun(Counter1, Value1),
    tuple_map_recur(Fun, Counter2, T, [Value2 | Acc]).

-compile({inline,{tuple_countmap,3}}).
tuple_countmap(Fun, Counter, Tuple) ->
    List = tuple_to_list(Tuple),
    tuple_countmap_recur(Fun, Counter, List, []).

-compile({inline,{tuple_countmap_recur,4}}).
tuple_countmap_recur(_Fun, Counter, [], Acc) ->
    {Counter, list_to_tuple(lists:reverse(Acc))};
tuple_countmap_recur(Fun, Counter1, [Value1 | T], Acc) ->
    Value2 = Fun(Counter1, Value1),
    Counter2 = Counter1 + 1,
    tuple_countmap_recur(Fun, Counter2, T, [Value2 | Acc]).

-compile({inline,{tuple_set,3}}).
tuple_set(Index, Value, Tuple) ->
    setelement(Index + 1, Tuple, Value).

%% ------------------------------------------------------------------
%% EUnit Definitions
%% ------------------------------------------------------------------
-ifdef(TEST).

empty_test() ->
    Vec = ?MODULE:new(),
    ?assert(?MODULE:is_empty(Vec)),
    ?assertEqual(0, ?MODULE:size(Vec)),
    ?assertEqual(it_is_empty, ?MODULE:last(Vec, it_is_empty)),
    ?assertError(badarg, ?MODULE:get(0, Vec)),
    ?assertError(emptyvec, ?MODULE:last(Vec)),
    ?assertEqual(not_found, ?MODULE:get(1, Vec, not_found)),
    ?assertEqual(error, ?MODULE:find(1, Vec)).

brute_get_test() ->
    Vec = #steady_vector{ count = 5, root = {{0,1,2}, {4}} },
    ?assertEqual(0, ?MODULE:get(0, Vec)),
    ?assertEqual(1, ?MODULE:get(1, Vec)),
    ?assertEqual(2, ?MODULE:get(2, Vec)),
    ?assertEqual(4, ?MODULE:get(4, Vec)).

append_to_tail_test() ->
    Vec1 = ?MODULE:append(0, ?MODULE:new()),
    ?assertEqual(1, ?MODULE:size(Vec1)),
    ?assertNot(?MODULE:is_empty(Vec1)),
    ?assertEqual(0, ?MODULE:get(0, Vec1)),

    Vec2 = ?MODULE:append(1, Vec1),
    ?assertEqual(2, ?MODULE:size(Vec2)),
    ?assertEqual(0, ?MODULE:get(0, Vec2)),
    ?assertEqual(1, ?MODULE:get(1, Vec2)).

append_to_root_test() ->
    C = 68,
    Vec1 =
        lists:foldl(
          fun append_and_assert_element_identity/2,
          ?MODULE:new(), lists:seq(0, C - 1)),
    ?assertEqual(C, ?MODULE:size(Vec1)),

    Vec2 = assert_element_identity( ?MODULE:append(C, Vec1) ),
    ?assertEqual(C + 1, ?MODULE:size(Vec2)),
    ?assertEqual(C, ?MODULE:get(C, Vec2)),

    ?assertError(badarg, ?MODULE:get(C + 1, Vec2)),
    ?assertError(badarg, ?MODULE:get("hello", Vec2)),
    ?assertError(badarg, ?MODULE:get({1}, Vec2)).

remove_all_test() ->
    C = 1000,
    List = lists:seq(1, C),
    Vec = ?MODULE:from_list(List),
    EmptyVec =
        lists:foldr(
          fun (Index, VecAcc) ->
                  NewVecAcc = ?MODULE:remove_last(VecAcc),
                  ?assertEqual(?MODULE:to_list(NewVecAcc), lists:seq(1, Index - 1)),
                  NewVecAcc
          end,
          Vec, List),
    ?assertError(emptyvec, ?MODULE:remove_last(EmptyVec)).

remove_last_tail_test() ->
    Vec1 = ?MODULE:append(0, ?MODULE:new()),
    Vec1_R = ?MODULE:remove_last(Vec1),
    ?assertEqual(0, ?MODULE:size(Vec1_R)),

    Vec2 = ?MODULE:append(1, Vec1),
    Vec2_R = ?MODULE:remove_last(Vec2),
    ?assertEqual(1, ?MODULE:size(Vec2_R)),
    ?assertEqual(0, ?MODULE:get(0, Vec2_R)).

remove_last_root_test() ->
    C = 20,
    Vec1 = lists:foldl(
             fun ?MODULE:append/2,
             ?MODULE:new(), lists:seq(0, C - 1)),
    Vec2 = lists:foldl(
             fun (Index, Acc) ->
                     assert_element_identity(Acc),
                     ?assertEqual(Index + 1, ?MODULE:size(Acc)),
                     ?MODULE:remove_last(Acc)
             end,
             Vec1, lists:seq(C - 1, 0, -1)),

    ?assertEqual(0, ?MODULE:size(Vec2)),
    ?assertError(emptyvec, ?MODULE:remove_last(Vec2)).

set_tail_test() ->
    Vec1 = assert_element_identity(
             ?MODULE:set(1, 1, ?MODULE:set(0, 0, ?MODULE:new())) ),
    ?assertEqual(2, ?MODULE:size(Vec1)),

    C = 4,
    IndexSeq = lists:seq(0, C - 1),
    Vec2A = lists:foldl(
              fun ?MODULE:append/2,
              ?MODULE:new(), IndexSeq),
    Vec2B = lists:foldl(
              fun (Index, Acc) ->
                      ?MODULE:set(Index, Index + 10, Acc)
              end,
              Vec1, IndexSeq),

    ?assertEqual(?MODULE:size(Vec2A), ?MODULE:size(Vec2B)),
    lists:foreach(
      fun (Index) ->
              ?assertEqual(?MODULE:get(Index, Vec2A), ?MODULE:get(Index, Vec2B) - 10)
      end,
      IndexSeq).

set_root_test() ->
    C = 20,
    IndexSeq = lists:seq(0, C - 1),
    Vec1 = lists:foldl(
              fun ?MODULE:append/2,
              ?MODULE:new(), IndexSeq),
    Vec2 = lists:foldl(
              fun (Index, Acc) ->
                      ?MODULE:set(Index, Index + 10, Acc)
              end,
              Vec1, IndexSeq),

    ?assertEqual(?MODULE:size(Vec1), ?MODULE:size(Vec2)),
    lists:foreach(
      fun (Index) ->
              ?assertEqual(?MODULE:get(Index, Vec1), ?MODULE:get(Index, Vec2) - 10)
      end,
      IndexSeq),
    ?assertError(badarg, ?MODULE:set(1, 1, ?MODULE:new())),
    ?assertError(badarg, ?MODULE:set("bla", 1, ?MODULE:new())).

from_and_to_list_test() ->
    C = 1000,
    List = [{rand_compat:uniform(), Index} || Index <- lists:seq(1, C)],

    % convert from
    Vec = ?MODULE:from_list(List),
    ?assertEqual(length(List), ?MODULE:size(Vec)),

    % convert to
    List2 = ?MODULE:to_list(Vec),
    ?assertEqual(?MODULE:size(Vec), length(List2)),

    % all elements were kept
    _ = lists:zipwith(
          fun (Left, Right) ->
                  ?assertEqual(Left, Right)
          end,
          List, List2).

filter_test() ->
    C = 1000,
    ListFilterFun = fun ({V, _Index}) -> V band 1 =:= 0 end,
    VecFilterFun = fun (Index, {_, OrigIndex} = Value) ->
                        ?assertEqual(Index, OrigIndex - 1),
                        ListFilterFun(Value)
                   end,
    List = [{rand_compat:uniform(1000), Index} || Index <- lists:seq(1, C)],
    Vec = ?MODULE:from_list(List),
    FilteredList = lists:filter(ListFilterFun, List),
    FilteredVec = ?MODULE:filter(VecFilterFun, Vec),
    ?MODULE:foldl(
       fun (_Index, VecValue, [ListValue | Next]) ->
               ?assertEqual(VecValue, ListValue),
               Next
       end,
       FilteredList, FilteredVec).

foldl_test() ->
    C = 1000,
    List = [{rand_compat:uniform(), Index} || Index <- lists:seq(1, C)],
    Vec = ?MODULE:from_list(List),
    ?MODULE:foldl(
       fun (VecIndex, {VecValue, OrigVecIndex},
            [{ListValue, OrigListIndex} | Next]) ->
               ?assertEqual(VecValue, ListValue),
               ?assertEqual(VecIndex, OrigVecIndex - 1),
               ?assertEqual(VecIndex, OrigListIndex - 1),
               Next
       end,
       List, Vec).

foldr_test() ->
    C = 1000,
    List = [{rand_compat:uniform(), Index} || Index <- lists:seq(1, C)],
    Vec = ?MODULE:from_list(List),
    RevList = lists:reverse(List),
    ?MODULE:foldr(
       fun (VecIndex, {VecValue, OrigVecIndex},
            [{ListValue, OrigListIndex} | Next]) ->
               ?assertEqual(VecValue, ListValue),
               ?assertEqual(VecIndex, OrigVecIndex - 1),
               ?assertEqual(VecIndex, OrigListIndex - 1),
               Next
       end,
       RevList, Vec).

foreach_test() ->
    C = 1000,
    List = [{rand_compat:uniform(), Index} || Index <- lists:seq(1, C)],
    Vec = ?MODULE:from_list(List),
    ProcDicKey = make_ref(),
    undefined = put(ProcDicKey, List),
    ?MODULE:foreach(
       fun (Index, {Value, OrigIndex}) ->
               [{ListValue, ListOrigIndex} | Next] = get(ProcDicKey),
               ?assertEqual(Value, ListValue),
               ?assertEqual(Index, OrigIndex - 1),
               ?assertEqual(Index, ListOrigIndex - 1),
               put(ProcDicKey, Next)
       end,
       Vec),
    erlang:put(ProcDicKey, undefined).

map_test() ->
    C = 1000,
    ListMapFun = fun ({V, Index}) -> {V * 2, Index} end,
    VecMapFun = fun (Index, {_, OrigIndex} = Value) ->
                        ?assertEqual(Index, OrigIndex - 1),
                        ListMapFun(Value)
                end,
    List = [{rand_compat:uniform(), Index} || Index <- lists:seq(1, C)],
    Vec = ?MODULE:from_list(List),
    MappedList = lists:map(ListMapFun, List),
    MappedVec = ?MODULE:map(VecMapFun, Vec),
    ?MODULE:foldl(
       fun (_Index, VecValue, [ListValue | Next]) ->
               ?assertEqual(VecValue, ListValue),
               Next
       end,
       MappedList, MappedVec).

append_and_assert_element_identity(Value, Vec1) ->
    Vec2 = ?MODULE:append(Value, Vec1),
    assert_element_identity(Vec2).

assert_element_identity(Vec) ->
    C = ?MODULE:size(Vec),

    % "randomly" use different getters
    ValidationFun =
        case C rem 3 of
            0 -> fun (Index) -> ?assertEqual(Index, ?MODULE:get(Index, Vec)) end;
            1 -> fun (Index) -> ?assertEqual(Index, ?MODULE:get(Index, Vec, not_found)) end;
            2 -> fun (Index) -> ?assertEqual({ok, Index}, ?MODULE:find(Index, Vec)) end
        end,

    lists:foreach(ValidationFun, lists:seq(0, C - 1)),

    if C > 0 ->
           ?assertEqual(C - 1, ?MODULE:last(Vec, empty)),
           ?assertEqual(C - 1, ?MODULE:last(Vec));
       true ->
           ?assertEqual(empty, ?MODULE:last(Vec, empty)),
           ?assertError(badarg, ?MODULE:last(Vec))
    end,
    Vec.

-endif.