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 }