aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib/src/gb_trees.erl
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2016-12-16 12:50:28 +0100
committerBjörn Gustavsson <[email protected]>2016-12-19 11:54:06 +0100
commita2d92dff3a8acc534daeeb3dea5edda406a6ab0d (patch)
treea61765af69f9cca94879083422571be3c959bd8c /lib/stdlib/src/gb_trees.erl
parent8362491325db87bd7d561399f8ef8c849df22d33 (diff)
downloadotp-a2d92dff3a8acc534daeeb3dea5edda406a6ab0d.tar.gz
otp-a2d92dff3a8acc534daeeb3dea5edda406a6ab0d.tar.bz2
otp-a2d92dff3a8acc534daeeb3dea5edda406a6ab0d.zip
Add take/2 to all dictionary modules
Similar to maps:take/2, add take/2 to the other dictionary modules in STDLIB: orddict:take(Key, Dict) -> {Val,NewDict} | 'error'. dict:take(Key, Dict) -> {Val,NewDict} | 'error'. gb_trees:take(Key, Dict) -> {Val,NewDict}. For gb_trees also add: gb_trees:take_any(Key, Dict) -> {Val,NewDict} | 'error'. gb_trees already has delete() and delete_any(), so we will follow that design pattern. Suggested by Boris Bochkaryov in https://github.com/erlang/otp/pull/1209.
Diffstat (limited to 'lib/stdlib/src/gb_trees.erl')
-rw-r--r--lib/stdlib/src/gb_trees.erl45
1 files changed, 44 insertions, 1 deletions
diff --git a/lib/stdlib/src/gb_trees.erl b/lib/stdlib/src/gb_trees.erl
index 457287fa52..c0cdde012e 100644
--- a/lib/stdlib/src/gb_trees.erl
+++ b/lib/stdlib/src/gb_trees.erl
@@ -52,6 +52,13 @@
%% - delete_any(X, T): removes key X from tree T if the key is present
%% in the tree, otherwise does nothing; returns new tree.
%%
+%% - take(X, T): removes element with key X from tree T; returns new tree
+%% without removed element. Assumes that the key is present in the tree.
+%%
+%% - take_any(X, T): removes element with key X from tree T and returns
+%% a new tree if the key is present; otherwise does nothing and returns
+%% 'error'.
+%%
%% - balance(T): rebalances tree T. Note that this is rarely necessary,
%% but may be motivated when a large number of entries have been
%% deleted from the tree without further insertions. Rebalancing could
@@ -114,7 +121,8 @@
-export([empty/0, is_empty/1, size/1, lookup/2, get/2, insert/3,
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,
+ smallest/1, largest/1, take/2, take_any/2,
+ take_smallest/1, take_largest/1,
iterator/1, iterator_from/2, next/1, map/2]).
@@ -416,6 +424,41 @@ merge(Smaller, Larger) ->
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+-spec take_any(Key, Tree1) -> {Value, Tree2} | 'error' when
+ Tree1 :: tree(Key, _),
+ Tree2 :: tree(Key, _),
+ Key :: term(),
+ Value :: term().
+
+take_any(Key, Tree) ->
+ case is_defined(Key, Tree) of
+ true -> take(Key, Tree);
+ false -> error
+ end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-spec take(Key, Tree1) -> {Value, Tree2} when
+ Tree1 :: tree(Key, _),
+ Tree2 :: tree(Key, _),
+ Key :: term(),
+ Value :: term().
+
+take(Key, {S, T}) when is_integer(S), S >= 0 ->
+ {Value, Res} = take_1(Key, T),
+ {Value, {S - 1, Res}}.
+
+take_1(Key, {Key1, Value, Smaller, Larger}) when Key < Key1 ->
+ {Value2, Smaller1} = take_1(Key, Smaller),
+ {Value2, {Key1, Value, Smaller1, Larger}};
+take_1(Key, {Key1, Value, Smaller, Bigger}) when Key > Key1 ->
+ {Value2, Bigger1} = take_1(Key, Bigger),
+ {Value2, {Key1, Value, Smaller, Bigger1}};
+take_1(_, {_Key, Value, Smaller, Larger}) ->
+ {Value, merge(Smaller, Larger)}.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
-spec take_smallest(Tree1) -> {Key, Value, Tree2} when
Tree1 :: tree(Key, Value),
Tree2 :: tree(Key, Value).