aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib/src/gb_trees.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/stdlib/src/gb_trees.erl')
-rw-r--r--lib/stdlib/src/gb_trees.erl191
1 files changed, 95 insertions, 96 deletions
diff --git a/lib/stdlib/src/gb_trees.erl b/lib/stdlib/src/gb_trees.erl
index de0c239e26..c4a20d92a7 100644
--- a/lib/stdlib/src/gb_trees.erl
+++ b/lib/stdlib/src/gb_trees.erl
@@ -1,19 +1,19 @@
-%% -*- coding: utf-8 -*-
%%
%% %CopyrightBegin%
%%
-%% Copyright Ericsson AB 2001-2012. All Rights Reserved.
+%% Copyright Ericsson AB 2001-2015. All Rights Reserved.
%%
-%% The contents of this file are subject to the Erlang Public License,
-%% Version 1.1, (the "License"); you may not use this file except in
-%% compliance with the License. You should have received a copy of the
-%% Erlang Public License along with this software. If not, it can be
-%% retrieved online at http://www.erlang.org/.
-%%
-%% Software distributed under the License is distributed on an "AS IS"
-%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
-%% the License for the specific language governing rights and limitations
-%% under the License.
+%% Licensed under the Apache License, Version 2.0 (the "License");
+%% you may not use this file except in compliance with the License.
+%% You may obtain a copy of the License at
+%%
+%% http://www.apache.org/licenses/LICENSE-2.0
+%%
+%% Unless required by applicable law or agreed to in writing, software
+%% distributed under the License is distributed on an "AS IS" BASIS,
+%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+%% See the License for the specific language governing permissions and
+%% limitations under the License.
%%
%% %CopyrightEnd%
%%
@@ -103,6 +103,10 @@
%% approach is that it does not require the complete list of all
%% elements to be built in memory at one time.
%%
+%% - iterator_from(K, T): returns an iterator that can be used for
+%% traversing the entries of tree T with key greater than or
+%% equal to K; see `next'.
+%%
%% - next(S): returns {X, V, S1} where X is the smallest key referred to
%% by the iterator S, and S1 is the new iterator to be used for
%% traversing the remaining entries, or the atom `none' if no entries
@@ -118,7 +122,7 @@
update/3, enter/3, delete/2, delete_any/2, balance/1,
is_defined/2, keys/1, values/1, to_list/1, from_orddict/1,
smallest/1, largest/1, take_smallest/1, take_largest/1,
- iterator/1, next/1, map/2]).
+ iterator/1, iterator_from/2, next/1, map/2]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -153,25 +157,24 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Some types.
--export_type([iter/0]).
+-export_type([tree/0, tree/2, iter/0, iter/2]).
--type gb_tree_node() :: 'nil' | {_, _, _, _}.
--opaque iter() :: [gb_tree_node()].
-
-%% A declaration equivalent to the following is currently hard-coded
-%% in erl_types.erl
-%%
-%% -opaque gb_tree() :: {non_neg_integer(), gb_tree_node()}.
+-type gb_tree_node(K, V) :: 'nil'
+ | {K, V, gb_tree_node(K, V), gb_tree_node(K, V)}.
+-opaque tree(Key, Value) :: {non_neg_integer(), gb_tree_node(Key, Value)}.
+-type tree() :: tree(_, _).
+-opaque iter(Key, Value) :: [gb_tree_node(Key, Value)].
+-type iter() :: iter(_, _).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
--spec empty() -> gb_tree().
+-spec empty() -> tree().
empty() ->
{0, nil}.
-spec is_empty(Tree) -> boolean() when
- Tree :: gb_tree().
+ Tree :: tree().
is_empty({0, nil}) ->
true;
@@ -179,17 +182,15 @@ is_empty(_) ->
false.
-spec size(Tree) -> non_neg_integer() when
- Tree :: gb_tree().
+ Tree :: tree().
size({Size, _}) when is_integer(Size), Size >= 0 ->
Size.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
--spec lookup(Key, Tree) -> 'none' | {'value', Val} when
- Key :: term(),
- Val :: term(),
- Tree :: gb_tree().
+-spec lookup(Key, Tree) -> 'none' | {'value', Value} when
+ Tree :: tree(Key, Value).
lookup(Key, {_, T}) ->
lookup_1(Key, T).
@@ -215,8 +216,7 @@ lookup_1(_, nil) ->
%% This is a specialized version of `lookup'.
-spec is_defined(Key, Tree) -> boolean() when
- Key :: term(),
- Tree :: gb_tree().
+ Tree :: tree(Key, Value :: term()).
is_defined(Key, {_, T}) ->
is_defined_1(Key, T).
@@ -234,10 +234,8 @@ is_defined_1(_, nil) ->
%% This is a specialized version of `lookup'.
--spec get(Key, Tree) -> Val when
- Key :: term(),
- Tree :: gb_tree(),
- Val :: term().
+-spec get(Key, Tree) -> Value when
+ Tree :: tree(Key, Value).
get(Key, {_, T}) ->
get_1(Key, T).
@@ -251,11 +249,9 @@ get_1(_, {_, Value, _, _}) ->
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
--spec update(Key, Val, Tree1) -> Tree2 when
- Key :: term(),
- Val :: term(),
- Tree1 :: gb_tree(),
- Tree2 :: gb_tree().
+-spec update(Key, Value, Tree1) -> Tree2 when
+ Tree1 :: tree(Key, Value),
+ Tree2 :: tree(Key, Value).
update(Key, Val, {S, T}) ->
T1 = update_1(Key, Val, T),
@@ -272,11 +268,9 @@ update_1(Key, Value, {_, _, Smaller, Bigger}) ->
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
--spec insert(Key, Val, Tree1) -> Tree2 when
- Key :: term(),
- Val :: term(),
- Tree1 :: gb_tree(),
- Tree2 :: gb_tree().
+-spec insert(Key, Value, Tree1) -> Tree2 when
+ Tree1 :: tree(Key, Value),
+ Tree2 :: tree(Key, Value).
insert(Key, Val, {S, T}) when is_integer(S) ->
S1 = S+1,
@@ -325,11 +319,9 @@ insert_1(Key, _, _, _) ->
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
--spec enter(Key, Val, Tree1) -> Tree2 when
- Key :: term(),
- Val :: term(),
- Tree1 :: gb_tree(),
- Tree2 :: gb_tree().
+-spec enter(Key, Value, Tree1) -> Tree2 when
+ Tree1 :: tree(Key, Value),
+ Tree2 :: tree(Key, Value).
enter(Key, Val, T) ->
case is_defined(Key, T) of
@@ -353,8 +345,8 @@ count(nil) ->
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-spec balance(Tree1) -> Tree2 when
- Tree1 :: gb_tree(),
- Tree2 :: gb_tree().
+ Tree1 :: tree(Key, Value),
+ Tree2 :: tree(Key, Value).
balance({S, T}) ->
{S, balance(T, S)}.
@@ -380,8 +372,8 @@ balance_list_1(L, 0) ->
{nil, L}.
-spec from_orddict(List) -> Tree when
- List :: [{Key :: term(), Val :: term()}],
- Tree :: gb_tree().
+ List :: [{Key, Value}],
+ Tree :: tree(Key, Value).
from_orddict(L) ->
S = length(L),
@@ -390,9 +382,8 @@ from_orddict(L) ->
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-spec delete_any(Key, Tree1) -> Tree2 when
- Key :: term(),
- Tree1 :: gb_tree(),
- Tree2 :: gb_tree().
+ Tree1 :: tree(Key, Value),
+ Tree2 :: tree(Key, Value).
delete_any(Key, T) ->
case is_defined(Key, T) of
@@ -405,9 +396,8 @@ delete_any(Key, T) ->
%%% delete. Assumes that key is present.
-spec delete(Key, Tree1) -> Tree2 when
- Key :: term(),
- Tree1 :: gb_tree(),
- Tree2 :: gb_tree().
+ Tree1 :: tree(Key, Value),
+ Tree2 :: tree(Key, Value).
delete(Key, {S, T}) when is_integer(S), S >= 0 ->
{S - 1, delete_1(Key, T)}.
@@ -433,11 +423,9 @@ merge(Smaller, Larger) ->
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
--spec take_smallest(Tree1) -> {Key, Val, Tree2} when
- Tree1 :: gb_tree(),
- Tree2 :: gb_tree(),
- Key :: term(),
- Val :: term().
+-spec take_smallest(Tree1) -> {Key, Value, Tree2} when
+ Tree1 :: tree(Key, Value),
+ Tree2 :: tree(Key, Value).
take_smallest({Size, Tree}) when is_integer(Size), Size >= 0 ->
{Key, Value, Larger} = take_smallest1(Tree),
@@ -449,10 +437,8 @@ take_smallest1({Key, Value, Smaller, Larger}) ->
{Key1, Value1, Smaller1} = take_smallest1(Smaller),
{Key1, Value1, {Key, Value, Smaller1, Larger}}.
--spec smallest(Tree) -> {Key, Val} when
- Tree :: gb_tree(),
- Key :: term(),
- Val :: term().
+-spec smallest(Tree) -> {Key, Value} when
+ Tree :: tree(Key, Value).
smallest({_, Tree}) ->
smallest_1(Tree).
@@ -462,11 +448,9 @@ smallest_1({Key, Value, nil, _Larger}) ->
smallest_1({_Key, _Value, Smaller, _Larger}) ->
smallest_1(Smaller).
--spec take_largest(Tree1) -> {Key, Val, Tree2} when
- Tree1 :: gb_tree(),
- Tree2 :: gb_tree(),
- Key :: term(),
- Val :: term().
+-spec take_largest(Tree1) -> {Key, Value, Tree2} when
+ Tree1 :: tree(Key, Value),
+ Tree2 :: tree(Key, Value).
take_largest({Size, Tree}) when is_integer(Size), Size >= 0 ->
{Key, Value, Smaller} = take_largest1(Tree),
@@ -478,10 +462,8 @@ take_largest1({Key, Value, Smaller, Larger}) ->
{Key1, Value1, Larger1} = take_largest1(Larger),
{Key1, Value1, {Key, Value, Smaller, Larger1}}.
--spec largest(Tree) -> {Key, Val} when
- Tree :: gb_tree(),
- Key :: term(),
- Val :: term().
+-spec largest(Tree) -> {Key, Value} when
+ Tree :: tree(Key, Value).
largest({_, Tree}) ->
largest_1(Tree).
@@ -493,10 +475,8 @@ largest_1({_Key, _Value, _Smaller, Larger}) ->
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
--spec to_list(Tree) -> [{Key, Val}] when
- Tree :: gb_tree(),
- Key :: term(),
- Val :: term().
+-spec to_list(Tree) -> [{Key, Value}] when
+ Tree :: tree(Key, Value).
to_list({_, T}) ->
to_list(T, []).
@@ -510,8 +490,7 @@ to_list(nil, L) -> L.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-spec keys(Tree) -> [Key] when
- Tree :: gb_tree(),
- Key :: term().
+ Tree :: tree(Key, Value :: term()).
keys({_, T}) ->
keys(T, []).
@@ -522,9 +501,8 @@ keys(nil, L) -> L.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
--spec values(Tree) -> [Val] when
- Tree :: gb_tree(),
- Val :: term().
+-spec values(Tree) -> [Value] when
+ Tree :: tree(Key :: term(), Value).
values({_, T}) ->
values(T, []).
@@ -536,8 +514,8 @@ values(nil, L) -> L.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-spec iterator(Tree) -> Iter when
- Tree :: gb_tree(),
- Iter :: iter().
+ Tree :: tree(Key, Value),
+ Iter :: iter(Key, Value).
iterator({_, T}) ->
iterator_1(T).
@@ -555,11 +533,32 @@ iterator({_, _, L, _} = T, As) ->
iterator(nil, As) ->
As.
--spec next(Iter1) -> 'none' | {Key, Val, Iter2} when
- Iter1 :: iter(),
- Iter2 :: iter(),
- Key :: term(),
- Val :: term().
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-spec iterator_from(Key, Tree) -> Iter when
+ Tree :: tree(Key, Value),
+ Iter :: iter(Key, Value).
+
+iterator_from(S, {_, T}) ->
+ iterator_1_from(S, T).
+
+iterator_1_from(S, T) ->
+ iterator_from(S, T, []).
+
+iterator_from(S, {K, _, _, T}, As) when K < S ->
+ iterator_from(S, T, As);
+iterator_from(_, {_, _, nil, _} = T, As) ->
+ [T | As];
+iterator_from(S, {_, _, L, _} = T, As) ->
+ iterator_from(S, L, [T | As]);
+iterator_from(_, nil, As) ->
+ As.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-spec next(Iter1) -> 'none' | {Key, Value, Iter2} when
+ Iter1 :: iter(Key, Value),
+ Iter2 :: iter(Key, Value).
next([{X, V, _, T} | As]) ->
{X, V, iterator(T, As)};
@@ -569,9 +568,9 @@ next([]) ->
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-spec map(Function, Tree1) -> Tree2 when
- Function :: fun((K :: term(), V1 :: term()) -> V2 :: term()),
- Tree1 :: gb_tree(),
- Tree2 :: gb_tree().
+ Function :: fun((K :: Key, V1 :: Value1) -> V2 :: Value2),
+ Tree1 :: tree(Key, Value1),
+ Tree2 :: tree(Key, Value2).
map(F, {Size, Tree}) when is_function(F, 2) ->
{Size, map_1(F, Tree)}.
generated by cgit v1.2.3 (git 2.25.1) at 2025-02-21 05:08:38 +0000