1 /**
2 * Treap container for internal usage.
3 *
4 * Copyright: Copyright Digital Mars 2014 - 2014.
5 * License: $(WEB www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
6 */
7 module rt.util.container.treap;
8
9 static import common = rt.util.container.common;
10 import rt.util.random;
11 import rt.qsort;
12
Treap(E)13 struct Treap(E)
14 {
15 nothrow:
16 static struct Node
17 {
18 Node* left, right;
19 E element;
20 uint priority;
21 }
22
23 @disable this(this);
24
25 ~this()
26 {
27 removeAll();
28 }
29
30 void initialize()
31 {
32 rand48.defaultSeed();
33 }
34
35 void insert(E element) @nogc
36 {
37 root = insert(root, element);
38 }
39
40 void remove(E element)
41 {
42 remove(&root, element);
43 }
44
45 int opApply(scope int delegate(ref E) nothrow dg)
46 {
47 return (cast(const)&this).opApply((ref const E e) => dg(*cast(E*)&e));
48 }
49
50 int opApply(scope int delegate(ref const E) nothrow dg) const
51 {
52 return opApplyHelper(root, dg);
53 }
54
55 version (unittest)
56 bool opEquals(E[] elements)
57 {
58 size_t i;
59 foreach (e; this)
60 {
61 if (i >= elements.length)
62 return false;
63 if (e != elements[i++])
64 return false;
65 }
66 return i == elements.length;
67 }
68
69 void removeAll()
70 {
71 removeAll(root);
72 root = null;
73 }
74
75 version (unittest)
76 bool valid()
77 {
78 return valid(root);
79 }
80
81
82 version (none)
83 uint height()
84 {
85 static uint height(Node* node)
86 {
87 if (!node)
88 return 0;
89 auto left = height(node.left);
90 auto right = height(node.right);
91 return 1 + (left > right ? left : right);
92 }
93 return height(root);
94 }
95
96 version (none)
97 size_t count()
98 {
99 static size_t count(Node* node)
100 {
101 if (!node)
102 return 0;
103 return count(node.left) + count(node.right) + 1;
104 }
105 return count(root);
106 }
107
108
109 private:
110 Node* root;
111 Rand48 rand48;
112
113 Node* allocNode(E element) @nogc
114 {
115 Node* node = cast(Node*)common.xmalloc(Node.sizeof);
116 node.left = node.right = null;
117 node.priority = rand48();
118 node.element = element;
119 return node;
120 }
121
122 Node* insert(Node* node, E element) @nogc
123 {
124 if (!node)
125 return allocNode(element);
126 else if (element < node.element)
127 {
128 node.left = insert(node.left, element);
129 if (node.left.priority < node.priority)
130 node = rotateR(node);
131 }
132 else if (element > node.element)
133 {
134 node.right = insert(node.right, element);
135 if (node.right.priority < node.priority)
136 node = rotateL(node);
137 }
138 else
139 {} // ignore duplicate
140
141 return node;
142 }
143
144 static:
145
146 void freeNode(Node* node)
147 {
148 common.free(node);
149 }
150
151 Node* rotateL(Node* root)
152 {
153 auto pivot = root.right;
154 root.right = pivot.left;
155 pivot.left = root;
156 return pivot;
157 }
158
159 Node* rotateR(Node* root)
160 {
161 auto pivot = root.left;
162 root.left = pivot.right;
163 pivot.right = root;
164 return pivot;
165 }
166
167 void remove(Node** ppnode, E element)
168 {
169 Node* node = *ppnode;
170 if (!node)
171 return; // element not in treap
172
173 if (element < node.element)
174 {
175 remove(&node.left, element);
176 }
177 else if (element > node.element)
178 {
179 remove(&node.right, element);
180 }
181 else
182 {
183 while (node.left && node.right)
184 {
185 if (node.left.priority < node.right.priority)
186 {
187 *ppnode = rotateR(node);
188 ppnode = &(*ppnode).right;
189 }
190 else
191 {
192 *ppnode = rotateL(node);
193 ppnode = &(*ppnode).left;
194 }
195 }
196 if (!node.left)
197 *ppnode = node.right;
198 else
199 *ppnode = node.left;
200 freeNode(node);
201 }
202 }
203
204 void removeAll(Node* node)
205 {
206 if (!node)
207 return;
208 removeAll(node.left);
209 removeAll(node.right);
210 freeNode(node);
211 }
212
213 int opApplyHelper(const Node* node, scope int delegate(ref const E) nothrow dg)
214 {
215 if (!node)
216 return 0;
217
218 int result = opApplyHelper(node.left, dg);
219 if (result)
220 return result;
221 result = dg(node.element);
222 if (result)
223 return result;
224 return opApplyHelper(node.right, dg);
225 }
226
227 version (unittest)
228 bool valid(Node* node)
229 {
230 if (!node)
231 return true;
232
233 if (node.left)
234 {
235 if (node.left.priority < node.priority)
236 return false;
237 if (node.left.element > node.element)
238 return false;
239 }
240 if (node.right)
241 {
242 if (node.right.priority < node.priority)
243 return false;
244 if (node.right.element < node.element)
245 return false;
246 }
247 return valid(node.left) && valid(node.right);
248 }
249 }
250
251 unittest
252 {
253 // randomized unittest for randomized data structure
254 import /*cstdlib = */core.stdc.stdlib : rand, srand;
255 import /*ctime = */core.stdc.time : time;
256
257 enum OP { add, remove }
258 enum initialSize = 1000;
259 enum randOps = 1000;
260
261 Treap!uint treap;
262 OP[] ops;
263 uint[] opdata;
264
265 treap.initialize();
266 srand(cast(uint)time(null));
267
268 uint[] data;
269 initialLoop:
270 foreach (i; 0 .. initialSize)
271 {
272 data ~= rand();
273 treap.insert(data[$-1]);
274 foreach (e; data[0..$-1])
275 if (e == data[$-1])
276 {
277 data = data[0..$-1];
278 continue initialLoop;
279 }
280 }
281 _adSort(*cast(void[]*)&data, typeid(data[0]));
282 assert(treap == data);
283 assert(treap.valid());
284
285 for (int i = randOps; i > 0; --i)
286 {
287 ops ~= cast(OP)(rand() < uint.max / 2 ? OP.add: OP.remove);
288 opdata ~= rand();
289 }
290
foreach(op;ops)291 foreach (op; ops)
292 {
293 if (op == OP.add)
294 {
295 treap.insert(opdata[0]);
296
297 size_t i;
298 for (i = 0; i < data.length; ++i)
299 if (data[i] >= opdata[0])
300 break;
301
302 if (i == data.length || data[i] != opdata[0])
303 { // not a duplicate
304 data.length++;
305 uint tmp = opdata[0];
306 for (; i < data.length; ++i)
307 {
308 uint tmp2 = data[i];
309 data[i] = tmp;
310 tmp = tmp2;
311 }
312 }
313 }
314 else if (!data.length) // nothing to remove
315 {
316 opdata = opdata[1..$];
317 continue;
318 }
319 else
320 {
321 uint tmp = data[opdata[0]%data.length];
322 treap.remove(tmp);
323 size_t i;
324 for (i = 0; data[i] < tmp; ++i)
325 {}
326 for (; i < data.length-1; ++i)
327 data[i] = data[i+1];
328 data.length--;
329 }
330 assert(treap.valid());
331 assert(treap == data);
332 opdata = opdata[1..$];
333 }
334
335 treap.removeAll();
336 data.length = 0;
337 assert(treap == data);
338 }
339