1 /** 2 Some additional alogorithm functions. 3 4 Copyright: © 2018 Arne Ludwig <arne.ludwig@posteo.de> 5 License: Subject to the terms of the MIT license, as written in the 6 included LICENSE file. 7 Authors: Arne Ludwig <arne.ludwig@posteo.de> 8 */ 9 module dentist.util.algorithm; 10 11 import std.algorithm : 12 copy, 13 countUntil, 14 min, 15 OpenRight, 16 uniq; 17 import std.conv : to; 18 import std.functional : binaryFun, unaryFun; 19 import std.traits : isDynamicArray; 20 import std.typecons : Yes; 21 import std.range.primitives; 22 23 /** 24 Order `a` and `b` lexicographically by applying each `fun` to them. For 25 unary functions compares `fun(a) < fun(b)`. 26 */ 27 bool orderLexicographically(T, fun...)(T a, T b) pure nothrow 28 { 29 static foreach (i, getFieldValue; fun) 30 { 31 { 32 auto aValue = unaryFun!getFieldValue(a); 33 auto bValue = unaryFun!getFieldValue(b); 34 35 if (aValue != bValue) 36 { 37 return aValue < bValue; 38 } 39 } 40 } 41 42 return false; 43 } 44 45 /** 46 Compare `a` and `b` lexicographically by applying each `fun` to them. For 47 unary functions compares `fun(a) < fun(b)`. 48 */ 49 int cmpLexicographically(T, fun...)(T a, T b) pure nothrow 50 { 51 static foreach (i, getFieldValue; fun) 52 { 53 { 54 auto aValue = unaryFun!getFieldValue(a); 55 auto bValue = unaryFun!getFieldValue(b); 56 57 if (aValue < bValue) 58 { 59 return -1; 60 } 61 else if (aValue > bValue) 62 { 63 return 1; 64 } 65 } 66 } 67 68 return 0; 69 } 70 71 /** 72 Slices an input array into slices of equivalent adjacent elements. 73 In other languages this is often called `partitionBy`, `groupBy` 74 or `sliceWhen`. 75 76 Equivalence is defined by the predicate `pred`, which can be binary, 77 which is passed to `std.functional.binaryFun`. Two range elements 78 `a` and `b` are considered equivalent if `pred(a,b)` is true. 79 80 This predicate must be an equivalence relation, that is, it must be 81 reflexive (`pred(x,x)` is always true), symmetric 82 (`pred(x,y) == pred(y,x)`), and transitive (`pred(x,y) && pred(y,z)` 83 implies `pred(x,z)`). If this is not the case, the range returned by 84 chunkBy may assert at runtime or behave erratically. 85 86 Params: 87 pred = Predicate for determining equivalence. 88 r = An array to be sliced. 89 90 Returns: With a binary predicate, a range of slices is returned in which 91 all elements in a given slice are equivalent under the given predicate. 92 93 Notes: 94 95 Equivalent elements separated by an intervening non-equivalent element will 96 appear in separate subranges; this function only considers adjacent 97 equivalence. Elements in the subranges will always appear in the same order 98 they appear in the original range. 99 */ 100 auto sliceBy(alias pred, Array)(Array array) pure nothrow 101 if (isDynamicArray!Array) 102 { 103 return SliceByImpl!(pred, Array)(array); 104 } 105 106 /// 107 unittest 108 { 109 import std.algorithm.comparison : equal; 110 111 // Grouping by particular attribute of each element: 112 auto data = [ 113 [1, 1], 114 [1, 2], 115 [2, 2], 116 [2, 3] 117 ]; 118 119 auto r1 = data.sliceBy!((a,b) => a[0] == b[0]); 120 assert(r1.equal([ 121 data[0 .. 2], 122 data[2 .. 4] 123 ])); 124 125 auto r2 = data.sliceBy!((a,b) => a[1] == b[1]); 126 assert(r2.equal([ 127 data[0 .. 1], 128 data[1 .. 3], 129 data[3 .. 4], 130 ])); 131 } 132 133 private struct SliceByImpl(alias pred, Array) 134 if (isDynamicArray!Array) 135 { 136 private alias equivalent = binaryFun!pred; 137 138 private Array array; 139 private size_t sliceStart; 140 private size_t sliceEnd; 141 142 this(Array array) 143 { 144 this.array = array; 145 146 if (!empty) 147 { 148 popFront(); 149 } 150 } 151 152 void popFront() 153 { 154 assert(!empty, "Attempting to popFront an empty SliceByImpl"); 155 156 sliceStart = sliceEnd++; 157 158 if (empty) 159 { 160 return; 161 } 162 163 auto refElement = array[sliceStart]; 164 while (sliceEnd < array.length && equivalent(refElement, array[sliceEnd])) 165 { 166 ++sliceEnd; 167 } 168 } 169 170 @property bool empty() const pure nothrow 171 { 172 return sliceStart >= array.length; 173 } 174 175 @property auto front() 176 { 177 assert(!empty, "Attempting to fetch the front of an empty SliceByImpl"); 178 179 return array[sliceStart .. sliceEnd]; 180 } 181 } 182 183 /// Return the prefix of `haystack` where `pred` is not satisfied. 184 Array sliceUntil(alias pred = "a == b", Array, Needle)( 185 Array haystack, 186 Needle needle, 187 OpenRight openRight = Yes.openRight, 188 ) 189 if (isDynamicArray!Array) 190 { 191 alias predFun = binaryFun!pred; 192 193 foreach (i, ref e; haystack) 194 if (predFun(e, needle)) 195 return haystack[0 .. (openRight ? i : i + 1)]; 196 197 return haystack[0 .. $]; 198 } 199 200 /// ditto 201 Array sliceUntil(alias pred = "a", Array)( 202 Array haystack, 203 OpenRight openRight = Yes.openRight, 204 ) 205 if (isDynamicArray!Array) 206 { 207 alias predFun = unaryFun!pred; 208 209 foreach (i, ref e; haystack) 210 if (predFun(e)) 211 return haystack[0 .. (openRight ? i : i + 1)]; 212 213 return haystack[0 .. $]; 214 } 215 216 /// 217 unittest 218 { 219 import std.typecons : No; 220 221 int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5]; 222 assert(a.sliceUntil(7) == [1, 2, 4]); 223 assert(a.sliceUntil!"a == 7" == [1, 2, 4]); 224 assert(a.sliceUntil(7, No.openRight) == [1, 2, 4, 7]); 225 } 226 227 /// Returns array `uniq`ified in-place. 228 Array uniqInPlace(alias pred = "a == b", Array)(auto ref Array array) if (isDynamicArray!Array) 229 { 230 auto bufferRest = array.uniq.copy(array); 231 232 array = array[0 .. $ - bufferRest.length]; 233 234 return array; 235 } 236 237 /// 238 unittest 239 { 240 auto arr = [1, 2, 2, 2, 3, 3, 4]; 241 242 assert(uniqInPlace(arr) == [1, 2, 3, 4]); 243 // The input array gets modified. 244 assert(arr == [1, 2, 3, 4]); 245 246 // Can be called with non-lvalues 247 assert(uniqInPlace([1, 2, 2, 2, 3, 3, 4]) == [1, 2, 3, 4]); 248 } 249 250 /// Replaces the first occurrence of `needle` by `replacement` in `array` if 251 /// present. Modifies array. 252 Array replaceInPlace(alias pred = "a == b", Array, E)(auto ref Array array, E needle, E replacement) 253 if (isDynamicArray!Array) 254 { 255 auto i = array.countUntil!pred(needle); 256 257 if (i < 0) 258 return array; 259 260 array[i] = replacement; 261 262 return array; 263 } 264 265 /// 266 unittest 267 { 268 auto arr = [1, 2, 3, 4, 2, 3]; 269 270 assert(arr.replaceInPlace(2, 7) == [1, 7, 3, 4, 2, 3]); 271 // The input array gets modified. 272 assert(arr == [1, 7, 3, 4, 2, 3]); 273 // Replaces only the first occurrence 274 assert(arr.replaceInPlace(2, 7) == [1, 7, 3, 4, 7, 3]); 275 276 // Can be called with non-lvalues 277 assert([1, 2, 3].replaceInPlace(2, 7) == [1, 7, 3]); 278 } 279 280 /// Get the first element in range assuming it to be non-empty. 281 ElementType!Range first(Range)(Range range) if (isInputRange!Range) 282 { 283 assert(!range.empty, "must not call first on an empty range"); 284 285 return range.front; 286 } 287 288 /// 289 unittest 290 { 291 assert(first([1, 2, 3]) == 1); 292 assert(first("abcd") == 'a'); 293 } 294 295 /// Get the last element in range assuming it to be non-empty. 296 ElementType!Range last(Range)(Range range) if (isInputRange!Range) 297 { 298 import std.stdio; 299 assert(!range.empty, "must not call last on an empty range"); 300 301 static if (isBidirectionalRange!Range) 302 { 303 return range.back; 304 } 305 else static if (hasLength!Range) 306 { 307 foreach (i; 0 .. range.length - 1) 308 range.popFront(); 309 310 return range.front; 311 } 312 else static if (isForwardRange!Range) 313 { 314 auto checkpoint = range; 315 316 while (!range.empty) 317 { 318 checkpoint = range.save; 319 range.popFront(); 320 } 321 322 return checkpoint.front; 323 } 324 else 325 { 326 typeof(return) lastElement; 327 328 while (!range.empty) 329 { 330 lastElement = range.front; 331 range.popFront(); 332 } 333 334 return lastElement; 335 } 336 337 } 338 339 /// 340 unittest 341 { 342 import std.algorithm : filter; 343 import std.range : take, takeExactly; 344 345 struct PowersOfTwo(bool shouldSave) 346 { 347 size_t i = 1; 348 349 void popFront() pure nothrow 350 { 351 i *= 2; 352 } 353 354 @property size_t front() const pure nothrow 355 { 356 return i + 0; 357 } 358 359 @property bool empty() const pure nothrow 360 { 361 return false; 362 } 363 364 static if (shouldSave) 365 { 366 @property PowersOfTwo save() const pure nothrow 367 { 368 return cast(typeof(return)) this; 369 } 370 } 371 } 372 373 assert(last([1, 2, 3]) == 3); 374 assert(last(PowersOfTwo!true(1).takeExactly(5)) == 16); 375 assert(last(PowersOfTwo!true(1).take(5)) == 16); 376 assert(last(PowersOfTwo!false(1).take(5)) == 16); 377 } 378 379 /// Returns one of a collection of expressions based on the value of the 380 /// switch expression. 381 template staticPredSwitch(T...) 382 { 383 auto staticPredSwitch(E)(E switchExpression) pure nothrow 384 { 385 static assert (T.length > 0, "missing choices"); 386 static assert (T.length % 2 == 1, "missing default clause"); 387 388 static foreach (i; 0 .. T.length - 1) 389 { 390 static if (i % 2 == 0) 391 { 392 if (switchExpression == T[i]) 393 return T[i + 1]; 394 } 395 } 396 397 return T[$ - 1]; 398 } 399 } 400 401 /// 402 unittest 403 { 404 alias numberName = staticPredSwitch!( 405 1, "one", 406 2, "two", 407 3, "three", 408 "many", 409 ); 410 411 static assert("one" == numberName(1)); 412 static assert("two" == numberName(2)); 413 static assert("three" == numberName(3)); 414 static assert("many" == numberName(4)); 415 }