1/**
2 * Treap container for internal usage.
3 *
4 * Copyright: Copyright Digital Mars 2014 - 2014.
5 * License:   $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
6 */
7module core.internal.container.treap;
8
9static import common = core.internal.container.common;
10import core.internal.qsort;
11
12struct Treap(E)
13{
14nothrow:
15    static struct Node
16    {
17        Node* left, right;
18        E element;
19        uint priority;
20    }
21
22    @disable this(this);
23
24    ~this()
25    {
26        removeAll();
27    }
28
29    void initialize(ulong randSeed)
30    {
31        Rand _rand = { randSeed };
32        rand = _rand;
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 (CoreUnittest)
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 (CoreUnittest)
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
109private:
110    Node* root;
111    Rand rand;
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 = rand();
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
144static:
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 (CoreUnittest)
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
251unittest
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    srand(cast(uint)time(null));
266    treap.initialize(rand());
267
268    uint[] data;
269initialLoop:
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
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
340/// Random number generators for internal usage.
341private struct Rand
342{
343    private ulong rng_state;
344
345@safe @nogc nothrow:
346pure:
347
348    auto opCall()
349    {
350        auto result = front;
351        popFront();
352        return result;
353    }
354
355    @property uint front()
356    {
357        return cast(uint)(rng_state >> 32);
358    }
359
360    void popFront()
361    {
362        immutable ulong a = 2862933555777941757;
363        immutable ulong c = 1;
364        rng_state = a * rng_state + c;
365    }
366
367    enum empty = false;
368}
369