1 /** Extensions to std.algorithm.searching. 2 Copyright: Per Nordlöw 2022-. 3 License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0). 4 Authors: $(WEB Per Nordlöw) 5 */ 6 module nxt.searching_ex; 7 8 /** This function returns the index of the `value` if it exist among `values`, 9 `size_t.max` otherwise. 10 11 TODO: Should we extend to isRandomAccessRange support? In that case we don't 12 get static array support by default. 13 */ 14 size_t binarySearch(R, E)(const R[] values, in E value) 15 if (is(typeof(values[0].init == E.init))) /+ TODO: SortedRange support +/ 16 { 17 // value is not in the array if the array is empty 18 if (values.length == 0) { return typeof(return).max; } 19 20 immutable mid = values.length / 2; // mid offset 21 if (value == values[mid]) 22 return mid; // direct hit 23 else if (value < values[mid]) 24 return binarySearch(values[0 .. mid], value); // recurse left 25 else 26 { 27 const index = binarySearch(values[mid + 1 .. $], value); // recurse right 28 if (index != typeof(return).max) 29 return index + mid + 1; // adjust the index; it is 0-based in the right-hand side slice. 30 return index; 31 } 32 } 33 34 /// 35 pure nothrow @safe @nogc unittest { 36 const int[9] x = [1, 3, 5, 6, 8, 9, 10, 13, 15]; 37 assert(x.binarySearch(0) == size_t.max); 38 assert(x.binarySearch(1) == 0); 39 assert(x.binarySearch(2) == size_t.max); 40 assert(x.binarySearch(3) == 1); 41 assert(x.binarySearch(4) == size_t.max); 42 assert(x.binarySearch(5) == 2); 43 assert(x.binarySearch(6) == 3); 44 assert(x.binarySearch(7) == size_t.max); 45 assert(x.binarySearch(8) == 4); 46 assert(x.binarySearch(9) == 5); 47 assert(x.binarySearch(10) == 6); 48 assert(x.binarySearch(11) == size_t.max); 49 assert(x.binarySearch(12) == size_t.max); 50 assert(x.binarySearch(13) == 7); 51 assert(x.binarySearch(14) == size_t.max); 52 assert(x.binarySearch(15) == 8); 53 } 54 55 import std.range : ElementType, SearchPolicy, SortedRange; 56 57 /** Same as `range.contains()` but also outputs `index` where last occurrence of 58 `key` is either currently stored (if `true` is returned) or should be stored 59 (if `false` is returned) in order to preserve sortedness of `range`. 60 61 The elements of `range` are assumed to be sorted in default (ascending) 62 order. 63 64 TODO: Move to member of `SortedRange` either as a new name or as an 65 `contains`-overload take an extra `index` as argument. 66 */ 67 bool containsStoreIndex(SearchPolicy sp = SearchPolicy.binarySearch, R, V) 68 (R range, V value, out size_t index) 69 if (is(typeof(ElementType!R.init == V.init)) && 70 is(R == SortedRange!(_), _)) /+ TODO: check for comparsion function +/ 71 { 72 /+ TODO: should we optimize for this case? +/ 73 // if (range.empty) 74 // { 75 // index = 0; 76 // return false; // no hit 77 // } 78 index = range.length - range.upperBound!sp(value).length; // always larger than zero 79 if (index >= 1 && range[index - 1] == value) 80 { 81 --index; // make index point to last occurrence of `value` 82 assert(range.contains(value)); // assert same behaviour as existing contains 83 return true; 84 } 85 assert(!range.contains(value)); // assert same behaviour as existing contains 86 return false; 87 } 88 89 /// 90 pure nothrow @safe @nogc unittest { 91 const int[0] x; 92 size_t index; 93 import std.range : assumeSorted; 94 assert(!x[].assumeSorted.containsStoreIndex(int.min, index) && index == 0); 95 assert(!x[].assumeSorted.containsStoreIndex(-1, index) && index == 0); 96 assert(!x[].assumeSorted.containsStoreIndex(0, index) && index == 0); 97 assert(!x[].assumeSorted.containsStoreIndex(1, index) && index == 0); 98 assert(!x[].assumeSorted.containsStoreIndex(int.max, index) && index == 0); 99 } 100 101 /// 102 pure nothrow @safe @nogc unittest { 103 const int[2] x = [1, 3]; 104 size_t index; 105 import std.range : assumeSorted; 106 assert(!x[].assumeSorted.containsStoreIndex(int.min, index) && index == 0); 107 assert(!x[].assumeSorted.containsStoreIndex(-1, index) && index == 0); 108 assert(!x[].assumeSorted.containsStoreIndex(0, index) && index == 0); 109 assert( x[].assumeSorted.containsStoreIndex(1, index) && index == 0); 110 assert(!x[].assumeSorted.containsStoreIndex(2, index) && index == 1); 111 assert( x[].assumeSorted.containsStoreIndex(3, index) && index == 1); 112 assert(!x[].assumeSorted.containsStoreIndex(4, index) && index == 2); 113 assert(!x[].assumeSorted.containsStoreIndex(5, index) && index == 2); 114 assert(!x[].assumeSorted.containsStoreIndex(int.max, index) && index == 2); 115 }