1 /// Algorithms for doing calculations on a range.
2 module tern.algorithm.iteration;
3 
4 import tern.traits;
5 import tern.object : loadLength;
6 import tern.algorithm.mutation : filter;
7 import tern.functional;
8 
9 public:
10 /**
11  * Calculates the distance between `comparer` and `comparee`.
12  *
13  * Params:
14  *  comparee = The string to calculate from.
15  *  comparee = The string to calculate against.
16  *
17  * Returns:
18  *  The distance between `comparer` and `comparee`.
19  *
20  * Remarks:
21  *  `A` and `B` must both be string types.
22  */
23 size_t levenshteinDistance(A, B)(A comparer, B comparee) pure nothrow
24     if (isString!A && isString!B)
25 {
26     auto m = comparer.length + 1;
27     auto n = comparee.length + 1;
28 
29     size_t[] dp;
30 
31     dp.length = n;
32 
33     foreach (j; 0..n)
34         dp[j] = j;
35 
36     size_t diag;
37     size_t top;
38     size_t left;
39 
40     foreach (i; 1..m)
41     {
42         diag = i - 1;
43         top = i;
44 
45         foreach (j; 1..n)
46         {
47             left = dp[j];
48             int cost = (comparer[i - 1] == comparee[j - 1]) ? 0 : 1;
49             dp[j] = top + 1;
50 
51             if (dp[j - 1] + 1 < dp[j])
52                 dp[j] = dp[j - 1] + 1;
53 
54             if (diag + cost < dp[j])
55                 dp[j] = diag + cost;
56 
57             diag = left;
58             top = dp[j];
59         }
60     }
61 
62     return dp[n - 1];
63 }
64 
65 /**
66  * Calculates the difference between `comparer` and `comparee`.
67  *
68  * Params:
69  *  comparee = The range to calculate from.
70  *  comparee = The range to calculate against.
71  *
72  * Returns:
73  *  The difference between `comparer` and `comparee`.
74  */
75 size_t difference(A, B)(A comparer, B comparee)
76     if (isIndexable!A && isIndexable!B)
77 {
78     size_t ret = comparer.loadLength - comparee.length;
79     foreach (i; 0..comparee.loadLength)
80     {
81         if (i >= comparer.length)
82             return ret;
83 
84         if (comparee[i] != comparer[i])
85             ret++;
86     }
87     return ret;
88 }
89 
90 /**
91  * Calculates the sum of all values in `range`.
92  *
93  * Params:
94  *  range = The range to sum.
95  *
96  * Returns:
97  *  The sum of all values in `range`.
98  */
99 ElementType!T sum(T)(T range)
100     if (isForward!T && isIntegral!(ElementType!T))
101 {
102     ElementType!T sum;
103     foreach (u; range)
104         sum += u;
105     return sum;
106 }
107 
108 /**
109  * Calculates the mean of all values in `range`.
110  *
111  * Params:
112  *  range = The range to mean.
113  *
114  * Returns:
115  *  The mean of all values in `range`.
116  */
117 ElementType!T mean(T)(T range)
118     if (isIndexable!T && isIntegral!(ElementType!T))
119 {
120     return range.sum / range.loadLength;
121 }
122 
123 /**
124  * Folds all values in `range` based on a predicate.
125  *
126  * Params:
127  *  F = The function to use for folding.
128  *  range = The range to fold.
129  *
130  * Returns:
131  *  Return value of `F` after folding.
132  */
133 auto fold(alias F, T)(T range)
134     if (isIndexable!T && isCallable!F)
135 {
136     return range.plane!(F, () => true);
137 }
138 
139 /**
140  * Creates an array of all unique values in `range`.
141  *
142  * Params:
143  *  range = The range to search for uniques in.
144  *
145  * Returns:
146  *  An array of all unique values in `range`.
147  */
148 ElementType!T[] uniq(T)(T range)
149     if (isIndexable!T)
150 {
151     bool[ElementType!T] ret;
152     foreach (u; range)
153     {
154         if (u !in ret)
155             ret[u] = true;
156     }
157     return ret.keys;
158 }
159 
160 /**
161  * Gets the last value in `range` that abides by `F`, or the default value of `T`.
162  *
163  * Params:
164  *  F = The function predicate.
165  *  range = The range to be predicated.
166  *
167  * Returns:
168  *  The last value in `range` that abides by `F`, or the default value of `T`.
169  */
170 ElementType!T lastOrDefault(alias F, T)(T range)
171     if (isIndexable!T && isCallable!F)
172 {
173     auto ret = range.filter!F;
174     return ret.length == 0 ? T.init : ret[$-1];
175 }
176 
177 /**
178  * Gets the first value in `range` that abides by `F`, or the default value of `T`.
179  *
180  * Params:
181  *  F = The function predicate.
182  *  range = The range to be predicated.
183  *
184  * Returns:
185  *  The first value in `range` that abides by `F`, or the default value of `T`.
186  */
187 ElementType!T firstOrDefault(alias F, T)(T range)
188     if (isIndexable!T && isCallable!F)
189 {
190     auto ret = range.filter!F;
191     return ret.length == 0 ? T.init : ret[0];
192 }
193 
194 /**
195  * Concats `range` to itself `iter` times.
196  *
197  * Params:
198  *  range = The range to repeat.
199  *  iter = The number of iterations to repeat.
200  *
201  * Returns:
202  *  The new repeated form of `range`.
203  */
204 T repeat(T)(T range, size_t iter)
205 {
206     T ret = range;
207     foreach (i; 0..iter)
208         ret ~= range;
209     return ret;
210 }
211 
212 /**
213  * Creates a `size_t[][]` holding every indices combination of a range of `length`.
214  *
215  * Params:
216  *  length = Length of hypothetical range to derive combinations from.
217  *
218  * Returns:
219  *  `size_t[][]` containing every indices combination of a range of `length`.
220  */
221 size_t[][] combinations(size_t length) pure nothrow
222 {
223     size_t[][] ret;
224     foreach (i; 0..(1 << length)) 
225     {
226         size_t[] combination;
227         foreach (j; 0..length) 
228         {
229             if (i & (1 << j))
230                 combination ~= j;
231         }
232         ret ~= combination;
233     }
234     return ret;
235 }
236 
237 /**
238  * Creates a `ubyte[][]` holding every `ubyte[]` permutation of a range of `length`.
239  *
240  * Params:
241  *  length = Length of the `ubyte[]` from which to generate from.
242  *
243  * Returns:
244  *  `ubyte[][]` containing every `ubyte[]` permutation of a range of `length`.
245  */
246 ubyte[][] permutations(size_t length) pure nothrow
247 {
248     ubyte[][] ret;
249     foreach (i; 0..(256 ^^ length))
250     {
251         ubyte[] perm;
252         foreach (j; 0..length)
253             perm ~= cast(ubyte)(i >> (8 * j));
254         ret ~= perm;
255     }
256     return ret;
257 }