1%% Licensed under the Apache License, Version 2.0 (the "License");
2%% you may not use this file except in compliance with the License.
3%% You may obtain a copy of the License at
4%%
5%%     http://www.apache.org/licenses/LICENSE-2.0
6%%
7%% Unless required by applicable law or agreed to in writing, software
8%% distributed under the License is distributed on an "AS IS" BASIS,
9%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
10%% See the License for the specific language governing permissions and
11%% limitations under the License.
12%%
13%% =====================================================================
14%% General Balanced Trees - highly efficient dictionaries.
15%%
16%% Copyright (C) 1999-2001 Sven-Olof Nyström, Richard Carlsson
17%%
18%% An efficient implementation of Prof. Arne Andersson's General
19%% Balanced Trees. These have no storage overhead compared to plain
20%% unbalanced binary trees, and their performance is in general better
21%% than AVL trees.
22%% ---------------------------------------------------------------------
23%% Operations:
24%%
25%% - empty(): returns empty tree.
26%%
27%% - is_empty(T): returns 'true' if T is an empty tree, and 'false'
28%%   otherwise.
29%%
30%% - size(T): returns the number of nodes in the tree as an integer.
31%%   Returns 0 (zero) if the tree is empty.
32%%
33%% - lookup(X, T): looks up key X in tree T; returns {value, V}, or
34%%   `none' if the key is not present.
35%%
36%% - get(X, T): retreives the value stored with key X in tree T. Assumes
37%%   that the key is present in the tree.
38%%
39%% - insert(X, V, T): inserts key X with value V into tree T; returns
40%%   the new tree. Assumes that the key is *not* present in the tree.
41%%
42%% - update(X, V, T): updates key X to value V in tree T; returns the
43%%   new tree. Assumes that the key is present in the tree.
44%%
45%% - enter(X, V, T): inserts key X with value V into tree T if the key
46%%   is not present in the tree, otherwise updates key X to value V in
47%%   T. Returns the new tree.
48%%
49%% - delete(X, T): removes key X from tree T; returns new tree. Assumes
50%%   that the key is present in the tree.
51%%
52%% - delete_any(X, T): removes key X from tree T if the key is present
53%%   in the tree, otherwise does nothing; returns new tree.
54%%
55%% - take(X, T): removes element with key X from tree T; returns new tree
56%%   without removed element. Assumes that the key is present in the tree.
57%%
58%% - take_any(X, T): removes element with key X from tree T and returns
59%%   a new tree if the key is present; otherwise does nothing and returns
60%%   'error'.
61%%
62%% - balance(T): rebalances tree T. Note that this is rarely necessary,
63%%   but may be motivated when a large number of entries have been
64%%   deleted from the tree without further insertions. Rebalancing could
65%%   then be forced in order to minimise lookup times, since deletion
66%%   only does not rebalance the tree.
67%%
68%% - is_defined(X, T): returns `true' if key X is present in tree T, and
69%%   `false' otherwise.
70%%
71%% - keys(T): returns an ordered list of all keys in tree T.
72%%
73%% - values(T): returns the list of values for all keys in tree T,
74%%   sorted by their corresponding keys. Duplicates are not removed.
75%%
76%% - to_list(T): returns an ordered list of {Key, Value} pairs for all
77%%   keys in tree T.
78%%
79%% - from_orddict(L): turns an ordered list L of {Key, Value} pairs into
80%%   a tree. The list must not contain duplicate keys.
81%%
82%% - smallest(T): returns {X, V}, where X is the smallest key in tree T,
83%%   and V is the value associated with X in T. Assumes that the tree T
84%%   is nonempty.
85%%
86%% - largest(T): returns {X, V}, where X is the largest key in tree T,
87%%   and V is the value associated with X in T. Assumes that the tree T
88%%   is nonempty.
89%%
90%% - take_smallest(T): returns {X, V, T1}, where X is the smallest key
91%%   in tree T, V is the value associated with X in T, and T1 is the
92%%   tree T with key X deleted. Assumes that the tree T is nonempty.
93%%
94%% - take_largest(T): returns {X, V, T1}, where X is the largest key
95%%   in tree T, V is the value associated with X in T, and T1 is the
96%%   tree T with key X deleted. Assumes that the tree T is nonempty.
97%%
98%% - iterator(T): returns an iterator that can be used for traversing
99%%   the entries of tree T; see `next'. The implementation of this is
100%%   very efficient; traversing the whole tree using `next' is only
101%%   slightly slower than getting the list of all elements using
102%%   `to_list' and traversing that. The main advantage of the iterator
103%%   approach is that it does not require the complete list of all
104%%   elements to be built in memory at one time.
105%%
106%% - iterator_from(K, T): returns an iterator that can be used for
107%%   traversing the entries of tree T with key greater than or
108%%   equal to K; see `next'.
109%%
110%% - next(S): returns {X, V, S1} where X is the smallest key referred to
111%%   by the iterator S, and S1 is the new iterator to be used for
112%%   traversing the remaining entries, or the atom `none' if no entries
113%%   remain.
114%%
115%% - map(F, T): maps the function F(K, V) -> V' to all key-value pairs
116%%   of the tree T and returns a new tree T' with the same set of keys
117%%   as T and the new set of values V'.
118
119-module(gb_trees).
120
121-export([empty/0, is_empty/1, size/1, lookup/2, get/2, insert/3,
122	 update/3, enter/3, delete/2, delete_any/2, balance/1,
123	 is_defined/2, keys/1, values/1, to_list/1, from_orddict/1,
124	 smallest/1, largest/1, take/2, take_any/2,
125         take_smallest/1, take_largest/1,
126	 iterator/1, iterator_from/2, next/1, map/2]).
127
128
129%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
130%% Data structure:
131%% - {Size, Tree}, where `Tree' is composed of nodes of the form:
132%%   - {Key, Value, Smaller, Bigger}, and the "empty tree" node:
133%%   - nil.
134%%
135%% I make no attempt to balance trees after deletions. Since deletions
136%% don't increase the height of a tree, I figure this is OK.
137%%
138%% Original balance condition h(T) <= ceil(c * log(|T|)) has been
139%% changed to the similar (but not quite equivalent) condition 2 ^ h(T)
140%% <= |T| ^ c. I figure this should also be OK.
141%%
142%% Performance is comparable to the AVL trees in the Erlang book (and
143%% faster in general due to less overhead); the difference is that
144%% deletion works for my trees, but not for the book's trees. Behaviour
145%% is logaritmic (as it should be).
146
147%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
148%% Some macros.
149
150-define(p, 2). % It seems that p = 2 is optimal for sorted keys
151
152-define(pow(A, _), A * A). % correct with exponent as defined above.
153
154-define(div2(X), X bsr 1).
155
156-define(mul2(X), X bsl 1).
157
158%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
159%% Some types.
160
161-export_type([tree/0, tree/2, iter/0, iter/2]).
162
163-type gb_tree_node(K, V) :: 'nil'
164                          | {K, V, gb_tree_node(K, V), gb_tree_node(K, V)}.
165-opaque tree(Key, Value) :: {non_neg_integer(), gb_tree_node(Key, Value)}.
166-type tree() :: tree(_, _).
167-opaque iter(Key, Value) :: [gb_tree_node(Key, Value)].
168-type iter() :: iter(_, _).
169
170%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
171
172-spec empty() -> tree().
173
174empty() ->
175    {0, nil}.
176
177-spec is_empty(Tree) -> boolean() when
178      Tree :: tree().
179
180is_empty({0, nil}) ->
181    true;
182is_empty(_) ->
183    false.
184
185-spec size(Tree) -> non_neg_integer() when
186      Tree :: tree().
187
188size({Size, _}) when is_integer(Size), Size >= 0 ->
189    Size.
190
191%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
192
193-spec lookup(Key, Tree) -> 'none' | {'value', Value} when
194      Tree :: tree(Key, Value).
195
196lookup(Key, {_, T}) ->
197    lookup_1(Key, T).
198
199%% The term order is an arithmetic total order, so we should not
200%% test exact equality for the keys. (If we do, then it becomes
201%% possible that neither `>', `<', nor `=:=' matches.) Testing '<'
202%% and '>' first is statistically better than testing for
203%% equality, and also allows us to skip the test completely in the
204%% remaining case.
205
206lookup_1(Key, {Key1, _, Smaller, _}) when Key < Key1 ->
207    lookup_1(Key, Smaller);
208lookup_1(Key, {Key1, _, _, Bigger}) when Key > Key1 ->
209    lookup_1(Key, Bigger);
210lookup_1(_, {_, Value, _, _}) ->
211    {value, Value};
212lookup_1(_, nil) ->
213    none.
214
215%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
216
217%% This is a specialized version of `lookup'.
218
219-spec is_defined(Key, Tree) -> boolean() when
220      Tree :: tree(Key, Value :: term()).
221
222is_defined(Key, {_, T}) ->
223    is_defined_1(Key, T).
224
225is_defined_1(Key, {Key1, _, Smaller, _}) when Key < Key1 ->
226    is_defined_1(Key, Smaller);
227is_defined_1(Key, {Key1, _, _, Bigger}) when Key > Key1 ->
228    is_defined_1(Key, Bigger);
229is_defined_1(_, {_, _, _, _}) ->
230    true;
231is_defined_1(_, nil) ->
232    false.
233
234%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
235
236%% This is a specialized version of `lookup'.
237
238-spec get(Key, Tree) -> Value when
239      Tree :: tree(Key, Value).
240
241get(Key, {_, T}) ->
242    get_1(Key, T).
243
244get_1(Key, {Key1, _, Smaller, _}) when Key < Key1 ->
245    get_1(Key, Smaller);
246get_1(Key, {Key1, _, _, Bigger}) when Key > Key1 ->
247    get_1(Key, Bigger);
248get_1(_, {_, Value, _, _}) ->
249    Value.
250
251%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
252
253-spec update(Key, Value, Tree1) -> Tree2 when
254      Tree1 :: tree(Key, Value),
255      Tree2 :: tree(Key, Value).
256
257update(Key, Val, {S, T}) ->
258    T1 = update_1(Key, Val, T),
259    {S, T1}.
260
261%% See `lookup' for notes on the term comparison order.
262
263update_1(Key, Value, {Key1, V, Smaller, Bigger}) when Key < Key1 ->
264    {Key1, V, update_1(Key, Value, Smaller), Bigger};
265update_1(Key, Value, {Key1, V, Smaller, Bigger}) when Key > Key1 ->
266    {Key1, V, Smaller, update_1(Key, Value, Bigger)};
267update_1(Key, Value, {_, _, Smaller, Bigger}) ->
268    {Key, Value, Smaller, Bigger}.
269
270%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
271
272-spec insert(Key, Value, Tree1) -> Tree2 when
273      Tree1 :: tree(Key, Value),
274      Tree2 :: tree(Key, Value).
275
276insert(Key, Val, {S, T}) when is_integer(S) ->
277    S1 = S+1,
278    {S1, insert_1(Key, Val, T, ?pow(S1, ?p))}.
279
280insert_1(Key, Value, {Key1, V, Smaller, Bigger}, S) when Key < Key1 ->
281    case insert_1(Key, Value, Smaller, ?div2(S)) of
282	{T1, H1, S1} ->
283	    T = {Key1, V, T1, Bigger},
284	    {H2, S2} = count(Bigger),
285	    H = ?mul2(erlang:max(H1, H2)),
286	    SS = S1 + S2 + 1,
287	    P = ?pow(SS, ?p),
288	    if
289		H > P ->
290		    balance(T, SS);
291		true ->
292		    {T, H, SS}
293	    end;
294	T1 ->
295	    {Key1, V, T1, Bigger}
296    end;
297insert_1(Key, Value, {Key1, V, Smaller, Bigger}, S) when Key > Key1 ->
298    case insert_1(Key, Value, Bigger, ?div2(S)) of
299	{T1, H1, S1} ->
300	    T = {Key1, V, Smaller, T1},
301	    {H2, S2} = count(Smaller),
302	    H = ?mul2(erlang:max(H1, H2)),
303	    SS = S1 + S2 + 1,
304	    P = ?pow(SS, ?p),
305	    if
306		H > P ->
307		    balance(T, SS);
308		true ->
309		    {T, H, SS}
310	    end;
311	T1 ->
312	    {Key1, V, Smaller, T1}
313    end;
314insert_1(Key, Value, nil, S) when S =:= 0 ->
315    {{Key, Value, nil, nil}, 1, 1};
316insert_1(Key, Value, nil, _S) ->
317    {Key, Value, nil, nil};
318insert_1(Key, _, _, _) ->
319    erlang:error({key_exists, Key}).
320
321%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
322
323-spec enter(Key, Value, Tree1) -> Tree2 when
324      Tree1 :: tree(Key, Value),
325      Tree2 :: tree(Key, Value).
326
327enter(Key, Val, T) ->
328    case is_defined(Key, T) of
329	true ->
330	    update(Key, Val, T);
331	false ->
332	    insert(Key, Val, T)
333    end.
334
335%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
336
337count({_, _, nil, nil}) ->
338    {1, 1};
339count({_, _, Sm, Bi}) ->
340    {H1, S1} = count(Sm),
341    {H2, S2} = count(Bi),
342    {?mul2(erlang:max(H1, H2)), S1 + S2 + 1};
343count(nil) ->
344    {1, 0}.
345
346%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
347
348-spec balance(Tree1) -> Tree2 when
349      Tree1 :: tree(Key, Value),
350      Tree2 :: tree(Key, Value).
351
352balance({S, T}) ->
353    {S, balance(T, S)}.
354
355balance(T, S) ->
356    balance_list(to_list_1(T), S).
357
358balance_list(L, S) ->
359    {T, []} = balance_list_1(L, S),
360    T.
361
362balance_list_1(L, S) when S > 1 ->
363    Sm = S - 1,
364    S2 = Sm div 2,
365    S1 = Sm - S2,
366    {T1, [{K, V} | L1]} = balance_list_1(L, S1),
367    {T2, L2} = balance_list_1(L1, S2),
368    T = {K, V, T1, T2},
369    {T, L2};
370balance_list_1([{Key, Val} | L], 1) ->
371    {{Key, Val, nil, nil}, L};
372balance_list_1(L, 0) ->
373    {nil, L}.
374
375-spec from_orddict(List) -> Tree when
376      List :: [{Key, Value}],
377      Tree :: tree(Key, Value).
378
379from_orddict(L) ->
380    S = length(L),
381    {S, balance_list(L, S)}.
382
383%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
384
385-spec delete_any(Key, Tree1) -> Tree2 when
386      Tree1 :: tree(Key, Value),
387      Tree2 :: tree(Key, Value).
388
389delete_any(Key, T) ->
390    case is_defined(Key, T) of
391	true ->
392	    delete(Key, T);
393	false ->
394	    T
395    end.
396
397%%% delete. Assumes that key is present.
398
399-spec delete(Key, Tree1) -> Tree2 when
400      Tree1 :: tree(Key, Value),
401      Tree2 :: tree(Key, Value).
402
403delete(Key, {S, T}) when is_integer(S), S >= 0 ->
404    {S - 1, delete_1(Key, T)}.
405
406%% See `lookup' for notes on the term comparison order.
407
408delete_1(Key, {Key1, Value, Smaller, Larger}) when Key < Key1 ->
409    Smaller1 = delete_1(Key, Smaller),
410    {Key1, Value, Smaller1, Larger};
411delete_1(Key, {Key1, Value, Smaller, Bigger}) when Key > Key1 ->
412    Bigger1 = delete_1(Key, Bigger),
413    {Key1, Value, Smaller, Bigger1};
414delete_1(_, {_, _, Smaller, Larger}) ->
415    merge(Smaller, Larger).
416
417merge(Smaller, nil) ->
418    Smaller;
419merge(nil, Larger) ->
420    Larger;
421merge(Smaller, Larger) ->
422    {Key, Value, Larger1} = take_smallest1(Larger),
423    {Key, Value, Smaller, Larger1}.
424
425%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
426
427-spec take_any(Key, Tree1) -> {Value, Tree2} | 'error' when
428      Tree1 :: tree(Key, _),
429      Tree2 :: tree(Key, _),
430      Key   :: term(),
431      Value :: term().
432
433take_any(Key, Tree) ->
434    case is_defined(Key, Tree) of
435        true -> take(Key, Tree);
436        false -> error
437    end.
438
439%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
440
441-spec take(Key, Tree1) -> {Value, Tree2} when
442      Tree1 :: tree(Key, _),
443      Tree2 :: tree(Key, _),
444      Key   :: term(),
445      Value :: term().
446
447take(Key, {S, T}) when is_integer(S), S >= 0 ->
448    {Value, Res} = take_1(Key, T),
449    {Value, {S - 1, Res}}.
450
451take_1(Key, {Key1, Value, Smaller, Larger}) when Key < Key1 ->
452    {Value2, Smaller1} = take_1(Key, Smaller),
453    {Value2, {Key1, Value, Smaller1, Larger}};
454take_1(Key, {Key1, Value, Smaller, Bigger}) when Key > Key1 ->
455    {Value2, Bigger1} = take_1(Key, Bigger),
456    {Value2, {Key1, Value, Smaller, Bigger1}};
457take_1(_, {_Key, Value, Smaller, Larger}) ->
458    {Value, merge(Smaller, Larger)}.
459
460%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
461
462-spec take_smallest(Tree1) -> {Key, Value, Tree2} when
463      Tree1 :: tree(Key, Value),
464      Tree2 :: tree(Key, Value).
465
466take_smallest({Size, Tree}) when is_integer(Size), Size >= 0 ->
467    {Key, Value, Larger} = take_smallest1(Tree),
468    {Key, Value, {Size - 1, Larger}}.
469
470take_smallest1({Key, Value, nil, Larger}) ->
471    {Key, Value, Larger};
472take_smallest1({Key, Value, Smaller, Larger}) ->
473    {Key1, Value1, Smaller1} = take_smallest1(Smaller),
474    {Key1, Value1, {Key, Value, Smaller1, Larger}}.
475
476-spec smallest(Tree) -> {Key, Value} when
477      Tree :: tree(Key, Value).
478
479smallest({_, Tree}) ->
480    smallest_1(Tree).
481
482smallest_1({Key, Value, nil, _Larger}) ->
483    {Key, Value};
484smallest_1({_Key, _Value, Smaller, _Larger}) ->
485    smallest_1(Smaller).
486
487-spec take_largest(Tree1) -> {Key, Value, Tree2} when
488      Tree1 :: tree(Key, Value),
489      Tree2 :: tree(Key, Value).
490
491take_largest({Size, Tree}) when is_integer(Size), Size >= 0 ->
492    {Key, Value, Smaller} = take_largest1(Tree),
493    {Key, Value, {Size - 1, Smaller}}.
494
495take_largest1({Key, Value, Smaller, nil}) ->
496    {Key, Value, Smaller};
497take_largest1({Key, Value, Smaller, Larger}) ->
498    {Key1, Value1, Larger1} = take_largest1(Larger),
499    {Key1, Value1, {Key, Value, Smaller, Larger1}}.
500
501-spec largest(Tree) -> {Key, Value} when
502      Tree :: tree(Key, Value).
503
504largest({_, Tree}) ->
505    largest_1(Tree).
506
507largest_1({Key, Value, _Smaller, nil}) ->
508    {Key, Value};
509largest_1({_Key, _Value, _Smaller, Larger}) ->
510    largest_1(Larger).
511
512%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
513
514-spec to_list(Tree) -> [{Key, Value}] when
515      Tree :: tree(Key, Value).
516
517to_list({_, T}) ->
518    to_list(T, []).
519
520to_list_1(T) -> to_list(T, []).
521
522to_list({Key, Value, Small, Big}, L) ->
523    to_list(Small, [{Key, Value} | to_list(Big, L)]);
524to_list(nil, L) -> L.
525
526%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
527
528-spec keys(Tree) -> [Key] when
529      Tree :: tree(Key, Value :: term()).
530
531keys({_, T}) ->
532    keys(T, []).
533
534keys({Key, _Value, Small, Big}, L) ->
535    keys(Small, [Key | keys(Big, L)]);
536keys(nil, L) -> L.
537
538%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
539
540-spec values(Tree) -> [Value] when
541      Tree :: tree(Key :: term(), Value).
542
543values({_, T}) ->
544    values(T, []).
545
546values({_Key, Value, Small, Big}, L) ->
547    values(Small, [Value | values(Big, L)]);
548values(nil, L) -> L.
549
550%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
551
552-spec iterator(Tree) -> Iter when
553      Tree :: tree(Key, Value),
554      Iter :: iter(Key, Value).
555
556iterator({_, T}) ->
557    iterator_1(T).
558
559iterator_1(T) ->
560    iterator(T, []).
561
562%% The iterator structure is really just a list corresponding to
563%% the call stack of an in-order traversal. This is quite fast.
564
565iterator({_, _, nil, _} = T, As) ->
566    [T | As];
567iterator({_, _, L, _} = T, As) ->
568    iterator(L, [T | As]);
569iterator(nil, As) ->
570    As.
571
572%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
573
574-spec iterator_from(Key, Tree) -> Iter when
575      Tree :: tree(Key, Value),
576      Iter :: iter(Key, Value).
577
578iterator_from(S, {_, T}) ->
579    iterator_1_from(S, T).
580
581iterator_1_from(S, T) ->
582    iterator_from(S, T, []).
583
584iterator_from(S, {K, _, _, T}, As) when K < S ->
585    iterator_from(S, T, As);
586iterator_from(_, {_, _, nil, _} = T, As) ->
587    [T | As];
588iterator_from(S, {_, _, L, _} = T, As) ->
589    iterator_from(S, L, [T | As]);
590iterator_from(_, nil, As) ->
591    As.
592
593%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
594
595-spec next(Iter1) -> 'none' | {Key, Value, Iter2} when
596      Iter1 :: iter(Key, Value),
597      Iter2 :: iter(Key, Value).
598
599next([{X, V, _, T} | As]) ->
600    {X, V, iterator(T, As)};
601next([]) ->
602    none.
603
604%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
605
606-spec map(Function, Tree1) -> Tree2 when
607      Function :: fun((K :: Key, V1 :: Value1) -> V2 :: Value2),
608      Tree1 :: tree(Key, Value1),
609      Tree2 :: tree(Key, Value2).
610
611map(F, {Size, Tree}) when is_function(F, 2) ->
612    {Size, map_1(F, Tree)}.
613
614map_1(_, nil) -> nil;
615map_1(F, {K, V, Smaller, Larger}) ->
616    {K, F(K, V), map_1(F, Smaller), map_1(F, Larger)}.
617