Merge branch 'dev' into major

1 files changed, 406 insertions, 0 deletions

diff --git a/lib/diameter/test/diameter_enum.erl b/lib/diameter/test/diameter_enum.erl
new file mode 100644
index 0000000000..dfb6d04e3c
--- /dev/null
+++ b/lib/diameter/test/diameter_enum.erl
@@ -0,0 +1,406 @@
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2010-2011. 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.
+%%
+%% %CopyrightEnd%
+%%
+
+-module(diameter_enum).
+
+%%
+%% This module constructs finite enumerations.
+%%
+%% An enumeration is represented as a function on integers, 0 mapping
+%% to the number of values enumerated and successive integers mapping
+%% to enumerated values. The function will fail on anything but 0 and
+%% positive integers less then or equal to the value of the function
+%% at 0.
+%%
+%% The purpose of this is to provide a way of stepping through a large
+%% number of values without explicitly constructing the list of all
+%% possible values. For example, consider the following function that
+%% given a list of lists constructs the list of all possible lists
+%% constructed by choosing one element from each sublist.
+%%
+%%   combine([H]) ->
+%%       [[X] || X <- H];
+%%   combine([H|T]) ->
+%%       Ys = combine(T),
+%%       [[X|Y] || X <- H, Y <- Ys].
+%%
+%% Eg. [[1,2],[3,4,5]] -> [[1,3],[1,4],[1,5],[2,3],[2,4],[2,5]]
+%%
+%% If L is a list of three 1000 element lists then combine(L) would
+%% construct a list of length 10^9 which will likely exhaust available
+%% memory. (Which is how this module came into being. A tail-recursive
+%% implementation doesn't fare much better.) By contrast,
+%%
+%%   F = enum:combine([enum:new(L) || L <- Lists])
+%%
+%% only maps existing lists. It may still be undesirable to step
+%% through a very large number of values but it's possible, and easy
+%% to step through a selection of values as an alternative.
+%%
+
+%% Functions that return enumerations.
+-export([new/1,
+         combine/1,
+         reverse/1,
+         map/2,
+         append/1,
+         duplicate/2,
+         nthtail/2,
+         seq/2,
+         seq/3,
+         zip/1,
+         zip/2,
+         slice/3,
+         split/2]).
+
+%% Functions that operate on existing enumerations.
+-export([foreach/2,
+         foldl/3,
+         foldr/3,
+         all/2,
+         any/2,
+         member/2,
+         last/1,
+         nth/2,
+         to_list/1]).
+
+%% ------------------------------------------------------------------------
+%% new/1
+%%
+%% Turn a list/tuple of values into an enumeration that steps through
+%% each element. Turn anything else into an enumeration of that single
+%% value.
+%% ------------------------------------------------------------------------
+
+new(L)
+  when is_list(L) ->
+    new(list_to_tuple(L));
+
+new(T)
+  when is_tuple(T) ->
+    enum(size(T), fun(N) -> element(N,T) end);
+
+new(T) ->
+    fun(0) -> 1; (1) -> T end.
+
+enum(Ord, F) ->
+    fun(0) -> Ord; (N) when 0 < N, N =< Ord -> F(N) end.
+
+%% ------------------------------------------------------------------------
+%% combine/1
+%%
+%% Map a list/tuple of enumerations to the enumeration of all
+%% lists/tuples constructed by choosing one value from each
+%% enumeration in the list/tuple.
+%% ------------------------------------------------------------------------
+
+combine(T)
+  when is_tuple(T) ->
+    F = combine(tuple_to_list(T)),
+    enum(F(0), fun(N) -> list_to_tuple(F(N)) end);
+
+combine([]) ->
+    fun(0) -> 0 end;
+
+%% Given positive integers n_1,...,n_k, construct a bijection from
+%% {0,...,\prod_{i=1}^k} n_i - 1} to {0,...,n_1} x ... x {0,...,n_k}
+%% that maps N to (N_1,...,N_k) where:
+%%
+%%   N_1 = (N div 1) rem n_1
+%%   ...
+%%   N_k = (N div n_1*...*n_{k-1}) rem n_k
+%%
+%% That is:
+%%
+%%   N_i = (N div \prod_{j=1}^{i-1} n_j) rem n_i
+%%
+%% This corresponds to looping through N_1, incrementing N_2 as N_1
+%% loops, and so on up through N_k. The inverse map is as follows.
+%%
+%%   (N_1,...,N_k) -> N = N_1 + N_2*n_1 + ... + N_k*n_{k-1}*...*n_1
+%%
+%%                      = \sum_{i=1}^k N_i*\prod_{j=i}^{i-1} n_j
+%%
+%% [Proof: Induction on k. For k=1 we have the identity map. If
+%%         g_k : (N_1,...,N_k) |-> N above is bijective then consider
+%%         the bijection
+%%
+%%           G : (t,n) |--> t + n*K,  K = n_k*...*n_1
+%%
+%%         from {0,...,K-1} x {0,...,n_{k+1}-1} onto {0,...,n_{k+1}*K - 1}
+%%         with inverse F : n |--> (n rem K, n div K). Since
+%%
+%%           g_{k+1}(N_1,...,N_{k+1}) = g_k(N_1,...,N_K) + N_{k+1}*K
+%%                                    = G(g_k(N_1,...,N_K), N_{k+1})
+%%
+%%         and G, g_k and ((N-1,...,N_k),N_{k+1}) -> (N_1,...,N_{k+1})
+%%         are all bijections, so is g_{k+1}.]
+
+combine([_|_] = L) ->
+    [Ord | Divs] = lists:foldl(fun(F,[D|_] = A) -> [F(0)*D | A] end, [1], L),
+    RL = lists:reverse(L),
+    enum(Ord, fun(N) -> combine(N, Ord, Divs, RL) end).
+
+%% Since we use 0 to return the number of elements enumerated, use
+%% bijections from {1,...,N} rather than {0,...,N-1}.
+
+combine(N, Ord, Divs, L)
+  when 0 < N, N =< Ord ->
+    {Vs, []} = lists:foldl(fun(F, {A, [D|Ds]}) ->
+                                   {[F(1 + (((N-1) div D) rem F(0))) | A], Ds}
+                           end,
+                           {[], Divs},
+                           L),
+    Vs.
+
+%% ------------------------------------------------------------------------
+%% reverse/1
+%%
+%% Construct the enumeration that reverses the order in which values
+%% are traversed.
+%% ------------------------------------------------------------------------
+
+reverse(E) ->
+    Ord = E(0),
+    enum(Ord, fun(N) -> E(Ord + 1 - N) end).
+
+%% ------------------------------------------------------------------------
+%% map/2
+%%
+%% Construct an enumeration that maps enumerated values.
+%% ------------------------------------------------------------------------
+
+map(Fun, E) ->
+    enum(E(0), fun(N) -> Fun(E(N)) end).
+
+%% ------------------------------------------------------------------------
+%% append/2
+%%
+%% Construct an enumeration that successively steps through each of a
+%% list of enumerations.
+%% ------------------------------------------------------------------------
+
+append(Es) ->
+    [Ord | Os] = lists:foldl(fun(E, [N|_] = A) -> [N+E(0)|A] end, [0], Es),
+    Rev = lists:reverse(Es),
+    enum(Ord, fun(N) -> append(N, Os, Rev) end).
+
+append(N, [Ord | _], [E | _])
+  when N > Ord ->
+    E(N - Ord);
+append(N, [_|Os], [_|Es]) ->
+    append(N, Os, Es).
+
+%% ------------------------------------------------------------------------
+%% duplicate/2
+%%
+%% Construct an enumeration that traverses an enumeration multiple
+%% times. Equivalent to append(lists:duplicate(N, E)).
+%% ------------------------------------------------------------------------
+
+duplicate(N, E) ->
+    Ord = E(0),
+    enum(N*Ord, fun(M) -> E(1 + ((M-1) rem Ord)) end).
+
+%% ------------------------------------------------------------------------
+%% nthtail/2
+%%
+%% Construct an enumeration that omits values at the head of an
+%% existing enumeration.
+%% ------------------------------------------------------------------------
+
+nthtail(N, E)
+  when 0 =< N ->
+    nthtail(E(0) - N, N, E).
+
+nthtail(Ord, N, E)
+  when 0 =< Ord ->
+    enum(Ord, fun(M) -> E(M+N) end).
+
+%% ------------------------------------------------------------------------
+%% seq/[23]
+%%
+%% Construct an enumeration that steps through a sequence of integers.
+%% ------------------------------------------------------------------------
+
+seq(From, To) ->
+    seq(From, To, 1).
+
+seq(From, To, Incr)
+  when From =< To ->
+    enum((To - From + Incr) div Incr, fun(N) -> From + (N-1)*Incr end).
+
+%% ------------------------------------------------------------------------
+%% zip/[12]
+%%
+%% Construct an enumeration whose nth value is the list of nth values
+%% of a list of enumerations.
+%% ------------------------------------------------------------------------
+
+zip(Es) ->
+    zip(fun(T) -> T end, Es).
+
+zip(_, []) ->
+    [];
+zip(Fun, Es) ->
+    enum(lists:min([E(0) || E <- Es]), fun(N) -> Fun([E(N) || E <- Es]) end).
+
+%% ------------------------------------------------------------------------
+%% slice/3
+%%
+%% Construct an enumeration of a given length from a given starting point.
+%% ------------------------------------------------------------------------
+
+slice(N, Len, E)
+  when is_integer(N), N > 0, is_integer(Len), Len >= 0 ->
+    slice(N, Len, E(0) - (N - 1), E).
+
+slice(_, _, Tail, _)
+  when Tail < 1 ->
+    fun(0) -> 0 end;
+
+slice(N, Len, Tail, E) ->
+    enum(lists:min([Len, Tail]), fun(M) -> E(N-1+M) end).
+
+%% ------------------------------------------------------------------------
+%% split/2
+%%
+%% Split an enumeration into a list of enumerations of the specified
+%% length. The last enumeration of the list may have order less than
+%% this length.
+%% ------------------------------------------------------------------------
+
+split(Len, E)
+  when is_integer(Len), Len > 0 ->
+    split(1, E(0), Len, E, []).
+
+split(N, Ord, _, _, Acc)
+  when N > Ord ->
+    lists:reverse(Acc);
+
+split(N, Ord, Len, E, Acc) ->
+    split(N+Len, Ord, Len, E, [slice(N, Len, E) | Acc]).
+
+%% ------------------------------------------------------------------------
+%% foreach/2
+%%
+%% Apply a fun to each value of an enumeration.
+%% ------------------------------------------------------------------------
+
+foreach(Fun, E) ->
+    foldl(fun(N,ok) -> Fun(N), ok end, ok, E).
+
+%% ------------------------------------------------------------------------
+%% foldl/3
+%% foldr/3
+%%
+%% Fold through values in an enumeration.
+%% ------------------------------------------------------------------------
+
+foldl(Fun, Acc, E) ->
+    foldl(E(0), 1, Fun, Acc, E).
+
+foldl(M, N, _, Acc, _)
+  when N == M+1 ->
+    Acc;
+foldl(M, N, Fun, Acc, E) ->
+    foldl(M, N+1, Fun, Fun(E(N), Acc), E).
+
+foldr(Fun, Acc, E) ->
+    foldl(Fun, Acc, reverse(E)).
+
+%% ------------------------------------------------------------------------
+%% all/2
+%%
+%% Do all values of an enumeration satisfy a predicate?
+%% ------------------------------------------------------------------------
+
+all(Pred, E) ->
+    all(E(0), 1, Pred, E).
+
+all(M, N, _, _)
+  when N == M+1 ->
+    true;
+all(M, N, Pred, E) ->
+    Pred(E(N)) andalso all(M, N+1, Pred, E).
+
+%% Note that andalso/orelse are tail-recusive as of R13A.
+
+%% ------------------------------------------------------------------------
+%% any/2
+%%
+%% Does any value of an enumeration satisfy a predicate?
+%% ------------------------------------------------------------------------
+
+any(Pred, E) ->
+    any(E(0), 1, Pred, E).
+
+any(M, N, _, _)
+  when N == M+1 ->
+    false;
+any(M, N, Pred, E) ->
+    Pred(E(N)) orelse any(M, N+1, Pred, E).
+
+%% ------------------------------------------------------------------------
+%% member/2
+%%
+%% Does a value match any in an enumeration?
+%% ------------------------------------------------------------------------
+
+member(X, E) ->
+    member(E(0), 1, X, E).
+
+member(M, N, _, _)
+  when N == M+1 ->
+    false;
+member(M, N, X, E) ->
+    match(E(N), X) orelse member(M, N+1, X, E).
+
+match(X, X) ->
+    true;
+match(_, _) ->
+    false.
+
+%% ------------------------------------------------------------------------
+%% last/1
+%%
+%% Return the last value of an enumeration.
+%% ------------------------------------------------------------------------
+
+last(E) ->
+    E(E(0)).
+
+%% ------------------------------------------------------------------------
+%% nth/2
+%%
+%% Return a selected value of an enumeration.
+%% ------------------------------------------------------------------------
+
+nth(N, E) ->
+    E(N).
+
+%% ------------------------------------------------------------------------
+%% to_list/1
+%%
+%% Turn an enumeration into a list. Not good if the very many values
+%% are enumerated.
+%% ------------------------------------------------------------------------
+
+to_list(E) ->
+    foldr(fun(X,A) -> [X|A] end, [], E).