gb_sets.erl

来自「OTP是开放电信平台的简称」· ERL 代码 · 共 709 行 · 第 1/2 页

%% ``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 via the world wide web 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.
%% 
%% The Initial Developer of the Original Code is Richard Carlsson.
%% Portions created by Ericsson are Copyright 1999, Ericsson Utvecklings
%% AB. All Rights Reserved.''
%% 
%%     $Id $
%%
%% =====================================================================
%% Ordered Sets implemented as General Balanced Trees
%%
%% Copyright (C) 1999-2001 Richard Carlsson
%%
%% An implementation of ordered sets using Prof. Arne Andersson's
%% General Balanced Trees. This can be much more efficient than using
%% ordered lists, for larger sets, but depends on the application. See
%% notes below for details.
%% ---------------------------------------------------------------------
%% Notes:
%%
%% The complexity on set operations is bounded by either O(|S|) or O(|T|
%% * log(|S|)), where S is the largest given set, depending on which is
%% fastest for any particular function call. For operating on sets of
%% almost equal size, this implementation is about 3 times slower than
%% using ordered-list sets directly. For sets of very different sizes,
%% however, this solution can be arbitrarily much faster; in practical
%% cases, often between 10 and 100 times. This implementation is
%% particularly suited for ackumulating elements a few at a time,
%% building up a large set (more than 100-200 elements), and repeatedly
%% testing for membership in the current set.
%%
%% As with normal tree structures, lookup (membership testing),
%% insertion and deletion have logarithmic complexity.
%%
%% Operations:
%%
%% - empty(): returns empty set.
%%
%%   Alias: new(), for compatibility with `sets'.
%%
%% - is_empty(S): returns 'true' if S is an empty set, and 'false'
%%   otherwise.
%%
%% - size(S): returns the number of nodes in the set as an integer.
%%   Returns 0 (zero) if the set is empty.
%%
%% - singleton(X): returns a set containing only the element X.
%%
%% - is_member(X, S): returns `true' if element X is a member of set S,
%%   and `false' otherwise.
%%
%%   Alias: is_element(), for compatibility with `sets'.
%%
%% - insert(X, S): inserts element X into set S; returns the new set.
%%   *Assumes that the element is not present in S.*
%%
%% - add(X, S): adds element X to set S; returns the new set. If X is
%%   already an element in S, nothing is changed.
%%
%%   Alias: add_element(), for compatibility with `sets'.
%%
%% - delete(X, S): removes element X from set S; returns new set.
%%   Assumes that the element exists in the set.
%%
%% - delete_any(X, S): removes key X from set S if the key is present
%%   in the set, otherwise does nothing; returns new set.
%%
%%   Alias: del_element(), for compatibility with `sets'.
%%
%% - balance(S): rebalances the tree representation of S. Note that this
%%   is rarely necessary, but may be motivated when a large number of
%%   elements have been deleted from the tree without further
%%   insertions. Rebalancing could then be forced in order to minimise
%%   lookup times, since deletion only does not rebalance the tree.
%%
%% - union(S1, S2): returns a new set that contains each element that is
%%   in either S1 or S2 or both, and no other elements.
%%
%% - union(Ss): returns a new set that contains each element that is in
%%   at least one of the sets in the list Ss, and no other elements.
%%
%% - intersection(S1, S2): returns a new set that contains each element
%%   that is in both S1 and S2, and no other elements.
%%
%% - intersection(Ss): returns a new set that contains each element that
%%   is in all of the sets in the list Ss, and no other elements.
%%
%% - difference(S1, S2): returns a new set that contains each element in
%%   S1 that is not also in S2, and no other elements.
%%
%%   Alias: subtract(), for compatibility with `sets'.
%%
%% - is_subset(S1, S2): returns `true' if each element in S1 is also a
%%   member of S2, and `false' otherwise.
%%
%% - to_list(S): returns an ordered list of all elements in set S. The
%%   list never contains duplicates.
%%
%% - from_list(List): creates a set containing all elements in List,
%%   where List may be unordered and contain duplicates.
%%
%% - from_ordset(L): turns an ordered-set list L into a set. The list
%%   must not contain duplicates.
%%
%% - smallest(S): returns the smallest element in set S. Assumes that
%%   the set S is nonempty.
%%
%% - largest(S): returns the largest element in set S. Assumes that the
%%   set S is nonempty.
%%
%% - take_smallest(S): returns {X, S1}, where X is the smallest element
%%   in set S, and S1 is the set S with element X deleted. Assumes that
%%   the set S is nonempty.
%%
%% - take_largest(S): returns {X, S1}, where X is the largest element in
%%   set S, and S1 is the set S with element X deleted. Assumes that the
%%   set S is nonempty.
%%
%% - iterator(S): returns an iterator that can be used for traversing
%%   the entries of set S; see `next'. The implementation of this is
%%   very efficient; traversing the whole set using `next' is only
%%   slightly slower than getting the list of all elements using
%%   `to_list' and traversing that. The main advantage of the iterator
%%   approach is that it does not require the complete list of all
%%   elements to be built in memory at one time.
%%
%% - next(T): returns {X, T1} where X is the smallest element referred
%%   to by the iterator T, and T1 is the new iterator to be used for
%%   traversing the remaining elements, or the atom `none' if no
%%   elements remain.
%%
%% - filter(P, S): Filters set S using predicate function P. Included
%%   for compatibility with `sets'.
%%
%% - fold(F, A, S): Folds function F over set S with A as the initial
%%   ackumulator. Included for compatibility with `sets'.
%%
%% - is_set(S): returns 'true' if S appears to be a set, and 'false'
%%   otherwise. Not recommended; included for compatibility with `sets'.

