dkh.segtree.primitive source code

1 module dkh.segtree.primitive;
2 
3 import std.conv : to;
4 
5 struct SegTree(alias E, Args...) {
6     import std.traits : ReturnType;
7     alias Engine = E!Args;
8     alias T = Engine.DataType;
9     alias L = Engine.LazyType;
10 
11     Engine eng;
12 
13     this(size_t n) { eng = Engine(n.to!uint); }
14     this(T[] first) { eng = Engine(first); }
15 
16     @property size_t length() const { return eng.length(); }
17     @property size_t opDollar() const { return eng.length(); }
18     
19     struct Range {
20         Engine* eng;
21         size_t start, end;
22         @property const(T) sum() {
23             return eng.sum(start.to!uint, end.to!uint);
24         }
25     }
26     const(T) opIndex(size_t k) {
27         assert(0 <= k && k < eng.length());
28         return eng.single(k.to!uint);
29     }
30     void opIndexAssign(T x, size_t k) {
31         assert(0 <= k && k < eng.length());
32         eng.singleSet(k.to!uint, x);
33     }
34     size_t[2] opSlice(size_t dim : 0)(size_t start, size_t end) {
35         assert(0 <= start && start <= end && end <= eng.length());
36         return [start, end];
37     }
38     Range opIndex(size_t[2] rng) {
39         return Range(&eng, rng[0].to!uint, rng[1].to!uint);
40     }
41     static if (!is(L == void)) {
42         void opIndexOpAssign(string op : "+")(L x, size_t[2] rng) {
43             eng.add(rng[0].to!uint, rng[1].to!uint, x);
44         }
45     }
46 }
47 
48 import std.traits : isInstanceOf;
49 
50 ptrdiff_t binSearchLeft(alias pred, TR)(TR t, ptrdiff_t a, ptrdiff_t b) 
51 if (isInstanceOf!(SegTree, TR)) {
52     return TR.Engine.BinSearch!(false, pred)(t.eng, a.to!int, b.to!int);
53 }
54 
55 ptrdiff_t binSearchRight(alias pred, TR)(TR t, ptrdiff_t a, ptrdiff_t b) 
56 if (isInstanceOf!(SegTree, TR)) {
57     return TR.Engine.BinSearch!(true, pred)(t.eng, a.to!int, b.to!int);
58 }