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