dkh.algorithm source code

1 module dkh.algorithm;
2 
3 import std.traits : isFloatingPoint, isIntegral;
4 
5 /**
6 Do binary search, pred(l) must be false, pred(r) must be true, and pred must have monotonic
7 
8 $(D [pred(l) = false, false, ..., false, true, true, ..., pred(r) = true])
9     
10 Returns:
11     minimum x, s.t. $(D pred(x) = true)
12  */
13 T binSearch(alias pred, T)(T l, T r) if (isIntegral!T) {
14     while (r-l > 1) {
15         T md = l + (r-l) / 2;
16         if (!pred(md)) l = md;
17         else r = md;
18     }
19     return r;
20 }
21 
22 /// ditto
23 T binSearch(alias pred, T)(T l, T r, int cnt = 60) if (isFloatingPoint!T) {
24     foreach (i; 0..cnt) {
25         T md = (l+r)/2;
26         if (!pred(md)) l = md;
27         else r = md;
28     }
29     return r;
30 }
31 
32 ///
33 unittest {
34     assert(binSearch!(x => x*x >= 100)(0, 20) == 10);
35     assert(binSearch!(x => x*x >= 101)(0, 20) == 11);
36     assert(binSearch!(x => true)(0, 20) == 1);
37     assert(binSearch!(x => false)(0, 20) == 20);
38 }
39 
40 import std.range.primitives;
41 
42 /// Find minimum
43 E minimum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed)
44 if (isInputRange!Range && !isInfinite!Range) {
45     import std.algorithm, std.functional;
46     return reduce!((a, b) => binaryFun!pred(a, b) ? a : b)(seed, range);
47 }
48 
49 /// ditto
50 ElementType!Range minimum(alias pred = "a < b", Range)(Range range) {
51     assert(!range.empty, "minimum: range must not empty");
52     auto e = range.front; range.popFront;
53     return minimum!pred(range, e);
54 }
55 
56 ///
57 unittest {
58     assert(minimum([2, 1, 3]) == 1);
59     assert(minimum!"a > b"([2, 1, 3]) == 3);
60     assert(minimum([2, 1, 3], -1) == -1);
61     assert(minimum!"a > b"([2, 1, 3], 100) == 100);
62 }
63 
64 /// Find maximum
65 E maximum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed)
66 if (isInputRange!Range && !isInfinite!Range) {
67     import std.algorithm, std.functional;
68     return reduce!((a, b) => binaryFun!pred(a, b) ? b : a)(seed, range);
69 }
70 
71 /// ditto
72 ElementType!Range maximum(alias pred = "a < b", Range)(Range range) {
73     assert(!range.empty, "maximum: range must not empty");
74     auto e = range.front; range.popFront;
75     return maximum!pred(range, e);
76 }
77 
78 ///
79 unittest {
80     assert(maximum([2, 1, 3]) == 3);
81     assert(maximum!"a > b"([2, 1, 3]) == 1);
82     assert(maximum([2, 1, 3], 100) == 100);
83     assert(maximum!"a > b"([2, 1, 3], -1) == -1);
84 }
85 
86 /**
87 Range that rotate elements.
88  */
89 Rotator!Range rotator(Range)(Range r) {
90     return Rotator!Range(r);
91 }
92 
93 /// ditto
94 struct Rotator(Range)
95 if (isForwardRange!Range && hasLength!Range) {
96     size_t cnt;
97     Range start, now;
98     this(Range r) {
99         cnt = 0;
100         start = r.save;
101         now = r.save;
102     }
103     this(this) {
104         start = start.save;
105         now = now.save;
106     }
107     @property bool empty() const {
108         return now.empty;
109     }
110     @property auto front() const {
111         assert(!now.empty);
112         import std.range : take, chain;
113         return chain(now, start.take(cnt));
114     }
115     @property Rotator!Range save() {
116         return this;
117     }
118     void popFront() {
119         cnt++;
120         now.popFront;
121     }
122 }
123 
124 ///
125 unittest {
126     import std.algorithm : equal, cmp;
127     import std.array : array;
128     int[] a = [1, 2, 3];
129     assert(equal!equal(a.rotator, [
130         [1, 2, 3],
131         [2, 3, 1],
132         [3, 1, 2],
133     ]));
134     int[] b = [3, 1, 4, 1, 5];
135     assert(equal(b.rotator.maximum!"cmp(a, b) == -1", [5, 3, 1, 4, 1]));
136 }