path: root/lib/diameter/test/diameter_enum.erl

%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 2010-2011. All Rights Reserved.
%%
%% 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%
%%

-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).