dkh.container.radixheap source code

1 module dkh.container.radixheap;
2 
3 import dkh.container.stackpayload;
4 
5 import std.functional : unaryFun;
6 import std.traits : isSigned, isUnsigned;
7 
8 /**
9 Radix Heap
10  */
11 template RadixHeap(T, alias pred = "a") {
12     alias _pred = unaryFun!pred; // pred(value) = key
13     alias K = typeof(_pred(T())); // key type
14     ///
15     static if (isUnsigned!K) {
16         // unsigned
17 
18         struct RadixHeap {
19             static struct Payload {
20                 StackPayload!T[K.sizeof*8+1] v;
21                 size_t len;
22                 K last;
23 
24                 // bsr(x) + 1
25                 private static int bsr1(K x) {
26                     import core.bitop : bsr;
27                     return (x == 0) ? 0 : bsr(x)+1;
28                 }
29                 private void assign(T item) {
30                     K key = _pred(item);
31                     assert(last <= key);
32                     v[bsr1(key^last)] ~= item;
33                 }
34                 private void pull() {
35                     import std.range, std.algorithm;
36                     if (v[0].length) return;
37                     auto i = iota(K.sizeof*8+1).find!(a => v[a].length).front;
38                     // reassign v[i]
39                     last = v[i].data[].map!_pred.reduce!min;
40                     v[i].data.each!(a => assign(a));
41                     v[i].clear();
42                 }
43 
44                 void insert(T item) {
45                     len++;
46                     assign(item);
47                 }
48                 T front() {
49                     pull();
50                     return v[0].back;
51                 }
52                 void removeFront() {
53                     pull();
54                     len--;
55                     v[0].removeBack();
56                 }
57             }
58             Payload* p;
59 
60             @property bool empty() const { return (!p || p.len == 0); } ///
61             @property size_t length() const { return (!p ? 0 : p.len); } ///
62             alias opDollar = length; /// ditto
63 
64             /// Warning: return minimum
65             T front() {
66                 assert(!empty, "RadixHeap.front: heap is empty");
67                 return p.front;
68             }
69             void insert(T item) {
70                 if (!p) p = new Payload();
71                 p.insert(item);
72             } ///
73             void removeFront() {
74                 assert(!empty, "RadixHeap.removeFront: heap is empty");
75                 p.removeFront();
76             } ///
77         }
78     } else static if (isSigned!K) {
79         // signed
80         import std.traits : Unsigned;
81         static Unsigned!K pred2(in T item) {
82             return _pred(item) ^ (K(1) << (K.sizeof*8 - 1));
83         }
84         alias RadixHeap = RadixHeap!(T, pred2);
85     } else {
86         static assert(false);
87     }
88 }
89 
90 ///
91 unittest {
92     RadixHeap!int q;
93     q.insert(2);
94     q.insert(1);
95     assert(q.front == 1);
96     q.removeFront();
97     assert(q.front == 2);
98 }
99 
100 unittest {
101     import std.algorithm;
102     import std.random;
103     void test(T)() {
104         RadixHeap!T q;
105         T[] a = new T[100];
106         a.each!((ref x) => x = uniform!"[]"(T.min, T.max));
107         foreach (i; 0..100) {
108             q.insert(a[i]);
109         }
110         a.sort!"a<b";
111         foreach (i; 0..100) {
112             assert(q.front() == a[i]);
113             q.removeFront();
114         }
115     }
116     test!ubyte();
117     test!ushort();
118     test!uint();
119     test!ulong();
120 
121     test!byte();
122     test!short();
123     test!int();
124     test!long();
125 }
126 
127 unittest {
128     RadixHeap!int r;
129     r.insert(100);
130     auto r2 = r;
131     r2.insert(10);
132     assert(r.length == 2);
133     r.removeFront();
134     assert(r2.length == 1);
135 }