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