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. As long as the usage is intended to contains keys, as in the 12 current version, this restriction is not only a restriction of the amount of elements but also on the contained 13 element values. 14 For optimization purposes, the size limit is size_t.max/2 + 1. The tree was tested on 64- and 32-bit arch. 15 So the largest element which can be stored is 4.294.967.295 on a 64-bit architecture. 16 */ 17 18 // (optional) todo: provide functionality to contain non-unique keys, i. e. exercise 20.3.1 from Cormen 19 20 /** 21 The library is supposed to contain a tree on keys only, for the data could be managed outside. Then, there could be 22 a simple method to combine the keys and the data together. 23 */ 24 25 /** 26 The main advantage of the Van Emde Boas tree appears on a large amount of elements, as the provided standard 27 operations of the tree are constant in time and of order O(lg2(lg2(U))), where U is the capacity of the tree. For 28 small amount of elements the overhead coming along with the structure take over. For example, for a universe size of 29 2^14 and 15872 insertion operatios the duration for the Van Emde Boas tree is about 1*10^(-3) times smaller. As one 30 of the unittests shows. 31 */ 32 33 /** 34 Be aware, the current container is intended to be used with keys. This implies, that the capacity, fixed on its 35 initialization has two meanings. As usual, it shows the maximum amount of elements the instanciated tree can keep. 36 But also, it states, that no value bigger then capacity - 1 exists in the tree. This, and the fact, that only 37 non-negative values can be used are infered from the term "key". 38 */ 39 40 /** 41 See_also: Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. 2001. <em>Introduction to 42 Algorithms</em> (2nd ed.). McGraw-Hill Higher Education. 43 */ 44 45 /** 46 As an important optimization a bottom out technique is used to compactify the tree to the level of nodes, where bit 47 operations become possible. As a side effect, the optimization now relies on the underlying architecture. This leads 48 to the fact, that the maximum of elements which can be stored is 49 2^16 on a 32-bit architecture and 50 2^32 on a 64-bit architecture. 51 This was intentionally chosen for two reasons: 52 i) to keep the size of a single node also depending from the underlying architecture. 53 ii) for bitoperations, which the tree is relying on, to use the native word size of the architecture without 54 emulating bigger entities. 55 */ 56 57 module vebtree; 58 59 import std.typecons; // used for Nullable 60 import core.bitop; // used for bit operations 61 import std.bitmanip; // used for bitfields 62 import std.traits; // used for generating the tree given an iterable 63 64 private enum vdebug = false; 65 66 version(unittest) 67 { 68 static if(vdebug){import std.stdio;} 69 import std.range; 70 import std.algorithm; 71 import std.random; 72 import std.datetime; 73 import std.conv : to; 74 import std.container; // red black tree may be used in unittests for comparison. 75 import std.math : sqrt; 76 size_t[] powersOfTwo = iota(0, 8 * size_t.sizeof).map!(a => size_t(1) << a).array; 77 Random rndGenInUse; 78 79 // helping function for output a given value in binary representation 80 static if(vdebug) 81 { 82 void bin(size_t n) 83 { 84 /* step 1 */ 85 if (n > 1) bin(n/2); 86 /* step 2 */ 87 write(n % 2); 88 } 89 } 90 91 // during tests it is ok a tree with a random capacity not going up to the maximum one. 92 enum testedSize = 1 << 2 * size_t.sizeof; //3 * size_t.sizeof; 93 // during tests helping static arrays are used, which have an absolute maximum of size_t.sizeof * 2^20 elements 94 enum allowedArraySize = 1 << size_t.sizeof; //(2 * size_t.sizeof + size_t.sizeof/2); 95 // choosed arbitrary, to avoid seg. faults 96 97 //an alternative method to calculate the amount of values contained in the tree. 98 auto elementCount(VEBtree vT){ return vT[].length; } 99 100 // some different filling functions for the tree. This simply tries to fill the tree with random numbers. Duplicates 101 // will be ignored, the given tree is modified. 102 auto fill(VEBtree vT, size_t m, Random rndGenInUse) 103 { 104 size_t n; 105 for(size_t i = 0; i < m; ++i) 106 { 107 auto x = uniform(0, vT.expectedSize, rndGenInUse); 108 // the check for membership is done to add only on inserting to the counter, not just 109 // because visiting the the loop 110 if(!vT.member(x)) 111 { 112 vT.insert(x); 113 ++n; 114 } 115 } 116 return n; 117 } 118 119 // Ditto. This method asserts, that a given filling percentage is achieved. 120 auto fill(VEBtree vT, ref size_t[] arr, Random rndGenInUse, size_t fillPercentage = 31) 121 { 122 size_t n; 123 arr.length = fillPercentage * vT.capacity/32; 124 while(n != fillPercentage * vT.capacity/32) 125 { 126 auto x = uniform(0, vT.capacity - 1, rndGenInUse); 127 // the check for membership is done to add only on inserting to the counter, not just 128 // because visiting the the loop 129 if(!vT.member(x)) 130 { 131 vT.insert(x); 132 arr[n] = x; 133 ++n; 134 } 135 } 136 assert(n == fillPercentage*vT.capacity/32); 137 return n; 138 } 139 } 140 141 /** 142 the baseSize defines the cutoff limit, where the node goes into the bit array mode. It is parametrized on the size 143 of size_t and changes dynamically with the architecture used. 144 */ 145 enum baseSize = 8 * size_t.sizeof; 146 147 /** 148 the maxSize defines the maximum the tree can be constructed with. It is parametrized on the size of size_t and 149 changes dynamically with the architecture used. 150 */ 151 enum maxSize = size_t(1) << baseSize/2; 152 153 /// Convinience function to return the ceiling to the next power of two of the given input. 154 @nogc size_t nPof2(size_t value) 155 in 156 { 157 assert(value != 0); 158 assert(bsr(value) < baseSize - 1); 159 } 160 body { return size_t(1) << (bsr(value) + 1); } 161 /// 162 unittest 163 { 164 const size_t currentSeed = unpredictableSeed(); 165 static if(vdebug){write("UT: nPof2. "); writeln("seed: ", currentSeed);} 166 rndGenInUse.seed(currentSeed); //initialize the random generator 167 const size_t M = uniform(1U,size_t.max/2, rndGenInUse); //set universe size to some integer. 168 169 const auto pOfM = nPof2(M); 170 assert((pOfM & (pOfM-1)) == 0); 171 const auto check = powersOfTwo.until(nPof2(M), OpenRight.no).array; 172 assert(M < check[$-1]); 173 assert(M > check[$-2]); 174 } 175 176 /** 177 This function returns the higher square root of the given input. It is needed in the initialization step 178 of the VEB tree to calculate the number of children of a given layer. And this is the universe size of the 179 summary of a node. The upper square root is defined by 2^{\lceil(\lg u)/2\rceil} 180 */ 181 size_t hSR(size_t value) 182 { 183 return size_t(1) << (bsr(value)/2 + ((bsr(value) & 1) || ((value != 0) && (value & (value - 1))))); 184 } 185 /// 186 unittest 187 { 188 const size_t currentSeed = unpredictableSeed(); 189 static if(vdebug){write("UT: hSR. "); writeln("seed: ", currentSeed);} 190 rndGenInUse.seed(currentSeed); //initialize the random generator 191 const size_t M = uniform(1U,size_t.max/2, rndGenInUse); //set universe size to some integer. 192 auto hSR = hSR(M); 193 194 assert((hSR & (hSR - 1)) == 0); 195 if(hSR < uint.max) assert(hSR >= sqrt(to!float(M))); 196 197 const auto check = powersOfTwo.until(hSR).array; 198 assert((check[$-1]) * (check[$-1]) < M); 199 } 200 201 /** 202 This function returns the lower square root of the given input. It is needed by the indexing functions 203 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 204 lower square root is defined by 2^{\lfloor(\lgu)/2\rfloor} 205 */ 206 @nogc size_t lSR(size_t value) { return size_t(1) << (bsr(value)/2); } 207 /// 208 unittest 209 { 210 const size_t currentSeed = unpredictableSeed(); 211 static if(vdebug){write("UT: lSR. "); writeln("seed: ", currentSeed);} 212 rndGenInUse.seed(currentSeed); //initialize the random generator 213 const size_t M = uniform(1U,size_t.max/2, rndGenInUse); //set universe size to some integer. 214 auto lSR = lSR(M); 215 216 assert((lSR & (lSR - 1)) == 0); 217 assert(lSR * lSR < M); 218 const auto check = powersOfTwo.find(lSR).array; 219 220 if(lSR < size_t.max/2) assert((check[1]) > sqrt(to!float(M))); 221 } 222 223 /* 224 This is an index function defined as \lfloor x/lSR(u)\rfloor. It is needed to find the appropriate cluster 225 of a element in the tree. It is a part of the ideal indexing function. 226 */ 227 private @nogc size_t high(size_t value, size_t uS) { return value >> (bsr(uS) / 2); } 228 // 229 unittest 230 { 231 const size_t currentSeed = unpredictableSeed(); 232 static if(vdebug){write("UT: high. "); writeln("seed: ", currentSeed);} 233 rndGenInUse.seed(currentSeed); //initialize the random generator 234 const size_t M = uniform(1U,size_t.max/2, rndGenInUse); //set universe size to some integer. 235 const size_t U = nPof2(M); 236 const size_t x = uniform(0U, U, rndGenInUse); 237 238 assert(high(x,U) == x / lSR(U)); 239 } 240 241 /* 242 This is an index function defined as fmod(value, lSR(uS)). It is needed to find the appropriate 243 value inside a cluster. It is part of the ideal indexing function 244 */ 245 private @nogc size_t low(size_t value, size_t uS) { return value & ((size_t(1) << (bsr(uS) / 2)) - 1); } 246 // 247 unittest 248 { 249 const size_t currentSeed = unpredictableSeed(); 250 static if(vdebug){write("UT: low. "); writeln("seed: ", currentSeed);} 251 rndGenInUse.seed(currentSeed); //initialize the random generator 252 const size_t M = uniform(1U,size_t.max/2, rndGenInUse); //set universe size to some integer. 253 const size_t U = nPof2(M); 254 const size_t x = uniform(0U, U, rndGenInUse); 255 256 assert(low(x, U) == (x & (lSR(U) - 1))); 257 } 258 259 /* 260 This is an index function to retain the searched value. It is defined as x * lSR(u) + y. Beyond this, the 261 relation holds: x = index(high(x), low(x)). This is the ideal indexing function of the tree. 262 */ 263 private @nogc size_t index(size_t uS, size_t x, size_t y){ return (x * lSR(uS) + y); } 264 // 265 unittest 266 { 267 const size_t currentSeed = unpredictableSeed(); 268 static if(vdebug){write("UT: index. "); writeln("seed: ", currentSeed);} 269 rndGenInUse.seed(currentSeed); //initialize the random generator 270 const size_t M = uniform(0U,size_t.max/2, rndGenInUse); //set universe size to some integer. 271 272 const size_t U = nPof2(M); 273 const size_t x = uniform(0U, U, rndGenInUse); 274 275 assert(index(U, high(x, U), low(x, U)) == x); 276 } 277 278 /** 279 This is the struct to represent a VEB tree node. As memebers it contains a value and a pointer to the children 280 array. As the pointer does not know the size of the array, it has to be passed in all methods, which require an 281 access to it. 282 Dependent from the (universe) size passed in a method the stored value will be interpretated in two different ways: 283 If the parameter passed shows, that the universe size is below the bit size of the stored value, then, it can be 284 handled as a bit array and all operations decay to operations defined in core.bitop. This case correspond to 285 the state of the node being a leaf. No children exist and the pointer should stay uninitialized 286 Otherwise, the value is interpretated as two values, the minimum and maximum stored at the same place in memory. The 287 minimum and maximum shows, which range is achievable through this node. The parameters passed to a function of the 288 node have to be well chosen, to hit the appropriate child. 289 The first element of the children array, if present is handled different. According to literature, it has the role 290 of the summary of the remaining children cluster. With it help it is possible to achieve a very small recursion 291 level during an access. 292 */ 293 private struct VEBnode 294 { 295 /* 296 This pointer acts as an array to nodes like this one. As the universe size is not provided, the length of the 297 array can not be used to calculate the most of operations, so no explicit array is needed. The only remaining 298 property is whether the pointer is set at all. From this property the node can decide, whether it is a leaf or 299 an intermediate node. 300 */ 301 VEBnode* ptrArr; // the first member behaves different, as the others, as it is the summary node. 302 @property ref VEBnode summary() 303 in { assert(!isLeaf); } 304 body { return ptrArr[0]; } 305 unittest 306 { 307 auto currentSeed = unpredictableSeed(); // 83_843; 898_797_859; 308 static if(vdebug){write("UT: vN, summary. "); writeln("seed: ", currentSeed);} 309 rndGenInUse.seed(currentSeed); //initialize the random generator 310 311 VEBnode vN = VEBnode(512); 312 assert(!vN.isLeaf); 313 vN.ptrArr[0]._val = 73; 314 assert(vN.summary._val == 73); 315 } 316 317 @property VEBnode* cluster() 318 in { assert(!isLeaf); } 319 body { return (ptrArr + 1); } 320 unittest 321 { 322 auto currentSeed = unpredictableSeed(); // 83_843; 898_797_859; 323 static if(vdebug){write("UT: vN, cluster. "); writeln("seed: ", currentSeed);} 324 rndGenInUse.seed(currentSeed); //initialize the random generator 325 326 const auto value = uniform!"[]"(2U, testedSize, rndGenInUse); 327 const auto place = uniform(0U,baseSize, rndGenInUse); 328 329 VEBnode vN = VEBnode(4096); 330 vN.ptrArr[place]._val = value; 331 assert(vN.ptrArr[place]._val == value); 332 assert(vN.cluster[place - 1]._val == value); // the right place: it is the (place - 1) location of clusters 333 vN.cluster[place]._val = 73; 334 } 335 336 /* 337 An unnamed union defines the essential behavior of the node. It is either a real node with a min and a max, or 338 it is a ulong which is handled as a bit array. 339 */ 340 union 341 { 342 /* 343 as the underlying type size_t is chosen. It is the intended choice, as this delivers the maximum storage 344 size without emulation of types, which size is not native to an architecture. 345 As the value behaves different depending on the node being a leaf. A special consideration should be done, 346 how the unset state has to be stored. 347 In case of being a leaf, the value is interpreated as bit vector, storing a "zero" correspond to setting the 348 least bit. So the unset state corresponds to value being zero. 349 In case of being an intermediate node, the both stored values min and max correspond to a range. In this 350 case the state of being unset is modeled by a minimum set to a value greater then the maximum on 351 initialization. 352 For the case a function is queried and the answer correnspond to a state being not set a Nullable.null is 353 returned from the very method. The null value in the Nullable type doesn't need to enlarge it, as on every 354 architecture all values beyond 2^(8 * size_t.sizeof / 2) - 1 stays unused It is not possible to construct 355 a tree large enough to contain these values. Due this fact the null-value for the Nullable is chosen to 356 2^(8 * size_t.sizeof / 2) 357 */ 358 size_t _val; 359 mixin(bitfields!( 360 size_t, "_min", baseSize/2, // the default value of the min is greater then the max. 361 size_t, "_max", baseSize/2 362 )); 363 } 364 365 /* 366 It is not allowed to construct a node without providing the current universe size as it has to be known on 367 creation whether the children nodes have to be constructed. So, the default case is forbidden, as the children 368 may not appended beyond the knowledge of the constructor. 369 */ 370 @disable this(); 371 /* 372 Node constructor. A universe size provided, if the size is below the cutoff there is nothing to be done, as the 373 underlying value created and set to zero by default. 374 If otherwise create an array of children. This array has to be (according to Cormen) of size of higher square 375 root of the current universe size + 1. The extra place is reserved for the summary. 376 For each just created child call its constructor. 377 For the summary with the universe size of the higher square root of the current universe size. 378 For each other child with the universe size of the lower square root of the currennt universe size. 379 Then, assign the fully initialized children array to the pointer in the current node, doing approprate steps to 380 show, that this node is an intermediate node, not containing any values yet. 381 The knowledge of the current universe size is lost at this moment. As this keeps every build up node smaller 382 (and there could be a lot of them). This is why, the VEBtree class continues to hold the global universe size, 383 which is passed on every call to the root node. In this way this, extern saved value has the role of being 384 outsourced array size for each (!) node in the tree, as its size is reconstructed during the access to them. 385 */ 386 this(size_t uS) 387 { 388 if(uS > baseSize) 389 { 390 VEBnode[] tmp; 391 tmp.reserve(hSR(uS) + 1); // reserve enough place for the summary and the children cluster 392 tmp ~= VEBnode(hSR(uS)); // add the summary with its universe of higher squaure root of the current universe 393 for(size_t i = 1; i <= hSR(uS); ++i) 394 tmp ~= VEBnode(lSR(uS)); // add higher square root children with lower square root universe each. 395 ptrArr = tmp.ptr; // save the pointer to the array, loosing the information about its length. 396 nullify; // set the value to the sentinel value to represent the empty state. 397 } 398 // else nothing todo. 399 } 400 unittest 401 { 402 auto currentSeed = unpredictableSeed(); 403 static if(vdebug){write("UT: vN, __ctor. "); writeln("seed: ", currentSeed);} 404 rndGenInUse.seed(currentSeed); //initialize the random generator 405 406 const auto uS = uniform!"[]"(2U, testedSize, rndGenInUse); 407 408 const VEBnode vN = VEBnode(uS); 409 if(uS <= baseSize) 410 { 411 assert(vN.isLeaf); 412 assert(vN._val == 0); 413 assert(vN.ptrArr == null); 414 } 415 else 416 { 417 assert(!vN.isLeaf); 418 assert(vN._val == 1); 419 assert(vN.ptrArr != null); 420 } 421 } 422 423 /* convinience method to check, if the node belongs to the lowest level in the tree */ 424 @nogc @property bool isLeaf() const { return ptrArr == null; } 425 426 /* method to check whether the current node holds a value */ 427 @nogc @property bool isNull() const { return isLeaf ? (_val == 0) : (_min > _max); } 428 429 /* method executing the appropriate steps to nullify the current node */ 430 @nogc @property void nullify() { _val = isLeaf ? 0 : 1; } 431 432 /* 433 method returning either the lower part of the stored value (intermediate node) or the lowest bit set (bit vector 434 mode. If the node does not contain any value (min > max or value == 0) Nullable.null is returned. 435 */ 436 @property Nullable!(size_t, maxSize) min() 437 { 438 // define the result as a nullable 439 Nullable!(size_t, maxSize) retVal; 440 /* 441 we have only a chance to get a value, if a value is present. 442 if it is a leaf, handle the val as a bit array and find the first bit set from the right. 443 if it is not a leaf, get the minimum. 444 */ 445 if(!isNull) retVal = isLeaf ? bsf(_val) : _min; 446 // return the result, even if it was not set to a value. 447 return retVal; 448 } 449 450 /* 451 setter for the min, setting either the lowest bit or the min part of the value. 452 */ 453 @property void min(size_t value) 454 { 455 if(isLeaf) 456 { 457 assert(min > value); 458 insert(value); 459 } 460 else 461 { 462 // the passed value should not exceed the allowed size of a size/2 463 assert(value < maxSize); 464 _min = value; 465 } 466 } 467 468 /* 469 method returning either the higher part of the stored value (intermediate node) or the highest bit set (bit 470 vector mode. If the node does not contain any value (min > max or value == 0) Nullable.null is returned. 471 */ 472 @property Nullable!(size_t, maxSize) max() 473 { 474 // define the result as a nullable 475 Nullable!(size_t, maxSize) retVal; 476 /* 477 we have only a chance to get a value, if a value is present. 478 if it is a leaf, handle the val as a bit array and find the first bit set from the left. 479 if it is not a leaf, get the max. 480 */ 481 if(!isNull) retVal = isLeaf ? bsr(_val) : _max; 482 // return the result, even if it was not set to a value. 483 return retVal; 484 } 485 486 /* 487 setter for the max, setting either the highest bit or the max part of the value. 488 */ 489 @property void max(size_t value) 490 { 491 if(isLeaf) 492 { 493 assert(max < value); 494 insert(value); 495 } 496 else 497 { 498 // the passed value should not exceed the allowed size of a size/2 499 assert(value < maxSize); 500 _max = value; 501 } 502 } 503 504 /* 505 member method for the case universe size < base size. Overloads by passing only one parameter, which is 506 the bit number of interest. Returns whether the appropriate bit inside the bitvector is set. 507 */ 508 bool member(size_t bitnum) 509 in 510 { 511 // method inside the node defined on leafs only. 512 assert(isLeaf); 513 // when a bitnum is passed to the leaf, then, it is an index to the bitarray and has to be in proper range 514 assert(bitnum < baseSize); 515 } 516 body { return bt(&_val, bitnum) != 0; } 517 // 518 unittest 519 { 520 auto currentSeed = unpredictableSeed(); // 83_843; 898_797_859; 521 static if(vdebug){write("UT: vN, member. "); writeln("seed: ", currentSeed);} 522 rndGenInUse.seed(currentSeed); //initialize the random generator 523 524 const auto value = uniform(0U,size_t.max, rndGenInUse); 525 const auto bitNum = uniform(0U,baseSize, rndGenInUse); 526 VEBnode vN = VEBnode(baseSize); 527 vN._val = value; 528 529 if((vN._val & size_t(1) << bitNum) != 0 ) assert(vN.member(bitNum)); 530 if((vN._val & size_t(1) << bitNum) == 0 ) assert(!vN.member(bitNum)); 531 } 532 533 /* 534 member method. this method is called from class with a universe size given. It performs recursion calls until 535 the universe size is reduced to the base size. Then the overloaded member method is called. 536 */ 537 bool member(size_t value, size_t uS) 538 { 539 if(uS <= baseSize) return member(value); // do not use other functionality any more, if descended so far. 540 541 if(this.isNull) return false; // if an empty intermediate node is found, nothing is stored below it. 542 if(value == this.min || value == this.max) return true; // case of a single valued range. 543 544 /* 545 else we have to descend, using the recursive indexing: 546 1. take the high(value, uS)-th child and 547 2. ask it about the reduced low(value, uS) value 548 3. use the lSR(uS) universe size of the childe node. 549 */ 550 return cluster[high(value, uS)].member(low(value, uS), lSR(uS)); 551 } 552 553 /* 554 insert method. given a leaf, sets the bit and returns, whether the bit was unset. Overloads by passing only one 555 parameter, which is the bit number of interest. 556 */ 557 bool insert(size_t bitnum) 558 in 559 { 560 // method inside the node defined on leafs only. 561 assert(isLeaf); 562 // when a bitnum is passed to the leaf, then, it is an index to the bitarray and has to be in proper range 563 assert(bitnum < baseSize); 564 } 565 body { return bts(&_val, bitnum) == 0; } 566 567 /* 568 insert method. this method is called from class with a universe size given. It performs recursion calls untill 569 the universe size is reduced to the base size. Then the overloaded insert method is called. 570 */ 571 bool insert(size_t value, size_t uS) 572 { 573 import std.algorithm.comparison : min, max; 574 575 if(uS <= baseSize) return this.insert(value); // if descended so far, do not use other functionality any more. 576 577 if(this.isNull) // if the current node does not contain anything put the value inside. 578 { 579 this.min = value; // the setters of min handle the value appropriately and do not need the universe size 580 this.max = value; // being explicitely provided, as they can check the isLeaf property. 581 assert(!this.isNull); 582 return true; 583 } 584 585 assert(!this.isNull); 586 assert(!this.min.isNull); 587 assert(!this.max.isNull); 588 589 if(value == this.min || value == this.max) return false; // return, if value is already here. 590 591 if(this.min == this.max) // if the node contains a single value only, expand the node to a range and leave. 592 { 593 this.min = min(this.min, value); 594 this.max = max(this.max, value); 595 return true; 596 } 597 /* 598 if none of the cases above was true (all of them are break conditions) we have to compare the given value 599 with the values present and adapt the range limits. This replaces the value we want to insert. 600 */ 601 // a swap can not be used here, as min is itself a (property) method 602 if(value < this.min) {const auto tmp = value; value = this.min.get; this.min = tmp; } 603 // a swap can not be used here, as max is itself a (property) method 604 if(value > this.max) {const auto tmp = value; value = this.max.get; this.max = tmp; } 605 606 // calculate the index of the children cluster by high(value, uS) we want to descent to. 607 auto nextTreeIndex = high(value, uS); 608 609 // if the child is happened to be null we have to update the summary and insert value of high(value, uS) into it 610 if(cluster[nextTreeIndex].isNull) summary.insert(high(value, uS), hSR(uS)); 611 612 // in any case we pass the lowered value low(value, uS) to the child. 613 auto res = cluster[nextTreeIndex].insert(low(value, uS), lSR(uS)); 614 return res; 615 } 616 617 /* 618 remove method. given a leaf, remove the bit and returns, whether the bit was set. Overloads by passing only one 619 parameter, which is the bit number of interest. 620 */ 621 bool remove(size_t bitnum) 622 in 623 { 624 assert(isLeaf); 625 assert(bitnum < baseSize); 626 } 627 body { return btr(&_val, bitnum) != 0; } 628 629 /* 630 remove method. this method is called from class with a universe size given. It performs recursion calls untill 631 the universe size is reduced to the base size. Then the overloaded remove method is called. 632 */ 633 bool remove(size_t value, size_t uS) 634 { 635 if(uS <= baseSize) return this.remove(value); // if descended so far, do not use other functionality any more. 636 if(this.isNull) return false; // if the current node is null, there is nothing to remove. 637 if(this.min == this.max) // if the current node contains only a single value 638 { 639 if(this.min != value) return false; // do nothing if the given value is not the stored one 640 this.nullify; // set this node to the sentinel-null if it does. 641 return true; 642 } 643 if(value == this.min) // if we met the minimum of a node 644 { 645 auto treeOffset = summary.min; // calculate an offset from the summary to continue with 646 if(treeOffset.isNull) // if the offset is invalid, then there is no further hierarchy and we are going to 647 { 648 this.min = this.max; // store a single value in this node. 649 return true; 650 } 651 auto min = cluster[treeOffset].min; // otherwise we get the minimum from the offset child 652 cluster[treeOffset].remove(min, lSR(uS)); // remove it from the child 653 654 // if it happens to become null during the remove process, we also remove the offset entry from the summary 655 if(cluster[treeOffset].isNull) summary.remove(treeOffset, hSR(uS)); 656 657 //anyway, the new min of the current node become the restored value of the calculated offset. 658 this.min = index(uS, treeOffset, min); 659 660 return true; 661 } 662 if(value == this.max) // if we met the maximum of a node 663 { 664 auto treeOffset = summary.max; // calculate an offset from the summary to contiue with 665 if(treeOffset.isNull) // if the offset is invalid, then there is no further hierarchy and we are going to 666 { 667 this.max = this.min; // store a single value in this node. 668 return true; 669 } 670 671 auto max = cluster[treeOffset].max; // otherwise we get maximum from the offset child 672 cluster[treeOffset].remove(max, lSR(uS)); // remove it from the child 673 674 // if it happens to become null during the remove process, we also remove the offset enty from the summary 675 if(cluster[treeOffset].isNull) summary.remove(treeOffset, hSR(uS)); 676 677 // anyway, the new max of the current node become the restored value of the calculated offset. 678 this.max = index(uS, treeOffset, max); 679 return true; 680 } 681 682 // if no condition was met we have to descend deeper. We get the offset by reducing the value to high(value, uS) 683 auto treeOffset = high(value, uS); 684 // and remove low(value, uS) from the offset child. 685 const bool retVal = cluster[treeOffset].remove(low(value, uS), lSR(uS)); 686 // if the cluster become null during the remove process we have to update the summary node. 687 if(cluster[treeOffset].isNull) summary.remove(treeOffset, hSR(uS)); 688 689 return retVal; 690 } 691 692 /* 693 predecessor method. given a leaf, returns the previous set bit if exists, otherwise Nullable.null. Overloads by 694 passing only one parameter, which is the bit number of interest. 695 */ 696 Nullable!(size_t, maxSize) predecessor(size_t bitNum) 697 in 698 { 699 assert(isLeaf); 700 assert(bitNum < baseSize); 701 } 702 body 703 { 704 Nullable!(size_t, maxSize) retVal; 705 706 if(!isNull && (bitNum != 0)) 707 { 708 // create a mask, which hides all higher bits of the stored value down to the given bit number, then apply 709 // bit search from the highest bit. 710 auto maskedVal = _val & ((size_t(1) << bitNum) - 1); 711 if(maskedVal != 0) retVal = bsr(maskedVal); 712 } 713 return retVal; 714 } 715 // 716 unittest 717 { 718 const size_t currentSeed = 3163857753U; unpredictableSeed(); 719 static if(vdebug){write("uT: vN, predecessor. "); writeln("seed: ", currentSeed);} 720 rndGenInUse.seed(currentSeed); //initialize the random generator 721 const size_t v = uniform(2U, testedSize, rndGenInUse); //set universe size to some integer. 722 const size_t x = uniform(1U, baseSize, rndGenInUse); 723 VEBnode vN = VEBnode(baseSize); 724 vN._val = v; 725 726 bool found; 727 728 for(size_t index = x - 1; index >= 0; --index) 729 { 730 if (v & (size_t(1) << index)) 731 { 732 found = true; 733 assert(!vN.isNull); 734 assert(vN.predecessor(x) == index); 735 break; 736 } 737 if(!index) break; 738 } 739 740 if(!found) assert(vN.predecessor(x).isNull); 741 } 742 743 /* 744 predecessor method. this method is called from class with a universe size given. It performs recursion calls 745 until the universe size is reduced to the base size. Then the overloaded predecessor method is called. 746 */ 747 Nullable!(size_t, maxSize) predecessor(size_t value, size_t uS) 748 { 749 Nullable!(size_t, maxSize) retVal; 750 751 if(uS <= baseSize) return predecessor(value); // if descended so far, do not use other functionality any more. 752 if(this.isNull) return retVal; // if this node is empty, no predecessor can be found here or deeper in the tree 753 if(value > this.max) return this.max; // if given value is greater then the stored max, the predecessor is max 754 if(value <= this.min) return retVal; // if given value is less then the min, no predecessor exists. 755 756 /* 757 if none of the break conditions was met we have to descend further into the tree. 758 */ 759 const auto childIndex = high(value, uS); // calculate the child index by high(value, uS) 760 const auto minlow = cluster[childIndex].min; // look into the child for its minimum 761 // if the minimum exists and the lowered given value is greater then the child's minimum 762 if(!minlow.isNull && low(value, uS) > minlow) 763 { 764 // calculate an offset to continue with by asking the child on predecessor of the lowered value. 765 auto offset = cluster[childIndex].predecessor(low(value, uS), lSR(uS)); 766 // the result is given by reconstruction of the answer. 767 retVal = index(uS, childIndex, offset); 768 } 769 else // otherwise we can not use the minimum of the child 770 { 771 // ask the summary for the predecessor cluster. 772 auto predcluster = summary.predecessor(childIndex, hSR(uS)); 773 // if the predecessor cluster is null return the current min, as this is the last remaining value 774 if(predcluster.isNull) return this.min; 775 // if the predecessor cluster exists, the offset is given by its maximum 776 // and the result by the reconstruction of the offset. 777 retVal = index(uS, predcluster, cluster[predcluster].max); 778 } 779 return retVal; 780 } 781 782 /* 783 successor method. given a leaf, returns the next set bit if exists, otherwise Nullable.null. Overloads by 784 passing only one parameter, which is the bit number of interest. 785 */ 786 Nullable!(size_t, maxSize) successor(size_t bitNum) 787 in 788 { 789 assert(isLeaf); 790 assert(bitNum < baseSize); 791 } 792 body 793 { 794 Nullable!(size_t, maxSize) retVal; 795 796 if(!isNull && (bitNum + 1 < baseSize)) 797 { 798 // create a mask, which hides all lower bits of the stored value up to the given bit number, then apply 799 // bit search from the lowest bit. 800 auto maskedVal = _val & ~((size_t(1) << (bitNum + 1)) - 1); 801 if(maskedVal != 0) retVal = bsf(maskedVal); 802 } 803 return retVal; 804 } 805 // 806 unittest 807 { 808 const size_t currentSeed = unpredictableSeed(); 809 static if(vdebug){write("UT: vN, successor. "); writeln("seed: ", currentSeed);} 810 rndGenInUse.seed(currentSeed); //initialize the random generator 811 const size_t v = uniform(0U, size_t.max, rndGenInUse); //set universe size to some integer. 812 const size_t x = uniform(0U, baseSize, rndGenInUse); 813 VEBnode vN = VEBnode(baseSize); 814 vN._val = v; 815 816 bool found; 817 818 for (size_t index = x + 1; index < baseSize; ++index) 819 { 820 if (v & (size_t(1) << index)) 821 { 822 found = true; 823 assert(vN.successor(x) == index); 824 break; 825 } 826 } 827 if(!found) assert(vN.successor(x).isNull); 828 } 829 830 /* 831 successor method. this method is called from class with a universe size given. It performs recursion calls until 832 the universe size is reduced to the base size. Then the overloaded successor method is called. 833 */ 834 Nullable!(size_t, maxSize) successor(size_t value, size_t uS) 835 { 836 Nullable!(size_t, maxSize) retVal; 837 if(uS <= baseSize) return successor(value); // if descended so far, do not use other functionality any more. 838 if(this.isNull) return retVal; // if this node is empty, no successor can be found here or deeper in the tree 839 if(value < this.min) return this.min; // if given value is less then the min, return the min as successor 840 if(value >= this.max) return retVal; // if given value is greater then the max, no predecessor exists 841 842 /* 843 if none of the break conditions was met, we have to descent further into the tree. 844 */ 845 const auto childIndex = high(value, uS); // calculate the child index by high(value, uS) 846 const auto maxlow = cluster[childIndex].max; // look into the child for its maximum 847 // if the maximum exists and the lowered given value is less then the child's maximum 848 if(!maxlow.isNull && low(value, uS) < maxlow) 849 { 850 // calculate an offset to continue with by asking the child on predecessor of the lowered value 851 auto offset = cluster[childIndex].successor(low(value, uS), lSR(uS)); 852 // the result is given by reconstruction of the answer 853 retVal = index(uS, childIndex, offset); 854 } 855 else // otherwise we can not use the maximum of the child 856 { 857 // ask the summary for the successor cluster. 858 auto succcluster = summary.successor(childIndex, hSR(uS)); 859 // if the successor cluster is null 860 if(succcluster.isNull) return this.max; // return the current max, as this is the last remaining value 861 // if the successor cluster exists, the offset is given by its minimum 862 // and the result by the reconstruction of the offset. 863 retVal = index(uS, succcluster, cluster[succcluster].min); 864 } 865 return retVal; 866 } 867 } 868 869 /// 870 unittest 871 { 872 VEBnode vN = VEBnode(baseSize); 873 static assert(vN.sizeof < baseSize/2); 874 assert(vN.isNull); 875 assert(vN.sizeof == 2 * size_t.sizeof); 876 assert(vN.isLeaf); 877 assert(vN.isNull); 878 vN._val = 3; 879 assert(vN._min == 3); 880 assert(vN.member(1)); 881 assert(!vN.member(2)); 882 assert(vN.isLeaf); 883 assert(vN.ptrArr == null); 884 vN.nullify; 885 assert(vN.isNull); 886 assert(vN._val == 0); 887 } 888 889 /** 890 This class represents the VEB tree itself. It saves the provided at the initialization step wished size. The 891 generated tree has the capacity of the next higher power of 2. Beyond this, it stores the root element, through 892 which all accesses to the tree are managed. The tree implements also the interface for being a bidirectional range. 893 */ 894 class VEBtree 895 { 896 // the root element of the tree. 897 private VEBnode root; 898 // this member is updated on every insertion and deletion to give the current element count on O(1) 899 private size_t _elementCount; 900 /// this member stores the initialization size, as it would be lost forever after initialization, otherwise 901 immutable size_t expectedSize; 902 903 /// default constructor of a VEB tree is disabled. 904 @disable this(); 905 906 /** 907 to construct a VEB tree the wished size has to be provided. However, the size should be greater then one and 908 should not excess the maximum allowed size for the current architecture. 909 */ 910 this(size_t value) 911 in 912 { 913 assert(value > 1); 914 assert(value <= maxSize); 915 } 916 body 917 { 918 // set the expected size to the passed value 919 expectedSize = value; 920 921 // delegate the creation of the nodes with the apropriate power of two of the needed universe size 922 root = VEBnode(nPof2(expectedSize - 1)); 923 924 assert(root.isNull); 925 } 926 /// 927 unittest 928 { 929 auto currentSeed = unpredictableSeed(); // 83_843; 898_797_859; 930 static if(vdebug){write("UT: vT, __ctor. "); writeln("seed: ", currentSeed);} 931 rndGenInUse.seed(currentSeed); //initialize the random generator 932 933 auto uS = uniform(1U << size_t(1),testedSize, rndGenInUse); 934 const VEBtree vT = new VEBtree(uS); 935 assert(vT.root.isNull); 936 if((uS & (uS - 1)) == 0) 937 assert(vT.capacity == uS); 938 else 939 assert(vT.capacity == (size_t(1) << (bsr(uS) + 1))); 940 941 assert(vT.expectedSize == uS); 942 943 const auto uS1 = uniform(1U << size_t(1),testedSize, rndGenInUse); 944 const auto uSsmall = uniform(1U << size_t(1),baseSize, rndGenInUse); 945 VEBtree vT1 = new VEBtree(uS1); 946 const VEBtree vTsmall = new VEBtree(uSsmall); 947 948 assert(vTsmall.root._val == 0); 949 assert(vTsmall.root.ptrArr == null); 950 951 if(uS1 > 8 * size_t.sizeof) 952 { 953 assert(vT1.root._val == 1); 954 assert(vT1.root.ptrArr != null); 955 956 //check every child for consistency. 957 // the size of a node is higher square root & the summary node. 958 959 // capacity is tested elsewhere. 960 // hSR is also tested elsewhere 961 const auto childsAmount_l1 = hSR(vT1.capacity) + 1; 962 const auto childsAmount_l2 = hSR(lSR(vT1.capacity)) > baseSize ? hSR(lSR(vT1.capacity)) + 1 : 0; 963 964 // the tree is just created, assert all children are nullified 965 for(size_t i; i < childsAmount_l1; ++i) 966 { 967 assert(vT1.root.ptrArr[i].isNull); 968 if(childsAmount_l1 > baseSize + 1) 969 { 970 for(size_t j; j < childsAmount_l2; ++j) 971 { 972 assert(vT1.root.ptrArr[i].ptrArr[j].isNull); 973 } 974 } 975 } 976 } 977 } 978 979 /// another possibility is to construct a VEB tree is by providing an array. 980 this(R)(R range) if(isIterable!R) 981 in 982 { 983 // check, whether the range is not too long. I. e. expressable with an uint. 984 assert(range.length < maxSize); 985 } 986 body 987 { 988 import std.algorithm.comparison : max; 989 990 // first, we have to determine the size of the tree. 991 // it is either derived from the length of the given tree or its greatest element 992 size_t limit; 993 foreach(size_t i; range) limit = max(limit,i); 994 // assert no element has exceeded the allowed range of baseSize/2 995 assert(limit < maxSize); 996 // if the array is longer, then the greatest element, but the length passes, substitute the limit 997 limit = max(limit, range.length); 998 // call the constructor with the limit 999 this(limit + 1); 1000 // put every element from the range into the tree 1001 foreach(size_t i; range) 1002 insert(i); 1003 } 1004 1005 /** 1006 this method returns the capacity of the tree. It is equal to the next power of 2 regarding the size used at 1007 initialization. 1008 */ 1009 size_t capacity() const { return nPof2(expectedSize - 1); } 1010 1011 /** 1012 this method is used to add an element to the tree. duplicate values will be ignored. the class provides an 1013 intermediate layer between the caller and the contained root and enrichs the input by the stored size. 1014 */ 1015 bool insert(size_t value) 1016 { 1017 if(value >= capacity) return false; 1018 const bool retVal = root.insert(value, capacity); 1019 if(retVal) ++_elementCount; 1020 return retVal; 1021 } 1022 /// 1023 unittest 1024 { 1025 auto currentSeed = unpredictableSeed(); 1026 static if(vdebug){write("UT: vT, insert. "); writeln("seed: ", currentSeed);} 1027 rndGenInUse.seed(currentSeed); //initialize the random generator 1028 1029 auto uS = uniform(allowedArraySize,testedSize, rndGenInUse); 1030 VEBtree vT = new VEBtree(uS); 1031 1032 size_t n; 1033 uint[allowedArraySize] insertedVals; 1034 while(n < allowedArraySize) 1035 { 1036 auto valToInsert = uniform(0U, uS, rndGenInUse); 1037 const bool inserted = vT.insert(valToInsert); 1038 if(inserted) 1039 { 1040 insertedVals[n] = valToInsert; 1041 n++; 1042 } 1043 } 1044 assert(vT._elementCount == insertedVals.length); 1045 1046 sort(insertedVals[]); 1047 assert(uniq(insertedVals[]).array.length == insertedVals.length); 1048 } 1049 1050 /// this method overrides the insert method to directly use arrays 1051 void insert(R)(R arr) if(isIterable!R){ foreach(size_t i; arr) insert(i); } 1052 1053 /// this method is used to remove elements from the tree. not existing values will be ignored. 1054 bool remove(size_t value) 1055 { 1056 const bool retVal = root.remove(value, capacity); 1057 if(retVal) --_elementCount; 1058 return retVal; 1059 } 1060 /// 1061 unittest 1062 { 1063 auto currentSeed = unpredictableSeed(); 1064 static if(vdebug){write("UT: vT, remove. "); writeln("seed: ", currentSeed);} 1065 rndGenInUse.seed(currentSeed); //initialize the random generator 1066 1067 auto uS = uniform(allowedArraySize,testedSize, rndGenInUse); 1068 VEBtree vT = new VEBtree(uS); 1069 1070 size_t n; 1071 uint[allowedArraySize] insertedVals; 1072 1073 while(n < allowedArraySize) 1074 { 1075 auto valToInsert = uniform(0U, uS, rndGenInUse); 1076 if(vT.insert(valToInsert)) 1077 { 1078 insertedVals[n] = valToInsert; 1079 n++; 1080 } 1081 } 1082 1083 assert(vT._elementCount == insertedVals.length); 1084 1085 foreach(size_t i; insertedVals) assert(vT.remove(i)); 1086 assert(vT.length == 0); 1087 } 1088 1089 /// this method is used to determine, whether an element is currently present in the tree 1090 bool member(size_t value) 1091 { 1092 if(value >= capacity) return false; 1093 return root.member(value, capacity); 1094 } 1095 /// 1096 unittest 1097 { 1098 auto currentSeed = unpredictableSeed(); 1099 static if(vdebug){write("UT: vT, member. "); writeln("seed: ", currentSeed);} 1100 rndGenInUse.seed(currentSeed); //initialize the random generator 1101 1102 auto uS = uniform(allowedArraySize,testedSize, rndGenInUse); 1103 VEBtree vT = new VEBtree(uS); 1104 1105 size_t n; 1106 uint[allowedArraySize] insertedVals; 1107 while(n < allowedArraySize) 1108 { 1109 auto valToInsert = uniform(0U, uS, rndGenInUse); 1110 if(vT.insert(valToInsert)) 1111 { 1112 insertedVals[n] = valToInsert; 1113 n++; 1114 } 1115 } 1116 1117 sort(insertedVals[]); 1118 auto sortedInserted = assumeSorted(insertedVals[]); 1119 for(size_t i; i < testedSize; ++i) 1120 { 1121 if(sortedInserted.contains(i)) 1122 { 1123 assert(vT.member(i)); 1124 } 1125 else 1126 { 1127 assert(!vT.member(i), "i: " ~ to!string(i)); //10481664, 8908800 1128 } 1129 } 1130 } 1131 1132 /// this method is used to determine the minimum of the tree 1133 @property Nullable!(size_t, maxSize) min(){ return root.min; } 1134 1135 /// this method is used to determine the maximum of the tree 1136 @property Nullable!(size_t, maxSize) max(){ return root.max; } 1137 1138 /// this method retrieves the successor of the given input. 1139 Nullable!(size_t, maxSize) successor(size_t value) { return root.successor(value, capacity); } 1140 unittest 1141 { 1142 auto currentSeed = unpredictableSeed(); 1143 static if(vdebug){write("UT: vT, successor. "); writeln("seed: ", currentSeed);} 1144 rndGenInUse.seed(currentSeed); //initialize the random generator 1145 1146 auto uS = uniform(allowedArraySize, testedSize, rndGenInUse); 1147 VEBtree vT = new VEBtree(uS); 1148 1149 size_t n; 1150 uint[allowedArraySize] insertedVals; 1151 while(n < allowedArraySize) 1152 { 1153 auto valToInsert = uniform(0U, uS, rndGenInUse); 1154 if(vT.insert(valToInsert)) 1155 { 1156 insertedVals[n] = valToInsert; 1157 n++; 1158 } 1159 } 1160 1161 auto sortedInserted = assumeSorted(sort(insertedVals[])); 1162 1163 assert(vT.max == sortedInserted.back); 1164 assert(vT.min == sortedInserted.front); 1165 size_t j; 1166 1167 for(size_t i = 0; i <= testedSize; ++i) 1168 { 1169 const auto el = vT.successor(i); 1170 1171 if(el.isNull) 1172 { 1173 assert(i == vT.max); 1174 assert(sortedInserted.contains(i)); 1175 break; // quit the loop; 1176 } 1177 else 1178 { 1179 if(sortedInserted.contains(i)) ++j; 1180 assert(el == sortedInserted[j]); 1181 } 1182 } 1183 } 1184 1185 /// this method retrieves the predecessor of the given input. 1186 Nullable!(size_t, maxSize) predecessor(size_t value) { return root.predecessor(value, capacity); } 1187 /// 1188 unittest 1189 { 1190 auto currentSeed = unpredictableSeed(); 1191 static if(vdebug){write("uT: vT, predecessor. "); writeln("seed: ", currentSeed);} 1192 rndGenInUse.seed(currentSeed); //initialize the random generator 1193 1194 auto uS = uniform(allowedArraySize,testedSize, rndGenInUse); 1195 VEBtree vT = new VEBtree(uS); 1196 1197 size_t n; 1198 uint[allowedArraySize] insertedVals; 1199 while(n < allowedArraySize) 1200 { 1201 auto valToInsert = uniform(0U, uS, rndGenInUse); 1202 if(vT.insert(valToInsert)) 1203 { 1204 insertedVals[n] = valToInsert; 1205 n++; 1206 } 1207 } 1208 1209 auto sortedInserted = assumeSorted(sort(insertedVals[])); 1210 1211 assert(vT.max == sortedInserted.back); 1212 assert(vT.min == sortedInserted.front); 1213 size_t j = allowedArraySize - 1; 1214 1215 size_t i = testedSize + 1; 1216 do 1217 { 1218 --i; 1219 const auto el = vT.predecessor(i); 1220 if(el.isNull) 1221 { 1222 assert(i == vT.min); 1223 assert(sortedInserted.contains(i)); 1224 break; // quit the loop; 1225 1226 } 1227 else 1228 { 1229 if(sortedInserted.contains(i)) --j; 1230 assert(el == sortedInserted[j]); 1231 } 1232 1233 }while(i > 0); 1234 } 1235 1236 /// this method is used to determine, whether the tree is currently containing an element. 1237 @property bool empty() { return root.isNull; } 1238 1239 /// this method returns the minimium. 1240 @property size_t front() 1241 in { assert(!root.isNull); } 1242 body { return root.min; } 1243 1244 /// this method removes the minimum element 1245 void popFront(){ if(!empty) remove(min); } 1246 1247 /// bidirectional range also needs 1248 @property size_t back() 1249 in { assert(!root.isNull); } 1250 body { return root.max; } 1251 1252 /// this method removes the maximum element 1253 void popBack() { if(!empty) remove(max); } 1254 1255 /// This method returns the amount of elements currently present in the tree. 1256 @property size_t length()const { return _elementCount; } 1257 1258 1259 /** 1260 forward range also needs save. This is a draft version of the save function, it uses the opslice of the struct 1261 to construct a new one via an array 1262 */ 1263 @property VEBtree save() { return new VEBtree(this[]); } 1264 1265 /** 1266 opSlice operator to get the underlying array. 1267 This is a draft version, as it uses the successor method of the class. So getting the underlying array is 1268 proportional to n. As this functionaly is not seen as crucial, it is enough for the first time. 1269 */ 1270 auto opSlice() 1271 { 1272 size_t[] retArray; 1273 retArray.length = this.length; 1274 if(!this.min.isNull) 1275 retArray[0] = this.min; 1276 for(size_t i = 1; i < retArray.length; ++i) 1277 retArray[i] = successor(retArray[i-1]); 1278 return retArray; 1279 } 1280 /** 1281 ditto 1282 */ 1283 auto opSlice(size_t a, size_t b) 1284 { 1285 size_t[] retArray; 1286 size_t currMin; 1287 if(this.member(a)) 1288 currMin = a; 1289 else 1290 if(!this.successor(a).isNull) 1291 currMin = this.successor(a); 1292 else // nothing to do 1293 return retArray; 1294 1295 retArray.length = b - currMin; 1296 retArray[0] = currMin; 1297 size_t counter = 1; 1298 while(true) 1299 { 1300 assert(counter <= retArray.length); 1301 const auto succ = this.successor(retArray[counter - 1]); 1302 if(succ.isNull || succ >= b) break; 1303 retArray[counter] = succ; 1304 ++counter; 1305 } 1306 retArray.length = counter; 1307 return retArray; 1308 } 1309 // (optional) todo: implement some kind of cool output as a graphViz pic, similiar to the graphs in Cormen. 1310 } 1311 1312 /// 1313 unittest 1314 { 1315 1316 VEBtree vT = new VEBtree(100); 1317 assert(vT.root.isNull); 1318 auto result = vT.insert(2); 1319 assert(result); 1320 assert(!vT.root.isNull); 1321 assert(vT.member(2)); 1322 VEBtree vT2 = vT.save(); 1323 assert(vT2.member(2)); 1324 result = vT2.insert(3); 1325 assert(result); 1326 assert(vT2.member(3)); 1327 assert(!vT.member(3)); 1328 } 1329 1330 /// 1331 unittest 1332 { 1333 assert(!__traits(compiles, new VEBtree())); 1334 VEBtree vT = new VEBtree(1000); 1335 assert(vT.capacity == 1024); 1336 assert(vT.min.isNull); 1337 assert(vT.insert(2)); 1338 vT.insert(5); 1339 assert(!vT.member(8)); 1340 assert(vT.insert(88)); 1341 assert(vT.member(88)); 1342 assert(vT.predecessor(4) == 2); 1343 assert(!vT.member(8)); 1344 assert(vT.insert(8)); 1345 assert(vT.member(8)); 1346 assert(vT.predecessor(75) == 8); 1347 assert(vT.predecessor(90) == 88); 1348 assert(vT.predecessor(7) == 5); 1349 assert(vT.predecessor(4) == 2); 1350 assert(vT.predecessor(2).isNull); 1351 assert(vT.successor(6) == 8); 1352 assert(vT.successor(5) == 8); 1353 assert(vT.successor(4) == 5); 1354 assert(vT.successor(1) == 2); 1355 assert(vT.successor(75) == 88); 1356 assert(vT.successor(90).isNull); 1357 assert(!vT.member(1029)); 1358 assert(!vT.member(1029)); 1359 assert(vT.successor(1025).isNull); 1360 1361 auto vT2 = new VEBtree(500); 1362 assert(vT2.empty); 1363 vT2.insert(50); 1364 vT2.insert(500); 1365 assert(vT2.max == 500); 1366 assert(vT2.min == 50); 1367 assert(vT2.successor(40) == 50); 1368 assert(vT2.successor(50) == 500); 1369 1370 /* about 20 seconds in debug mode. 1371 auto vT3 = new VEBtree(uint.max); 1372 assert(vT3.insert(5)); 1373 assert(vT3.member(5)); 1374 assert(vT3.capacity == cast(ulong)uint.max + 1); 1375 //*/ 1376 1377 assert(!vT.member(1029)); 1378 assert(!vT.member(865)); 1379 assert(vT.insert(865)); 1380 assert(vT.member(865)); 1381 assert(!vT.insert(865)); 1382 assert(vT.member(865)); 1383 assert(!vT.member(866)); 1384 assert(!vT.remove(866)); 1385 assert(vT.member(865)); 1386 assert(vT.remove(865)); 1387 assert(!vT.member(865)); 1388 } 1389 1390 /// 1391 unittest 1392 { 1393 auto currentSeed = unpredictableSeed(); 1394 static if(vdebug){write("UT: rand, succ. "); writeln("seed: ", currentSeed);} 1395 rndGenInUse.seed(currentSeed); //initialize the random generator 1396 1397 auto M = uniform(2U,testedSize, rndGenInUse); //set universe size to some integer. 1398 VEBtree vT = new VEBtree(M); //create the tree 1399 assert(vT.capacity == nPof2(M-1)); 1400 const auto m = vT.fill(40, rndGenInUse); //(try to) fill the tree with thousend values 1401 size_t n; 1402 Nullable!(size_t, maxSize) i = vT.max; 1403 1404 // discover the thousend (or little less) values with the predecessor method 1405 while(!i.isNull) 1406 { 1407 ++n; 1408 i = vT.predecessor(i); 1409 if(n > m) break; 1410 } 1411 1412 size_t o; 1413 i = vT.min; 1414 while(!i.isNull) 1415 { 1416 ++o; 1417 i = vT.successor(i.get); 1418 if(o - 1 > m) break; 1419 } 1420 1421 // assert, that all members are discovered, iff when no predecessors are left 1422 assert(n == m); 1423 assert(o == m); 1424 } 1425 1426 /// 1427 unittest 1428 { 1429 auto currentSeed = unpredictableSeed(); 1430 static if(vdebug){write("UT: rand, pred "); writeln("seed: ", currentSeed);} 1431 rndGenInUse.seed(currentSeed); //initialize the random generator 1432 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1433 VEBtree vT = new VEBtree(M); 1434 vT.fill(1000, rndGenInUse); //fill the tree with some values 1435 Nullable!(size_t, maxSize) i = vT.max; 1436 1437 // remove all members beginning from the maximum 1438 bool result; 1439 while(!i.isNull) 1440 { 1441 result = vT.remove(i); 1442 assert(result); 1443 const auto j = vT.predecessor(i); 1444 if(!j.isNull) 1445 assert(j != i); 1446 i = j; 1447 } 1448 1449 // assert, that all members are removed, iff when no predecessors are left. 1450 assert(vT.empty); 1451 } 1452 1453 /// 1454 unittest 1455 { 1456 auto currentSeed = unpredictableSeed(); 1457 static if(vdebug){write("UT: rand, remove "); writeln("seed: ", currentSeed);} 1458 rndGenInUse.seed(currentSeed); //initialize the random generator 1459 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1460 VEBtree vT = new VEBtree(M); 1461 vT.fill(1000, rndGenInUse); //fill the tree with some values 1462 Nullable!(size_t, maxSize) i = vT.min; 1463 1464 // remove all members beginning from the minimum 1465 bool result; 1466 while(!i.isNull) 1467 { 1468 result = vT.remove(i); 1469 assert(result); 1470 const auto j = vT.successor(i); 1471 if(!j.isNull) 1472 assert(j != i); 1473 i = j; 1474 } 1475 1476 // assert, that all members are removed, iff when no successors are left. 1477 assert(vT.empty); 1478 } 1479 1480 /// 1481 unittest 1482 { 1483 const uint M = testedSize; 1484 VEBtree vT = new VEBtree(M); 1485 vT.insert(0x000f); 1486 assert(vT.predecessor(0x000f).isNull); 1487 vT.insert(0x00f0); 1488 assert(vT.predecessor(0x00f0) == 0x000f); 1489 vT.insert(0x0f00); 1490 assert(vT.predecessor(0x0f00) == 0x00f0); 1491 vT.insert(0xf000); 1492 assert(vT.predecessor(0xf000) == 0x0f00); 1493 1494 auto result = vT.remove(0xf000); 1495 assert(result); 1496 assert(vT.predecessor(0xf000) == 0x0f00); 1497 result = vT.remove(0x0f00); 1498 assert(result); 1499 assert(vT.predecessor(0x0f00) == 0x00f0); 1500 result = vT.remove(0x00f0); 1501 assert(result); 1502 assert(vT.predecessor(0x00f0) == 0x000f); 1503 result = vT.remove(0x000f); 1504 assert(result); 1505 assert(vT.predecessor(0x000f).isNull); 1506 } 1507 1508 /// 1509 unittest 1510 { 1511 const uint M = testedSize; 1512 VEBtree vT = new VEBtree(M); 1513 vT.insert(0xf000); 1514 assert(vT.member(0xf000)); 1515 vT.insert(0x0f00); 1516 assert(vT.member(0x0f00)); 1517 vT.insert(0x00f0); 1518 assert(vT.member(0x00f0)); 1519 vT.insert(0x000f); 1520 assert(vT.member(0x000f)); 1521 1522 auto result = vT.remove(0xf000); 1523 assert(result); 1524 assert(!vT.member(0xf000)); 1525 result = vT.remove(0x0f00); 1526 assert(result); 1527 assert(!vT.member(0x0f00)); 1528 result = vT.remove(0x00f0); 1529 assert(result); 1530 assert(!vT.member(0x00f0)); 1531 result = vT.remove(0x000f); 1532 assert(result); 1533 assert(!vT.member(0x000f)); 1534 } 1535 1536 /// 1537 unittest 1538 { 1539 //stress test 1540 auto currentSeed = unpredictableSeed(); 1541 static if(vdebug){write("UT: rand, stress "); writeln("seed: ", currentSeed);} 1542 rndGenInUse.seed(currentSeed); //initialize the random generator 1543 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 1544 // last test says: see below. 1545 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1546 VEBtree vT = new VEBtree(M); 1547 size_t[] arr; 1548 const auto howMuchFilled = vT.fill(arr, rndGenInUse); 1549 1550 assert(arr.length == howMuchFilled); 1551 1552 VEBtree vT2 = new VEBtree(M); 1553 1554 assert(vT2.capacity == vT.capacity); 1555 1556 auto rbt = redBlackTree!size_t(0); 1557 rbt.clear; 1558 1559 void fill1() 1560 { 1561 foreach(size_t i; arr) 1562 { 1563 vT2.insert(i); 1564 } 1565 1566 foreach(size_t i; arr) 1567 { 1568 vT2.remove(i); 1569 } 1570 assert(vT2.empty); 1571 1572 } 1573 1574 void fill2() 1575 { 1576 foreach(size_t i; arr) 1577 { 1578 rbt.insert(i); 1579 } 1580 } 1581 1582 /* 1583 this part is for speed test 1584 */ 1585 /* 1586 compiled with ldc2 vebtree.d -O -main -unittest 1587 results of stress tests: 1588 size of tree: 16777216 1589 howMuchFilled: 16252928 1590 VEB: 2 secs, 382 ms, 588 μs, and 8 hnsecs 1591 */ 1592 /* 1593 import std.stdio; 1594 writeln("size of tree: ", vT2.capacity); 1595 writeln("howMuchFilled: ", howMuchFilled); 1596 //auto r = benchmark!(fill1, fill2)(1); 1597 auto r = benchmark!(fill1)(1); 1598 //auto r = benchmark!(fill1)(1); 1599 auto f0Result = to!Duration(r[0]); 1600 //auto f1Result = to!Duration(r[1]); 1601 writeln("VEB: ", f0Result); //10ms 1602 //writeln("rbt: ", f1Result); //40sec 1603 //assert(f0Result < f1Result); 1604 //*/ 1605 } 1606 1607 /// 1608 unittest 1609 { 1610 const uint currentSeed = unpredictableSeed(); 1611 static if(vdebug){write("UT: rand, member "); writeln("seed: ", currentSeed);} 1612 rndGenInUse.seed(currentSeed); //initialize the random generator 1613 const uint M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1614 uint[] sourceArr; 1615 sourceArr.length = M; 1616 // generate a random array as the source for the tree 1617 for(uint i = 0; i < M; i++) sourceArr[i] = uniform(0U, M, rndGenInUse); 1618 // constructor to test 1619 VEBtree vT = new VEBtree(sourceArr); 1620 // make the array values unique. 1621 auto uniqueArr = sort(sourceArr).uniq; 1622 // check, that all values are filled 1623 bool result; 1624 foreach(uint i; uniqueArr) 1625 { 1626 assert(vT.member(i)); 1627 result = vT.remove(i); 1628 assert(result); 1629 } 1630 // check, that no other elements are present. 1631 assert(vT.empty); 1632 } 1633 1634 /// 1635 unittest 1636 { 1637 auto currentSeed = unpredictableSeed(); 1638 static if(vdebug){write("UT: rand, opslice "); writeln("seed: ", currentSeed);} 1639 rndGenInUse.seed(currentSeed); //initialize the random generator 1640 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 1641 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1642 VEBtree vT = new VEBtree(M); 1643 size_t[] arr; 1644 vT.fill(arr, rndGenInUse, 16); 1645 1646 assert(setSymmetricDifference(vT[], sort(arr)).empty); 1647 } 1648 1649 /// 1650 unittest 1651 { 1652 const uint currentSeed = unpredictableSeed(); 1653 static if(vdebug){write("UT: rand, opslice[]. "); writeln("seed: ", currentSeed);} 1654 rndGenInUse.seed(currentSeed); //initialize the random generator 1655 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 1656 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1657 VEBtree vT = new VEBtree(M); 1658 size_t[] arr; 1659 vT.fill(arr, rndGenInUse, 16); 1660 const auto begin = 5; 1661 const auto end = 100; 1662 const auto filterRes = sort(arr).filter!(a => a >= begin && a < end).array; 1663 assert(setSymmetricDifference(filterRes, vT[begin..end]).empty); 1664 } 1665 1666 /// 1667 unittest { assert(isBidirectionalRange!VEBtree); } 1668 1669 /// 1670 unittest 1671 { 1672 VEBtree vT = new VEBtree(14); 1673 auto result = vT.insert(2); 1674 assert(result); 1675 result = vT.insert(5); 1676 assert(result); 1677 result = vT.insert(10); 1678 assert(result); 1679 assert(vT[] == [2, 5, 10]); 1680 } 1681 1682 /// 1683 unittest 1684 { 1685 /+ 1686 //another stress test 1687 auto currentSeed = unpredictableSeed(); 1688 static if(vdebug){write("UT: stress test 2 "); writeln("seed: ", currentSeed);} 1689 rndGenInUse.seed(currentSeed); //initialize the random generator 1690 1691 void fill16(){ VEBtree vT = new VEBtree(1 << 16); } 1692 void fill17(){ VEBtree vT = new VEBtree(1 << 17); } 1693 void fill18(){ VEBtree vT = new VEBtree(1 << 18); } 1694 void fill19(){ VEBtree vT = new VEBtree(1 << 19); } 1695 void fill20(){ VEBtree vT = new VEBtree(1 << 20); } 1696 void fill21(){ VEBtree vT = new VEBtree(1 << 21); } 1697 void fill22(){ VEBtree vT = new VEBtree(1 << 22); } 1698 void fill23(){ VEBtree vT = new VEBtree(1 << 23); } 1699 void fill24(){ VEBtree vT = new VEBtree(1 << 24); } 1700 void fill25(){ VEBtree vT = new VEBtree(1 << 25); } 1701 1702 /* 1703 This part is for speed test. 1704 */ 1705 /* 1706 import std.stdio; 1707 auto r = benchmark!(fill16, fill17, fill18, fill19, fill20, fill21, fill22, fill23, fill24, fill25)(1); 1708 //auto r = benchmark!(fill1)(1); 1709 auto f16Result = to!Duration(r[0]); 1710 auto f17Result = to!Duration(r[1]); 1711 auto f18Result = to!Duration(r[2]); 1712 auto f19Result = to!Duration(r[3]); 1713 auto f20Result = to!Duration(r[4]); 1714 auto f21Result = to!Duration(r[5]); 1715 auto f22Result = to!Duration(r[6]); 1716 auto f23Result = to!Duration(r[7]); 1717 auto f24Result = to!Duration(r[8]); 1718 auto f25Result = to!Duration(r[9]); 1719 writeln("VEB with M of ", 1 << 16, ": ", f16Result); 1720 writeln("VEB with M of ", 1 << 17, ": ", f17Result); 1721 writeln("VEB with M of ", 1 << 18, ": ", f18Result); 1722 writeln("VEB with M of ", 1 << 19, ": ", f19Result); 1723 writeln("VEB with M of ", 1 << 20, ": ", f20Result); 1724 writeln("VEB with M of ", 1 << 21, ": ", f21Result); 1725 writeln("VEB with M of ", 1 << 22, ": ", f22Result); 1726 writeln("VEB with M of ", 1 << 23, ": ", f23Result); 1727 writeln("VEB with M of ", 1 << 24, ": ", f24Result); 1728 writeln("VEB with M of ", 1 << 25, ": ", f25Result); 1729 //*/ 1730 +/ 1731 } 1732 1733 /// 1734 unittest 1735 { 1736 // This unittest is for check of adding of big numbers 1737 /* in debug mode about 1 min. 1738 const uint[] arr = [1, 2, 8, 2_147_483_647]; 1739 new VEBtree(arr); 1740 //*/ 1741 }