libphobos/libdruntime/core/internal/container/treap.d

   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  */
   7 module core.internal.container.treap;
   8
   9 static import common = core.internal.container.common;
  10 import core.internal.qsort;
  11
  12 struct Treap(E)
  13 {
  14 nothrow:
  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
 109 private:
 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
 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 (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
 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     srand(cast(uint)time(null));
 266     treap.initialize(rand());
 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
 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.
 341 private struct Rand
 342 {
 343     private ulong rng_state;
 344
 345 @safe @nogc nothrow:
 346 pure:
 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 }