1%%
2%% %CopyrightBegin%
3%%
4%% Copyright Ericsson AB 2010-2016. All Rights Reserved.
5%%
6%% Licensed under the Apache License, Version 2.0 (the "License");
7%% you may not use this file except in compliance with the License.
8%% You may obtain a copy of the License at
9%%
10%%     http://www.apache.org/licenses/LICENSE-2.0
11%%
12%% Unless required by applicable law or agreed to in writing, software
13%% distributed under the License is distributed on an "AS IS" BASIS,
14%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15%% See the License for the specific language governing permissions and
16%% limitations under the License.
17%%
18%% %CopyrightEnd%
19%%
20
21-module(diameter_enum).
22
23%%
24%% This module constructs finite enumerations.
25%%
26%% An enumeration is represented as a function on integers, 0 mapping
27%% to the number of values enumerated and successive integers mapping
28%% to enumerated values. The function will fail on anything but 0 and
29%% positive integers less then or equal to the value of the function
30%% at 0.
31%%
32%% The purpose of this is to provide a way of stepping through a large
33%% number of values without explicitly constructing the list of all
34%% possible values. For example, consider the following function that
35%% given a list of lists constructs the list of all possible lists
36%% constructed by choosing one element from each sublist.
37%%
38%%   combine([H]) ->
39%%       [[X] || X <- H];
40%%   combine([H|T]) ->
41%%       Ys = combine(T),
42%%       [[X|Y] || X <- H, Y <- Ys].
43%%
44%% Eg. [[1,2],[3,4,5]] -> [[1,3],[1,4],[1,5],[2,3],[2,4],[2,5]]
45%%
46%% If L is a list of three 1000 element lists then combine(L) would
47%% construct a list of length 10^9 which will likely exhaust available
48%% memory. (Which is how this module came into being. A tail-recursive
49%% implementation doesn't fare much better.) By contrast,
50%%
51%%   F = enum:combine([enum:new(L) || L <- Lists])
52%%
53%% only maps existing lists. It may still be undesirable to step
54%% through a very large number of values but it's possible, and easy
55%% to step through a selection of values as an alternative.
56%%
57
58%% Functions that return enumerations.
59-export([new/1,
60         combine/1,
61         reverse/1,
62         map/2,
63         append/1,
64         duplicate/2,
65         nthtail/2,
66         seq/2,
67         seq/3,
68         zip/1,
69         zip/2,
70         slice/3,
71         split/2]).
72
73%% Functions that operate on existing enumerations.
74-export([foreach/2,
75         foldl/3,
76         foldr/3,
77         all/2,
78         any/2,
79         member/2,
80         last/1,
81         nth/2,
82         to_list/1]).
83
84%% ------------------------------------------------------------------------
85%% new/1
86%%
87%% Turn a list/tuple of values into an enumeration that steps through
88%% each element. Turn anything else into an enumeration of that single
89%% value.
90%% ------------------------------------------------------------------------
91
92new(L)
93  when is_list(L) ->
94    new(list_to_tuple(L));
95
96new(T)
97  when is_tuple(T) ->
98    enum(size(T), fun(N) -> element(N,T) end);
99
100new(T) ->
101    fun(0) -> 1; (1) -> T end.
102
103enum(Ord, F) ->
104    fun(0) -> Ord; (N) when 0 < N, N =< Ord -> F(N) end.
105
106%% ------------------------------------------------------------------------
107%% combine/1
108%%
109%% Map a list/tuple of enumerations to the enumeration of all
110%% lists/tuples constructed by choosing one value from each
111%% enumeration in the list/tuple.
112%% ------------------------------------------------------------------------
113
114combine(T)
115  when is_tuple(T) ->
116    F = combine(tuple_to_list(T)),
117    enum(F(0), fun(N) -> list_to_tuple(F(N)) end);
118
119combine([]) ->
120    fun(0) -> 0 end;
121
122%% Given positive integers n_1,...,n_k, construct a bijection from
123%% {0,...,\prod_{i=1}^k} n_i - 1} to {0,...,n_1} x ... x {0,...,n_k}
124%% that maps N to (N_1,...,N_k) where:
125%%
126%%   N_1 = (N div 1) rem n_1
127%%   ...
128%%   N_k = (N div n_1*...*n_{k-1}) rem n_k
129%%
130%% That is:
131%%
132%%   N_i = (N div \prod_{j=1}^{i-1} n_j) rem n_i
133%%
134%% This corresponds to looping through N_1, incrementing N_2 as N_1
135%% loops, and so on up through N_k. The inverse map is as follows.
136%%
137%%   (N_1,...,N_k) -> N = N_1 + N_2*n_1 + ... + N_k*n_{k-1}*...*n_1
138%%
139%%                      = \sum_{i=1}^k N_i*\prod_{j=i}^{i-1} n_j
140%%
141%% [Proof: Induction on k. For k=1 we have the identity map. If
142%%         g_k : (N_1,...,N_k) |-> N above is bijective then consider
143%%         the bijection
144%%
145%%           G : (t,n) |--> t + n*K,  K = n_k*...*n_1
146%%
147%%         from {0,...,K-1} x {0,...,n_{k+1}-1} onto {0,...,n_{k+1}*K - 1}
148%%         with inverse F : n |--> (n rem K, n div K). Since
149%%
150%%           g_{k+1}(N_1,...,N_{k+1}) = g_k(N_1,...,N_K) + N_{k+1}*K
151%%                                    = G(g_k(N_1,...,N_K), N_{k+1})
152%%
153%%         and G, g_k and ((N-1,...,N_k),N_{k+1}) -> (N_1,...,N_{k+1})
154%%         are all bijections, so is g_{k+1}.]
155
156combine([_|_] = L) ->
157    [Ord | Divs] = lists:foldl(fun(F,[D|_] = A) -> [F(0)*D | A] end, [1], L),
158    RL = lists:reverse(L),
159    enum(Ord, fun(N) -> combine(N, Ord, Divs, RL) end).
160
161%% Since we use 0 to return the number of elements enumerated, use
162%% bijections from {1,...,N} rather than {0,...,N-1}.
163
164combine(N, Ord, Divs, L)
165  when 0 < N, N =< Ord ->
166    {Vs, []} = lists:foldl(fun(F, {A, [D|Ds]}) ->
167                                   {[F(1 + (((N-1) div D) rem F(0))) | A], Ds}
168                           end,
169                           {[], Divs},
170                           L),
171    Vs.
172
173%% ------------------------------------------------------------------------
174%% reverse/1
175%%
176%% Construct the enumeration that reverses the order in which values
177%% are traversed.
178%% ------------------------------------------------------------------------
179
180reverse(E) ->
181    Ord = E(0),
182    enum(Ord, fun(N) -> E(Ord + 1 - N) end).
183
184%% ------------------------------------------------------------------------
185%% map/2
186%%
187%% Construct an enumeration that maps enumerated values.
188%% ------------------------------------------------------------------------
189
190map(Fun, E) ->
191    enum(E(0), fun(N) -> Fun(E(N)) end).
192
193%% ------------------------------------------------------------------------
194%% append/2
195%%
196%% Construct an enumeration that successively steps through each of a
197%% list of enumerations.
198%% ------------------------------------------------------------------------
199
200append(Es) ->
201    [Ord | Os] = lists:foldl(fun(E, [N|_] = A) -> [N+E(0)|A] end, [0], Es),
202    Rev = lists:reverse(Es),
203    enum(Ord, fun(N) -> append(N, Os, Rev) end).
204
205append(N, [Ord | _], [E | _])
206  when N > Ord ->
207    E(N - Ord);
208append(N, [_|Os], [_|Es]) ->
209    append(N, Os, Es).
210
211%% ------------------------------------------------------------------------
212%% duplicate/2
213%%
214%% Construct an enumeration that traverses an enumeration multiple
215%% times. Equivalent to append(lists:duplicate(N, E)).
216%% ------------------------------------------------------------------------
217
218duplicate(N, E) ->
219    Ord = E(0),
220    enum(N*Ord, fun(M) -> E(1 + ((M-1) rem Ord)) end).
221
222%% ------------------------------------------------------------------------
223%% nthtail/2
224%%
225%% Construct an enumeration that omits values at the head of an
226%% existing enumeration.
227%% ------------------------------------------------------------------------
228
229nthtail(N, E)
230  when 0 =< N ->
231    nthtail(E(0) - N, N, E).
232
233nthtail(Ord, N, E)
234  when 0 =< Ord ->
235    enum(Ord, fun(M) -> E(M+N) end).
236
237%% ------------------------------------------------------------------------
238%% seq/[23]
239%%
240%% Construct an enumeration that steps through a sequence of integers.
241%% ------------------------------------------------------------------------
242
243seq(From, To) ->
244    seq(From, To, 1).
245
246seq(From, To, Incr)
247  when From =< To ->
248    enum((To - From + Incr) div Incr, fun(N) -> From + (N-1)*Incr end).
249
250%% ------------------------------------------------------------------------
251%% zip/[12]
252%%
253%% Construct an enumeration whose nth value is the list of nth values
254%% of a list of enumerations.
255%% ------------------------------------------------------------------------
256
257zip(Es) ->
258    zip(fun(T) -> T end, Es).
259
260zip(_, []) ->
261    [];
262zip(Fun, Es) ->
263    enum(lists:min([E(0) || E <- Es]), fun(N) -> Fun([E(N) || E <- Es]) end).
264
265%% ------------------------------------------------------------------------
266%% slice/3
267%%
268%% Construct an enumeration of a given length from a given starting point.
269%% ------------------------------------------------------------------------
270
271slice(N, Len, E)
272  when is_integer(N), N > 0, is_integer(Len), Len >= 0 ->
273    slice(N, Len, E(0) - (N - 1), E).
274
275slice(_, _, Tail, _)
276  when Tail < 1 ->
277    fun(0) -> 0 end;
278
279slice(N, Len, Tail, E) ->
280    enum(lists:min([Len, Tail]), fun(M) -> E(N-1+M) end).
281
282%% ------------------------------------------------------------------------
283%% split/2
284%%
285%% Split an enumeration into a list of enumerations of the specified
286%% length. The last enumeration of the list may have order less than
287%% this length.
288%% ------------------------------------------------------------------------
289
290split(Len, E)
291  when is_integer(Len), Len > 0 ->
292    split(1, E(0), Len, E, []).
293
294split(N, Ord, _, _, Acc)
295  when N > Ord ->
296    lists:reverse(Acc);
297
298split(N, Ord, Len, E, Acc) ->
299    split(N+Len, Ord, Len, E, [slice(N, Len, E) | Acc]).
300
301%% ------------------------------------------------------------------------
302%% foreach/2
303%%
304%% Apply a fun to each value of an enumeration.
305%% ------------------------------------------------------------------------
306
307foreach(Fun, E) ->
308    foldl(fun(N,ok) -> Fun(N), ok end, ok, E).
309
310%% ------------------------------------------------------------------------
311%% foldl/3
312%% foldr/3
313%%
314%% Fold through values in an enumeration.
315%% ------------------------------------------------------------------------
316
317foldl(Fun, Acc, E) ->
318    foldl(E(0), 1, Fun, Acc, E).
319
320foldl(M, N, _, Acc, _)
321  when N == M+1 ->
322    Acc;
323foldl(M, N, Fun, Acc, E) ->
324    foldl(M, N+1, Fun, Fun(E(N), Acc), E).
325
326foldr(Fun, Acc, E) ->
327    foldl(Fun, Acc, reverse(E)).
328
329%% ------------------------------------------------------------------------
330%% all/2
331%%
332%% Do all values of an enumeration satisfy a predicate?
333%% ------------------------------------------------------------------------
334
335all(Pred, E) ->
336    all(E(0), 1, Pred, E).
337
338all(M, N, _, _)
339  when N == M+1 ->
340    true;
341all(M, N, Pred, E) ->
342    Pred(E(N)) andalso all(M, N+1, Pred, E).
343
344%% Note that andalso/orelse are tail-recusive as of R13A.
345
346%% ------------------------------------------------------------------------
347%% any/2
348%%
349%% Does any value of an enumeration satisfy a predicate?
350%% ------------------------------------------------------------------------
351
352any(Pred, E) ->
353    any(E(0), 1, Pred, E).
354
355any(M, N, _, _)
356  when N == M+1 ->
357    false;
358any(M, N, Pred, E) ->
359    Pred(E(N)) orelse any(M, N+1, Pred, E).
360
361%% ------------------------------------------------------------------------
362%% member/2
363%%
364%% Does a value match any in an enumeration?
365%% ------------------------------------------------------------------------
366
367member(X, E) ->
368    member(E(0), 1, X, E).
369
370member(M, N, _, _)
371  when N == M+1 ->
372    false;
373member(M, N, X, E) ->
374    match(E(N), X) orelse member(M, N+1, X, E).
375
376match(X, X) ->
377    true;
378match(_, _) ->
379    false.
380
381%% ------------------------------------------------------------------------
382%% last/1
383%%
384%% Return the last value of an enumeration.
385%% ------------------------------------------------------------------------
386
387last(E) ->
388    E(E(0)).
389
390%% ------------------------------------------------------------------------
391%% nth/2
392%%
393%% Return a selected value of an enumeration.
394%% ------------------------------------------------------------------------
395
396nth(N, E) ->
397    E(N).
398
399%% ------------------------------------------------------------------------
400%% to_list/1
401%%
402%% Turn an enumeration into a list. Not good if the very many values
403%% are enumerated.
404%% ------------------------------------------------------------------------
405
406to_list(E) ->
407    foldr(fun(X,A) -> [X|A] end, [], E).
408