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