-module(gb_sets).

-export([empty/0, is_empty/1, size/1, singleton/1, is_member/2,
	 insert/2, add/2, delete/2, delete_any/2, balance/1, union/2,
	 union/1, intersection/2, intersection/1, difference/2,
	 is_subset/2, to_list/1, from_list/1, from_ordset/1, smallest/1,
	 largest/1, take_smallest/1, take_largest/1, iterator/1, next/1,
	 filter/2, fold/3, is_set/1]).

%% `sets' compatibility aliases:

-export([new/0, is_element/2, add_element/2, del_element/2,
	 subtract/2]).

%% GB-trees adapted from Sven-Olof Nystr鰉s implementation for
%% representation of sets.
%%
%% Data structures:
%% - {Size, Tree}, where `Tree' is composed of nodes of the form:
%% - {Key, Smaller, Bigger}, and the "empty tree" node:
%% - nil.
%%
%% No attempt is made to balance trees after deletions. Since deletions
%% don't increase the height of a tree, this should be OK.
%%
%% Original balance condition h(T) <= ceil(c * log(|T|)) has been
%% changed to the similar (but not quite equivalent) condition 2 ^ h(T)
%% <= |T| ^ c. This should also be OK.
%%
%% Behaviour is logarithmic (as it should be).

%% Some macros. 

-define(p, 2). % It seems that p = 2 is optimal for sorted keys

-define(pow(A, _), A * A). % correct with exponent as defined above.

-define(div2(X), X bsr 1). 

-define(mul2(X), X bsl 1).


empty() ->
    {0, nil}.

new() -> empty().

is_empty({0, nil}) ->
    true;
is_empty(_) ->
    false.

size({Size, _}) ->
    Size.

singleton(Key) ->
    {1, {Key, nil, nil}}.

is_element(Key, S) ->
    is_member(Key, S).

is_member(Key, {_, T}) ->
    is_member_1(Key, T).

is_member_1(Key, {Key1, Smaller, _}) when Key < Key1 ->
    is_member_1(Key, Smaller);
is_member_1(Key, {Key1, _, Bigger}) when Key > Key1 ->
    is_member_1(Key, Bigger);
is_member_1(_, {_, _, _}) ->
    true;
is_member_1(_, nil) ->
    false.

insert(Key, {S, T}) ->
    S1 = S + 1,
    {S1, insert_1(Key, T, ?pow(S1, ?p))}.

