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