dkh.segtree.naive source code

1 module dkh.segtree.naive;
2 
3 static struct NaiveSimple(T, alias opTT, T eT) {
4     import std.conv : to;
5     alias DataType = T;
6     alias LazyType = void;
7     alias BinSearch = binSearchNaive;
8     T[] d;
9     @property size_t length() const { return d.length; }
10     this(uint n) {
11         d = new T[n];
12     }
13     this(T[] first) {
14         d = first.dup;
15     }
16     const(T) sum(uint l, uint r) {
17         T sm = eT;
18         foreach (i; l..r) {
19             sm = opTT(sm, d[i]);
20         }
21         return sm;
22     }
23     const(T) single(int k) { return d[k]; }
24     void singleSet(int k, in T x) { d[k] = x; }
25 }
26 
27 static struct Naive(T, L, alias opTT, alias opTL, alias opLL, T eT, L eL) {
28     import std.conv : to;
29     alias DataType = T;
30     alias LazyType = L;
31     alias BinSearch = binSearchNaiveLazy;
32     T[] d;
33     @property size_t length() const { return d.length; }
34     this(uint n) {
35         d = new T[n];
36     }
37     this(T[] first) {
38         d = first.dup;
39     }
40     const(T) sum(uint l, uint r) {
41         T sm = eT;
42         foreach (i; l..r) {
43             sm = opTT(sm, d[i]);
44         }
45         return sm;
46     }
47     void add(uint l, uint r, in L m) {
48         foreach (i; l..r) {
49             d[i] = opTL(d[i], m);
50         }
51     }
52     const(T) single(int k) { return d[k]; }
53     void singleSet(int k, in T x) { d[k] = x; }
54 }
55 
56 
57 int binSearchNaive(bool rev, alias pred, TR)(TR t, int a, int b) {
58     import std.traits : TemplateArgsOf;
59     alias args = TemplateArgsOf!TR;
60     alias opTT = args[1];
61     auto x = args[2];
62     with (t) {
63         static if (!rev) {
64             //left
65             if (pred(x)) return a-1;
66             foreach (i; a..b) {
67                 x = opTT(x, d[i]);
68                 if (pred(x)) return i;
69             }
70             return b;
71         } else {
72             if (pred(x)) return b;
73             foreach_reverse (i; a..b) {
74                 x = opTT(d[i], x);
75                 if (pred(x)) return i;
76             }
77             return a-1;
78         }
79     }
80 }
81 
82 int binSearchNaiveLazy(bool rev, alias pred, TR)(TR t, int a, int b) {
83     import std.traits : TemplateArgsOf;
84     alias args = TemplateArgsOf!TR;
85     alias opTT = args[2];
86     auto x = args[5];
87     with (t) {
88         static if (!rev) {
89             //left
90             if (pred(x)) return a-1;
91             foreach (i; a..b) {
92                 x = opTT(x, d[i]);
93                 if (pred(x)) return i;
94             }
95             return b;
96         } else {
97             if (pred(x)) return b;
98             foreach_reverse (i; a..b) {
99                 x = opTT(d[i], x);
100                 if (pred(x)) return i;
101             }
102             return a-1;
103         }
104     }
105 }