nxt.searching_ex source code

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