Current section
Files
Jump to
Current section
Files
src/treelist.erl
-module(treelist).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch]).
-export([new/0, size/1, get/2, first/1, last/1, wrap/1, insert/3, add/2, from_list/1, to_list/1, remove/2, rest/1, drop/2, repeat/2, to_iterator/1, to_iterator_reverse/1, set/3, index_of/2, contains/2, last_index_of/2, filter/2, filter_map/2, map/2, do_reverse/1, reverse/1, try_map/2, take/2, append/2, fold/3, fold_right/3]).
-export_type([tree_list/1, node_/1]).
-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.
?MODULEDOC(
" TreeLists are ordered sequence of elements stored in an efficient binary\n"
" tree structure\n"
" \n"
" New elements can be added at any index of the structure and will\n"
" be stored efficiently with O(log n) complexity\n"
" \n"
" Based on https://en.wikipedia.org/wiki/AVL_tree\n"
" \n"
).
-opaque tree_list(GGL) :: {tree_list, node_(GGL)}.
-opaque node_(GGM) :: {node, GGM, integer(), integer(), node_(GGM), node_(GGM)} |
blank_node.
-file("src/treelist.gleam", 32).
-spec new_node(GGN) -> node_(GGN).
new_node(Value) ->
{node, Value, 1, 1, blank_node, blank_node}.
-file("src/treelist.gleam", 37).
?DOC(" Creates an empty treelist\n").
-spec new() -> tree_list(any()).
new() ->
{tree_list, blank_node}.
-file("src/treelist.gleam", 717).
-spec get_size(node_(any())) -> integer().
get_size(Node) ->
case Node of
blank_node ->
0;
{node, _, _, Size, _, _} ->
Size
end.
-file("src/treelist.gleam", 42).
?DOC(" Returns the number of elements in the provided treelist\n").
-spec size(tree_list(any())) -> integer().
size(List) ->
get_size(erlang:element(2, List)).
-file("src/treelist.gleam", 724).
-spec get_height(node_(any())) -> integer().
get_height(Node) ->
case Node of
blank_node ->
0;
{node, _, Height, _, _, _} ->
Height
end.
-file("src/treelist.gleam", 731).
-spec get_node_at(node_(GLA), integer()) -> node_(GLA).
get_node_at(Node, Index) ->
case Node of
{node, _, _, _, Left, Right} ->
case gleam@int:compare(Index, get_size(Left)) of
lt ->
get_node_at(Left, Index);
gt ->
get_node_at(Right, (Index - get_size(Left)) - 1);
eq ->
Node
end;
_ ->
blank_node
end.
-file("src/treelist.gleam", 67).
?DOC(
" Returns the element at the specified position in the provided treelist\n"
" \n"
" Returns an Error(Nil) if the index is outside the allowed range\n"
" \n"
" Index is zero based\n"
" \n"
" \n"
" ## Examples\n"
" \n"
" ```gleam\n"
" let list = new()\n"
" let assert Ok(new_list) = add(list, \"Test\")\n"
" get(new_list, 0)\n"
" // -> Ok(\"Test\")\n"
" ```\n"
" \n"
" ```gleam\n"
" new() |> get(0)\n"
" // -> Error(Nil)\n"
" ```\n"
).
-spec get(tree_list(GGT), integer()) -> {ok, GGT} | {error, nil}.
get(List, Index) ->
gleam@bool:guard(
(Index < 0) orelse (Index >= size(List)),
{error, nil},
fun() -> case get_node_at(erlang:element(2, List), Index) of
{node, Value, _, _, _, _} ->
{ok, Value};
blank_node ->
{error, nil}
end end
).
-file("src/treelist.gleam", 409).
?DOC(
" Gets the first element from the start of the treelist, if there is one.\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" first(new())\n"
" // -> Error(Nil)\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([0])\n"
" first(list)\n"
" // -> Ok(0)\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2])\n"
" first(list)\n"
" // -> Ok(1)\n"
" ```\n"
).
-spec first(tree_list(GIV)) -> {ok, GIV} | {error, nil}.
first(Tlist) ->
case size(Tlist) of
0 ->
{error, nil};
_ ->
get(Tlist, 0)
end.
-file("src/treelist.gleam", 468).
?DOC(
" Gets the last element from the start of the treelist, if there is one.\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" last(new())\n"
" // -> Error(Nil)\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([0])\n"
" last(list)\n"
" // -> Ok(0)\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2])\n"
" last(list)\n"
" // -> Ok(2)\n"
" ```\n"
).
-spec last(tree_list(GJE)) -> {ok, GJE} | {error, nil}.
last(Tlist) ->
case size(Tlist) of
0 ->
{error, nil};
Size ->
get(Tlist, Size - 1)
end.
-file("src/treelist.gleam", 785).
-spec recalculate(node_(GLG)) -> node_(GLG).
recalculate(Node) ->
case Node of
{node, Value, _, _, Left, Right} ->
New_height = gleam@int:max(get_height(Left), get_height(Right)) + 1,
New_size = (get_size(Left) + get_size(Right)) + 1,
{node, Value, New_height, New_size, Left, Right};
_ ->
blank_node
end.
-file("src/treelist.gleam", 823).
-spec rotate_left(node_(GLM)) -> node_(GLM).
rotate_left(Node) ->
case Node of
{node,
Value,
Height,
Size,
Left,
{node,
Right_value,
Right_height,
Right_size,
Right_left,
Right_right}} ->
recalculate(
{node,
Right_value,
Right_height,
Right_size,
recalculate({node, Value, Height, Size, Left, Right_left}),
Right_right}
);
_ ->
blank_node
end.
-file("src/treelist.gleam", 856).
-spec rotate_right(node_(GLP)) -> node_(GLP).
rotate_right(Node) ->
case Node of
{node,
Value,
Height,
Size,
{node, Left_value, Left_height, Left_size, Left_left, Left_right},
Right} ->
recalculate(
{node,
Left_value,
Left_height,
Left_size,
Left_left,
recalculate({node, Value, Height, Size, Left_right, Right})}
);
_ ->
blank_node
end.
-file("src/treelist.gleam", 896).
-spec get_balance(node_(any()), node_(any())) -> integer().
get_balance(Left, Right) ->
get_height(Right) - get_height(Left).
-file("src/treelist.gleam", 889).
-spec balance_of(node_(any())) -> integer().
balance_of(Node) ->
case Node of
{node, _, _, _, Left, Right} ->
get_balance(Left, Right);
_ ->
9999
end.
-file("src/treelist.gleam", 796).
-spec balance(node_(GLJ)) -> node_(GLJ).
balance(Node) ->
case Node of
{node, Value, Height, Size, Left, Right} ->
case get_balance(Left, Right) of
-2 ->
rotate_right(case balance_of(Left) of
1 ->
{node,
Value,
Height,
Size,
rotate_left(Left),
Right};
_ ->
Node
end);
2 ->
rotate_left(case balance_of(Right) of
-1 ->
{node,
Value,
Height,
Size,
Left,
rotate_right(Right)};
_ ->
Node
end);
_ ->
Node
end;
_ ->
blank_node
end.
-file("src/treelist.gleam", 748).
-spec insert_node_at(node_(GLD), integer(), GLD) -> node_(GLD).
insert_node_at(Node, Index, New_value) ->
case Node of
{node, Value, Height, Size, Left, Right} ->
Left_size = get_size(Left),
Res = case gleam@int:compare(Index, Left_size) of
lt ->
{node,
Value,
Height,
Size,
insert_node_at(Left, Index, New_value),
Right};
eq ->
{node,
Value,
Height,
Size,
insert_node_at(Left, Index, New_value),
Right};
gt ->
{node,
Value,
Height,
Size,
Left,
insert_node_at(
Right,
(Index - Left_size) - 1,
New_value
)}
end,
case recalculate(Res) of
blank_node ->
blank_node;
Node@1 ->
balance(Node@1)
end;
_ ->
new_node(New_value)
end.
-file("src/treelist.gleam", 659).
?DOC(
" Returns the given item wrapped in a list.\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" wrap(1)\n"
" |> to_list\n"
" // -> [1]\n"
"\n"
" wrap([\"a\", \"b\", \"c\"])\n"
" |> to_list\n"
" // -> [[\"a\", \"b\", \"c\"]]\n"
"\n"
" wrap([[]])\n"
" |> to_list\n"
" // -> [[[]]]\n"
" ```\n"
).
-spec wrap(GKI) -> tree_list(GKI).
wrap(Val) ->
{tree_list, insert_node_at(blank_node, 0, Val)}.
-file("src/treelist.gleam", 900).
-spec get_max_int() -> integer().
get_max_int() ->
999999999999.
-file("src/treelist.gleam", 112).
?DOC(
" Inserts an element at the specified index in the provided treelist\n"
" \n"
" Returns an Error(Nil) if the index is outside the allowed range\n"
" \n"
" Index is zero based\n"
" \n"
" Returns a new TreeList containing the provided element\n"
" \n"
" ```gleam\n"
" let list = new()\n"
" let assert Ok(new_list) = insert(list, 0, \"Test\")\n"
" get(new_list, 0)\n"
" // -> Ok(\"Test\")\n"
" ```\n"
" \n"
" ```gleam\n"
" let list = new()\n"
" insert(list, 1, \"Test\")\n"
" // -> Error(Nil)\n"
" ```\n"
).
-spec insert(tree_list(GHC), integer(), GHC) -> {ok, tree_list(GHC)} |
{error, nil}.
insert(List, Index, Value) ->
gleam@bool:guard(
(Index < 0) orelse (Index > size(List)),
{error, nil},
fun() ->
gleam@bool:guard(
Index > get_max_int(),
{error, nil},
fun() ->
{ok,
{tree_list,
insert_node_at(
erlang:element(2, List),
Index,
Value
)}}
end
)
end
).
-file("src/treelist.gleam", 87).
?DOC(
" Adds an element to the end of the provided treelist\n"
" i.e. insert at position size(list)\n"
" \n"
" Returns a new TreeList containing the provided element\n"
" \n"
" ```gleam\n"
" let list = new()\n"
" let assert Ok(new_list) = add(list, \"Test\")\n"
" get(new_list, 0)\n"
" // -> Ok(\"Test\")\n"
" ```\n"
).
-spec add(tree_list(GGX), GGX) -> {ok, tree_list(GGX)} | {error, nil}.
add(List, Value) ->
insert(List, size(List), Value).
-file("src/treelist.gleam", 175).
?DOC(
" Takes a list and returns a new TreeList containing all the\n"
" elements from the list in the same order as that list\n"
" \n"
" Returns an Error(Nil) in the case that the list is too large\n"
" \n"
" ```gleam\n"
" let assert Ok(list) = from_list([1,2,3])\n"
" get(list, 1)\n"
" // -> Ok(2)\n"
" ```\n"
).
-spec from_list(list(GHP)) -> {ok, tree_list(GHP)} | {error, nil}.
from_list(List) ->
gleam@list:try_fold(List, new(), fun(Acc, Val) -> add(Acc, Val) end).
-file("src/treelist.gleam", 904).
-spec do_to_list(node_(GLY)) -> list(GLY).
do_to_list(Node) ->
case Node of
{node, Value, _, _, Left, Right} ->
Left_list = case Left of
blank_node ->
[];
_ ->
do_to_list(Left)
end,
Right_list = case Right of
blank_node ->
[];
_ ->
do_to_list(Right)
end,
lists:append(Left_list, [Value | Right_list]);
_ ->
[]
end.
-file("src/treelist.gleam", 160).
?DOC(
" Converts a TreeList into a standard Gleam list\n"
" \n"
" ```gleam\n"
" let list = new()\n"
" let assert Ok(new_list) = insert(list, 0, \"Test\")\n"
" let assert Ok(new_list2) = insert(new_list, 1, \"Second\")\n"
" to_list(new_list2)\n"
" // -> [\"Test\", \"Second\"]\n"
" ```\n"
).
-spec to_list(tree_list(GHM)) -> list(GHM).
to_list(L) ->
do_to_list(erlang:element(2, L)).
-file("src/treelist.gleam", 997).
-spec find_ultimate_left(node_(GMF)) -> node_(GMF).
find_ultimate_left(Node) ->
case Node of
{node, _, _, _, Left, _} ->
case Left of
blank_node ->
Node;
_ ->
find_ultimate_left(Left)
end;
blank_node ->
erlang:error(#{gleam_error => panic,
message => <<"`panic` expression evaluated."/utf8>>,
module => <<"treelist"/utf8>>,
function => <<"find_ultimate_left"/utf8>>,
line => 1005})
end.
-file("src/treelist.gleam", 922).
-spec remove_node_at(node_(GMB), integer()) -> {node_(GMB),
gleam@option:option(GMB)}.
remove_node_at(Node, Index) ->
case Node of
{node, Value, Height, Size, Left, Right} ->
{Res, Removed_value, Rebalance} = case gleam@int:compare(
Index,
get_size(Left)
) of
lt ->
case remove_node_at(Left, Index) of
{New_node, {some, Rval}} ->
{{node, Value, Height, Size, New_node, Right},
{some, Rval},
true};
_ ->
{blank_node, none, false}
end;
gt ->
case remove_node_at(Right, (Index - get_size(Left)) - 1) of
{New_node@1, {some, Rval@1}} ->
{{node, Value, Height, Size, Left, New_node@1},
{some, Rval@1},
true};
_ ->
{blank_node, none, false}
end;
eq ->
case {Left, Right} of
{blank_node, blank_node} ->
{blank_node, {some, Value}, false};
{_, blank_node} ->
{Left, {some, Value}, false};
{blank_node, _} ->
{Right, {some, Value}, false};
{_, _} ->
Temp = find_ultimate_left(Right),
case {remove_node_at(Right, 0), Temp} of
{{New_node@2, _},
{node, Unode_value, _, _, _, _}} ->
{{node,
Unode_value,
Height,
Size,
Left,
New_node@2},
{some, Value},
true};
{_, _} ->
{blank_node, none, false}
end
end
end,
case Rebalance of
false ->
{Res, Removed_value};
true ->
case recalculate(Res) of
blank_node ->
{blank_node, none};
Node@1 ->
{balance(Node@1), Removed_value}
end
end;
_ ->
{blank_node, none}
end.
-file("src/treelist.gleam", 202).
?DOC(
" Removes an element at the specified index in the provided treelist\n"
" \n"
" Returns an Error(Nil) if the index is outside the allowed range\n"
" \n"
" Index is zero based\n"
" \n"
" Returns a tuple containing the value at the specified index and the new TreeList\n"
" \n"
" ```gleam\n"
" let list = new()\n"
" let assert Ok(new_list) = insert(list, 0, \"Test\")\n"
" get(new_list, 0)\n"
" // -> Ok(\"Test\")\n"
" remove(new_list, 0)\n"
" // -> #(\"Test\", TreeList(..))\n"
" ```\n"
" \n"
" ```gleam\n"
" let list = new()\n"
" remove(list, 1)\n"
" // -> Error(Nil)\n"
" ```\n"
).
-spec remove(tree_list(GHU), integer()) -> {ok, {GHU, tree_list(GHU)}} |
{error, nil}.
remove(List, Index) ->
gleam@bool:guard(
(Index < 0) orelse (Index > size(List)),
{error, nil},
fun() -> case remove_node_at(erlang:element(2, List), Index) of
{New_root, {some, Value}} ->
{ok, {Value, {tree_list, New_root}}};
_ ->
{error, nil}
end end
).
-file("src/treelist.gleam", 439).
?DOC(
" Returns a new treelist minus the first element. If the treelist is empty, \n"
" `Error(Nil)` is returned.\n"
"\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" rest(new())\n"
" // -> Error(Nil)\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([0])\n"
" rest(list)\n"
" // -> Ok([])\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2])\n"
" rest(list)\n"
" // -> Ok([2])\n"
" ```\n"
).
-spec rest(tree_list(GIZ)) -> {ok, tree_list(GIZ)} | {error, nil}.
rest(Tlist) ->
case size(Tlist) of
0 ->
{error, nil};
1 ->
{ok, new()};
_ ->
{ok,
{tree_list,
erlang:element(
1,
remove_node_at(erlang:element(2, Tlist), 0)
)}}
end.
-file("src/treelist.gleam", 592).
?DOC(
" Returns a treelist that is the given treelist with up to the given number of\n"
" elements removed from the front of the treelist.\n"
"\n"
" If the treelist has less than the number of elements an empty treelist is\n"
" returned.\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4])\n"
" drop(list, 2)\n"
" |> to_list\n"
" // -> [3, 4]\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4])\n"
" drop(list, 9)\n"
" |> to_list\n"
" // -> []\n"
" ```\n"
).
-spec drop(tree_list(GKC), integer()) -> tree_list(GKC).
drop(Tlist, Up_to_n) ->
case gleam@int:compare(size(Tlist), Up_to_n) of
eq ->
new();
lt ->
new();
gt ->
{tree_list,
begin
_pipe = gleam@yielder:repeat(0),
_pipe@1 = gleam@yielder:take(_pipe, Up_to_n),
gleam@yielder:fold(
_pipe@1,
erlang:element(2, Tlist),
fun(Acc, N) ->
{New_list, _} = remove_node_at(Acc, N),
New_list
end
)
end}
end.
-file("src/treelist.gleam", 1009).
-spec do_repeat(GMI, integer(), node_(GMI)) -> node_(GMI).
do_repeat(A, Times, Acc) ->
case Times =< 0 of
true ->
Acc;
false ->
do_repeat(A, Times - 1, insert_node_at(Acc, 0, A))
end.
-file("src/treelist.gleam", 229).
?DOC(
" Builds a list of a given value a given number of times.\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" repeat(\"a\", times: 0)\n"
" // -> new()\n"
" ```\n"
"\n"
" ```gleam\n"
" repeat(\"a\", times: 5)\n"
" |> to_list\n"
" // -> [\"a\", \"a\", \"a\", \"a\", \"a\"]\n"
" ```\n"
).
-spec repeat(GHZ, integer()) -> {ok, tree_list(GHZ)} | {error, nil}.
repeat(A, Times) ->
gleam@bool:guard(
Times > get_max_int(),
{error, nil},
fun() -> {ok, {tree_list, do_repeat(A, Times, blank_node)}} end
).
-file("src/treelist.gleam", 1052).
-spec get_left_stack(node_(GMV), list(node_(GMV))) -> list(node_(GMV)).
get_left_stack(Node, Acc) ->
case Node of
blank_node ->
Acc;
{node, _, _, _, Left, _} ->
get_left_stack(Left, [Node | Acc])
end.
-file("src/treelist.gleam", 1016).
-spec node_iterator(node_(GML), fun((node_(GML), GML, integer()) -> GMO)) -> gleam@yielder:yielder(GMO).
node_iterator(Tlist, Ret_fn) ->
Stack = {get_left_stack(Tlist, []), 0},
Yield = fun(Acc) -> case Acc of
{[{node, Value, _, _, _, Right} = Node | Rest], Index} ->
Rest@1 = lists:append(get_left_stack(Right, []), Rest),
{next, Ret_fn(Node, Value, Index), {Rest@1, Index + 1}};
_ ->
done
end end,
gleam@yielder:unfold(Stack, Yield).
-file("src/treelist.gleam", 244).
?DOC(
" Creates an iterator that yields each element from the given treelist.\n"
"\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4])\n"
" to_iterator(list)\n"
" |> to_list\n"
" // -> [1, 2, 3, 4]\n"
" ```\n"
).
-spec to_iterator(tree_list(GID)) -> gleam@yielder:yielder(GID).
to_iterator(Tlist) ->
node_iterator(erlang:element(2, Tlist), fun(_, Value, _) -> Value end).
-file("src/treelist.gleam", 1062).
-spec get_right_stack(node_(GNB), list(node_(GNB))) -> list(node_(GNB)).
get_right_stack(Node, Acc) ->
case Node of
blank_node ->
Acc;
{node, _, _, _, _, Right} ->
get_right_stack(Right, [Node | Acc])
end.
-file("src/treelist.gleam", 1034).
-spec node_iterator_reverse(
node_(GMQ),
fun((node_(GMQ), GMQ, integer()) -> GMT)
) -> gleam@yielder:yielder(GMT).
node_iterator_reverse(Tlist, Ret_fn) ->
Stack = {get_right_stack(Tlist, []), 0},
Yield = fun(Acc) -> case Acc of
{[{node, Value, _, _, Left, _} = Node | Rest], Index} ->
Rest@1 = lists:append(get_right_stack(Left, []), Rest),
{next, Ret_fn(Node, Value, Index), {Rest@1, Index + 1}};
_ ->
done
end end,
gleam@yielder:unfold(Stack, Yield).
-file("src/treelist.gleam", 258).
?DOC(
" Creates an iterator that yields each element from the given treelist.\n"
"\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4])\n"
" to_iterator_reverse(list)\n"
" |> to_list\n"
" // -> [4, 3, 2, 1]\n"
" ```\n"
).
-spec to_iterator_reverse(tree_list(GIG)) -> gleam@yielder:yielder(GIG).
to_iterator_reverse(Tlist) ->
node_iterator_reverse(
erlang:element(2, Tlist),
fun(_, Value, _) -> Value end
).
-file("src/treelist.gleam", 1072).
-spec set_node_at(node_(GNH), integer(), GNH) -> node_(GNH).
set_node_at(Node, Index, New_value) ->
case Node of
{node, Value, Height, Size, Left, Right} ->
Left_size = get_size(Left),
case gleam@int:compare(Index, Left_size) of
lt ->
{node,
Value,
Height,
Size,
set_node_at(Left, Index, New_value),
Right};
gt ->
{node,
Value,
Height,
Size,
Left,
set_node_at(Right, (Index - Left_size) - 1, New_value)};
eq ->
{node, New_value, Height, Size, Left, Right}
end;
_ ->
blank_node
end.
-file("src/treelist.gleam", 140).
?DOC(
" Updates the element at index specified in the provided treelist\n"
" \n"
" Returns an Error(Nil) if the index is outside the allowed range\n"
" \n"
" Index is zero based\n"
" \n"
" Returns a new TreeList containing the updated node\n"
" \n"
" ```gleam\n"
" let list = new()\n"
" let assert Ok(new_list) = add(list, \"Test\")\n"
" get(new_list, 0)\n"
" // -> Ok(\"Test\")\n"
" let assert Ok(new_list) = set(list, 0, \"Updated\")\n"
" get(new_list, 0)\n"
" // -> Ok(\"Updated\")\n"
" ```\n"
).
-spec set(tree_list(GHH), integer(), GHH) -> {ok, tree_list(GHH)} | {error, nil}.
set(List, Index, Value) ->
gleam@bool:guard(
(Index < 0) orelse (Index >= size(List)),
{error, nil},
fun() ->
{ok,
{tree_list, set_node_at(erlang:element(2, List), Index, Value)}}
end
).
-file("src/treelist.gleam", 1102).
-spec do_index_of(list(node_(GNK)), integer(), GNK) -> integer().
do_index_of(Node_stack, Index, Search_value) ->
case Node_stack of
[{node, Value, _, _, _, Right} | Rest] ->
case Value =:= Search_value of
true ->
Index;
false ->
do_index_of(
lists:append(get_left_stack(Right, []), Rest),
Index + 1,
Search_value
)
end;
_ ->
-1
end.
-file("src/treelist.gleam", 283).
?DOC(
" Returns the index of the first occurrence of the specified element\n"
" in this list, or -1 if this list does not contain the element.\n"
" \n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4])\n"
" index_of(list, 3)\n"
" // -> 2\n"
" ```\n"
" \n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4, 2, 2])\n"
" index_of(list, 2)\n"
" // -> 1\n"
" ```\n"
" \n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4])\n"
" index_of(list, 999)\n"
" // -> -1\n"
" ```\n"
).
-spec index_of(tree_list(GIJ), GIJ) -> integer().
index_of(Tlist, Item) ->
Stack = get_left_stack(erlang:element(2, Tlist), []),
do_index_of(Stack, 0, Item).
-file("src/treelist.gleam", 328).
?DOC(
" Returns true if this list contains the specified element.\n"
" \n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4])\n"
" contains(list, 3)\n"
" // -> True\n"
" ```\n"
" \n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4])\n"
" contains(list, 999)\n"
" // -> False\n"
" ```\n"
).
-spec contains(tree_list(GIN), GIN) -> boolean().
contains(Tlist, Item) ->
index_of(Tlist, Item) >= 0.
-file("src/treelist.gleam", 1123).
-spec do_last_index_of(list(node_(GNN)), integer(), GNN) -> integer().
do_last_index_of(Node_stack, Index, Search_value) ->
case Node_stack of
[{node, Value, _, _, Left, _} | Rest] ->
case Value =:= Search_value of
true ->
Index;
false ->
do_last_index_of(
lists:append(get_right_stack(Left, []), Rest),
Index - 1,
Search_value
)
end;
_ ->
-1
end.
-file("src/treelist.gleam", 309).
?DOC(
" Returns the index of the last occurrence of the specified element\n"
" in this list, or -1 if this list does not contain the element.\n"
" \n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4])\n"
" last_index_of(list, 3)\n"
" // -> 2\n"
" ```\n"
" \n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4, 2, 2])\n"
" last_index_of(list, 2)\n"
" // -> 5\n"
" ```\n"
" \n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4])\n"
" last_index_of(list, 999)\n"
" // -> -1\n"
" ```\n"
).
-spec last_index_of(tree_list(GIL), GIL) -> integer().
last_index_of(Tlist, Item) ->
Stack = get_right_stack(erlang:element(2, Tlist), []),
do_last_index_of(Stack, size(Tlist) - 1, Item).
-file("src/treelist.gleam", 1144).
-spec do_filter(list(node_(GNQ)), node_(GNQ), fun((GNQ) -> boolean())) -> node_(GNQ).
do_filter(Node_stack, Acc, Filter_fn) ->
case Node_stack of
[{node, Value, _, _, _, Right} | Rest] ->
do_filter(
lists:append(get_left_stack(Right, []), Rest),
case Filter_fn(Value) of
true ->
insert_node_at(Acc, get_size(Acc), Value);
false ->
Acc
end,
Filter_fn
);
_ ->
Acc
end.
-file("src/treelist.gleam", 351).
?DOC(
" Returns a new treelist containing only the elements from the first treelist for\n"
" which the given functions returns `True`.\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([2, 4, 6, 1])\n"
" filter(list), fn(x) { x > 2 })\n"
" |> to_list\n"
" // -> [4, 6]\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([2, 4, 6, 1])\n"
" filter(list), fn(x) { x > 6 })\n"
" |> to_list\n"
" // -> []\n"
" ```\n"
).
-spec filter(tree_list(GIP), fun((GIP) -> boolean())) -> tree_list(GIP).
filter(Tlist, Filter_fn) ->
Stack = get_left_stack(erlang:element(2, Tlist), []),
{tree_list, do_filter(Stack, blank_node, Filter_fn)}.
-file("src/treelist.gleam", 1165).
-spec do_filter_map(
list(node_(GNV)),
node_(GNY),
fun((GNV) -> {ok, GNY} | {error, any()})
) -> node_(GNY).
do_filter_map(Node_stack, Acc, Filter_fn) ->
case Node_stack of
[{node, Value, _, _, _, Right} | Rest] ->
do_filter_map(
lists:append(get_left_stack(Right, []), Rest),
case Filter_fn(Value) of
{ok, Val} ->
insert_node_at(Acc, get_size(Acc), Val);
_ ->
Acc
end,
Filter_fn
);
_ ->
Acc
end.
-file("src/treelist.gleam", 493).
?DOC(
" Returns a new treelist containing only the elements from the first treelist for\n"
" which the given functions returns `Ok(_)`.\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([2, 4, 6, 1])\n"
" filter_map(list, Error)\n"
" // -> []\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([2, 4, 6, 1])\n"
" filter_map(list, fn(x) { Ok(x + 1) })\n"
" |> to_list\n"
" // -> [3, 5, 7, 2]\n"
" ```\n"
).
-spec filter_map(tree_list(GJI), fun((GJI) -> {ok, GJK} | {error, any()})) -> tree_list(GJK).
filter_map(Tlist, Filter_fn) ->
Stack = get_left_stack(erlang:element(2, Tlist), []),
{tree_list, do_filter_map(Stack, blank_node, Filter_fn)}.
-file("src/treelist.gleam", 1186).
-spec do_map(list(node_(GOE)), node_(GOH), fun((GOE) -> GOH)) -> node_(GOH).
do_map(Node_stack, Acc, Filter_fn) ->
case Node_stack of
[{node, Value, _, _, _, Right} | Rest] ->
do_map(
lists:append(get_left_stack(Right, []), Rest),
insert_node_at(Acc, get_size(Acc), Filter_fn(Value)),
Filter_fn
);
_ ->
Acc
end.
-file("src/treelist.gleam", 513).
?DOC(
" Returns a new treelist containing only the elements of the first list after \n"
" the function has been applied to each one.\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([2, 4, 6])\n"
" map(list, fn(x) { x * 2 })\n"
" |> to_list\n"
" // -> [4, 8, 12]\n"
" ```\n"
).
-spec map(tree_list(GJP), fun((GJP) -> GJR)) -> tree_list(GJR).
map(Tlist, Filter_fn) ->
Stack = get_left_stack(erlang:element(2, Tlist), []),
{tree_list, do_map(Stack, blank_node, Filter_fn)}.
-file("src/treelist.gleam", 1203).
-spec do_reverse(node_(GOK)) -> node_(GOK).
do_reverse(Node) ->
case Node of
{node, Value, Height, Size, Left, Right} ->
{node, Value, Height, Size, do_reverse(Right), do_reverse(Left)};
_ ->
Node
end.
-file("src/treelist.gleam", 384).
?DOC(
" Creates a new treelist from a given treelist containing the same elements but in the\n"
" opposite order.\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" reverse(new())\n"
" |> to_list\n"
" // -> []\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1])\n"
" reverse(list)\n"
" |> to_list\n"
" // -> [1]\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2])\n"
" reverse(list)\n"
" |> to_list\n"
" // -> [2, 1]\n"
" ```\n"
).
-spec reverse(tree_list(GIS)) -> tree_list(GIS).
reverse(Tlist) ->
{tree_list, do_reverse(erlang:element(2, Tlist))}.
-file("src/treelist.gleam", 1217).
-spec do_try_map(
list(node_(GON)),
node_(GOQ),
fun((GON) -> {ok, GOQ} | {error, GOS})
) -> {ok, node_(GOQ)} | {error, GOS}.
do_try_map(Node_stack, Acc, Filter_fn) ->
case Node_stack of
[{node, Value, _, _, _, Right} | Rest] ->
case Filter_fn(Value) of
{error, Err} ->
{error, Err};
{ok, Value@1} ->
do_try_map(
lists:append(get_left_stack(Right, []), Rest),
insert_node_at(Acc, get_size(Acc), Value@1),
Filter_fn
)
end;
_ ->
{ok, Acc}
end.
-file("src/treelist.gleam", 559).
?DOC(
" Takes a function that returns a `Result` and applies it to each element in a\n"
" given treelist in turn.\n"
"\n"
" If the function returns `Ok(new_value)` for all elements in the treelist then a\n"
" treelist of the new values is returned.\n"
"\n"
" If the function returns `Error(reason)` for any of the elements then it is\n"
" returned immediately. None of the elements in the treelist are processed after\n"
" one returns an `Error`.\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3])\n"
" let assert Ok(tl) = try_map(list, fn(x) { Ok(x + 2) })\n"
" treelist.to_list(tl)\n"
" // -> [3, 4, 5]\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3])\n"
" try_map(list, fn(_) { Error(0) })\n"
" // -> Error(0)\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([[1], [2, 3]])\n"
" let assert Ok(tl) = try_map(list, first)\n"
" treelist.to_list(tl)\n"
" // -> Ok([1, 2])\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([[1], [], [2]])\n"
" try_map(list, first)\n"
" // -> Error(Nil)\n"
" ```\n"
).
-spec try_map(tree_list(GJT), fun((GJT) -> {ok, GJV} | {error, GJW})) -> {ok,
tree_list(GJV)} |
{error, GJW}.
try_map(Tlist, Filter_fn) ->
Stack = get_left_stack(erlang:element(2, Tlist), []),
case do_try_map(Stack, blank_node, Filter_fn) of
{error, Err} ->
{error, Err};
{ok, Node} ->
{ok, {tree_list, Node}}
end.
-file("src/treelist.gleam", 1238).
-spec do_take(list(node_(GOY)), node_(GOY), integer()) -> node_(GOY).
do_take(Node_stack, Acc, Index) ->
case Index >= 0 of
true ->
case Node_stack of
[{node, Value, _, _, _, Right} | Rest] ->
do_take(
lists:append(get_left_stack(Right, []), Rest),
insert_node_at(Acc, get_size(Acc), Value),
Index - 1
);
_ ->
Acc
end;
false ->
Acc
end.
-file("src/treelist.gleam", 631).
?DOC(
" Returns a treelist containing the first given number of elements from the given\n"
" treelist.\n"
"\n"
" If the treelist has less than the number of elements then the full treelist is\n"
" returned.\n"
"\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4])\n"
" take(list, 2)\n"
" |> to_list\n"
" // -> [1, 2]\n"
" ```\n"
"\n"
" ```gleam\n"
" let assert Ok(list) = from_list([1, 2, 3, 4])\n"
" take(list, 9)\n"
" |> to_list\n"
" // -> [1, 2, 3, 4]\n"
" ```\n"
).
-spec take(tree_list(GKF), integer()) -> tree_list(GKF).
take(Tlist, Up_to_n) ->
case gleam@int:compare(size(Tlist), Up_to_n) of
eq ->
Tlist;
lt ->
Tlist;
gt ->
{tree_list,
do_take(
get_left_stack(erlang:element(2, Tlist), []),
blank_node,
Up_to_n - 1
)}
end.
-file("src/treelist.gleam", 1260).
-spec do_append(list(node_(GPD)), node_(GPD)) -> node_(GPD).
do_append(Node_stack, Acc) ->
case Node_stack of
[{node, Value, _, _, _, Right} | Rest] ->
do_append(
lists:append(get_left_stack(Right, []), Rest),
insert_node_at(Acc, get_size(Acc), Value)
);
_ ->
Acc
end.
-file("src/treelist.gleam", 675).
?DOC(
" Joins one treelist onto the end of another.\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" let assert Ok(l1) = treelist.from_list([1, 2])\n"
" let assert Ok(l2) = treelist.from_list([3])\n"
" let assert Ok(list) = append(l1, l2)\n"
" to_list(list)\n"
" // -> [1, 2, 3]\n"
" ```\n"
).
-spec append(tree_list(GKK), tree_list(GKK)) -> {ok, tree_list(GKK)} |
{error, nil}.
append(Tlist, Tlist2) ->
gleam@bool:guard(
(size(Tlist) + size(Tlist2)) > get_max_int(),
{error, nil},
fun() ->
{ok,
{tree_list,
do_append(
get_left_stack(erlang:element(2, Tlist2), []),
erlang:element(2, Tlist)
)}}
end
).
-file("src/treelist.gleam", 1272).
-spec do_fold(list(node_(GPI)), GPL, fun((GPL, GPI) -> GPL)) -> GPL.
do_fold(Node_stack, Acc, Fold_fn) ->
case Node_stack of
[{node, Value, _, _, _, Right} | Rest] ->
do_fold(
lists:append(get_left_stack(Right, []), Rest),
Fold_fn(Acc, Value),
Fold_fn
);
_ ->
Acc
end.
-file("src/treelist.gleam", 693).
?DOC(
" Reduces a treelist of elements into a single value by calling a given function\n"
" on each element, going from left to right.\n"
"\n"
" `fold([1, 2, 3], 0, add)` is the equivalent of\n"
" `add(add(add(0, 1), 2), 3)`.\n"
).
-spec fold(tree_list(GKQ), GKS, fun((GKS, GKQ) -> GKS)) -> GKS.
fold(List, Initial, Fun) ->
do_fold(get_left_stack(erlang:element(2, List), []), Initial, Fun).
-file("src/treelist.gleam", 1289).
-spec do_fold_right(list(node_(GPM)), GPP, fun((GPP, GPM) -> GPP)) -> GPP.
do_fold_right(Node_stack, Acc, Fold_fn) ->
case Node_stack of
[{node, Value, _, _, Left, _} | Rest] ->
do_fold_right(
lists:append(get_right_stack(Left, []), Rest),
Fold_fn(Acc, Value),
Fold_fn
);
_ ->
Acc
end.
-file("src/treelist.gleam", 707).
?DOC(
" Reduces a treelist of elements into a single value by calling a given function\n"
" on each element, going from right to left.\n"
"\n"
" `fold_right([1, 2, 3], 0, add)` is the equivalent of\n"
" `add(add(add(0, 3), 2), 1)`.\n"
).
-spec fold_right(tree_list(GKT), GKV, fun((GKV, GKT) -> GKV)) -> GKV.
fold_right(List, Initial, Fun) ->
do_fold_right(get_right_stack(erlang:element(2, List), []), Initial, Fun).