nxt.searching_ex source code

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 @safe pure nothrow @nogc unittest
36 {
37     const int[9] x = [1, 3, 5, 6, 8, 9, 10, 13, 15];
38     assert(x.binarySearch(0) == size_t.max);
39     assert(x.binarySearch(1) == 0);
40     assert(x.binarySearch(2) == size_t.max);
41     assert(x.binarySearch(3) == 1);
42     assert(x.binarySearch(4) == size_t.max);
43     assert(x.binarySearch(5) == 2);
44     assert(x.binarySearch(6) == 3);
45     assert(x.binarySearch(7) == size_t.max);
46     assert(x.binarySearch(8) == 4);
47     assert(x.binarySearch(9) == 5);
48     assert(x.binarySearch(10) == 6);
49     assert(x.binarySearch(11) == size_t.max);
50     assert(x.binarySearch(12) == size_t.max);
51     assert(x.binarySearch(13) == 7);
52     assert(x.binarySearch(14) == size_t.max);
53     assert(x.binarySearch(15) == 8);
54 }
55 
56 import std.range : ElementType, SearchPolicy, SortedRange;
57 
58 /** Same as `range.contains()` but also outputs `index` where last occurrence of
59     `key` is either currently stored (if `true` is returned) or should be stored
60     (if `false` is returned) in order to preserve sortedness of `range`.
61 
62     The elements of `range` are assumed to be sorted in default (ascending)
63     order.
64 
65     TODO: Move to member of `SortedRange` either as a new name or as an
66     `contains`-overload take an extra `index` as argument.
67  */
68 bool containsStoreIndex(SearchPolicy sp = SearchPolicy.binarySearch, R, V)
69                        (R range, V value, out size_t index)
70     if (is(typeof(ElementType!R.init == V.init)) &&
71         is(R == SortedRange!(_), _)) // TODO: check for comparsion function
72 {
73     // TODO: should we optimize for this case?
74     // if (range.empty)
75     // {
76     //     index = 0;
77     //     return false;           // no hit
78     // }
79     index = range.length - range.upperBound!sp(value).length; // always larger than zero
80     if (index >= 1 && range[index - 1] == value)
81     {
82         --index;                             // make index point to last occurrence of `value`
83         assert(range.contains(value)); // assert same behaviour as existing contains
84         return true;
85     }
86     assert(!range.contains(value)); // assert same behaviour as existing contains
87     return false;
88 }
89 
90 ///
91 @safe pure nothrow @nogc unittest
92 {
93     const int[0] x;
94     size_t index;
95     import std.range : assumeSorted;
96     assert(!x[].assumeSorted.containsStoreIndex(int.min, index) && index == 0);
97     assert(!x[].assumeSorted.containsStoreIndex(-1,      index) && index == 0);
98     assert(!x[].assumeSorted.containsStoreIndex(0,       index) && index == 0);
99     assert(!x[].assumeSorted.containsStoreIndex(1,       index) && index == 0);
100     assert(!x[].assumeSorted.containsStoreIndex(int.max, index) && index == 0);
101 }
102 
103 ///
104 @safe pure nothrow @nogc unittest
105 {
106     const int[2] x = [1, 3];
107     size_t index;
108     import std.range : assumeSorted;
109     assert(!x[].assumeSorted.containsStoreIndex(int.min, index) && index == 0);
110     assert(!x[].assumeSorted.containsStoreIndex(-1,      index) && index == 0);
111     assert(!x[].assumeSorted.containsStoreIndex(0,       index) && index == 0);
112     assert( x[].assumeSorted.containsStoreIndex(1,       index) && index == 0);
113     assert(!x[].assumeSorted.containsStoreIndex(2,       index) && index == 1);
114     assert( x[].assumeSorted.containsStoreIndex(3,       index) && index == 1);
115     assert(!x[].assumeSorted.containsStoreIndex(4,       index) && index == 2);
116     assert(!x[].assumeSorted.containsStoreIndex(5,       index) && index == 2);
117     assert(!x[].assumeSorted.containsStoreIndex(int.max, index) && index == 2);
118 }