insert_1(Key, {Key1, Smaller, Bigger}, S) when Key < Key1 -> 
    case insert_1(Key, Smaller, ?div2(S)) of
	{T1, H1, S1} when is_integer(H1) ->
	    T = {Key1, T1, Bigger},
	    {H2, S2} = count(Bigger),
	    H = ?mul2(max(H1, H2)),
	    SS = S1 + S2 + 1,
	    P = ?pow(SS, ?p),
	    if
		H > P -> 
		    balance(T, SS);
		true ->
		    {T, H, SS}
	    end;
	T1 ->
	    {Key1, T1, Bigger}
    end;
insert_1(Key, {Key1, Smaller, Bigger}, S) when Key > Key1 -> 
    case insert_1(Key, Bigger, ?div2(S)) of
	{T1, H1, S1} when is_integer(H1) ->
	    T = {Key1, Smaller, T1},
	    {H2, S2} = count(Smaller),
	    H = ?mul2(max(H1, H2)),
	    SS = S1 + S2 + 1,
	    P = ?pow(SS, ?p),
	    if
		H > P -> 
		    balance(T, SS);
		true ->
		    {T, H, SS}
	    end;
	T1 ->
	    {Key1, Smaller, T1}
    end;
insert_1(Key, nil, 0) ->
    {{Key, nil, nil}, 1, 1};
insert_1(Key, nil, _) ->
    {Key, nil, nil};
insert_1(Key, _, _) ->
    erlang:fault({key_exists, Key}).

count({_, nil, nil}) ->
    {1, 1};
count({_, Sm, Bi}) ->
    {H1, S1} = count(Sm),
    {H2, S2} = count(Bi),
    {?mul2(max(H1, H2)), S1 + S2 + 1};
count(nil) ->
    {1, 0}.

max(X, Y) when X < Y ->
    Y;
max(X, _Y) ->
    X.

balance({S, T}) ->
    {S, balance(T, S)}.

balance(T, S) ->
    balance_list(to_list_1(T), S).

balance_list(L, S) ->
    {T, _} = balance_list_1(L, S),
    T.

balance_list_1(L, S) when S > 1 ->
    Sm = S - 1,
    S2 = Sm div 2,
    S1 = Sm - S2,
    {T1, [K | L1]} = balance_list_1(L, S1),
    {T2, L2} = balance_list_1(L1, S2),
    T = {K, T1, T2},
    {T, L2};
balance_list_1([Key | L], 1) ->
    {{Key, nil, nil}, L};
balance_list_1(L, 0) ->
    {nil, L}.

add_element(X, S) ->
    add(X, S).

add(X, S) ->
    case is_member(X, S) of
	true ->
	    S;    % we don't have to do anything here
	false ->
	    insert(X, S)
    end.

from_list(L) ->
    from_ordset(ordsets:from_list(L)).

from_ordset(L) ->
    S = length(L),
    {S, balance_list(L, S)}.

del_element(Key, S) ->
    delete_any(Key, S).

delete_any(Key, S) ->
    case is_member(Key, S) of
 	true ->
 	    delete(Key, S);
 	false ->
 	    S
    end.

delete(Key, {S, T}) ->
    {S - 1, delete_1(Key, T)}.

delete_1(Key, {Key1, Smaller, Larger}) when Key < Key1 ->
    Smaller1 = delete_1(Key, Smaller),
    {Key1, Smaller1, Larger};
delete_1(Key, {Key1, Smaller, Bigger}) when Key > Key1 ->
    Bigger1 = delete_1(Key, Bigger),
    {Key1, Smaller, Bigger1};
delete_1(_, {_, Smaller, Larger}) ->
    merge(Smaller, Larger).

merge(Smaller, nil) ->
    Smaller;
merge(nil, Larger) ->
    Larger;
merge(Smaller, Larger) ->
    {Key, Larger1} = take_smallest1(Larger),
    {Key, Smaller, Larger1}.

take_smallest({S, T}) ->
    {Key, Larger} = take_smallest1(T),