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$(RPAREN) to keep the size of a single node also depending from the underlying architecture. 51 ii$(RPAREN) 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 { 1169 if(val is null) 1170 { 1171 return true; 1172 } 1173 else 1174 { 1175 if(isLeaf) 1176 { 1177 return *val == 0; 1178 } 1179 else 1180 { 1181 return (*val & lowerMask) > ((*val & higherMask) >> (size_t.sizeof * CHAR_BIT/2)); 1182 } 1183 } 1184 } 1185 1186 /** 1187 member method for the case universe size < base size. Overloads by passing only one parameter, which is 1188 the bit number of interest. Returns whether the appropriate bit inside the bitvector is set. 1189 */ 1190 bool opBinaryRight(string op)(size_t key) if(op == "in") // @nogc nothrow 1191 { 1192 assert(universe); 1193 if(key > universe.nextPow2) 1194 { 1195 return false; 1196 } 1197 if(isLeaf) 1198 { 1199 assert(key < baseSize); 1200 return bt(val, key) != 0; 1201 } 1202 else 1203 { 1204 if(empty) 1205 { 1206 // if an empty intermediate node is found, nothing is stored below it. 1207 return false; 1208 } 1209 // case of a single valued range. 1210 if(key == front || key == back) 1211 { 1212 return true; 1213 } 1214 1215 /* 1216 else we have to descend, using the recursive indexing: 1217 1. take the high(value, uS)-th child and 1218 2. ask it about the reduced low(value, uS) value 1219 3. use the lSR(uS) universe size of the childe node. 1220 */ 1221 1222 assert(cluster[high(key)].universe == lSR(universe.nextPow2)); 1223 return low(key) in cluster[high(key)]; 1224 } 1225 } 1226 1227 alias put = insert; 1228 /** 1229 insert method. this method is called from class with a universe size given. It performs recursion calls untill 1230 the universe size is reduced to the base size. Then the overloaded insert method is called. 1231 */ 1232 bool insert(T...)(size_t key, ref T value) @nogc 1233 if((is(T == void) && T.length == 0) || (!is(T == void) && T.length < 2))// @nogc nothrow 1234 { 1235 debug 1236 { 1237 static if(T.length) 1238 { 1239 auto insertingNewVal = this[key]; 1240 1241 scope(exit) 1242 { 1243 assert(this[key] !is null); 1244 1245 if(insertingNewVal is null) 1246 { 1247 assert(this[key] == &value[0]); 1248 } 1249 else 1250 { 1251 assert(this[key] == insertingNewVal); 1252 } 1253 } 1254 } 1255 } 1256 1257 typeof(return) res; 1258 1259 if(key > capacity) 1260 { 1261 res = false; 1262 length = length + res; 1263 return res; 1264 } 1265 1266 // if descended so far, do not use other functionality any more. 1267 if(isLeaf) 1268 { 1269 assert(val !is null); 1270 res = bts(val, key) == 0; 1271 static if(T.length) 1272 { 1273 if(res) 1274 { 1275 dataArr[key] = &value[0]; 1276 } 1277 } 1278 length = length + res; 1279 return res; 1280 } 1281 1282 if(empty) // if the current node does not contain anything put the value inside. 1283 { 1284 static if(T.length) 1285 { 1286 // the setters of min handle the value appropriately and do not need the universe size 1287 front(key, value); 1288 // being explicitely provided, as they can check the isLeaf property. 1289 back(key, value); 1290 } 1291 else 1292 { 1293 front(key); 1294 back(key); 1295 } 1296 1297 assert(!empty); 1298 res = true; 1299 length = length + res; 1300 return res; 1301 } 1302 1303 assert(!empty); 1304 assert(!front.isNull); 1305 assert(!back.isNull); 1306 1307 if(key == front || key == back) 1308 { 1309 res = false; // return, if value is already here. 1310 return res; 1311 } 1312 1313 if(front == back) // if the node contains a single value only, expand the node to a range and leave. 1314 { 1315 if(front > key) 1316 { 1317 front(key, value); 1318 } 1319 if(back < key) 1320 { 1321 back(key, value); 1322 } 1323 1324 res = true; 1325 length = length + res; 1326 return res; 1327 } 1328 /* 1329 if none of the cases above was true (all of them are break conditions) we have to compare the given value 1330 with the values present and adapt the range limits. This replaces the value we want to insert. 1331 */ 1332 // a swap can not be used here, as min is itself a (property) method 1333 if(key < front) 1334 { 1335 auto tmpKey = key; 1336 1337 static if(T.length) 1338 { 1339 auto tmpVal = &value[0]; 1340 } 1341 1342 key = front.get; 1343 1344 static if(T.length) 1345 { 1346 value[0] = *this[front.get]; 1347 } 1348 1349 static if(T.length) 1350 { 1351 front(tmpKey, *tmpVal); 1352 } 1353 else 1354 { 1355 front(tmpKey); 1356 } 1357 1358 } 1359 // a swap can not be used here, as max is itself a (property) method 1360 if(key > back) 1361 { 1362 auto tmpKey = key; 1363 1364 static if(T.length) 1365 { 1366 auto tmpVal = &value[0]; 1367 } 1368 1369 key = back.get; 1370 1371 static if(T.length) 1372 { 1373 value[0] = *this[back.get]; 1374 } 1375 1376 static if(T.length) 1377 { 1378 back(tmpKey, *tmpVal); 1379 } 1380 else 1381 { 1382 back(tmpKey); 1383 } 1384 } 1385 1386 // calculate the index of the children cluster by high(value, uS) we want to descent to. 1387 auto nextTreeIndex = high(key); 1388 1389 // if the child is happened to be null we have to update the summary and insert value of high(value, uS) into it 1390 assert(summary.universe == hSR(universe.nextPow2)); 1391 1392 if(cluster[nextTreeIndex].empty) 1393 { 1394 summary.insert(high(key), value); 1395 } 1396 1397 // in any case we pass the lowered value low(value, uS) to the child. 1398 assert(cluster[nextTreeIndex].universe == lSR(universe.nextPow2)); 1399 res = cluster[nextTreeIndex].insert(low(key), value); 1400 length = length + res; 1401 return res; 1402 } 1403 1404 /** 1405 remove method. this method is called from class with a universe size given. It performs recursion calls untill 1406 the universe size is reduced to the base size. Then the overloaded remove method is called. 1407 */ 1408 auto remove(size_t key) // @nogc nothrow 1409 { 1410 bool res; 1411 static if(!is(T == void)) 1412 { 1413 T* value; 1414 } 1415 1416 // if descended so far, do not use other functionality any more. 1417 if(isLeaf) 1418 { 1419 res = btr(val, key) != 0; 1420 static if(!is(T == void)) 1421 { 1422 if(res) 1423 { 1424 value = dataArr[key]; 1425 dataArr[key] = null; 1426 } 1427 } 1428 1429 length = length - res; 1430 1431 static if(is(T == void)) 1432 { 1433 return res; 1434 } 1435 else 1436 { 1437 return value; 1438 } 1439 } 1440 1441 if(empty) 1442 { 1443 // if the current node is null, there is nothing to remove. 1444 res = false; 1445 static if(is(T == void)) 1446 { 1447 return res; 1448 } 1449 else 1450 { 1451 return value; 1452 } 1453 } 1454 1455 if(front == back) // if the current node contains only a single value 1456 { 1457 if(front != key) 1458 { 1459 // do nothing if the given value is not the stored one 1460 res = false; 1461 1462 static if(is(T == void)) 1463 { 1464 return res; 1465 } 1466 else 1467 { 1468 return value; 1469 } 1470 } 1471 1472 // set this node to the sentinel-null if it does. 1473 static if(!is(T == void)) 1474 { 1475 value = this.nullify; 1476 } 1477 else 1478 { 1479 this.nullify; 1480 } 1481 1482 res = true; 1483 length = length - res; 1484 static if(is(T == void)) 1485 { 1486 return res; 1487 } 1488 else 1489 { 1490 return value; 1491 } 1492 } 1493 1494 if(key == front) // if we met the minimum of a node 1495 { 1496 auto treeOffset = summary.front; // calculate an offset from the summary to continue with 1497 if(treeOffset.isNull) // if the offset is invalid, then there is no further hierarchy and we are going to 1498 { 1499 front = back; // store a single value in this node. 1500 res = true; 1501 length = length - res; 1502 static if(is(T == void)) 1503 { 1504 return res; 1505 } 1506 else 1507 { 1508 value = dataArr[0]; 1509 dataArr[0] = dataArr[1]; 1510 return value; 1511 } 1512 } 1513 auto min = cluster[treeOffset.get].front; // otherwise we get the minimum from the offset child 1514 1515 assert(cluster[treeOffset].universe == lSR(universe.nextPow2)); 1516 1517 // remove it from the child 1518 static if(is(T == void)) 1519 { 1520 cluster[treeOffset.get].remove(min); 1521 } 1522 else 1523 { 1524 auto minVal = cluster[treeOffset.get].remove(min); 1525 } 1526 1527 // if it happens to become null during the remove process, we also remove the offset entry from the summary 1528 assert(summary.universe == hSR(universe.nextPow2)); 1529 if(cluster[treeOffset.get].empty) 1530 { 1531 summary.remove(treeOffset.get); 1532 } 1533 1534 //anyway, the new min of the current node become the restored value of the calculated offset. 1535 static if(is(T == void)) 1536 { 1537 front(index(treeOffset.get, min)); 1538 } 1539 else 1540 { 1541 value = dataArr[0]; 1542 front(index(treeOffset.get, min), *minVal); 1543 } 1544 1545 res = true; 1546 length = length - res; 1547 static if(is(T == void)) 1548 { 1549 return res; 1550 } 1551 else 1552 { 1553 return value; 1554 } 1555 1556 } 1557 1558 // if we met the maximum of a node 1559 if(key == back) 1560 { 1561 // calculate an offset from the summary to contiue with 1562 auto treeOffset = summary.back; 1563 // if the offset is invalid, then there is no further hierarchy and we are going to 1564 if(treeOffset.isNull) 1565 { 1566 // store a single value in this node. 1567 back = front; 1568 res = true; 1569 length = length - res; 1570 static if(is(T == void)) 1571 { 1572 return res; 1573 } 1574 else 1575 { 1576 value = dataArr[1]; 1577 dataArr[1] = dataArr[0]; 1578 return value; 1579 } 1580 } 1581 1582 // otherwise we get maximum from the offset child 1583 auto max = cluster[treeOffset.get].back; 1584 assert(cluster[treeOffset.get].universe == lSR(universe.nextPow2)); 1585 1586 // remove it from the child 1587 static if(is(T == void)) 1588 { 1589 cluster[treeOffset.get].remove(max); 1590 } 1591 else 1592 { 1593 auto maxValue = cluster[treeOffset.get].remove(max); 1594 } 1595 1596 1597 // if it happens to become null during the remove process, we also remove the offset enty from the summary 1598 assert(summary.universe == hSR(universe.nextPow2)); 1599 if(cluster[treeOffset.get].empty) summary.remove(treeOffset.get); 1600 1601 // anyway, the new max of the current node become the restored value of the calculated offset. 1602 static if(is(T == void)) 1603 { 1604 back(index(treeOffset.get, max)); 1605 } 1606 else 1607 { 1608 value = dataArr[1]; 1609 back(index(treeOffset.get, max), *maxValue); 1610 } 1611 1612 res = true; 1613 length = length - res; 1614 static if(is(T == void)) 1615 { 1616 return res; 1617 } 1618 else 1619 { 1620 return value; 1621 } 1622 1623 } 1624 1625 // if no condition was met we have to descend deeper. We get the offset by reducing the value to high(value, uS) 1626 auto treeOffset = high(key); 1627 // and remove low(value, uS) from the offset child. 1628 assert(cluster[treeOffset].universe == lSR(universe.nextPow2)); 1629 1630 static if(is(T == void)) 1631 { 1632 res = cluster[treeOffset].remove(low(key)); 1633 } 1634 else 1635 { 1636 auto prelength = cluster[treeOffset].length; 1637 value = cluster[treeOffset].remove(low(key)); 1638 } 1639 1640 // if the cluster become null during the remove process we have to update the summary node. 1641 assert(summary.universe == hSR(universe.nextPow2)); 1642 if(cluster[treeOffset].empty) 1643 { 1644 summary.remove(treeOffset); 1645 } 1646 1647 static if(is(T == void)) 1648 { 1649 length = length - res; 1650 return res; 1651 } 1652 else 1653 { 1654 res = prelength > cluster[treeOffset].length; 1655 length = length - res; 1656 return value; 1657 } 1658 } 1659 1660 /** 1661 predecessor method. this method is called from class with a universe size given. It performs recursion calls 1662 until the universe size is reduced to the base size. Then the overloaded predecessor method is called. 1663 */ 1664 Response predecessor(size_t value) // @nogc nothrow 1665 { 1666 typeof(return) retVal; 1667 1668 // if descended so far, do not use other functionality any more. 1669 if(isLeaf) 1670 { 1671 if(!empty && (value != 0)) 1672 { 1673 /* 1674 create a mask, which hides all higher bits of the stored value down to the given bit number, then apply 1675 bit search from the highest bit. 1676 */ 1677 auto maskedVal = *val & ((size_t(1) << value) - 1); 1678 if(maskedVal != 0) 1679 { 1680 retVal = bsr(maskedVal); 1681 } 1682 } 1683 return retVal; 1684 } 1685 // if this node is empty, no predecessor can be found here or deeper in the tree 1686 if(empty) 1687 { 1688 return retVal; 1689 } 1690 // if given value is greater then the stored max, the predecessor is max 1691 if(value > back) 1692 { 1693 return back; 1694 } 1695 // if given value is less then the min, no predecessor exists. 1696 if(value <= front) 1697 { 1698 return retVal; 1699 } 1700 /* 1701 if none of the break conditions was met we have to descend further into the tree. 1702 */ 1703 auto childIndex = high(value); // calculate the child index by high(value, uS) 1704 auto minlow = cluster[childIndex].front; // look into the child for its minimum 1705 // if the minimum exists and the lowered given value is greater then the child's minimum 1706 if(!minlow.isNull && low(value) > minlow) 1707 { 1708 // calculate an offset to continue with by asking the child on predecessor of the lowered value. 1709 assert(cluster[childIndex].universe == lSR(universe.nextPow2)); 1710 auto offset = cluster[childIndex].predecessor(low(value)); 1711 // the result is given by reconstruction of the answer. 1712 retVal = index(childIndex, offset); 1713 } 1714 else // otherwise we can not use the minimum of the child 1715 { 1716 // ask the summary for the predecessor cluster. 1717 assert(summary.universe == hSR(universe.nextPow2)); 1718 auto predcluster = summary.predecessor(childIndex); 1719 // if the predecessor cluster is null return the current min, as this is the last remaining value 1720 if(predcluster.isNull) return front; 1721 // if the predecessor cluster exists, the offset is given by its maximum 1722 // and the result by the reconstruction of the offset. 1723 retVal = index(predcluster, cluster[predcluster].back); 1724 } 1725 return retVal; 1726 } 1727 1728 /** 1729 successor method. this method is called from class with a universe size given. It performs recursion calls until 1730 the universe size is reduced to the base size. Then the overloaded successor method is called. 1731 */ 1732 Response successor(size_t value) //@nogc nothrow 1733 { 1734 // if descended so far, do not use other functionality any more. 1735 typeof(return) retVal; 1736 if(isLeaf) 1737 { 1738 if(!empty && (value + 1 < baseSize)) 1739 { 1740 // create a mask, which hides all lower bits of the stored value up to the given bit number, then apply 1741 // bit search from the lowest bit. 1742 auto maskedVal = *val & ~((size_t(1) << (value + 1)) - 1); 1743 if(maskedVal != 0) retVal = bsf(maskedVal); 1744 } 1745 return retVal; 1746 } 1747 if(empty) return retVal; // if this node is empty, no successor can be found here or deeper in the tree 1748 if(value < front) return front; // if given value is less then the min, return the min as successor 1749 if(value >= back) return retVal; // if given value is greater then the max, no predecessor exists 1750 1751 /* 1752 if none of the break conditions was met, we have to descent further into the tree. 1753 */ 1754 auto childIndex = high(value); // calculate the child index by high(value, uS) 1755 auto maxlow = cluster[childIndex].back; // look into the child for its maximum 1756 // if the maximum exists and the lowered given value is less then the child's maximum 1757 if(!maxlow.isNull && low(value) < maxlow) 1758 { 1759 // calculate an offset to continue with by asking the child on predecessor of the lowered value 1760 assert(cluster[childIndex].universe == lSR(universe.nextPow2)); 1761 auto offset = cluster[childIndex].successor(low(value)); 1762 // the result is given by reconstruction of the answer 1763 retVal = index(childIndex, offset); 1764 } 1765 else // otherwise we can not use the maximum of the child 1766 { 1767 // ask the summary for the successor cluster. 1768 assert(summary.universe == hSR(universe.nextPow2)); 1769 auto succcluster = summary.successor(childIndex); 1770 // if the successor cluster is null 1771 if(succcluster.isNull) return back; // return the current max, as this is the last remaining value 1772 // if the successor cluster exists, the offset is given by its minimum 1773 // and the result by the reconstruction of the offset. 1774 retVal = index(succcluster, cluster[succcluster].front); 1775 } 1776 return retVal; 1777 } 1778 1779 /** 1780 dummy toHash method. 1781 */ 1782 size_t toHash() const { assert(0); } 1783 1784 /** 1785 comparison operator for the recursive node of the same kind. 1786 */ 1787 bool opEquals(O)(ref const O input) const if(is(Unqual!O == Unqual!(typeof(this)))) 1788 { 1789 // short circuit, if pointers are the same 1790 if(stats == input.stats) 1791 { 1792 assert(val == input.val); 1793 return true; 1794 } 1795 1796 // otherwise we have to check the whole structure. 1797 if(*stats != *input.stats) 1798 { 1799 return false; 1800 } 1801 if(*val != *input.val) 1802 { 1803 return false; 1804 } 1805 if(!isLeaf) 1806 { 1807 if(summary != input.summary) 1808 { 1809 return false; 1810 } 1811 foreach(i, ref c; cluster) 1812 { 1813 if(c != input.cluster[i]) 1814 { 1815 return false; 1816 } 1817 } 1818 } 1819 else 1820 { 1821 if(!input.isLeaf) 1822 { 1823 return false; 1824 } 1825 } 1826 return true; 1827 } 1828 1829 private: 1830 /* 1831 This pointer acts as an array to nodes like this one. As the universe size is not provided, the length of the 1832 array can not be used to calculate the most of operations, so no explicit array is needed. The only remaining 1833 property is whether the pointer is set at all. From this property the node can decide, whether it is a leaf or 1834 an intermediate node. // the first member behaves different, as the others, as it is the summary node. 1835 */ 1836 1837 static if(!is(T == void)) 1838 { 1839 T** dataArr; 1840 typeof(this)* ptrArr; 1841 } 1842 else 1843 { 1844 typeof(this)[] ptrArr; 1845 } 1846 1847 // contains max and min, or the bit array of keys 1848 size_t* val; 1849 // contains universe size and the current length 1850 size_t* stats; 1851 1852 // property returning the summary node 1853 @property auto ref summary() inout// @nogc nothrow 1854 in 1855 { 1856 assert(!isLeaf); 1857 } 1858 do 1859 { 1860 return ptrArr[0]; 1861 } 1862 1863 // property returning the cluster array 1864 @property auto ref cluster() inout// @nogc nothrow 1865 in 1866 { 1867 assert(!isLeaf); 1868 } 1869 do 1870 { 1871 return ptrArr[1 .. hSR(universe.nextPow2) + 1]; 1872 } 1873 1874 @property void universe(size_t input) 1875 in 1876 { 1877 assert(stats !is null); 1878 assert(input < maxSizeBound); 1879 } 1880 do 1881 { 1882 *stats = *stats & lowerMask; 1883 *stats = *stats | (input << (size_t.sizeof * CHAR_BIT/2)); 1884 } 1885 1886 @property void length(size_t input) 1887 in 1888 { 1889 assert(stats !is null); 1890 assert(input < maxSizeBound); 1891 } 1892 do 1893 { 1894 *stats = *stats & higherMask; 1895 *stats = *stats | input; 1896 } 1897 1898 /** 1899 Node constructor. A universe size provided, if the size is below the cutoff there is nothing to be done, as the 1900 underlying value created and set to zero by default. 1901 If otherwise create an array of children. This array has to be (according to Cormen) of size of higher square 1902 root of the current universe size + 1. The extra place is reserved for the summary. 1903 For each just created child call its constructor. 1904 For the summary with the universe size of the higher square root of the current universe size. 1905 For each other child with the universe size of the lower square root of the currennt universe size. 1906 Then, assign the fully initialized children array to the pointer in the current node, doing approprate steps to 1907 show, that this node is an intermediate node, not containing any values yet. 1908 The knowledge of the current universe size is lost at this moment. As this keeps every build up node smaller 1909 (and there could be a lot of them). This is why, the VEBtree class continues to hold the global universe size, 1910 which is passed on every call to the root node. In this way this, extern saved value has the role of being 1911 outsourced array size for each (!) node in the tree, as its size is reconstructed during the access to them. 1912 */ 1913 this(size_t uS) // nothrow 1914 { 1915 stats = new size_t(); 1916 val = new size_t(); 1917 1918 universe = uS; 1919 1920 static if(!is(T == void)) 1921 { 1922 T*[] tmpDataArr; 1923 } 1924 1925 assert(stats !is null); 1926 if(universe > baseSize) 1927 { 1928 // reserve enough place for the summary and the children cluster 1929 typeof(this)[] tmpArr; 1930 assert(stats !is null); 1931 tmpArr.length = hSR(universe.nextPow2) + 1; 1932 1933 static if(!is(T == void)) 1934 { 1935 ptrArr = tmpArr.ptr; 1936 tmpDataArr.length = 2; 1937 } 1938 else 1939 { 1940 ptrArr = tmpArr; 1941 } 1942 1943 // add the summary with its universe of higher squaure root of the current universe 1944 assert(stats !is null); 1945 summary = typeof(this)(hSR(universe.nextPow2)); 1946 assert(stats !is null); 1947 assert(ptrArr[0].stats !is null); 1948 assert(ptrArr[0].universe == hSR(universe.nextPow2)); 1949 // add higher square root children with lower square root universe each. 1950 assert(stats !is null); 1951 1952 cluster.each!((ref el) => el = typeof(this)(lSR(universe.nextPow2))); 1953 assert(stats !is null); 1954 ptrArr[1 .. hSR(universe.nextPow2) + 1].each!((ref el) => assert(el.universe == lSR(universe.nextPow2))); 1955 1956 } 1957 else 1958 { 1959 static if(!is(T == void)) 1960 { 1961 tmpDataArr.length = baseSize; 1962 } 1963 } 1964 static if(!is(T == void)) 1965 { 1966 dataArr = tmpDataArr.ptr; 1967 } 1968 nullify; // set the value to the sentinel value to represent the empty state. 1969 } 1970 1971 /** convinience method to check, if the node belongs to the lowest level in the tree */ 1972 @property bool isLeaf() @nogc nothrow inout 1973 in 1974 { 1975 assert(stats !is null); 1976 } 1977 do 1978 { 1979 return universe <= baseSize; 1980 } 1981 1982 /** method executing the appropriate steps to nullify the current node */ 1983 @property auto nullify() // @nogc nothrow 1984 in 1985 { 1986 assert(val !is null); 1987 } 1988 do 1989 { 1990 if(isLeaf) 1991 { 1992 *val = 0; 1993 } 1994 else 1995 { 1996 *val = 1; 1997 } 1998 1999 static if(!is(T == void)) 2000 { 2001 T* retVal; 2002 if(isLeaf) 2003 { 2004 foreach(el; dataArr[0 .. baseSize]) 2005 { 2006 if(el !is null) 2007 { 2008 assert(retVal is null); 2009 retVal = el; 2010 version(release) 2011 { 2012 break; 2013 } 2014 } 2015 } 2016 dataArr[0 .. baseSize] = null; 2017 } 2018 else 2019 { 2020 assert(dataArr[0] == dataArr[1]); 2021 retVal = dataArr[0]; 2022 dataArr[0 .. 2] = null; 2023 2024 } 2025 return retVal; 2026 } 2027 } 2028 2029 /** 2030 setter for the min, setting either the lowest bit or the min part of the value. 2031 */ 2032 @property void front(T...)(size_t key, ref T value) @nogc 2033 if((is(T == void) && T.length == 0) || (!is(T == void) && T.length < 2))// @nogc nothrow 2034 { 2035 if(isLeaf) 2036 { 2037 assert(front > key); 2038 insert(key, value); 2039 } 2040 else 2041 { 2042 // the passed value should not exceed the allowed size of a size/2 2043 assert(key < maxSizeBound); 2044 *val = *val & higherMask; 2045 *val = *val | key; 2046 static if(T.length) 2047 { 2048 dataArr[0] = &value[0]; 2049 } 2050 } 2051 } 2052 2053 /** 2054 setter for the max, setting either the highest bit or the max part of the value. 2055 */ 2056 @property void back(T...)(size_t key, ref T value) 2057 if((is(T == void) && T.length == 0) || (!is(T == void) && T.length < 2))// @nogc nothrow 2058 { 2059 if(isLeaf) 2060 { 2061 assert(back < key); 2062 insert(key, value); 2063 } 2064 else 2065 { 2066 // the passed value should not exceed the allowed size of a size/2 2067 assert(key < maxSizeBound); 2068 *val = *val & lowerMask; 2069 *val = *val | (key << (size_t.sizeof * CHAR_BIT/2)); 2070 static if(T.length) 2071 { 2072 dataArr[1] = &value[0]; 2073 } 2074 } 2075 } 2076 2077 size_t low(size_t key) //@nogc nothrow 2078 { 2079 return .low(universe.nextPow2, key); 2080 } 2081 2082 size_t high(size_t key) //@nogc nothrow 2083 { 2084 return .high(universe.nextPow2, key); 2085 } 2086 2087 size_t index(size_t x, size_t y) //@nogc nothrow 2088 { 2089 return .index(universe.nextPow2, x, y); 2090 } 2091 } 2092 2093 /// 2094 unittest 2095 { 2096 2097 auto vN = vebRoot(baseSize); 2098 assert(vN.empty); 2099 static assert(vN.sizeof == 4 * size_t.sizeof); 2100 assert(vN.isLeaf); 2101 assert(vN.empty); 2102 *vN.val = 3; 2103 assert(vN.front == 0); 2104 assert(1 in vN); 2105 assert(!(2 in vN)); 2106 assert(vN.isLeaf); 2107 assert(vN.ptrArr == null); 2108 vN.nullify; 2109 assert(vN.empty); 2110 assert(*vN.val == 0); 2111 2112 } 2113 2114 /// 2115 unittest 2116 { 2117 2118 auto vT = vebRoot(100); 2119 assert(vT.empty); 2120 auto result = vT.insert(2); 2121 2122 assert(result); 2123 assert(!vT.empty); 2124 assert(2 in vT); 2125 assert(vT.length == 1); 2126 2127 auto vT2 = vT; 2128 auto vT3 = vT.dup(); 2129 assert(2 in vT2); 2130 assert(vT2.length == 1); 2131 auto result2 = vT2.insert(3); 2132 assert(vT2.length == 2); 2133 assert(result2); 2134 assert(3 in vT2); 2135 assert(3 in vT); 2136 assert(!(3 in vT3)); 2137 assert(vT2.length == 2); 2138 2139 } 2140 2141 /// 2142 unittest 2143 { 2144 2145 auto currentSeed = unpredictableSeed(); 2146 static if(vdebug){write("UT: vT, [], () "); writeln("seed: ", currentSeed);} 2147 rndGenInUse.seed(currentSeed); //initialize the random generator 2148 2149 size_t M = uniform(2U,testedSize, rndGenInUse); //set universe size to some integer. 2150 auto vT = vebRoot(M); //create the tree 2151 assert(M.iota.map!(i => vT.insert(uniform(0, vT.universe, rndGenInUse))).sum == vT.length); 2152 2153 assert(vT[].front == 0); 2154 assert(vT[].back == vT.universe); 2155 2156 } 2157 /// 2158 unittest 2159 { 2160 auto p = vebRoot(100); 2161 assert(p.empty); 2162 p.insert(5); 2163 p.insert(100); 2164 assert(!p.empty); 2165 assert(p.successor(0) == 5); 2166 assert(p.successor(4) == 5); 2167 assert(p.successor(5) == 100); 2168 auto s = p[]; 2169 static assert(isBidirectionalRange!(typeof(s))); 2170 assert(s.front == 0); 2171 assert(p.front == 5); 2172 s.popFront; 2173 assert(!s.empty); 2174 assert(s.front == 5); 2175 s.popFront; 2176 assert(s.front == 100); 2177 s.popFront; 2178 assert(s.empty); 2179 2180 auto pp = vebRoot(100); 2181 assert(pp.empty); 2182 pp.insert(5); 2183 assert(!pp.empty); 2184 assert(pp.successor(0) == 5); 2185 assert(pp.successor(4) == 5); 2186 assert(pp.successor(5).isNull); 2187 assert(pp[].successor(5) == 100); 2188 auto ss = pp(); 2189 static assert(isBidirectionalRange!(typeof(ss))); 2190 assert(ss.front == 5); 2191 ss.popFront; 2192 assert(ss.empty); 2193 assert(ss.front.isNull); 2194 } 2195 /// 2196 unittest 2197 { 2198 2199 auto vT = vebRoot(1000); 2200 assert(vT.capacity == 1024); 2201 assert(vT.front.isNull); 2202 assert(vT.insert(2)); 2203 assert(vT.insert(5)); 2204 assert(!(8 in vT)); 2205 assert(vT.insert(88)); 2206 assert(88 in vT); 2207 assert(vT.predecessor(4) == 2); 2208 assert(!(8 in vT)); 2209 assert(vT.insert(8)); 2210 assert(8 in vT); 2211 assert(vT.predecessor(75) == 8); 2212 2213 assert(vT.predecessor(90) == 88); 2214 2215 assert(vT.predecessor(7) == 5); 2216 assert(vT.predecessor(4) == 2); 2217 assert(vT.predecessor(2).isNull); 2218 2219 //TODO: reactivate this by slicing assert(vT[].predecessor(2) == 0); 2220 2221 assert(vT.predecessor(2).isNull); 2222 2223 assert(vT.successor(6) == 8); 2224 assert(vT.successor(5) == 8); 2225 2226 assert(vT.successor(4) == 5); 2227 assert(vT.successor(1) == 2); 2228 assert(vT.successor(75) == 88); 2229 assert(vT.successor(90).isNull); 2230 //TODO: reactivate this by slicing assert(vT[].successor(90) == vT.universe); 2231 2232 assert(!(1029 in vT)); 2233 2234 assert(vT.successor(1025).isNull); 2235 assert(vT.successor(1025).isNull); 2236 2237 auto vT2 = vebRoot(500); 2238 assert(vT2.empty); 2239 vT2.insert(50); 2240 vT2.insert(500); 2241 assert(vT2.back == 500); 2242 assert(vT2.front == 50); 2243 assert(vT2.successor(40) == 50); 2244 assert(vT2.successor(50) == 500); 2245 2246 vT2 = vebRoot(500); 2247 assert(vT2.empty); 2248 vT2.insert(50); 2249 vT2.insert(500); 2250 assert(vT2.back == 500); 2251 assert(vT2.front == 50); 2252 assert(vT2.successor(40) == 50); 2253 assert(vT2.successor(50) == 500); 2254 2255 /* about 20 seconds in debug mode. 2256 auto vT3 = vebRoot(halfSizeT.max); 2257 assert(vT3.insert(5)); 2258 assert(vT3.member(5)); 2259 assert(vT3.capacity == cast(ulong)halfSizeT.max + 1UL); 2260 //*/ 2261 2262 assert(!(1029 in vT)); 2263 assert(!(865 in vT)); 2264 assert(vT.insert(865)); 2265 assert(865 in vT); 2266 assert(!vT.insert(865)); 2267 assert(865 in vT); 2268 assert(!(866 in vT)); 2269 assert(!vT.remove(866)); 2270 assert(865 in vT); 2271 assert(vT.remove(865)); 2272 assert(!(865 in vT)); 2273 2274 } 2275 2276 /// 2277 unittest 2278 { 2279 auto currentSeed = unpredictableSeed(); 2280 static if(vdebug){write("UT: rand, succ "); writeln("seed: ", currentSeed);} 2281 rndGenInUse.seed(currentSeed); //initialize the random generator 2282 2283 size_t M = uniform(2U,testedSize, rndGenInUse); //set universe size to some integer. 2284 auto vT = vebRoot(M); //create the tree 2285 assert(vT.capacity == nextPow2(M-1)); 2286 2287 auto filled = M.iota.map!(i => vT.insert(uniform(0, vT.universe, rndGenInUse))).sum; 2288 assert(filled == vT.length); 2289 2290 size_t n; 2291 auto i = vT.back; 2292 2293 // discover the thousend (or little less) values with the predecessor method 2294 while(!i.isNull) 2295 { 2296 ++n; 2297 i = vT.predecessor(i); 2298 if(n > filled) break; 2299 } 2300 2301 size_t o; 2302 i = vT.front; 2303 while(!i.isNull) 2304 { 2305 ++o; 2306 i = vT.successor(i.get); 2307 if(o - 1 > filled) break; 2308 } 2309 2310 // assert, that all members are discovered, iff when no predecessors are left 2311 assert(n == filled); 2312 assert(o == filled); 2313 } 2314 2315 /// 2316 unittest 2317 { 2318 auto currentSeed = unpredictableSeed(); 2319 static if(vdebug){write("UT: rand, pred "); writeln("seed: ", currentSeed);} 2320 rndGenInUse.seed(currentSeed); //initialize the random generator 2321 size_t M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 2322 auto vT = vebRoot(M); 2323 assert(M.iota.map!(i => vT.insert(uniform(0, vT.universe, rndGenInUse))).sum == vT.length); 2324 auto i = vT.back; 2325 2326 // remove all members beginning from the maximum 2327 bool result; 2328 while(!i.isNull) 2329 { 2330 result = vT.remove(i); 2331 assert(result); 2332 auto j = vT.predecessor(i); 2333 if(!j.isNull) 2334 assert(j != i); 2335 i = j; 2336 } 2337 2338 // assert, that all members are removed, iff when no predecessors are left. 2339 assert(vT.empty); 2340 } 2341 2342 /// 2343 unittest 2344 { 2345 auto currentSeed = unpredictableSeed(); 2346 static if(vdebug){write("UT: rand, remove "); writeln("seed: ", currentSeed);} 2347 rndGenInUse.seed(currentSeed); //initialize the random generator 2348 size_t M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 2349 auto vT = vebRoot(M); 2350 assert(M.iota.map!(i => vT.insert(uniform(0, vT.universe, rndGenInUse))).sum == vT.length); 2351 auto i = vT.front; 2352 2353 // remove all members beginning from the minimum 2354 bool result; 2355 while(!i.isNull) 2356 { 2357 result = vT.remove(i); 2358 assert(result); 2359 auto j = vT.successor(i); 2360 if(!j.isNull) 2361 assert(j != i); 2362 i = j; 2363 } 2364 2365 // assert, that all members are removed, iff when no successors are left. 2366 assert(vT.empty); 2367 } 2368 2369 /// 2370 unittest 2371 { 2372 size_t M = testedSize; 2373 auto vT = vebRoot(M); 2374 vT.insert(0x000f); 2375 assert(vT.predecessor(0x000f).isNull); 2376 vT.insert(0x00f0); 2377 assert(vT.predecessor(0x00f0) == 0x000f); 2378 vT.insert(0x0f00); 2379 assert(vT.predecessor(0x0f00) == 0x00f0); 2380 vT.insert(0xf000); 2381 assert(vT.predecessor(0xf000) == 0x0f00); 2382 2383 auto result = vT.remove(0xf000); 2384 assert(result); 2385 assert(vT.predecessor(0xf000) == 0x0f00); 2386 result = vT.remove(0x0f00); 2387 assert(result); 2388 assert(vT.predecessor(0x0f00) == 0x00f0); 2389 result = vT.remove(0x00f0); 2390 assert(result); 2391 assert(vT.predecessor(0x00f0) == 0x000f); 2392 result = vT.remove(0x000f); 2393 assert(result); 2394 assert(vT.predecessor(0x000f).isNull); 2395 } 2396 2397 /// 2398 unittest 2399 { 2400 size_t M = testedSize; 2401 auto vT = vebRoot(M); 2402 vT.insert(0xf000); 2403 assert(0xf000 in vT); 2404 vT.insert(0x0f00); 2405 assert(0x0f00 in vT); 2406 vT.insert(0x00f0); 2407 assert(0x00f0 in vT); 2408 vT.insert(0x000f); 2409 assert(0x000f in vT); 2410 2411 auto result = vT.remove(0xf000); 2412 assert(result); 2413 assert(!(0xf000 in vT)); 2414 result = vT.remove(0x0f00); 2415 assert(result); 2416 assert(!(0x0f00 in vT)); 2417 result = vT.remove(0x00f0); 2418 assert(result); 2419 assert(!(0x00f0 in vT)); 2420 result = vT.remove(0x000f); 2421 assert(result); 2422 assert(!(0x000f in vT)); 2423 } 2424 2425 /// 2426 unittest 2427 { 2428 //stress test 2429 auto currentSeed = unpredictableSeed(); 2430 static if(vdebug){write("UT: rand, stress "); writeln("seed: ", currentSeed);} 2431 rndGenInUse.seed(currentSeed); //initialize the random generator 2432 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 2433 // last test says: see below. 2434 size_t M = uniform(2U, allowedArraySize, rndGenInUse); // set universe size to some integer. 2435 auto vT = vebRoot(M); 2436 2437 size_t[] arr; 2438 arr.length = 31 * vT.capacity/typeof(vT).sizeof; 2439 (vT.capacity - 1).iota.randomCover(rndGenInUse).take(arr.length) 2440 .enumerate 2441 .tee!(el => arr[el.index] = el.value) 2442 .each!(el => vT.insert(el.value)); 2443 2444 auto vT2 = vebRoot(M); 2445 2446 assert(vT2.capacity == vT.capacity); 2447 2448 auto rbt = redBlackTree!size_t(0); 2449 rbt.clear; 2450 2451 void fill1() 2452 { 2453 foreach(size_t i; arr) 2454 { 2455 vT2.insert(i); 2456 } 2457 2458 foreach(size_t i; arr) 2459 { 2460 vT2.remove(i); 2461 } 2462 assert(vT2.empty); 2463 2464 } 2465 2466 void fill2() 2467 { 2468 foreach(size_t i; arr) 2469 { 2470 rbt.insert(i); 2471 } 2472 } 2473 2474 /* 2475 this part is for speed test 2476 */ 2477 /* 2478 compiled with ldc2 vebtree.d -O -main -unittest 2479 results of stress tests: 2480 size of tree: 16777216 2481 howMuchFilled: 16252928 2482 VEB: 2 secs, 382 ms, 588 μs, and 8 hnsecs 2483 */ 2484 /* 2485 2486 writeln("size of tree: ", vT2.capacity); 2487 writeln("howMuchFilled: ", howMuchFilled); 2488 //auto r = benchmark!(fill1, fill2)(1); 2489 auto r = benchmark!(fill1)(1); 2490 2491 auto f0Result = to!Duration(r[0]); 2492 //auto f1Result = to!Duration(r[1]); 2493 writeln("VEB: ", f0Result); //10ms 2494 //writeln("rbt: ", f1Result); //40sec 2495 //assert(f0Result < f1Result); 2496 //*/ 2497 } 2498 2499 /// 2500 unittest 2501 { 2502 auto currentSeed = unpredictableSeed(); 2503 static if(vdebug){write("UT: rand, member "); writeln("seed: ", currentSeed);} 2504 rndGenInUse.seed(currentSeed); //initialize the random generator 2505 size_t M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 2506 size_t[] sourceArr; 2507 sourceArr.length = M; 2508 // generate a random array as the source for the tree 2509 iota(M).each!(i => sourceArr[i] = uniform(0U, M, rndGenInUse)); 2510 // make the array values unique. 2511 auto uniqueArr = sourceArr.sort.uniq; 2512 // constructor to test 2513 auto vT = vebRoot(sourceArr.length); 2514 uniqueArr.each!(el => vT.insert(el)); 2515 // check, that all values are filled 2516 bool result; 2517 foreach(i; uniqueArr) 2518 { 2519 assert(i in vT); 2520 result = vT.remove(i); 2521 assert(result); 2522 } 2523 // check, that no other elements are present. 2524 assert(vT.empty); 2525 } 2526 2527 /// 2528 unittest 2529 { 2530 auto currentSeed = unpredictableSeed(); 2531 static if(vdebug){write("UT: rand, opSlice "); writeln("seed: ", currentSeed);} 2532 rndGenInUse.seed(currentSeed); //initialize the random generator 2533 // do not use more then "1 << 16", as for the red-black tree the insertion duration is almost 4 (!) minutes. 2534 size_t M = uniform(2U, allowedArraySize, rndGenInUse); // set universe size to some integer. 2535 auto vT = vebRoot(M); 2536 size_t[] arr; 2537 arr.length = 16 * vT.capacity/typeof(vT).sizeof; 2538 (vT.capacity - 1).iota.randomCover(rndGenInUse).take(arr.length) 2539 .enumerate 2540 .tee!(el => arr[el.index] = el.value) 2541 .each!(el => vT.insert(el.value)); 2542 2543 assert(setSymmetricDifference(vT(), arr.sort).empty); 2544 } 2545 2546 /// 2547 unittest 2548 { 2549 static assert(!isInputRange!(VEBroot!())); 2550 static assert(isIterable!(VEBroot!())); 2551 static assert(isBidirectionalRange!(typeof(VEBroot!()[]))); 2552 static assert(is(typeof(vebRoot!(size_t)(4)[2]))); 2553 static assert(!is(typeof(vebRoot(4)[2]))); 2554 } 2555 2556 /// 2557 unittest 2558 { 2559 auto vT = vebRoot(14); 2560 auto result = vT.insert(2); 2561 assert(result); 2562 result = vT.insert(5); 2563 assert(result); 2564 result = vT.insert(10); 2565 assert(result); 2566 assert(vT[] == [0, 2, 5, 10, 14]); 2567 assert(vT() == [2, 5, 10]); 2568 } 2569 2570 /// 2571 unittest 2572 { 2573 /* 2574 //another stress test 2575 auto currentSeed = unpredictableSeed(); 2576 static if(vdebug){write("UT: stress test 2 "); writeln("seed: ", currentSeed);} 2577 rndGenInUse.seed(currentSeed); //initialize the random generator 2578 2579 void fill16(){ auto vT = vebRoot(1 << 16); } 2580 void fill17(){ auto vT = vebRoot(1 << 17); } 2581 void fill18(){ auto vT = vebRoot(1 << 18); } 2582 void fill19(){ auto vT = vebRoot(1 << 19); } 2583 void fill20(){ auto vT = vebRoot(1 << 20); } 2584 void fill21(){ auto vT = vebRoot(1 << 21); } 2585 void fill22(){ auto vT = vebRoot(1 << 22); } 2586 void fill23(){ auto vT = vebRoot(1 << 23); } 2587 void fill24(){ auto vT = vebRoot(1 << 24); } 2588 void fill25(){ auto vT = vebRoot(1 << 25); } 2589 void fill26(){ auto vT = vebRoot(1 << 26); } 2590 void fill27(){ auto vT = vebRoot(1 << 27); } 2591 void fill28(){ auto vT = vebRoot(1 << 28); } 2592 void fill29(){ auto vT = vebRoot(1 << 29); } 2593 void fill30(){ auto vT = vebRoot(1 << 30); } 2594 2595 auto r = benchmark!(fill16, fill17, fill18, fill19, fill20, fill21, fill22, fill23, fill24, fill25, fill26, fill27, 2596 fill28, fill29, fill30)(1); 2597 //auto r = benchmark!(fill1)(1); 2598 auto f16Result = to!Duration(r[0]); 2599 auto f17Result = to!Duration(r[1]); 2600 auto f18Result = to!Duration(r[2]); 2601 auto f19Result = to!Duration(r[3]); 2602 auto f20Result = to!Duration(r[4]); 2603 auto f21Result = to!Duration(r[5]); 2604 auto f22Result = to!Duration(r[6]); 2605 auto f23Result = to!Duration(r[7]); 2606 auto f24Result = to!Duration(r[8]); 2607 auto f25Result = to!Duration(r[9]); 2608 auto f26Result = to!Duration(r[10]); 2609 auto f27Result = to!Duration(r[11]); 2610 auto f28Result = to!Duration(r[12]); 2611 auto f29Result = to!Duration(r[13]); 2612 auto f30Result = to!Duration(r[14]); 2613 2614 writeln("VEB with M of ", 1 << 16, ": ", f16Result); 2615 writeln("VEB with M of ", 1 << 17, ": ", f17Result); 2616 writeln("VEB with M of ", 1 << 18, ": ", f18Result); 2617 writeln("VEB with M of ", 1 << 19, ": ", f19Result); 2618 writeln("VEB with M of ", 1 << 20, ": ", f20Result); 2619 writeln("VEB with M of ", 1 << 21, ": ", f21Result); 2620 writeln("VEB with M of ", 1 << 22, ": ", f22Result); 2621 writeln("VEB with M of ", 1 << 23, ": ", f23Result); 2622 writeln("VEB with M of ", 1 << 24, ": ", f24Result); 2623 writeln("VEB with M of ", 1 << 25, ": ", f25Result); 2624 writeln("VEB with M of ", 1 << 26, ": ", f26Result); 2625 writeln("VEB with M of ", 1 << 27, ": ", f27Result); 2626 writeln("VEB with M of ", 1 << 28, ": ", f28Result); 2627 writeln("VEB with M of ", 1 << 29, ": ", f29Result); 2628 writeln("VEB with M of ", 1 << 30, ": ", f30Result); 2629 //*/ 2630 2631 } 2632 2633 /// 2634 unittest 2635 { 2636 //stress test 2637 auto currentSeed = unpredictableSeed(); 2638 static if(vdebug){write("UT: rand, ranges "); writeln("seed: ", currentSeed);} 2639 rndGenInUse.seed(currentSeed); //initialize the random generator 2640 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 2641 // last test says: see below. 2642 size_t M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 2643 auto vT = vebRoot(M); 2644 /*testing the range methods*/ 2645 assert(vT.empty); 2646 2647 size_t[] sourceArr; 2648 sourceArr.length = uniform(2U, M, rndGenInUse); 2649 iota(sourceArr.length).each!(i => sourceArr[i] = uniform(0U, sourceArr.length, rndGenInUse)); 2650 2651 auto uniqueArr = sourceArr.sort.uniq; 2652 2653 // constructor to test 2654 2655 auto vTnew = vebRoot(sourceArr.length); 2656 uniqueArr.each!(el => vTnew.insert(el)); 2657 2658 assert(!vTnew.empty); 2659 assert(vTnew.length == uniqueArr.walkLength); 2660 auto vT2 = vTnew; 2661 static assert(isIterable!(typeof(vTnew))); 2662 auto slice = vTnew(); 2663 assert(slice.front == uniqueArr.front); 2664 assert(vTnew() == uniqueArr); 2665 assert(!vTnew.empty); 2666 assert(!vT2.empty); 2667 2668 size_t N = 100; 2669 auto vT3 = vebRoot(N); 2670 assert(vT3.empty); 2671 auto unique3 = N.iota.map!(i => uniform(0U, N, rndGenInUse)).array.sort.uniq.array; 2672 unique3.each!(u => vT3.insert(u)); 2673 unique3.each!(u => assert(u in vT3)); 2674 assert(vT3.length == unique3.length); 2675 auto sl3 = vT3[]; 2676 2677 if(unique3.front == 0 && unique3.back == vT3.universe) 2678 { 2679 assert(sl3.length == unique3.length); 2680 } 2681 else if(unique3.front == 0 || unique3.back == vT3.universe) 2682 { 2683 assert(sl3.length == unique3.length + 1); 2684 } 2685 else 2686 { 2687 assert(sl3.length == unique3.length + 2); 2688 } 2689 assert(sl3.length); 2690 assert(!sl3.empty); 2691 2692 unique3.each!(u => vT3.remove(u)); 2693 assert(vT3.empty); 2694 2695 //* Works. Duration in debug mode: about 35 seconds. 2696 //auto vTT = vebRoot((size_t(1) << 27) - 1); 2697 //assert(vTT.insert(42)); 2698 //assert(42 in vTT); 2699 //*/ 2700 } 2701 2702 private struct VEBtree(Flag!"inclusive" inclusive, R : Root!Source, alias Root, Source...) 2703 { 2704 static assert(isBidirectionalRange!(typeof(this))); 2705 2706 R root; 2707 2708 auto opBinaryRight(string op)(size_t key) if(op == "in") // @nogc nothrow 2709 { 2710 return key in root; 2711 } 2712 2713 static if(inclusive) 2714 { 2715 size_t frontKey; 2716 size_t backKey; 2717 } 2718 else 2719 { 2720 Response frontKey; 2721 Response backKey; 2722 } 2723 2724 size_t length; 2725 2726 private this(R val) 2727 { 2728 root = val; 2729 length = root.length; 2730 2731 static if(inclusive) 2732 { 2733 if(root.empty) 2734 { 2735 backKey = root.universe; 2736 assert(!length); 2737 length += 2; 2738 } 2739 else 2740 { 2741 if(root.back.get <= root.universe) 2742 { 2743 backKey = root.universe; 2744 if(root.back.get < root.universe) 2745 { 2746 length += 1; 2747 } 2748 } 2749 else 2750 { 2751 assert(root.back.get < root.capacity); 2752 backKey = root.capacity; 2753 length += 1; 2754 } 2755 2756 if(root.front.get) // i. e. front != 0 2757 { 2758 length += 1; 2759 } 2760 } 2761 } 2762 else 2763 { 2764 frontKey = root.front; 2765 backKey = root.back; 2766 } 2767 } 2768 2769 auto front() 2770 { 2771 return frontKey; 2772 } 2773 2774 void popFront() 2775 in 2776 { 2777 assert(!empty); 2778 } 2779 do 2780 { 2781 auto front = root.successor(frontKey.get); 2782 static if(inclusive) 2783 { 2784 if(front.isNull) 2785 { 2786 if(frontKey <= root.universe) 2787 { 2788 frontKey = root.universe; 2789 } 2790 else if(frontKey <= root.capacity) 2791 { 2792 frontKey = root.capacity; 2793 } 2794 else 2795 { 2796 assert(0, "key exceeds tree capacity"); 2797 } 2798 } 2799 else 2800 { 2801 frontKey = front.get; 2802 } 2803 } 2804 else 2805 { 2806 frontKey = front; 2807 } 2808 2809 --length; 2810 } 2811 2812 auto back() 2813 { 2814 return backKey; 2815 } 2816 2817 void popBack() 2818 in 2819 { 2820 assert(length); 2821 } 2822 do 2823 { 2824 auto back = root.predecessor(backKey.get); 2825 static if(inclusive) 2826 { 2827 if(back.isNull) 2828 { 2829 backKey = 0; 2830 } 2831 else 2832 { 2833 backKey = back.get; 2834 } 2835 } 2836 else 2837 { 2838 backKey = back; 2839 } 2840 --length; 2841 } 2842 2843 auto predecessor(size_t key) 2844 { 2845 auto pred = root.predecessor(key); 2846 static if(inclusive) 2847 { 2848 if(pred.isNull) 2849 { 2850 return 0; 2851 } 2852 else 2853 { 2854 return pred.get; 2855 } 2856 } 2857 else 2858 { 2859 return pred; 2860 } 2861 } 2862 2863 auto successor(size_t key) 2864 { 2865 auto succ = root.successor(key); 2866 static if(inclusive) 2867 { 2868 if(succ.isNull) 2869 { 2870 if(key <= root.universe) 2871 { 2872 return root.universe; 2873 } 2874 else if(key <= root.capacity) 2875 { 2876 return root.capacity; 2877 } 2878 else 2879 { 2880 assert(0, "key exceeds tree capacity"); 2881 } 2882 } 2883 else 2884 { 2885 return succ.get; 2886 } 2887 } 2888 else 2889 { 2890 return succ; 2891 } 2892 2893 } 2894 2895 static if(!is(Source[0] == void)) 2896 { 2897 static assert(!is(Source[0] == void)); 2898 auto ref opIndex(size_t key) //@nogc 2899 { 2900 return root[key]; 2901 } 2902 2903 /** 2904 opApply method in case of present source for iterating over key value pairs 2905 */ 2906 int opApply(scope int delegate(size_t, ref Source[0]) /*@nogc*/ operations) //@nogc 2907 { 2908 int result; 2909 2910 //for(auto leading = front; !leading.isNull; leading = successor(leading.get)) 2911 for(auto leading = front; !empty; popFront) 2912 { 2913 result = operations(leading.get, *root[leading.get]); 2914 2915 if(result) 2916 { 2917 break; 2918 } 2919 } 2920 2921 return result; 2922 } 2923 2924 /** 2925 opApply method in case of present source for iterating over key value pairs 2926 */ 2927 int opApply(scope int delegate(size_t) /*@nogc*/ operations) //@nogc 2928 { 2929 int result; 2930 2931 //for(auto leading = front; !leading.isNull; leading = successor(leading.get)) 2932 for(auto leading = front; !empty; popFront) 2933 { 2934 result = operations(leading.get); 2935 2936 if(result) 2937 { 2938 break; 2939 } 2940 } 2941 2942 return result; 2943 } 2944 } 2945 2946 bool empty() 2947 { 2948 return !length; 2949 } 2950 2951 auto save() 2952 { 2953 return this; 2954 } 2955 2956 typeof(this) dup() 2957 { 2958 auto copy = this; 2959 copy.root = root.dup; 2960 return copy; 2961 } 2962 2963 size_t toHash() const 2964 { 2965 assert(0); 2966 } 2967 2968 /** 2969 for comparison with an iterable, the iterable will be iterated, as the current object. If the iterable object is an 2970 input range, it will be destroyed. 2971 */ 2972 bool opEquals(T)(auto ref T input) if(isIterable!T) 2973 { 2974 static if(is(T == typeof(this))) 2975 { 2976 return root == input.root; 2977 } 2978 2979 static if(hasLength!T) 2980 { 2981 if(length != input.length) 2982 { 2983 return false; 2984 } 2985 } 2986 2987 auto copy = this.save; 2988 2989 foreach(el; input) 2990 { 2991 if(el != copy.front.get) 2992 { 2993 return false; 2994 } 2995 copy.popFront; 2996 } 2997 2998 return true; 2999 } 3000 } 3001 3002 private : 3003 size_t get(size_t input) @nogc 3004 { 3005 return input; 3006 } 3007 3008 bool isNull(size_t) @nogc 3009 { 3010 return false; 3011 }