1 /** 2 Copyright: Copyright (c) 2016- Alexander Orlov. All rights reserved. 3 License: $(LINK2 https://opensource.org/licenses/MIT, MIT License). 4 Authors: Alexander Orlov, $(LINK2 mailto:sascha.orlov@gmail.com, sascha.orlov@gmail.com) 5 */ 6 7 /** 8 This module implements a Van Emde Boas tree container. 9 The module is still a work in progress. So, if you find an error by chance, please let me know in any way. 10 The main idea of the container is, to restrict the capacity of the tree by the next power of two universe size, 11 given an arbitrary size at the initialization. The tree can be used in two different modes: 12 1. Tree contains keys only. Supported operations are 13 inserting, deletion, membership testing, neighborhood searching. All queries are of order (lglg U), where U is the 14 capacity of the tree, set on initialization. 15 2. Tree contains keys and values. Additionally to the above operations the indexing operation is supported. It 16 yields the pointer to a stored object, if the key is contained in the tree, otherwise null. 17 For optimization purposes, the size limit is halfSizeT.max + 1. The tree was tested on 64- and 32-bit arch. 18 So the largest element which can be stored is 4.294.967.295 on a 64-bit architecture. 19 */ 20 21 // (optional) todo: provide functionality to contain non-unique keys, i. e. exercise 20.3.1 from Cormen 22 23 /** 24 The main advantage of the Van Emde Boas tree appears on a large amount of elements, as the provided standard 25 operations of the tree are constant in time and of order O(lg2(lg2(U))), where U is the capacity of the tree. For 26 small amount of elements the overhead coming along with the structure take over. For example, for a universe size of 27 2^14 and 15872 insertion operatios the duration for the Van Emde Boas tree is about 1*10^(-3) times smaller. As one 28 of the unittests shows. 29 */ 30 31 /** 32 Be aware, the current container is intended to be used with keys. This implies, that the capacity, fixed on its 33 initialization has two meanings. As usual, it shows the maximum amount of elements the instanciated tree can keep. 34 But also, it states, that no value bigger then capacity - 1 exists in the tree. This, and the fact, that only 35 non-negative values can be used are infered from the term "key". 36 */ 37 38 /** 39 See_also: Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. 2001. <em>Introduction to 40 Algorithms</em> (2nd ed.). McGraw-Hill Higher Education. 41 */ 42 43 /** 44 As an important optimization a bottom out technique is used to compactify the tree to the level of nodes, where bit 45 operations become possible. As a side effect, the optimization now relies on the underlying architecture. This leads 46 to the fact, that the maximum of elements which can be stored is 47 2^16 on a 32-bit architecture and 48 2^32 on a 64-bit architecture. 49 This was intentionally chosen for two reasons: 50 i) to keep the size of a single node also depending from the underlying architecture. 51 ii) for bitoperations, which the tree is relying on, to use the native word size of the architecture without 52 emulating bigger entities. 53 */ 54 55 module vebtree; 56 57 import std.typecons : Nullable; 58 import core.bitop; 59 import std.traits; 60 import std.range; 61 import std.math : nextPow2; 62 import core.stdc.limits : CHAR_BIT; 63 import std.algorithm.iteration : each, map, uniq, sum, filter; 64 import std.algorithm.searching : until, find, canFind, maxIndex; 65 import std.algorithm.sorting : sort; 66 import std.algorithm.setops : setSymmetricDifference; 67 import std.algorithm.comparison : min, max; 68 69 70 private enum vdebug = true; 71 72 version(unittest) 73 { 74 import std.random; 75 import std.datetime.stopwatch; 76 import std.conv : to; 77 import std.container; // red black tree may be used in unittests for comparison. 78 import std.math : sqrt; 79 80 static if(vdebug) 81 { 82 import std.stdio; 83 // helping function for output a given value in binary representation 84 void bin(size_t n) 85 { 86 /* step 1 */ 87 if (n > 1) bin(n/2); 88 /* step 2 */ 89 write(n % 2); 90 } 91 } 92 93 /// precalculated powers of two table for unit testing 94 enum powersOfTwo = iota(0, CHAR_BIT * size_t.sizeof).map!(a => size_t(1) << a); 95 96 Random rndGenInUse; 97 98 // during tests it is ok a tree with a random capacity not going up to the maximum one. 99 enum testedSize = 1 << 2 * size_t.sizeof; //3 * size_t.sizeof; 100 // during tests helping static arrays are used, which have an absolute maximum of size_t.sizeof * 2^20 elements 101 enum allowedArraySize = 1 << size_t.sizeof; //(2 * size_t.sizeof + size_t.sizeof/2); 102 // choosed arbitrary, to avoid seg. faults 103 /** 104 up to 1 << 27 = 1 << (32 - bsf(sizeof(VEBroot!()))) any capacity works for unit testing. 105 */ 106 } 107 108 /** 109 the baseSize defines the cutoff limit, where the node goes into the bit array mode. It is parametrized on the size 110 of size_t and changes dynamically with the architecture used. 111 */ 112 enum baseSize = CHAR_BIT * size_t.sizeof; 113 114 /** 115 the maxSizeBound defines the maximum the tree can be constructed with. It is parametrized on the size of size_t and 116 changes dynamically with the architecture used. 117 */ 118 enum maxSizeBound = size_t(1) << baseSize/2; // == uint.max + 1 on a 64-bit system 119 120 /** 121 The default response of a tree node on a key request is null. I. e. if a key is not contained, null is returned. 122 */ 123 alias Response = Nullable!(size_t, maxSizeBound); 124 125 /// calculating the type, based on native type of the underlying system 126 static if(size_t.sizeof == 16) // future 127 { 128 alias halfSizeT = ulong; 129 } 130 else static if(size_t.sizeof == 8) // 64-bit case 131 { 132 alias halfSizeT = uint; 133 } 134 else static if(size_t.sizeof == 4) // 32-bit case 135 { 136 alias halfSizeT = ushort; 137 } 138 else static if(size_t.sizeof == 2) // 16-bit case 139 { 140 alias halfSizeT = ubyte; 141 } 142 else 143 { 144 static assert(0); 145 } 146 147 /// bit mask representing uint.max. 148 enum size_t lowerMask = halfSizeT.max; 149 /// bit mask representing size_t.max without uint.max. 150 enum size_t higherMask = (size_t.max ^ lowerMask); 151 152 /** 153 This function returns the higher square root of the given input. It is needed in the initialization step 154 of the VEB tree to calculate the number of children of a given layer. And this is the universe size of the 155 summary of a node. The upper square root is defined by 2^{\lceil(\lg u)/2\rceil} 156 */ 157 size_t hSR(size_t value) @nogc nothrow 158 { 159 return size_t(1) << (bsr(value)/2 + ((bsr(value) & 1) || ((value != 0) && (value & (value - 1))))); 160 } 161 /// 162 unittest 163 { 164 auto currentSeed = unpredictableSeed(); 165 static if(vdebug){write("UT: hSR "); writeln("seed: ", currentSeed);} 166 rndGenInUse.seed(currentSeed); //initialize the random generator 167 size_t M = uniform(1U,halfSizeT.max, rndGenInUse); //set universe size to some integer. 168 auto hSR = hSR(M); 169 170 assert((hSR & (hSR - 1)) == 0); 171 if(hSR < halfSizeT.max) assert(hSR >= sqrt(to!float(M))); 172 173 auto check = powersOfTwo.until(hSR).array; 174 assert((check[$-1]) * (check[$-1]) < M); 175 } 176 177 /** 178 This function returns the lower square root of the given input. It is needed by the indexing functions 179 high(x), low(x) and index(x,y) of elements in the tree. Also, this is the universe size of a child of a node. The 180 lower square root is defined by 2^{\lfloor(\lgu)/2\rfloor} 181 */ 182 size_t lSR(size_t value) @nogc nothrow 183 { 184 return size_t(1) << (bsr(value)/2); 185 } 186 /// 187 unittest 188 { 189 auto currentSeed = unpredictableSeed(); 190 static if(vdebug){write("UT: lSR "); writeln("seed: ", currentSeed);} 191 rndGenInUse.seed(currentSeed); //initialize the random generator 192 size_t M = uniform(1U,halfSizeT.max, rndGenInUse); //set universe size to some integer. 193 auto lSR = lSR(M); 194 195 assert((lSR & (lSR - 1)) == 0); 196 assert(lSR * lSR < M); 197 auto check = powersOfTwo.find(lSR); 198 199 if(lSR < halfSizeT.max) assert((check.drop(1).front) > sqrt(to!float(M))); 200 } 201 202 /* 203 This is an index function defined as \lfloor x/lSR(u)\rfloor. It is needed to find the appropriate cluster 204 of a element in the tree. It is a part of the ideal indexing function. 205 */ 206 private size_t high(size_t universe, size_t value) @nogc nothrow 207 in 208 { 209 assert((universe & (universe - 1)) == 0); 210 } 211 do 212 { 213 return value >> (bsr(universe) / 2); 214 } 215 // 216 unittest 217 { 218 auto currentSeed = unpredictableSeed(); 219 static if(vdebug){write("UT: high "); writeln("seed: ", currentSeed);} 220 rndGenInUse.seed(currentSeed); //initialize the random generator 221 size_t M = uniform(1U,halfSizeT.max, rndGenInUse); //set universe size to some integer. 222 size_t U = nextPow2(M); 223 auto x = uniform(0U, U, rndGenInUse); 224 225 assert(high(U, x) == x / lSR(U)); 226 } 227 228 /* 229 This is an index function defined as fmod(value, lSR(universe)). It is needed to find the appropriate 230 value inside a cluster. It is part of the ideal indexing function 231 */ 232 private size_t low(size_t universe, size_t value) @nogc nothrow 233 in 234 { 235 assert((universe & (universe - 1)) == 0); 236 } 237 do 238 { 239 return value & ((size_t(1) << (bsr(universe) / 2)) - 1); 240 } 241 // 242 unittest 243 { 244 auto currentSeed = unpredictableSeed(); 245 static if(vdebug){write("UT: low "); writeln("seed: ", currentSeed);} 246 rndGenInUse.seed(currentSeed); //initialize the random generator 247 size_t M = uniform(1U,halfSizeT.max, rndGenInUse); //set universe size to some integer. 248 size_t U = nextPow2(M); 249 auto x = uniform(0U, U, rndGenInUse); 250 251 assert(low(U, x) == (x & (lSR(U) - 1))); 252 } 253 254 /* 255 This is an index function to retain the searched value. It is defined as x * lSR(u) + y. Beyond this, the 256 relation holds: x = index(high(x), low(x)). This is the ideal indexing function of the tree. 257 */ 258 private size_t index(size_t universe, size_t x, size_t y) @nogc nothrow 259 { 260 return (x * lSR(universe) + y); 261 } 262 // 263 unittest 264 { 265 auto currentSeed = unpredictableSeed(); 266 static if(vdebug){write("UT: index "); writeln("seed: ", currentSeed);} 267 rndGenInUse.seed(currentSeed); //initialize the random generator 268 size_t M = uniform(0U,halfSizeT.max, rndGenInUse); //set universe size to some integer. 269 270 size_t U = nextPow2(M); 271 auto x = uniform(0U, U, rndGenInUse); 272 273 assert(index(U, high(U, x), low(U, x)) == x); 274 } 275 276 /// convenience method for initializing a van emde boas tree root. This is the default method to get a tree. 277 auto vebRoot(size_t universe) 278 in 279 { 280 assert(universe); 281 } 282 do 283 { 284 return VEBroot!()(universe); 285 } 286 /// 287 unittest 288 { 289 auto currentSeed = unpredictableSeed(); 290 static if(vdebug){write("UT: 1. use case "); writeln("seed: ", currentSeed);} 291 rndGenInUse.seed(currentSeed); //initialize the random generator 292 293 size_t M = uniform(2U, baseSize, rndGenInUse); //set universe size to some integer (small). 294 size_t N = uniform(1U, M, rndGenInUse); //set universe size to some integer (small). 295 296 auto vT = vebRoot(M); 297 assert(vT.empty); 298 299 size_t[] testArray = new size_t[N]; 300 M.iota.randomCover(rndGenInUse).take(N) 301 .enumerate 302 .tee!(el => testArray[el.index] = el.value) 303 .each!(el => vT.insert(el.value)); 304 305 assert(vT.front == testArray.sort.front); 306 assert(vT.back == testArray.sort.back); 307 assert(vT().front == testArray.sort.front); 308 assert(vT().back == testArray.sort.back); 309 assert(vT[].front == 0); 310 assert(vT[].back == vT.universe); 311 assert(vT.length == testArray.length); 312 assert(vT() == testArray); 313 assert(vT.capacity == baseSize); 314 assert(vT.universe == M); 315 assert(!vT.empty); 316 testArray.each!(el => assert(el in vT)); 317 size_t counter; 318 for(auto el = vT.front; el != vT.back; el = vT.successor(el.get)) 319 { 320 assert(el.get == testArray.sort[counter]); 321 ++counter; 322 } 323 for(auto el = vT.back; el != vT.front; el = vT.predecessor(el.get)) 324 { 325 assert(el.get == testArray.sort[counter]); 326 --counter; 327 } 328 auto secondElementQ = vT.successor(testArray.sort[0]); 329 if(!secondElementQ.isNull) 330 { 331 assert(testArray.sort.lowerBound(secondElementQ.get).length == 1); 332 } 333 334 auto randomElement = testArray[uniform(0, testArray.length, rndGenInUse)]; 335 assert(!vT.insert(randomElement)); 336 337 auto vTdeepCopy = vT.dup; 338 foreach(el; testArray) 339 { 340 vT.remove(el); 341 } 342 assert(vT.empty); 343 assert(!vT.length); 344 assert(vTdeepCopy.length == testArray.length); 345 346 auto vTdeepCopy2 = vTdeepCopy.dup; 347 348 vTdeepCopy2.remove(testArray[0]); 349 assert(vTdeepCopy2.length + 1 == testArray.length); 350 auto inclusiveSlice = vTdeepCopy[]; 351 if(0 in vTdeepCopy) 352 { 353 assert(inclusiveSlice.length == testArray.length + 1); 354 } 355 else 356 { 357 assert(inclusiveSlice.length == testArray.length + 2); 358 } 359 360 auto exclusiveSlice = vTdeepCopy(); 361 assert(exclusiveSlice.length == vTdeepCopy.length); 362 foreach(el; vTdeepCopy) 363 { 364 assert(el in exclusiveSlice); 365 } 366 foreach(el; exclusiveSlice) 367 { 368 assert(el in vTdeepCopy); 369 } 370 auto shallowCopyFromRoot = vTdeepCopy; 371 static assert(is(typeof(vTdeepCopy) : VEBroot!T, T...)); 372 assert(!vTdeepCopy.empty); 373 assert(vTdeepCopy.length == vTdeepCopy().length); 374 assert(shallowCopyFromRoot == vTdeepCopy().save); 375 376 inclusiveSlice = vTdeepCopy[]; 377 auto shallowCopyFromSlice = inclusiveSlice.save; 378 assert(inclusiveSlice.front == shallowCopyFromSlice.front); 379 inclusiveSlice.popFront; 380 assert(inclusiveSlice.front != shallowCopyFromSlice.front); 381 382 if(0 in vTdeepCopy) 383 { 384 assert(inclusiveSlice.front == vTdeepCopy.successor(0)); 385 } 386 else 387 { 388 assert(inclusiveSlice.front == vTdeepCopy.front); 389 } 390 391 assert(vTdeepCopy() == testArray); 392 auto vTdeepCopy3 = vT.dup; 393 auto vTshallowCopy = vT; 394 assert(shallowCopyFromRoot.front == vTdeepCopy.front); 395 vTdeepCopy.remove(vTdeepCopy.front.get); 396 assert(shallowCopyFromRoot.front == vTdeepCopy.front); 397 398 assert(vTshallowCopy == vT); 399 assert(vTdeepCopy3 == vT); 400 401 assert(vT() == vT); 402 assert(vT == vT()); 403 } 404 /// 405 unittest 406 { 407 auto currentSeed = unpredictableSeed(); 408 static if(vdebug){write("UT: 2. use case "); writeln("seed: ", currentSeed);} 409 rndGenInUse.seed(currentSeed); //initialize the random generator 410 411 size_t M = uniform(baseSize + 1, testedSize, rndGenInUse); //set universe size to some integer (small). 412 size_t N = uniform(1U, min(M, allowedArraySize), rndGenInUse); //set universe size to some integer (small). 413 414 auto vT = vebRoot(M); 415 assert(vT.empty); 416 417 size_t[] testArray = new size_t[N]; 418 419 M.iota.randomCover(rndGenInUse).take(N) 420 .enumerate 421 .tee!(el => testArray[el.index] = el.value) 422 .each!(el => vT.insert(el.value)); 423 424 assert(vT.front == testArray.sort.front); 425 assert(vT.back == testArray.sort.back); 426 assert(vT().front == testArray.sort.front); 427 assert(vT().back == testArray.sort.back); 428 assert(vT[].front == 0); 429 assert(vT[].back == vT.universe); 430 assert(vT.length == testArray.length); 431 assert(vT() == testArray); 432 assert(vT.capacity == M.nextPow2); 433 assert(vT.universe == M); 434 assert(!vT.empty); 435 436 testArray.each!(el => assert(el in vT)); 437 size_t counter; 438 for(auto el = vT.front; el != vT.back; el = vT.successor(el.get)) 439 { 440 assert(el.get == testArray.sort[counter]); 441 ++counter; 442 } 443 for(auto el = vT.back; el != vT.front; el = vT.predecessor(el.get)) 444 { 445 assert(el.get == testArray.sort[counter]); 446 --counter; 447 } 448 449 auto secondElementQ = vT.successor(testArray.sort[0]); 450 if(!secondElementQ.isNull) 451 { 452 assert(testArray.sort.lowerBound(secondElementQ.get).length == 1); 453 } 454 455 auto randomElement = testArray[uniform(0, testArray.length, rndGenInUse)]; 456 assert(!vT.insert(randomElement)); 457 458 auto vTdeepCopy = vT.dup; 459 foreach(el; testArray) 460 { 461 vT.remove(el); 462 } 463 assert(vT.empty); 464 assert(!vT.length); 465 assert(vTdeepCopy.length == testArray.length); 466 467 auto vTdeepCopy2 = vTdeepCopy.dup; 468 469 vTdeepCopy2.remove(testArray[0]); 470 assert(vTdeepCopy2.length + 1 == testArray.length); 471 472 auto inclusiveSlice = vTdeepCopy[]; 473 if(0 in vTdeepCopy) 474 { 475 assert(inclusiveSlice.length == testArray.length + 1); 476 } 477 else 478 { 479 assert(inclusiveSlice.length == testArray.length + 2); 480 } 481 482 auto exclusiveSlice = vTdeepCopy(); 483 assert(exclusiveSlice.length == vTdeepCopy.length); 484 foreach(el; vTdeepCopy) 485 { 486 assert(el in exclusiveSlice); 487 } 488 foreach(el; exclusiveSlice) 489 { 490 assert(el in vTdeepCopy); 491 } 492 493 auto shallowCopyFromRoot = vTdeepCopy; 494 assert(shallowCopyFromRoot == vTdeepCopy().save); 495 inclusiveSlice = vTdeepCopy[]; 496 auto shallowCopyFromSlice = inclusiveSlice.save; 497 assert(inclusiveSlice.front == shallowCopyFromSlice.front); 498 inclusiveSlice.popFront; 499 assert(inclusiveSlice.front != shallowCopyFromSlice.front); 500 501 if(0 in vTdeepCopy) 502 { 503 assert(inclusiveSlice.front == vTdeepCopy.successor(0)); 504 } 505 else 506 { 507 assert(inclusiveSlice.front == vTdeepCopy.front); 508 } 509 510 assert(vTdeepCopy() == testArray); 511 auto vTdeepCopy3 = vT.dup; 512 auto vTshallowCopy = vT; 513 assert(shallowCopyFromRoot.front == vTdeepCopy.front); 514 vTdeepCopy.remove(vTdeepCopy.front.get); 515 assert(shallowCopyFromRoot.front == vTdeepCopy.front); 516 517 assert(vTshallowCopy == vT); 518 assert(vTdeepCopy3 == vT); 519 520 assert(vT() == vT); 521 assert(vT == vT()); 522 } 523 524 /** 525 convenience function to get a van emde boas tree, containing pointers to data of type T 526 */ 527 auto vebRoot(T)(size_t universe) 528 in 529 { 530 assert(universe); 531 } 532 do 533 { 534 return VEBroot!T(universe); 535 } 536 /// 537 unittest 538 { 539 auto vr = vebRoot!size_t(100); 540 assert(vr.empty); 541 542 size_t input = 42; 543 544 vr.insert(3, input); 545 assert(vr.front == 3); 546 assert(*vr[3] == 42); 547 548 size_t input2 = 73; 549 vr.insert(3, input2); 550 assert(*vr[3] == 42); 551 *vr[3] = 73; 552 assert(*vr[3] == 73); 553 554 assert(vr[8] is null); 555 vr[15] = input2; 556 assert(vr[15] !is null); 557 vr.remove(15); 558 assert(vr[15] is null); 559 } 560 /// 561 unittest 562 { 563 auto currentSeed = unpredictableSeed(); 564 static if(vdebug){write("UT: 3. use case "); writeln("seed: ", currentSeed);} 565 rndGenInUse.seed(currentSeed); //initialize the random generator 566 567 size_t M = uniform(2U, baseSize, rndGenInUse); //set universe size to some integer (small). 568 size_t N = uniform(1U, M, rndGenInUse); //set universe size to some integer (small). 569 570 auto vT = vebRoot!size_t(M); 571 assert(vT.empty); 572 573 size_t[] testArray = new size_t[N]; 574 size_t[] testValArray = new size_t[N]; 575 testValArray.each!((ref el) => el = uniform(0UL, size_t.max, rndGenInUse)); 576 577 M.iota.randomCover(rndGenInUse).take(N) 578 .enumerate 579 .tee!(el => testArray[el.index] = el.value) 580 .each!(el => vT.insert(el.value, testValArray[el.index])); 581 582 assert(vT.front == testArray.dup.sort.front); 583 584 assert(vT.length == testValArray.length); 585 vT.each!((key, value) => assert(testValArray.canFind(value))); 586 assert(*vT[vT.back] == testValArray[testArray.maxIndex]); 587 assert(vT().front == testArray.sort.front); 588 assert(vT().back == testArray.sort.back); 589 assert(vT[].front == 0); 590 assert(vT[].back == vT.universe); 591 assert(vT.length == testArray.length); 592 assert(vT() == testArray); 593 assert(vT.capacity == baseSize); 594 assert(vT.universe == M); 595 assert(!vT.empty); 596 testArray.each!(el => assert(el in vT)); 597 size_t counter; 598 for(auto el = vT.front; el != vT.back; el = vT.successor(el.get)) 599 { 600 assert(el.get == testArray.sort[counter]); 601 ++counter; 602 } 603 for(auto el = vT.back; el != vT.front; el = vT.predecessor(el.get)) 604 { 605 assert(el.get == testArray.sort[counter]); 606 --counter; 607 } 608 auto secondElementQ = vT.successor(testArray.sort[0]); 609 if(!secondElementQ.isNull) 610 { 611 assert(testArray.sort.lowerBound(secondElementQ.get).length == 1); 612 } 613 auto randomElement = testArray[uniform(0, testArray.length, rndGenInUse)]; 614 assert(!vT.insert(randomElement)); 615 616 auto vTdeepCopy = vT.dup; 617 foreach(el; testArray) 618 { 619 vT.remove(el); 620 } 621 assert(vT.empty); 622 assert(!vT.length); 623 assert(vTdeepCopy.length == testArray.length); 624 auto vTdeepCopy2 = vTdeepCopy.dup; 625 626 vTdeepCopy2.remove(testArray[0]); 627 assert(vTdeepCopy2.length + 1== testArray.length); 628 629 auto inclusiveSlice = vTdeepCopy[]; 630 if(0 in vTdeepCopy) 631 { 632 assert(inclusiveSlice.length == testArray.length + 1); 633 } 634 else 635 { 636 assert(inclusiveSlice.length == testArray.length + 2); 637 } 638 auto exclusiveSlice = vTdeepCopy(); 639 assert(exclusiveSlice.length == vTdeepCopy.length); 640 foreach(el; vTdeepCopy) 641 { 642 assert(el in exclusiveSlice); 643 } 644 foreach(el; exclusiveSlice) 645 { 646 assert(el in vTdeepCopy); 647 } 648 auto shallowCopyFromRoot = vTdeepCopy; 649 static assert(is(typeof(vTdeepCopy) : VEBroot!T, T...)); 650 assert(!vTdeepCopy.empty); 651 assert(vTdeepCopy.length == vTdeepCopy().length); 652 assert(shallowCopyFromRoot == vTdeepCopy().save); 653 654 inclusiveSlice = vTdeepCopy[]; 655 auto shallowCopyFromSlice = inclusiveSlice.save; 656 assert(inclusiveSlice.front == shallowCopyFromSlice.front); 657 inclusiveSlice.popFront; 658 assert(inclusiveSlice.front != shallowCopyFromSlice.front); 659 660 if(0 in vTdeepCopy) 661 { 662 assert(inclusiveSlice.front == vTdeepCopy.successor(0)); 663 } 664 else 665 { 666 assert(inclusiveSlice.front == vTdeepCopy.front); 667 } 668 669 assert(vTdeepCopy() == testArray); 670 auto vTdeepCopy3 = vT.dup; 671 auto vTshallowCopy = vT; 672 assert(shallowCopyFromRoot.front == vTdeepCopy.front); 673 vTdeepCopy.remove(vTdeepCopy.front.get); 674 assert(shallowCopyFromRoot.front == vTdeepCopy.front); 675 676 assert(vTshallowCopy == vT); 677 assert(vTdeepCopy3 == vT); 678 679 assert(vT() == vT); 680 assert(vT == vT()); 681 } 682 /// 683 unittest 684 { 685 auto currentSeed = unpredictableSeed(); 686 static if(vdebug){write("UT: 4. use case "); writeln("seed: ", currentSeed);} 687 rndGenInUse.seed(currentSeed); //initialize the random generator 688 689 size_t M = uniform(baseSize + 1, testedSize, rndGenInUse); //set universe size to some integer (small). 690 size_t N = uniform(1U, min(M, allowedArraySize), rndGenInUse); //set universe size to some integer (small). 691 692 auto vT = vebRoot!size_t(M); 693 assert(vT.empty); 694 695 size_t[] testArray = new size_t[N]; 696 size_t[] testValArray = new size_t[N]; 697 testValArray.each!((ref el) => el = uniform(0UL, size_t.max, rndGenInUse)); 698 699 M.iota.randomCover(rndGenInUse).take(N) 700 .enumerate 701 .tee!(el => testArray[el.index] = el.value) 702 .each!(el => vT.insert(el.value, testValArray[el.index])); 703 704 assert(vT.front == testArray.dup.sort.front); 705 706 assert(vT.length == testValArray.length); 707 assert(!vT.front.isNull); 708 assert(vT[vT.front.get] !is null); 709 vT.each!((key, ref value) => assert(testValArray.canFind(value))); 710 711 assert(*vT[vT.back] == testValArray[testArray.maxIndex]); 712 assert(vT().front == testArray.sort.front); 713 assert(vT().back == testArray.sort.back); 714 assert(vT[].front == 0); 715 assert(vT[].back == vT.universe); 716 assert(vT.length == testArray.length); 717 assert(vT() == testArray); 718 assert(vT.capacity == M.nextPow2); 719 assert(vT.universe == M); 720 assert(!vT.empty); 721 722 testArray.each!(el => assert(el in vT)); 723 size_t counter; 724 for(auto el = vT.front; el != vT.back; el = vT.successor(el.get)) 725 { 726 assert(el.get == testArray.sort[counter]); 727 ++counter; 728 } 729 for(auto el = vT.back; el != vT.front; el = vT.predecessor(el.get)) 730 { 731 assert(el.get == testArray.sort[counter]); 732 --counter; 733 } 734 auto secondElementQ = vT.successor(testArray.sort[0]); 735 if(!secondElementQ.isNull) 736 { 737 assert(testArray.sort.lowerBound(secondElementQ.get).length == 1); 738 } 739 auto randomElement = testArray[uniform(0, testArray.length, rndGenInUse)]; 740 assert(!vT.insert(randomElement)); 741 742 auto vTdeepCopy = vT.dup; 743 foreach(el; testArray) 744 { 745 vT.remove(el); 746 } 747 assert(vT.empty); 748 assert(!vT.length); 749 assert(vTdeepCopy.length == testArray.length); 750 auto vTdeepCopy2 = vTdeepCopy.dup; 751 752 vTdeepCopy2.remove(testArray[0]); 753 assert(vTdeepCopy2.length + 1 == testArray.length); 754 755 auto inclusiveSlice = vTdeepCopy[]; 756 if(0 in vTdeepCopy) 757 { 758 assert(inclusiveSlice.length == testArray.length + 1); 759 } 760 else 761 { 762 assert(inclusiveSlice.length == testArray.length + 2); 763 } 764 auto exclusiveSlice = vTdeepCopy(); 765 assert(exclusiveSlice.length == vTdeepCopy.length); 766 foreach(el; vTdeepCopy) 767 { 768 assert(el in exclusiveSlice); 769 } 770 foreach(el; exclusiveSlice) 771 { 772 assert(el in vTdeepCopy); 773 } 774 auto shallowCopyFromRoot = vTdeepCopy; 775 static assert(is(typeof(vTdeepCopy) : VEBroot!T, T...)); 776 assert(!vTdeepCopy.empty); 777 assert(vTdeepCopy.length == vTdeepCopy().length); 778 assert(shallowCopyFromRoot == vTdeepCopy().save); 779 780 inclusiveSlice = vTdeepCopy[]; 781 auto shallowCopyFromSlice = inclusiveSlice.save; 782 assert(inclusiveSlice.front == shallowCopyFromSlice.front); 783 inclusiveSlice.popFront; 784 assert(inclusiveSlice.front != shallowCopyFromSlice.front); 785 786 if(0 in vTdeepCopy) 787 { 788 assert(inclusiveSlice.front == vTdeepCopy.successor(0)); 789 } 790 else 791 { 792 assert(inclusiveSlice.front == vTdeepCopy.front); 793 } 794 795 assert(vTdeepCopy() == testArray); 796 auto vTdeepCopy3 = vT.dup; 797 auto vTshallowCopy = vT; 798 assert(shallowCopyFromRoot.front == vTdeepCopy.front); 799 vTdeepCopy.remove(vTdeepCopy.front.get); 800 assert(shallowCopyFromRoot.front == vTdeepCopy.front); 801 802 assert(vTshallowCopy == vT); 803 assert(vTdeepCopy3 == vT); 804 805 assert(vT() == vT); 806 assert(vT == vT()); 807 } 808 809 // 810 unittest 811 { 812 auto currentSeed = unpredictableSeed(); // 83_843; 898_797_859; 813 static if(vdebug){write("UT: vN, opBinaryIn "); writeln("seed: ", currentSeed);} 814 rndGenInUse.seed(currentSeed); //initialize the random generator 815 816 auto value = uniform(0U, size_t.max, rndGenInUse); 817 auto bitNum = uniform(0U, baseSize, rndGenInUse); 818 auto vN = vebRoot(baseSize); 819 *vN.val = value; 820 821 if((*vN.val & size_t(1) << bitNum) != 0 ) 822 { 823 assert(bitNum in vN); 824 } 825 826 if((*vN.val & size_t(1) << bitNum) == 0 ) 827 { 828 assert(!(bitNum in vN)); 829 } 830 } 831 // 832 unittest 833 { 834 auto currentSeed = unpredictableSeed(); 835 static if(vdebug){write("UT: vN, predecessor "); writeln("seed: ", currentSeed);} 836 rndGenInUse.seed(currentSeed); //initialize the random generator 837 auto v = uniform(2U, testedSize, rndGenInUse); //set universe size to some integer. 838 auto x = uniform(1U, baseSize, rndGenInUse); 839 auto vN = vebRoot(baseSize); 840 *vN.val = v; 841 842 bool found; 843 844 for(size_t index = x - 1; index >= 0; --index) 845 { 846 if (v & (size_t(1) << index)) 847 { 848 found = true; 849 assert(!vN.empty); 850 assert(vN.predecessor(x) == index); 851 break; 852 } 853 if(!index) break; 854 } 855 856 if(!found) assert(vN.predecessor(x).isNull); 857 } 858 // 859 unittest 860 { 861 auto currentSeed = unpredictableSeed(); 862 static if(vdebug){write("UT: vN, successor "); writeln("seed: ", currentSeed);} 863 rndGenInUse.seed(currentSeed); //initialize the random generator 864 auto v = uniform(0U, size_t.max, rndGenInUse); //set universe size to some integer. 865 auto x = uniform(0U, baseSize, rndGenInUse); 866 auto vN = vebRoot(baseSize); 867 *vN.val = v; 868 bool found; 869 870 for (size_t index = x + 1; index < baseSize; ++index) 871 { 872 if (v & (size_t(1) << index)) 873 { 874 found = true; 875 assert(vN.successor(x).get == index); 876 break; 877 } 878 } 879 if(!found) assert(vN.successor(x).isNull); 880 } 881 882 /** 883 This is the struct to represent a VEB tree node. Its members are 884 - a pointer to the stats: universe and current inserted element amount 885 - a pointer to the min and max values. These pointee is used as a bit array in the leaf nodes. 886 - a poitner (or array) to the child nodes, in case the node is not a leaf node 887 - a pointer (an array) to the data pointers, in case the tree is used with data. 888 Dependent from the universe size passed in a method the stored value will be interpretated in two different ways: 889 If the parameter passed shows, that the universe size is below the bit size of the stored value, then, it can be 890 handled as a bit array and all operations decay to operations defined in core.bitop. This case correspond to 891 the state of the node being a leaf. No children exist and the pointer should stay uninitialized 892 Otherwise, the value is interpretated as two values, the minimum and maximum stored at the same place in memory. The 893 minimum and maximum shows, which range is achievable through this node. The parameters passed to a function of the 894 node have to be well chosen, to hit the appropriate child. 895 The first element of the children array, if present is handled different. According to literature, it has the role 896 of the summary of the remaining children cluster. With it help it is possible to achieve a very small recursion 897 level during an access. 898 */ 899 struct VEBroot(T = void) 900 { 901 /** 902 yields the next power of two, based un universe size 903 */ 904 @property size_t capacity() 905 in 906 { 907 assert(stats !is null); 908 } 909 do 910 { 911 if(universe <= baseSize) 912 { 913 return baseSize; 914 } 915 else 916 { 917 return universe.nextPow2; 918 } 919 } 920 921 /** 922 yields the universe size of a node. The root has the unvierse size, defined on tree creation 923 */ 924 @property size_t universe() const 925 in 926 { 927 assert(stats !is null); 928 } 929 do 930 { 931 return (*stats & higherMask) >> (size_t.sizeof * CHAR_BIT/2); 932 } 933 934 /** 935 yields the current inserted elements under the node, including the two elements of the node itself. 936 */ 937 @property size_t length() 938 in 939 { 940 assert(stats !is null); 941 } 942 do 943 { 944 return *stats & lowerMask; 945 } 946 947 /** 948 the opApply method grants the correct foreach behavior 949 */ 950 int opApply(scope int delegate(ref size_t) /*@nogc*/ operations) //@nogc 951 { 952 int result; 953 954 for(auto leading = front; !leading.isNull; leading = successor(leading.get)) 955 { 956 result = operations(leading.get); 957 958 if(result) 959 { 960 break; 961 } 962 } 963 964 return result; 965 } 966 967 static if(!is(T == void)) 968 { 969 /* 970 TODO: as a further optimization, the accessing functions front, back, successor, predecessor 971 could be designed as templates, returning a reference to the stored value as a ref/out parameter. 972 This seems to be somewhat strange, as it would be unsure, whether the init comes from the defaultness of the 973 param or from the fact, that the default value is stored by chance in the tree. 974 In the form it is now, two calls (with constant time) are needed: first to get the key, next to get the value. 975 */ 976 /** 977 opApply method in case of present source for iterating over key value pairs 978 */ 979 int opApply(scope int delegate(ref size_t, ref T) /*@nogc*/ operations) //@nogc 980 { 981 int result; 982 983 for(auto leading = front; !leading.isNull; leading = successor(leading.get)) 984 { 985 assert(this[leading.get] !is null); 986 result = operations(leading.get, *(this[leading.get])); 987 988 if(result) 989 { 990 break; 991 } 992 } 993 994 return result; 995 } 996 } 997 998 /** 999 method returning either the lower part of the stored value (intermediate node) or the lowest bit set (bit vector 1000 mode. If the node does not contain any value (min > max or value == 0) Nullable.null is returned. 1001 */ 1002 @property Response front() @nogc nothrow 1003 { 1004 // define the result as a nullable 1005 typeof(return) retVal; 1006 /* 1007 we have only a chance to get a value, if a value is present. 1008 if it is a leaf, handle the val as a bit array and find the first bit set from the right. 1009 if it is not a leaf, get the minimum. 1010 */ 1011 if(!empty) 1012 { 1013 if(isLeaf) 1014 { 1015 retVal = bsf(*val); 1016 } 1017 else 1018 { 1019 retVal = *val & lowerMask; 1020 } 1021 } 1022 // return the result, even if it was not set to a value. 1023 return retVal; 1024 } 1025 1026 1027 /** 1028 method returning either the higher part of the stored value (intermediate node) or the highest bit set (bit 1029 vector mode. If the node does not contain any value (min > max or value == 0) Nullable.null is returned. 1030 */ 1031 @property Response back() // @nogc nothrow 1032 { 1033 // define the result as a nullable 1034 typeof(return) retVal; 1035 /* 1036 we have only a chance to get a value, if a value is present. 1037 if it is a leaf, handle the val as a bit array and find the first bit set from the left. 1038 if it is not a leaf, get the max. 1039 */ 1040 if(!empty) 1041 { 1042 if(isLeaf) 1043 { 1044 retVal = bsr(*val); 1045 } 1046 else 1047 { 1048 retVal = (*val & higherMask) >> (size_t.sizeof * CHAR_BIT/2); 1049 } 1050 } 1051 // return the result, even if it was not set to a value. 1052 return retVal; 1053 } 1054 1055 /** 1056 yields a deep copy of the node. I. e. copies all data in children and allocates another tree 1057 */ 1058 typeof(this) dup() 1059 { 1060 auto copy = this; 1061 copy.stats = new size_t(); 1062 copy.val = new size_t(); 1063 *copy.stats = *this.stats; 1064 *copy.val = *this.val; 1065 if(isLeaf) 1066 { 1067 static if(!is(T == void)) 1068 { 1069 copy.dataArr = this.dataArr[0 .. baseSize].dup.ptr; 1070 } 1071 } 1072 else 1073 { 1074 1075 static if(!is(T == void)) 1076 { 1077 copy.ptrArr = this.ptrArr[0 .. hSR(universe.nextPow2) + 1].dup.ptr; 1078 copy.dataArr = this.dataArr[0 .. 2].dup.ptr; 1079 } 1080 else 1081 { 1082 copy.ptrArr = this.ptrArr[0 .. hSR(universe.nextPow2) + 1].dup; 1083 } 1084 1085 copy.ptrArr[0 .. hSR(universe.nextPow2) + 1].each!((ref n) => n = n.dup); 1086 } 1087 1088 return copy; 1089 } 1090 1091 static if(!is(T == void)) 1092 { 1093 /** 1094 method exists only, when in data mode. Then, yields a pointer to the data, associated with the key. If no data 1095 is associated or the key is not in the tree, yields null. 1096 */ 1097 auto ref opIndex(size_t key) @nogc 1098 { 1099 assert(universe); 1100 if(key > universe.nextPow2) 1101 { 1102 return null; 1103 } 1104 if(isLeaf) 1105 { 1106 assert(key < baseSize); 1107 return dataArr[key]; 1108 } 1109 else 1110 { 1111 if(empty) 1112 { 1113 // if an empty intermediate node is found, nothing is stored below it. 1114 return null; 1115 } 1116 // case of a single valued range. 1117 if(key == front) 1118 { 1119 return dataArr[0]; 1120 } 1121 1122 if(key == back) 1123 { 1124 return dataArr[1]; 1125 } 1126 1127 /* 1128 else we have to descend, using the recursive indexing: 1129 1. take the high(value, uS)-th child and 1130 2. ask it about the reduced low(value, uS) value 1131 3. use the lSR(uS) universe size of the childe node. 1132 */ 1133 1134 assert(cluster[high(key)].universe == lSR(universe.nextPow2)); 1135 return cluster[high(key)][low(key)]; 1136 } 1137 } 1138 1139 /** 1140 operator is used for re assigning data, if the key already exists. 1141 */ 1142 void opIndexAssign(ref T value, size_t key) 1143 { 1144 insert(key, value); 1145 } 1146 } 1147 1148 /** 1149 []-slicing. Yields a "random access range" with the content of the tree, always containing zero and universe as keys 1150 */ 1151 auto opIndex() 1152 { 1153 return VEBtree!(Yes.inclusive, typeof(this))(this); 1154 } 1155 1156 /** 1157 ()-slicing. Yields a "random access range" with the content of the tree. Keys can be isNull. 1158 */ 1159 auto opCall() 1160 { 1161 return VEBtree!(No.inclusive, typeof(this))(this); 1162 } 1163 1164 /** 1165 method to check whether the current node holds a value 1166 */ 1167 @property bool empty() @nogc nothrow 1168 in 1169 { 1170 assert(val !is null); 1171 } 1172 do 1173 { 1174 if(isLeaf) 1175 { 1176 return *val == 0; 1177 } 1178 else 1179 { 1180 return (*val & lowerMask) > ((*val & higherMask) >> (size_t.sizeof * CHAR_BIT/2)); 1181 } 1182 } 1183 1184 /** 1185 member method for the case universe size < base size. Overloads by passing only one parameter, which is 1186 the bit number of interest. Returns whether the appropriate bit inside the bitvector is set. 1187 */ 1188 bool opBinaryRight(string op)(size_t key) if(op == "in") // @nogc nothrow 1189 { 1190 assert(universe); 1191 if(key > universe.nextPow2) 1192 { 1193 return false; 1194 } 1195 if(isLeaf) 1196 { 1197 assert(key < baseSize); 1198 return bt(val, key) != 0; 1199 } 1200 else 1201 { 1202 if(empty) 1203 { 1204 // if an empty intermediate node is found, nothing is stored below it. 1205 return false; 1206 } 1207 // case of a single valued range. 1208 if(key == front || key == back) 1209 { 1210 return true; 1211 } 1212 1213 /* 1214 else we have to descend, using the recursive indexing: 1215 1. take the high(value, uS)-th child and 1216 2. ask it about the reduced low(value, uS) value 1217 3. use the lSR(uS) universe size of the childe node. 1218 */ 1219 1220 assert(cluster[high(key)].universe == lSR(universe.nextPow2)); 1221 return low(key) in cluster[high(key)]; 1222 } 1223 } 1224 1225 alias put = insert; 1226 /** 1227 insert method. this method is called from class with a universe size given. It performs recursion calls untill 1228 the universe size is reduced to the base size. Then the overloaded insert method is called. 1229 */ 1230 bool insert(T...)(size_t key, ref T value) 1231 if((is(T == void) && T.length == 0) || (!is(T == void) && T.length < 2))// @nogc nothrow 1232 { 1233 debug 1234 { 1235 static if(T.length) 1236 { 1237 bool insertingNewVal = this[key] is null ? true : false; 1238 } 1239 } 1240 typeof(return) res; 1241 scope(exit) 1242 { 1243 length = length + res; 1244 debug 1245 { 1246 static if(T.length) 1247 { 1248 //writeln("value[0]: ") 1249 assert(this[key] !is null); 1250 if(insertingNewVal) 1251 { 1252 assert(*this[key] == value[0]); 1253 } 1254 } 1255 } 1256 } 1257 1258 if(key > capacity) 1259 { 1260 res = false; 1261 return res; 1262 } 1263 1264 // if descended so far, do not use other functionality any more. 1265 if(isLeaf) 1266 { 1267 assert(val !is null); 1268 res = bts(val, key) == 0; 1269 static if(T.length) 1270 { 1271 if(res) 1272 { 1273 dataArr[key] = &value[0]; 1274 } 1275 } 1276 return res; 1277 } 1278 1279 if(empty) // if the current node does not contain anything put the value inside. 1280 { 1281 front(key, value); // the setters of min handle the value appropriately and do not need the universe size 1282 back(key, value); // being explicitely provided, as they can check the isLeaf property. 1283 assert(!empty); 1284 res = true; 1285 return res; 1286 } 1287 1288 assert(!empty); 1289 assert(!front.isNull); 1290 assert(!back.isNull); 1291 1292 if(key == front || key == back) 1293 { 1294 res = false; // return, if value is already here. 1295 return res; 1296 } 1297 1298 if(front == back) // if the node contains a single value only, expand the node to a range and leave. 1299 { 1300 if(front > key) 1301 { 1302 front(key, value); 1303 } 1304 if(back < key) 1305 { 1306 back(key, value); 1307 } 1308 1309 res = true; 1310 return res; 1311 } 1312 /* 1313 if none of the cases above was true (all of them are break conditions) we have to compare the given value 1314 with the values present and adapt the range limits. This replaces the value we want to insert. 1315 */ 1316 // a swap can not be used here, as min is itself a (property) method 1317 if(key < front) 1318 { 1319 auto tmpKey = key; 1320 1321 static if(T.length) 1322 { 1323 auto tmpVal = &value[0]; 1324 } 1325 1326 key = front.get; 1327 1328 static if(T.length) 1329 { 1330 value[0] = *this[front.get]; 1331 } 1332 1333 static if(T.length) 1334 { 1335 front(tmpKey, *tmpVal); 1336 } 1337 else 1338 { 1339 front(tmpKey); 1340 } 1341 1342 } 1343 // a swap can not be used here, as max is itself a (property) method 1344 if(key > back) 1345 { 1346 auto tmpKey = key; 1347 1348 static if(T.length) 1349 { 1350 auto tmpVal = &value[0]; 1351 } 1352 1353 key = back.get; 1354 1355 static if(T.length) 1356 { 1357 value[0] = *this[back.get]; 1358 } 1359 1360 static if(T.length) 1361 { 1362 back(tmpKey, *tmpVal); 1363 } 1364 else 1365 { 1366 back(tmpKey); 1367 } 1368 } 1369 1370 // calculate the index of the children cluster by high(value, uS) we want to descent to. 1371 auto nextTreeIndex = high(key); 1372 1373 // if the child is happened to be null we have to update the summary and insert value of high(value, uS) into it 1374 assert(summary.universe == hSR(universe.nextPow2)); 1375 1376 if(cluster[nextTreeIndex].empty) 1377 { 1378 summary.insert(high(key), value); 1379 } 1380 1381 // in any case we pass the lowered value low(value, uS) to the child. 1382 assert(cluster[nextTreeIndex].universe == lSR(universe.nextPow2)); 1383 res = cluster[nextTreeIndex].insert(low(key), value); 1384 1385 return res; 1386 } 1387 1388 /** 1389 remove method. this method is called from class with a universe size given. It performs recursion calls untill 1390 the universe size is reduced to the base size. Then the overloaded remove method is called. 1391 */ 1392 auto remove(size_t key) // @nogc nothrow 1393 { 1394 bool res; 1395 static if(!is(T == void)) 1396 { 1397 T* value; 1398 } 1399 1400 scope(exit) 1401 { 1402 length = length - res; 1403 } 1404 // if descended so far, do not use other functionality any more. 1405 if(isLeaf) 1406 { 1407 res = btr(val, key) != 0; 1408 static if(!is(T == void)) 1409 { 1410 if(res) 1411 { 1412 value = dataArr[key]; 1413 dataArr[key] = null; 1414 } 1415 } 1416 1417 static if(is(T == void)) 1418 { 1419 return res; 1420 } 1421 else 1422 { 1423 return value; 1424 } 1425 } 1426 1427 if(empty) 1428 { 1429 // if the current node is null, there is nothing to remove. 1430 res = false; 1431 static if(is(T == void)) 1432 { 1433 return res; 1434 } 1435 else 1436 { 1437 return value; 1438 } 1439 } 1440 1441 if(front == back) // if the current node contains only a single value 1442 { 1443 if(front != key) 1444 { 1445 // do nothing if the given value is not the stored one 1446 res = false; 1447 1448 static if(is(T == void)) 1449 { 1450 return res; 1451 } 1452 else 1453 { 1454 return value; 1455 } 1456 } 1457 1458 // set this node to the sentinel-null if it does. 1459 static if(!is(T == void)) 1460 { 1461 value = this.nullify; 1462 } 1463 else 1464 { 1465 this.nullify; 1466 } 1467 1468 res = true; 1469 1470 static if(is(T == void)) 1471 { 1472 return res; 1473 } 1474 else 1475 { 1476 return value; 1477 } 1478 } 1479 1480 if(key == front) // if we met the minimum of a node 1481 { 1482 auto treeOffset = summary.front; // calculate an offset from the summary to continue with 1483 if(treeOffset.isNull) // if the offset is invalid, then there is no further hierarchy and we are going to 1484 { 1485 front = back; // store a single value in this node. 1486 res = true; 1487 1488 static if(is(T == void)) 1489 { 1490 return res; 1491 } 1492 else 1493 { 1494 value = dataArr[0]; 1495 dataArr[0] = dataArr[1]; 1496 return value; 1497 } 1498 } 1499 auto min = cluster[treeOffset.get].front; // otherwise we get the minimum from the offset child 1500 1501 assert(cluster[treeOffset].universe == lSR(universe.nextPow2)); 1502 1503 // remove it from the child 1504 static if(is(T == void)) 1505 { 1506 cluster[treeOffset.get].remove(min); 1507 } 1508 else 1509 { 1510 auto minVal = cluster[treeOffset.get].remove(min); 1511 } 1512 1513 // if it happens to become null during the remove process, we also remove the offset entry from the summary 1514 assert(summary.universe == hSR(universe.nextPow2)); 1515 if(cluster[treeOffset.get].empty) 1516 { 1517 summary.remove(treeOffset.get); 1518 } 1519 1520 //anyway, the new min of the current node become the restored value of the calculated offset. 1521 static if(is(T == void)) 1522 { 1523 front(index(treeOffset.get, min)); 1524 } 1525 else 1526 { 1527 value = dataArr[0]; 1528 front(index(treeOffset.get, min), *minVal); 1529 } 1530 1531 res = true; 1532 static if(is(T == void)) 1533 { 1534 return res; 1535 } 1536 else 1537 { 1538 return value; 1539 } 1540 1541 } 1542 1543 // if we met the maximum of a node 1544 if(key == back) 1545 { 1546 // calculate an offset from the summary to contiue with 1547 auto treeOffset = summary.back; 1548 // if the offset is invalid, then there is no further hierarchy and we are going to 1549 if(treeOffset.isNull) 1550 { 1551 // store a single value in this node. 1552 back = front; 1553 res = true; 1554 static if(is(T == void)) 1555 { 1556 return res; 1557 } 1558 else 1559 { 1560 value = dataArr[1]; 1561 dataArr[1] = dataArr[0]; 1562 return value; 1563 } 1564 } 1565 1566 // otherwise we get maximum from the offset child 1567 auto max = cluster[treeOffset.get].back; 1568 assert(cluster[treeOffset.get].universe == lSR(universe.nextPow2)); 1569 1570 // remove it from the child 1571 static if(is(T == void)) 1572 { 1573 cluster[treeOffset.get].remove(max); 1574 } 1575 else 1576 { 1577 auto maxValue = cluster[treeOffset.get].remove(max); 1578 } 1579 1580 1581 // if it happens to become null during the remove process, we also remove the offset enty from the summary 1582 assert(summary.universe == hSR(universe.nextPow2)); 1583 if(cluster[treeOffset.get].empty) summary.remove(treeOffset.get); 1584 1585 // anyway, the new max of the current node become the restored value of the calculated offset. 1586 static if(is(T == void)) 1587 { 1588 back(index(treeOffset.get, max)); 1589 } 1590 else 1591 { 1592 value = dataArr[1]; 1593 back(index(treeOffset.get, max), *maxValue); 1594 } 1595 1596 res = true; 1597 static if(is(T == void)) 1598 { 1599 return res; 1600 } 1601 else 1602 { 1603 return value; 1604 } 1605 1606 } 1607 1608 // if no condition was met we have to descend deeper. We get the offset by reducing the value to high(value, uS) 1609 auto treeOffset = high(key); 1610 // and remove low(value, uS) from the offset child. 1611 assert(cluster[treeOffset].universe == lSR(universe.nextPow2)); 1612 1613 static if(is(T == void)) 1614 { 1615 res = cluster[treeOffset].remove(low(key)); 1616 } 1617 else 1618 { 1619 auto prelength = cluster[treeOffset].length; 1620 value = cluster[treeOffset].remove(low(key)); 1621 } 1622 1623 // if the cluster become null during the remove process we have to update the summary node. 1624 assert(summary.universe == hSR(universe.nextPow2)); 1625 if(cluster[treeOffset].empty) 1626 { 1627 summary.remove(treeOffset); 1628 } 1629 1630 static if(is(T == void)) 1631 { 1632 return res; 1633 } 1634 else 1635 { 1636 res = prelength > cluster[treeOffset].length; 1637 return value; 1638 } 1639 } 1640 1641 /** 1642 predecessor method. this method is called from class with a universe size given. It performs recursion calls 1643 until the universe size is reduced to the base size. Then the overloaded predecessor method is called. 1644 */ 1645 Response predecessor(size_t value) // @nogc nothrow 1646 { 1647 typeof(return) retVal; 1648 1649 // if descended so far, do not use other functionality any more. 1650 if(isLeaf) 1651 { 1652 if(!empty && (value != 0)) 1653 { 1654 /* 1655 create a mask, which hides all higher bits of the stored value down to the given bit number, then apply 1656 bit search from the highest bit. 1657 */ 1658 auto maskedVal = *val & ((size_t(1) << value) - 1); 1659 if(maskedVal != 0) 1660 { 1661 retVal = bsr(maskedVal); 1662 } 1663 } 1664 return retVal; 1665 } 1666 // if this node is empty, no predecessor can be found here or deeper in the tree 1667 if(empty) 1668 { 1669 return retVal; 1670 } 1671 // if given value is greater then the stored max, the predecessor is max 1672 if(value > back) 1673 { 1674 return back; 1675 } 1676 // if given value is less then the min, no predecessor exists. 1677 if(value <= front) 1678 { 1679 return retVal; 1680 } 1681 /* 1682 if none of the break conditions was met we have to descend further into the tree. 1683 */ 1684 auto childIndex = high(value); // calculate the child index by high(value, uS) 1685 auto minlow = cluster[childIndex].front; // look into the child for its minimum 1686 // if the minimum exists and the lowered given value is greater then the child's minimum 1687 if(!minlow.isNull && low(value) > minlow) 1688 { 1689 // calculate an offset to continue with by asking the child on predecessor of the lowered value. 1690 assert(cluster[childIndex].universe == lSR(universe.nextPow2)); 1691 auto offset = cluster[childIndex].predecessor(low(value)); 1692 // the result is given by reconstruction of the answer. 1693 retVal = index(childIndex, offset); 1694 } 1695 else // otherwise we can not use the minimum of the child 1696 { 1697 // ask the summary for the predecessor cluster. 1698 assert(summary.universe == hSR(universe.nextPow2)); 1699 auto predcluster = summary.predecessor(childIndex); 1700 // if the predecessor cluster is null return the current min, as this is the last remaining value 1701 if(predcluster.isNull) return front; 1702 // if the predecessor cluster exists, the offset is given by its maximum 1703 // and the result by the reconstruction of the offset. 1704 retVal = index(predcluster, cluster[predcluster].back); 1705 } 1706 return retVal; 1707 } 1708 1709 /** 1710 successor method. this method is called from class with a universe size given. It performs recursion calls until 1711 the universe size is reduced to the base size. Then the overloaded successor method is called. 1712 */ 1713 Response successor(size_t value) //@nogc nothrow 1714 { 1715 // if descended so far, do not use other functionality any more. 1716 typeof(return) retVal; 1717 if(isLeaf) 1718 { 1719 if(!empty && (value + 1 < baseSize)) 1720 { 1721 // create a mask, which hides all lower bits of the stored value up to the given bit number, then apply 1722 // bit search from the lowest bit. 1723 auto maskedVal = *val & ~((size_t(1) << (value + 1)) - 1); 1724 if(maskedVal != 0) retVal = bsf(maskedVal); 1725 } 1726 return retVal; 1727 } 1728 if(empty) return retVal; // if this node is empty, no successor can be found here or deeper in the tree 1729 if(value < front) return front; // if given value is less then the min, return the min as successor 1730 if(value >= back) return retVal; // if given value is greater then the max, no predecessor exists 1731 1732 /* 1733 if none of the break conditions was met, we have to descent further into the tree. 1734 */ 1735 auto childIndex = high(value); // calculate the child index by high(value, uS) 1736 auto maxlow = cluster[childIndex].back; // look into the child for its maximum 1737 // if the maximum exists and the lowered given value is less then the child's maximum 1738 if(!maxlow.isNull && low(value) < maxlow) 1739 { 1740 // calculate an offset to continue with by asking the child on predecessor of the lowered value 1741 assert(cluster[childIndex].universe == lSR(universe.nextPow2)); 1742 auto offset = cluster[childIndex].successor(low(value)); 1743 // the result is given by reconstruction of the answer 1744 retVal = index(childIndex, offset); 1745 } 1746 else // otherwise we can not use the maximum of the child 1747 { 1748 // ask the summary for the successor cluster. 1749 assert(summary.universe == hSR(universe.nextPow2)); 1750 auto succcluster = summary.successor(childIndex); 1751 // if the successor cluster is null 1752 if(succcluster.isNull) return back; // return the current max, as this is the last remaining value 1753 // if the successor cluster exists, the offset is given by its minimum 1754 // and the result by the reconstruction of the offset. 1755 retVal = index(succcluster, cluster[succcluster].front); 1756 } 1757 return retVal; 1758 } 1759 1760 /** 1761 dummy toHash method. 1762 */ 1763 size_t toHash() const { assert(0); } 1764 1765 /** 1766 comparison operator for the recursive node of the same kind. 1767 */ 1768 bool opEquals(O)(ref const O input) const if(is(Unqual!O == Unqual!(typeof(this)))) 1769 { 1770 // short circuit, if pointers are the same 1771 if(stats == input.stats) 1772 { 1773 assert(val == input.val); 1774 return true; 1775 } 1776 1777 // otherwise we have to check the whole structure. 1778 if(*stats != *input.stats) 1779 { 1780 return false; 1781 } 1782 if(*val != *input.val) 1783 { 1784 return false; 1785 } 1786 if(!isLeaf) 1787 { 1788 if(summary != input.summary) 1789 { 1790 return false; 1791 } 1792 foreach(i, ref c; cluster) 1793 { 1794 if(c != input.cluster[i]) 1795 { 1796 return false; 1797 } 1798 } 1799 } 1800 else 1801 { 1802 if(!input.isLeaf) 1803 { 1804 return false; 1805 } 1806 } 1807 return true; 1808 } 1809 1810 private: 1811 /* 1812 This pointer acts as an array to nodes like this one. As the universe size is not provided, the length of the 1813 array can not be used to calculate the most of operations, so no explicit array is needed. The only remaining 1814 property is whether the pointer is set at all. From this property the node can decide, whether it is a leaf or 1815 an intermediate node. // the first member behaves different, as the others, as it is the summary node. 1816 */ 1817 1818 static if(!is(T == void)) 1819 { 1820 T** dataArr; 1821 typeof(this)* ptrArr; 1822 } 1823 else 1824 { 1825 typeof(this)[] ptrArr; 1826 } 1827 1828 // contains max and min, or the bit array of keys 1829 size_t* val; 1830 // contains universe size and the current length 1831 size_t* stats; 1832 1833 // property returning the summary node 1834 @property auto ref summary() inout// @nogc nothrow 1835 in 1836 { 1837 assert(!isLeaf); 1838 } 1839 do 1840 { 1841 return ptrArr[0]; 1842 } 1843 1844 // property returning the cluster array 1845 @property auto ref cluster() inout// @nogc nothrow 1846 in 1847 { 1848 assert(!isLeaf); 1849 } 1850 do 1851 { 1852 return ptrArr[1 .. hSR(universe.nextPow2) + 1]; 1853 } 1854 1855 @property void universe(size_t input) 1856 in 1857 { 1858 assert(stats !is null); 1859 assert(input < maxSizeBound); 1860 } 1861 do 1862 { 1863 *stats = *stats & lowerMask; 1864 *stats = *stats | (input << (size_t.sizeof * CHAR_BIT/2)); 1865 } 1866 1867 @property void length(size_t input) 1868 in 1869 { 1870 assert(stats !is null); 1871 assert(input < maxSizeBound); 1872 } 1873 do 1874 { 1875 *stats = *stats & higherMask; 1876 *stats = *stats | input; 1877 } 1878 1879 /** 1880 Node constructor. A universe size provided, if the size is below the cutoff there is nothing to be done, as the 1881 underlying value created and set to zero by default. 1882 If otherwise create an array of children. This array has to be (according to Cormen) of size of higher square 1883 root of the current universe size + 1. The extra place is reserved for the summary. 1884 For each just created child call its constructor. 1885 For the summary with the universe size of the higher square root of the current universe size. 1886 For each other child with the universe size of the lower square root of the currennt universe size. 1887 Then, assign the fully initialized children array to the pointer in the current node, doing approprate steps to 1888 show, that this node is an intermediate node, not containing any values yet. 1889 The knowledge of the current universe size is lost at this moment. As this keeps every build up node smaller 1890 (and there could be a lot of them). This is why, the VEBtree class continues to hold the global universe size, 1891 which is passed on every call to the root node. In this way this, extern saved value has the role of being 1892 outsourced array size for each (!) node in the tree, as its size is reconstructed during the access to them. 1893 */ 1894 this(size_t uS) // nothrow 1895 { 1896 stats = new size_t(); 1897 val = new size_t(); 1898 1899 universe = uS; 1900 1901 static if(!is(T == void)) 1902 { 1903 T*[] tmpDataArr; 1904 } 1905 1906 assert(stats !is null); 1907 if(universe > baseSize) 1908 { 1909 // reserve enough place for the summary and the children cluster 1910 typeof(this)[] tmpArr; 1911 assert(stats !is null); 1912 tmpArr.length = hSR(universe.nextPow2) + 1; 1913 1914 static if(!is(T == void)) 1915 { 1916 ptrArr = tmpArr.ptr; 1917 tmpDataArr.length = 2; 1918 } 1919 else 1920 { 1921 ptrArr = tmpArr; 1922 } 1923 1924 // add the summary with its universe of higher squaure root of the current universe 1925 assert(stats !is null); 1926 summary = typeof(this)(hSR(universe.nextPow2)); 1927 assert(stats !is null); 1928 assert(ptrArr[0].stats !is null); 1929 assert(ptrArr[0].universe == hSR(universe.nextPow2)); 1930 // add higher square root children with lower square root universe each. 1931 assert(stats !is null); 1932 1933 cluster.each!((ref el) => el = typeof(this)(lSR(universe.nextPow2))); 1934 assert(stats !is null); 1935 ptrArr[1 .. hSR(universe.nextPow2) + 1].each!((ref el) => assert(el.universe == lSR(universe.nextPow2))); 1936 1937 } 1938 else 1939 { 1940 static if(!is(T == void)) 1941 { 1942 tmpDataArr.length = baseSize; 1943 } 1944 } 1945 static if(!is(T == void)) 1946 { 1947 dataArr = tmpDataArr.ptr; 1948 } 1949 nullify; // set the value to the sentinel value to represent the empty state. 1950 } 1951 1952 /** convinience method to check, if the node belongs to the lowest level in the tree */ 1953 @property bool isLeaf() @nogc nothrow inout 1954 in 1955 { 1956 assert(stats !is null); 1957 } 1958 do 1959 { 1960 return universe <= baseSize; 1961 } 1962 1963 /** method executing the appropriate steps to nullify the current node */ 1964 @property auto nullify() // @nogc nothrow 1965 in 1966 { 1967 assert(val !is null); 1968 } 1969 do 1970 { 1971 if(isLeaf) 1972 { 1973 *val = 0; 1974 } 1975 else 1976 { 1977 *val = 1; 1978 } 1979 1980 static if(!is(T == void)) 1981 { 1982 T* retVal; 1983 if(isLeaf) 1984 { 1985 foreach(el; dataArr[0 .. baseSize]) 1986 { 1987 if(el !is null) 1988 { 1989 assert(retVal is null); 1990 retVal = el; 1991 version(release) 1992 { 1993 break; 1994 } 1995 } 1996 } 1997 dataArr[0 .. baseSize] = null; 1998 } 1999 else 2000 { 2001 assert(dataArr[0] == dataArr[1]); 2002 retVal = dataArr[0]; 2003 dataArr[0 .. 2] = null; 2004 2005 } 2006 return retVal; 2007 } 2008 } 2009 2010 /** 2011 setter for the min, setting either the lowest bit or the min part of the value. 2012 */ 2013 @property void front(T...)(size_t key, ref T value) 2014 if((is(T == void) && T.length == 0) || (!is(T == void) && T.length < 2))// @nogc nothrow 2015 { 2016 if(isLeaf) 2017 { 2018 assert(front > key); 2019 insert(key, value); 2020 } 2021 else 2022 { 2023 // the passed value should not exceed the allowed size of a size/2 2024 assert(key < maxSizeBound); 2025 *val = *val & higherMask; 2026 *val = *val | key; 2027 static if(T.length) 2028 { 2029 dataArr[0] = &value[0]; 2030 } 2031 } 2032 } 2033 2034 /** 2035 setter for the max, setting either the highest bit or the max part of the value. 2036 */ 2037 @property void back(T...)(size_t key, ref T value) 2038 if((is(T == void) && T.length == 0) || (!is(T == void) && T.length < 2))// @nogc nothrow 2039 { 2040 if(isLeaf) 2041 { 2042 assert(back < key); 2043 insert(key, value); 2044 } 2045 else 2046 { 2047 // the passed value should not exceed the allowed size of a size/2 2048 assert(key < maxSizeBound); 2049 *val = *val & lowerMask; 2050 *val = *val | (key << (size_t.sizeof * CHAR_BIT/2)); 2051 static if(T.length) 2052 { 2053 dataArr[1] = &value[0]; 2054 } 2055 } 2056 } 2057 2058 size_t low(size_t key) //@nogc nothrow 2059 { 2060 return .low(universe.nextPow2, key); 2061 } 2062 2063 size_t high(size_t key) //@nogc nothrow 2064 { 2065 return .high(universe.nextPow2, key); 2066 } 2067 2068 size_t index(size_t x, size_t y) //@nogc nothrow 2069 { 2070 return .index(universe.nextPow2, x, y); 2071 } 2072 } 2073 2074 /// 2075 unittest 2076 { 2077 2078 auto vN = vebRoot(baseSize); 2079 assert(vN.empty); 2080 static assert(vN.sizeof == 4 * size_t.sizeof); 2081 assert(vN.isLeaf); 2082 assert(vN.empty); 2083 *vN.val = 3; 2084 assert(vN.front == 0); 2085 assert(1 in vN); 2086 assert(!(2 in vN)); 2087 assert(vN.isLeaf); 2088 assert(vN.ptrArr == null); 2089 vN.nullify; 2090 assert(vN.empty); 2091 assert(*vN.val == 0); 2092 2093 } 2094 2095 /// 2096 unittest 2097 { 2098 2099 auto vT = vebRoot(100); 2100 assert(vT.empty); 2101 auto result = vT.insert(2); 2102 2103 assert(result); 2104 assert(!vT.empty); 2105 assert(2 in vT); 2106 assert(vT.length == 1); 2107 2108 auto vT2 = vT; 2109 auto vT3 = vT.dup(); 2110 assert(2 in vT2); 2111 assert(vT2.length == 1); 2112 auto result2 = vT2.insert(3); 2113 assert(vT2.length == 2); 2114 assert(result2); 2115 assert(3 in vT2); 2116 assert(3 in vT); 2117 assert(!(3 in vT3)); 2118 assert(vT2.length == 2); 2119 2120 } 2121 2122 /// 2123 unittest 2124 { 2125 2126 auto currentSeed = unpredictableSeed(); 2127 static if(vdebug){write("UT: vT, [], () "); writeln("seed: ", currentSeed);} 2128 rndGenInUse.seed(currentSeed); //initialize the random generator 2129 2130 size_t M = uniform(2U,testedSize, rndGenInUse); //set universe size to some integer. 2131 auto vT = vebRoot(M); //create the tree 2132 assert(M.iota.map!(i => vT.insert(uniform(0, vT.universe, rndGenInUse))).sum == vT.length); 2133 2134 assert(vT[].front == 0); 2135 assert(vT[].back == vT.universe); 2136 2137 } 2138 /// 2139 unittest 2140 { 2141 2142 auto vT = vebRoot(1000); 2143 assert(vT.capacity == 1024); 2144 assert(vT.front.isNull); 2145 assert(vT.insert(2)); 2146 assert(vT.insert(5)); 2147 assert(!(8 in vT)); 2148 assert(vT.insert(88)); 2149 assert(88 in vT); 2150 assert(vT.predecessor(4) == 2); 2151 assert(!(8 in vT)); 2152 assert(vT.insert(8)); 2153 assert(8 in vT); 2154 assert(vT.predecessor(75) == 8); 2155 2156 assert(vT.predecessor(90) == 88); 2157 2158 assert(vT.predecessor(7) == 5); 2159 assert(vT.predecessor(4) == 2); 2160 assert(vT.predecessor(2).isNull); 2161 2162 //TODO: reactivate this by slicing assert(vT[].predecessor(2) == 0); 2163 2164 assert(vT.predecessor(2).isNull); 2165 2166 assert(vT.successor(6) == 8); 2167 assert(vT.successor(5) == 8); 2168 2169 assert(vT.successor(4) == 5); 2170 assert(vT.successor(1) == 2); 2171 assert(vT.successor(75) == 88); 2172 assert(vT.successor(90).isNull); 2173 //TODO: reactivate this by slicing assert(vT[].successor(90) == vT.universe); 2174 2175 assert(!(1029 in vT)); 2176 2177 assert(vT.successor(1025).isNull); 2178 assert(vT.successor(1025).isNull); 2179 2180 auto vT2 = vebRoot(500); 2181 assert(vT2.empty); 2182 vT2.insert(50); 2183 vT2.insert(500); 2184 assert(vT2.back == 500); 2185 assert(vT2.front == 50); 2186 assert(vT2.successor(40) == 50); 2187 assert(vT2.successor(50) == 500); 2188 2189 vT2 = vebRoot(500); 2190 assert(vT2.empty); 2191 vT2.insert(50); 2192 vT2.insert(500); 2193 assert(vT2.back == 500); 2194 assert(vT2.front == 50); 2195 assert(vT2.successor(40) == 50); 2196 assert(vT2.successor(50) == 500); 2197 2198 /* about 20 seconds in debug mode. 2199 auto vT3 = vebRoot(halfSizeT.max); 2200 assert(vT3.insert(5)); 2201 assert(vT3.member(5)); 2202 assert(vT3.capacity == cast(ulong)halfSizeT.max + 1UL); 2203 //*/ 2204 2205 assert(!(1029 in vT)); 2206 assert(!(865 in vT)); 2207 assert(vT.insert(865)); 2208 assert(865 in vT); 2209 assert(!vT.insert(865)); 2210 assert(865 in vT); 2211 assert(!(866 in vT)); 2212 assert(!vT.remove(866)); 2213 assert(865 in vT); 2214 assert(vT.remove(865)); 2215 assert(!(865 in vT)); 2216 2217 } 2218 2219 /// 2220 unittest 2221 { 2222 auto currentSeed = unpredictableSeed(); 2223 static if(vdebug){write("UT: rand, succ "); writeln("seed: ", currentSeed);} 2224 rndGenInUse.seed(currentSeed); //initialize the random generator 2225 2226 size_t M = uniform(2U,testedSize, rndGenInUse); //set universe size to some integer. 2227 auto vT = vebRoot(M); //create the tree 2228 assert(vT.capacity == nextPow2(M-1)); 2229 2230 auto filled = M.iota.map!(i => vT.insert(uniform(0, vT.universe, rndGenInUse))).sum; 2231 assert(filled == vT.length); 2232 2233 size_t n; 2234 auto i = vT.back; 2235 2236 // discover the thousend (or little less) values with the predecessor method 2237 while(!i.isNull) 2238 { 2239 ++n; 2240 i = vT.predecessor(i); 2241 if(n > filled) break; 2242 } 2243 2244 size_t o; 2245 i = vT.front; 2246 while(!i.isNull) 2247 { 2248 ++o; 2249 i = vT.successor(i.get); 2250 if(o - 1 > filled) break; 2251 } 2252 2253 // assert, that all members are discovered, iff when no predecessors are left 2254 assert(n == filled); 2255 assert(o == filled); 2256 } 2257 2258 /// 2259 unittest 2260 { 2261 auto currentSeed = unpredictableSeed(); 2262 static if(vdebug){write("UT: rand, pred "); writeln("seed: ", currentSeed);} 2263 rndGenInUse.seed(currentSeed); //initialize the random generator 2264 size_t M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 2265 auto vT = vebRoot(M); 2266 assert(M.iota.map!(i => vT.insert(uniform(0, vT.universe, rndGenInUse))).sum == vT.length); 2267 auto i = vT.back; 2268 2269 // remove all members beginning from the maximum 2270 bool result; 2271 while(!i.isNull) 2272 { 2273 result = vT.remove(i); 2274 assert(result); 2275 auto j = vT.predecessor(i); 2276 if(!j.isNull) 2277 assert(j != i); 2278 i = j; 2279 } 2280 2281 // assert, that all members are removed, iff when no predecessors are left. 2282 assert(vT.empty); 2283 } 2284 2285 /// 2286 unittest 2287 { 2288 auto currentSeed = unpredictableSeed(); 2289 static if(vdebug){write("UT: rand, remove "); writeln("seed: ", currentSeed);} 2290 rndGenInUse.seed(currentSeed); //initialize the random generator 2291 size_t M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 2292 auto vT = vebRoot(M); 2293 assert(M.iota.map!(i => vT.insert(uniform(0, vT.universe, rndGenInUse))).sum == vT.length); 2294 auto i = vT.front; 2295 2296 // remove all members beginning from the minimum 2297 bool result; 2298 while(!i.isNull) 2299 { 2300 result = vT.remove(i); 2301 assert(result); 2302 auto j = vT.successor(i); 2303 if(!j.isNull) 2304 assert(j != i); 2305 i = j; 2306 } 2307 2308 // assert, that all members are removed, iff when no successors are left. 2309 assert(vT.empty); 2310 } 2311 2312 /// 2313 unittest 2314 { 2315 size_t M = testedSize; 2316 auto vT = vebRoot(M); 2317 vT.insert(0x000f); 2318 assert(vT.predecessor(0x000f).isNull); 2319 vT.insert(0x00f0); 2320 assert(vT.predecessor(0x00f0) == 0x000f); 2321 vT.insert(0x0f00); 2322 assert(vT.predecessor(0x0f00) == 0x00f0); 2323 vT.insert(0xf000); 2324 assert(vT.predecessor(0xf000) == 0x0f00); 2325 2326 auto result = vT.remove(0xf000); 2327 assert(result); 2328 assert(vT.predecessor(0xf000) == 0x0f00); 2329 result = vT.remove(0x0f00); 2330 assert(result); 2331 assert(vT.predecessor(0x0f00) == 0x00f0); 2332 result = vT.remove(0x00f0); 2333 assert(result); 2334 assert(vT.predecessor(0x00f0) == 0x000f); 2335 result = vT.remove(0x000f); 2336 assert(result); 2337 assert(vT.predecessor(0x000f).isNull); 2338 } 2339 2340 /// 2341 unittest 2342 { 2343 size_t M = testedSize; 2344 auto vT = vebRoot(M); 2345 vT.insert(0xf000); 2346 assert(0xf000 in vT); 2347 vT.insert(0x0f00); 2348 assert(0x0f00 in vT); 2349 vT.insert(0x00f0); 2350 assert(0x00f0 in vT); 2351 vT.insert(0x000f); 2352 assert(0x000f in vT); 2353 2354 auto result = vT.remove(0xf000); 2355 assert(result); 2356 assert(!(0xf000 in vT)); 2357 result = vT.remove(0x0f00); 2358 assert(result); 2359 assert(!(0x0f00 in vT)); 2360 result = vT.remove(0x00f0); 2361 assert(result); 2362 assert(!(0x00f0 in vT)); 2363 result = vT.remove(0x000f); 2364 assert(result); 2365 assert(!(0x000f in vT)); 2366 } 2367 2368 /// 2369 unittest 2370 { 2371 //stress test 2372 auto currentSeed = unpredictableSeed(); 2373 static if(vdebug){write("UT: rand, stress "); writeln("seed: ", currentSeed);} 2374 rndGenInUse.seed(currentSeed); //initialize the random generator 2375 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 2376 // last test says: see below. 2377 size_t M = uniform(2U, allowedArraySize, rndGenInUse); // set universe size to some integer. 2378 auto vT = vebRoot(M); 2379 2380 size_t[] arr; 2381 arr.length = 31 * vT.capacity/typeof(vT).sizeof; 2382 (vT.capacity - 1).iota.randomCover(rndGenInUse).take(arr.length) 2383 .enumerate 2384 .tee!(el => arr[el.index] = el.value) 2385 .each!(el => vT.insert(el.value)); 2386 2387 auto vT2 = vebRoot(M); 2388 2389 assert(vT2.capacity == vT.capacity); 2390 2391 auto rbt = redBlackTree!size_t(0); 2392 rbt.clear; 2393 2394 void fill1() 2395 { 2396 foreach(size_t i; arr) 2397 { 2398 vT2.insert(i); 2399 } 2400 2401 foreach(size_t i; arr) 2402 { 2403 vT2.remove(i); 2404 } 2405 assert(vT2.empty); 2406 2407 } 2408 2409 void fill2() 2410 { 2411 foreach(size_t i; arr) 2412 { 2413 rbt.insert(i); 2414 } 2415 } 2416 2417 /* 2418 this part is for speed test 2419 */ 2420 /* 2421 compiled with ldc2 vebtree.d -O -main -unittest 2422 results of stress tests: 2423 size of tree: 16777216 2424 howMuchFilled: 16252928 2425 VEB: 2 secs, 382 ms, 588 μs, and 8 hnsecs 2426 */ 2427 /* 2428 2429 writeln("size of tree: ", vT2.capacity); 2430 writeln("howMuchFilled: ", howMuchFilled); 2431 //auto r = benchmark!(fill1, fill2)(1); 2432 auto r = benchmark!(fill1)(1); 2433 2434 auto f0Result = to!Duration(r[0]); 2435 //auto f1Result = to!Duration(r[1]); 2436 writeln("VEB: ", f0Result); //10ms 2437 //writeln("rbt: ", f1Result); //40sec 2438 //assert(f0Result < f1Result); 2439 //*/ 2440 } 2441 2442 /// 2443 unittest 2444 { 2445 auto currentSeed = unpredictableSeed(); 2446 static if(vdebug){write("UT: rand, member "); writeln("seed: ", currentSeed);} 2447 rndGenInUse.seed(currentSeed); //initialize the random generator 2448 size_t M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 2449 size_t[] sourceArr; 2450 sourceArr.length = M; 2451 // generate a random array as the source for the tree 2452 iota(M).each!(i => sourceArr[i] = uniform(0U, M, rndGenInUse)); 2453 // make the array values unique. 2454 auto uniqueArr = sourceArr.sort.uniq; 2455 // constructor to test 2456 auto vT = vebRoot(sourceArr.length); 2457 uniqueArr.each!(el => vT.insert(el)); 2458 // check, that all values are filled 2459 bool result; 2460 foreach(i; uniqueArr) 2461 { 2462 assert(i in vT); 2463 result = vT.remove(i); 2464 assert(result); 2465 } 2466 // check, that no other elements are present. 2467 assert(vT.empty); 2468 } 2469 2470 /// 2471 unittest 2472 { 2473 auto currentSeed = unpredictableSeed(); 2474 static if(vdebug){write("UT: rand, opSlice "); writeln("seed: ", currentSeed);} 2475 rndGenInUse.seed(currentSeed); //initialize the random generator 2476 // do not use more then "1 << 16", as for the red-black tree the insertion duration is almost 4 (!) minutes. 2477 size_t M = uniform(2U, allowedArraySize, rndGenInUse); // set universe size to some integer. 2478 auto vT = vebRoot(M); 2479 size_t[] arr; 2480 arr.length = 16 * vT.capacity/typeof(vT).sizeof; 2481 (vT.capacity - 1).iota.randomCover(rndGenInUse).take(arr.length) 2482 .enumerate 2483 .tee!(el => arr[el.index] = el.value) 2484 .each!(el => vT.insert(el.value)); 2485 2486 assert(setSymmetricDifference(vT(), arr.sort).empty); 2487 } 2488 2489 /// 2490 unittest 2491 { 2492 static assert(!isInputRange!(VEBroot!())); 2493 static assert(isIterable!(VEBroot!())); 2494 static assert(isBidirectionalRange!(typeof(VEBroot!()[]))); 2495 static assert(is(typeof(vebRoot!(size_t)(4)[2]))); 2496 static assert(!is(typeof(vebRoot(4)[2]))); 2497 } 2498 2499 /// 2500 unittest 2501 { 2502 auto vT = vebRoot(14); 2503 auto result = vT.insert(2); 2504 assert(result); 2505 result = vT.insert(5); 2506 assert(result); 2507 result = vT.insert(10); 2508 assert(result); 2509 assert(vT[] == [0, 2, 5, 10, 14]); 2510 assert(vT() == [2, 5, 10]); 2511 } 2512 2513 /// 2514 unittest 2515 { 2516 /* 2517 //another stress test 2518 auto currentSeed = unpredictableSeed(); 2519 static if(vdebug){write("UT: stress test 2 "); writeln("seed: ", currentSeed);} 2520 rndGenInUse.seed(currentSeed); //initialize the random generator 2521 2522 void fill16(){ auto vT = vebRoot(1 << 16); } 2523 void fill17(){ auto vT = vebRoot(1 << 17); } 2524 void fill18(){ auto vT = vebRoot(1 << 18); } 2525 void fill19(){ auto vT = vebRoot(1 << 19); } 2526 void fill20(){ auto vT = vebRoot(1 << 20); } 2527 void fill21(){ auto vT = vebRoot(1 << 21); } 2528 void fill22(){ auto vT = vebRoot(1 << 22); } 2529 void fill23(){ auto vT = vebRoot(1 << 23); } 2530 void fill24(){ auto vT = vebRoot(1 << 24); } 2531 void fill25(){ auto vT = vebRoot(1 << 25); } 2532 void fill26(){ auto vT = vebRoot(1 << 26); } 2533 void fill27(){ auto vT = vebRoot(1 << 27); } 2534 void fill28(){ auto vT = vebRoot(1 << 28); } 2535 void fill29(){ auto vT = vebRoot(1 << 29); } 2536 void fill30(){ auto vT = vebRoot(1 << 30); } 2537 2538 auto r = benchmark!(fill16, fill17, fill18, fill19, fill20, fill21, fill22, fill23, fill24, fill25, fill26, fill27, 2539 fill28, fill29, fill30)(1); 2540 //auto r = benchmark!(fill1)(1); 2541 auto f16Result = to!Duration(r[0]); 2542 auto f17Result = to!Duration(r[1]); 2543 auto f18Result = to!Duration(r[2]); 2544 auto f19Result = to!Duration(r[3]); 2545 auto f20Result = to!Duration(r[4]); 2546 auto f21Result = to!Duration(r[5]); 2547 auto f22Result = to!Duration(r[6]); 2548 auto f23Result = to!Duration(r[7]); 2549 auto f24Result = to!Duration(r[8]); 2550 auto f25Result = to!Duration(r[9]); 2551 auto f26Result = to!Duration(r[10]); 2552 auto f27Result = to!Duration(r[11]); 2553 auto f28Result = to!Duration(r[12]); 2554 auto f29Result = to!Duration(r[13]); 2555 auto f30Result = to!Duration(r[14]); 2556 2557 writeln("VEB with M of ", 1 << 16, ": ", f16Result); 2558 writeln("VEB with M of ", 1 << 17, ": ", f17Result); 2559 writeln("VEB with M of ", 1 << 18, ": ", f18Result); 2560 writeln("VEB with M of ", 1 << 19, ": ", f19Result); 2561 writeln("VEB with M of ", 1 << 20, ": ", f20Result); 2562 writeln("VEB with M of ", 1 << 21, ": ", f21Result); 2563 writeln("VEB with M of ", 1 << 22, ": ", f22Result); 2564 writeln("VEB with M of ", 1 << 23, ": ", f23Result); 2565 writeln("VEB with M of ", 1 << 24, ": ", f24Result); 2566 writeln("VEB with M of ", 1 << 25, ": ", f25Result); 2567 writeln("VEB with M of ", 1 << 26, ": ", f26Result); 2568 writeln("VEB with M of ", 1 << 27, ": ", f27Result); 2569 writeln("VEB with M of ", 1 << 28, ": ", f28Result); 2570 writeln("VEB with M of ", 1 << 29, ": ", f29Result); 2571 writeln("VEB with M of ", 1 << 30, ": ", f30Result); 2572 //*/ 2573 2574 } 2575 2576 /// 2577 unittest 2578 { 2579 //stress test 2580 auto currentSeed = unpredictableSeed(); 2581 static if(vdebug){write("UT: rand, ranges "); writeln("seed: ", currentSeed);} 2582 rndGenInUse.seed(currentSeed); //initialize the random generator 2583 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 2584 // last test says: see below. 2585 size_t M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 2586 auto vT = vebRoot(M); 2587 /*testing the range methods*/ 2588 assert(vT.empty); 2589 2590 size_t[] sourceArr; 2591 sourceArr.length = uniform(2U, M, rndGenInUse); 2592 iota(sourceArr.length).each!(i => sourceArr[i] = uniform(0U, sourceArr.length, rndGenInUse)); 2593 2594 auto uniqueArr = sourceArr.sort.uniq; 2595 2596 // constructor to test 2597 2598 auto vTnew = vebRoot(sourceArr.length); 2599 uniqueArr.each!(el => vTnew.insert(el)); 2600 2601 assert(!vTnew.empty); 2602 assert(vTnew.length == uniqueArr.walkLength); 2603 auto vT2 = vTnew; 2604 static assert(isIterable!(typeof(vTnew))); 2605 auto slice = vTnew(); 2606 assert(slice.front == uniqueArr.front); 2607 assert(vTnew() == uniqueArr); 2608 assert(!vTnew.empty); 2609 assert(!vT2.empty); 2610 2611 size_t N = 100; 2612 auto vT3 = vebRoot(N); 2613 assert(vT3.empty); 2614 auto unique3 = N.iota.map!(i => uniform(0U, N, rndGenInUse)).array.sort.uniq.array; 2615 unique3.each!(u => vT3.insert(u)); 2616 unique3.each!(u => assert(u in vT3)); 2617 assert(vT3.length == unique3.length); 2618 auto sl3 = vT3[]; 2619 2620 if(unique3.front == 0 && unique3.back == vT3.universe) 2621 { 2622 assert(sl3.length == unique3.length); 2623 } 2624 else if(unique3.front == 0 || unique3.back == vT3.universe) 2625 { 2626 assert(sl3.length == unique3.length + 1); 2627 } 2628 else 2629 { 2630 assert(sl3.length == unique3.length + 2); 2631 } 2632 assert(sl3.length); 2633 assert(!sl3.empty); 2634 2635 unique3.each!(u => vT3.remove(u)); 2636 assert(vT3.empty); 2637 2638 //* Works. Duration in debug mode: about 35 seconds. 2639 //auto vTT = vebRoot((size_t(1) << 27) - 1); 2640 //assert(vTT.insert(42)); 2641 //assert(42 in vTT); 2642 //*/ 2643 } 2644 2645 private struct VEBtree(Flag!"inclusive" inclusive, R : Root!Source, alias Root, Source...) 2646 { 2647 static assert(isBidirectionalRange!(typeof(this))); 2648 2649 R root; 2650 2651 auto opBinaryRight(string op)(size_t key) if(op == "in") // @nogc nothrow 2652 { 2653 return key in root; 2654 } 2655 2656 static if(inclusive) 2657 { 2658 size_t frontKey; 2659 size_t backKey; 2660 } 2661 else 2662 { 2663 Response frontKey; 2664 Response backKey; 2665 } 2666 2667 size_t length; 2668 2669 private this(R val) 2670 { 2671 root = val; 2672 length = root.length; 2673 2674 static if(inclusive) 2675 { 2676 if(root.empty) 2677 { 2678 backKey = root.universe; 2679 assert(!length); 2680 length += 2; 2681 } 2682 else 2683 { 2684 if(root.back.get <= root.universe) 2685 { 2686 backKey = root.universe; 2687 if(root.back.get < root.universe) 2688 { 2689 length += 1; 2690 } 2691 } 2692 else 2693 { 2694 assert(root.back.get < root.capacity); 2695 backKey = root.capacity; 2696 length += 1; 2697 } 2698 2699 if(root.front.get) // i. e. front != 0 2700 { 2701 length += 1; 2702 } 2703 } 2704 } 2705 else 2706 { 2707 frontKey = root.front; 2708 backKey = root.back; 2709 } 2710 } 2711 2712 auto front() 2713 { 2714 return frontKey; 2715 } 2716 2717 void popFront() 2718 in 2719 { 2720 assert(!empty); 2721 } 2722 do 2723 { 2724 auto front = root.successor(frontKey.get); 2725 static if(inclusive) 2726 { 2727 if(front.isNull) 2728 { 2729 frontKey = root.universe; 2730 } 2731 else 2732 { 2733 frontKey = front.get; 2734 } 2735 } 2736 else 2737 { 2738 frontKey = front; 2739 } 2740 2741 --length; 2742 } 2743 2744 auto back() 2745 { 2746 return backKey; 2747 } 2748 2749 void popBack() 2750 in 2751 { 2752 assert(length); 2753 } 2754 do 2755 { 2756 auto back = root.predecessor(backKey.get); 2757 static if(inclusive) 2758 { 2759 if(back.isNull) 2760 { 2761 backKey = 0; 2762 } 2763 } 2764 else 2765 { 2766 backKey = back; 2767 } 2768 --length; 2769 } 2770 2771 auto predecessor(size_t key) 2772 { 2773 return root.predecessor(key); 2774 } 2775 2776 auto successor(size_t key) 2777 { 2778 return root.successor(key); 2779 } 2780 2781 static if(!is(Source[0] == void)) 2782 { 2783 static assert(!is(Source[0] == void)); 2784 auto ref opIndex(size_t key) //@nogc 2785 { 2786 return root[key]; 2787 } 2788 2789 /** 2790 opApply method in case of present source for iterating over key value pairs 2791 */ 2792 int opApply(scope int delegate(size_t, ref Source[0]) /*@nogc*/ operations) //@nogc 2793 { 2794 int result; 2795 2796 //for(auto leading = front; !leading.isNull; leading = successor(leading.get)) 2797 for(auto leading = front; !empty; popFront) 2798 { 2799 result = operations(leading.get, *root[leading.get]); 2800 2801 if(result) 2802 { 2803 break; 2804 } 2805 } 2806 2807 return result; 2808 } 2809 2810 /** 2811 opApply method in case of present source for iterating over key value pairs 2812 */ 2813 int opApply(scope int delegate(size_t) /*@nogc*/ operations) //@nogc 2814 { 2815 int result; 2816 2817 //for(auto leading = front; !leading.isNull; leading = successor(leading.get)) 2818 for(auto leading = front; !empty; popFront) 2819 { 2820 result = operations(leading.get); 2821 2822 if(result) 2823 { 2824 break; 2825 } 2826 } 2827 2828 return result; 2829 } 2830 } 2831 2832 bool empty() 2833 { 2834 return !length; 2835 } 2836 2837 auto save() 2838 { 2839 return this; 2840 } 2841 2842 typeof(this) dup() 2843 { 2844 auto copy = this; 2845 copy.root = root.dup; 2846 return copy; 2847 } 2848 2849 size_t toHash() const 2850 { 2851 assert(0); 2852 } 2853 2854 /** 2855 for comparison with an iterable, the iterable will be iterated, as the current object. If the iterable object is an 2856 input range, it will be destroyed. 2857 */ 2858 bool opEquals(T)(auto ref T input) if(isIterable!T) 2859 { 2860 static if(is(T == typeof(this))) 2861 { 2862 return root == input.root; 2863 } 2864 2865 static if(hasLength!T) 2866 { 2867 if(length != input.length) 2868 { 2869 return false; 2870 } 2871 } 2872 2873 auto copy = this.save; 2874 2875 foreach(el; input) 2876 { 2877 if(el != copy.front.get) 2878 { 2879 return false; 2880 } 2881 copy.popFront; 2882 } 2883 2884 return true; 2885 } 2886 } 2887 2888 private : 2889 size_t get(size_t input) @nogc 2890 { 2891 return input; 2892 } 2893 2894 bool isNull(size_t) @nogc 2895 { 2896 return false; 2897 }