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 = true; 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(!(x in vT)) 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(!(x in vT)) 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 maxSizeBound 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 maxSizeBound = (size_t(1) << baseSize/2) + 1; 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, maxSizeBound) min() 437 { 438 // define the result as a nullable 439 Nullable!(size_t, maxSizeBound) 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 < maxSizeBound); 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, maxSizeBound) max() 473 { 474 // define the result as a nullable 475 Nullable!(size_t, maxSizeBound) 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 < maxSizeBound); 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 opIn_r(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, opIn_r. "); 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(bitNum in vN); 530 if((vN._val & size_t(1) << bitNum) == 0 ) assert(!(bitNum in vN)); 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 (value in this); // 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, maxSizeBound) predecessor(size_t bitNum) 697 in 698 { 699 assert(isLeaf); 700 assert(bitNum < baseSize); 701 } 702 body 703 { 704 Nullable!(size_t, maxSizeBound) 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 = 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, maxSizeBound) predecessor(size_t value, size_t uS) 748 { 749 Nullable!(size_t, maxSizeBound) 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, maxSizeBound) successor(size_t bitNum) 787 in 788 { 789 assert(isLeaf); 790 assert(bitNum < baseSize); 791 } 792 body 793 { 794 Nullable!(size_t, maxSizeBound) 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, maxSizeBound) successor(size_t value, size_t uS) 835 { 836 Nullable!(size_t, maxSizeBound) 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(1 in vN); 881 assert(!(2 in vN)); 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 < maxSizeBound); 915 } 916 body 917 { 918 // set the expected size to the passed value 919 expectedSize = value; 920 // delegate the creation of the nodes with the apropriate power of two of the needed universe size 921 root = VEBnode(nPof2(expectedSize - 1)); 922 923 assert(this.empty); 924 } 925 /// 926 unittest 927 { 928 auto currentSeed = unpredictableSeed(); 929 static if(vdebug){write("UT: vT, __ctor. "); writeln("seed: ", currentSeed);} 930 rndGenInUse.seed(currentSeed); //initialize the random generator 931 932 auto uS = uniform(1U << size_t(1),testedSize, rndGenInUse); 933 const VEBtree vT = new VEBtree(uS); 934 assert(vT.empty); 935 if((uS & (uS - 1)) == 0) 936 assert(vT.capacity == uS); 937 else 938 assert(vT.capacity == (size_t(1) << (bsr(uS) + 1))); 939 940 assert(vT.expectedSize == uS); 941 942 const auto uS1 = uniform(1U << size_t(1),testedSize, rndGenInUse); 943 const auto uSsmall = uniform(1U << size_t(1),baseSize, rndGenInUse); 944 VEBtree vT1 = new VEBtree(uS1); 945 const VEBtree vTsmall = new VEBtree(uSsmall); 946 947 assert(vTsmall.root._val == 0); 948 assert(vTsmall.root.ptrArr == null); 949 950 if(uS1 > 8 * size_t.sizeof) 951 { 952 assert(vT1.root._val == 1); 953 assert(vT1.root.ptrArr != null); 954 955 //check every child for consistency. 956 // the size of a node is higher square root & the summary node. 957 958 // capacity is tested elsewhere. 959 // hSR is also tested elsewhere 960 const auto childsAmount_l1 = hSR(vT1.capacity) + 1; 961 const auto childsAmount_l2 = hSR(lSR(vT1.capacity)) > baseSize ? hSR(lSR(vT1.capacity)) + 1 : 0; 962 963 // the tree is just created, assert all children are nullified 964 for(size_t i; i < childsAmount_l1; ++i) 965 { 966 assert(vT1.root.ptrArr[i].isNull); 967 if(childsAmount_l1 > baseSize + 1) 968 { 969 for(size_t j; j < childsAmount_l2; ++j) 970 { 971 assert(vT1.root.ptrArr[i].ptrArr[j].isNull); 972 } 973 } 974 } 975 } 976 } 977 978 /// another possibility is to construct a VEB tree is by providing an array. 979 this(R)(R range) if(isIterable!R) 980 in 981 { 982 // check, whether the range is not too long. I. e. expressable with an uint. 983 assert(range.length < maxSizeBound); 984 } 985 body 986 { 987 import std.algorithm.comparison : max; 988 // first, we have to determine the size of the tree. 989 // it is either derived from the length of the given tree or its greatest element 990 size_t limit; 991 foreach(size_t i; range) limit = max(limit,i); 992 // assert no element has exceeded the allowed range of baseSize/2 993 assert(limit < maxSizeBound); 994 // if the array is longer, then the greatest element, but the length passes, substitute the limit 995 limit = max(limit, range.length); 996 // call the constructor with the limit 997 this(limit + 1); 998 // put every element from the range into the tree 999 foreach(size_t i; range) insert(i); 1000 } 1001 1002 /** 1003 this method returns the capacity of the tree. It is equal to the next power of 2 regarding the size used at 1004 initialization. 1005 */ 1006 size_t capacity() const { return nPof2(expectedSize - 1); } 1007 1008 /** 1009 this method is used to add an element to the tree. duplicate values will be ignored. the class provides an 1010 intermediate layer between the caller and the contained root and enrichs the input by the stored size. 1011 */ 1012 bool insert(size_t value) 1013 { 1014 if(value >= capacity) return false; 1015 const bool retVal = root.insert(value, capacity); 1016 if(retVal) ++_elementCount; 1017 return retVal; 1018 } 1019 /// 1020 unittest 1021 { 1022 auto currentSeed = unpredictableSeed(); 1023 static if(vdebug){write("UT: vT, insert. "); writeln("seed: ", currentSeed);} 1024 rndGenInUse.seed(currentSeed); //initialize the random generator 1025 1026 auto uS = uniform(allowedArraySize,testedSize, rndGenInUse); 1027 VEBtree vT = new VEBtree(uS); 1028 1029 size_t n; 1030 uint[allowedArraySize] insertedVals; 1031 while(n < allowedArraySize) 1032 { 1033 auto valToInsert = uniform(0U, uS, rndGenInUse); 1034 const bool inserted = vT.insert(valToInsert); 1035 if(inserted) 1036 { 1037 insertedVals[n] = valToInsert; 1038 n++; 1039 } 1040 } 1041 assert(vT._elementCount == insertedVals.length); 1042 1043 sort(insertedVals[]); 1044 assert(uniq(insertedVals[]).array.length == insertedVals.length); 1045 } 1046 1047 /// this method overrides the insert method to directly use arrays 1048 void insert(R)(R arr) if(isIterable!R){ foreach(size_t i; arr) insert(i); } 1049 1050 /// this method is used to remove elements from the tree. not existing values will be ignored. 1051 bool remove(size_t value) 1052 { 1053 const bool retVal = root.remove(value, capacity); 1054 if(retVal) --_elementCount; 1055 return retVal; 1056 } 1057 /// 1058 unittest 1059 { 1060 auto currentSeed = unpredictableSeed(); 1061 static if(vdebug){write("UT: vT, remove. "); writeln("seed: ", currentSeed);} 1062 rndGenInUse.seed(currentSeed); //initialize the random generator 1063 1064 auto uS = uniform(allowedArraySize,testedSize, rndGenInUse); 1065 VEBtree vT = new VEBtree(uS); 1066 1067 size_t n; 1068 uint[allowedArraySize] insertedVals; 1069 1070 while(n < allowedArraySize) 1071 { 1072 auto valToInsert = uniform(0U, uS, rndGenInUse); 1073 if(vT.insert(valToInsert)) 1074 { 1075 insertedVals[n] = valToInsert; 1076 n++; 1077 } 1078 } 1079 1080 assert(vT._elementCount == insertedVals.length); 1081 1082 foreach(size_t i; insertedVals) assert(vT.remove(i)); 1083 assert(vT.length == 0); 1084 } 1085 1086 /// this method is used to determine, whether an element is currently present in the tree 1087 bool opIn_r(size_t value) 1088 { 1089 if(value >= capacity) return false; 1090 return root.member(value, capacity); 1091 } 1092 /// 1093 unittest 1094 { 1095 auto currentSeed = unpredictableSeed(); 1096 static if(vdebug){write("UT: vT, member. "); writeln("seed: ", currentSeed);} 1097 rndGenInUse.seed(currentSeed); //initialize the random generator 1098 1099 auto uS = uniform(allowedArraySize,testedSize, rndGenInUse); 1100 VEBtree vT = new VEBtree(uS); 1101 1102 size_t n; 1103 uint[allowedArraySize] insertedVals; 1104 while(n < allowedArraySize) 1105 { 1106 auto valToInsert = uniform(0U, uS, rndGenInUse); 1107 if(vT.insert(valToInsert)) 1108 { 1109 insertedVals[n] = valToInsert; 1110 n++; 1111 } 1112 } 1113 1114 sort(insertedVals[]); 1115 auto sortedInserted = assumeSorted(insertedVals[]); 1116 for(size_t i; i < testedSize; ++i) 1117 { 1118 if(sortedInserted.contains(i)) 1119 { 1120 assert(i in vT); 1121 } 1122 else 1123 { 1124 assert(!(i in vT), "i: " ~ to!string(i)); 1125 } 1126 } 1127 } 1128 1129 /// this method is used to determine the minimum of the tree 1130 @property Nullable!(size_t, maxSizeBound) min(){ return root.min; } 1131 1132 /// this method is used to determine the maximum of the tree 1133 @property Nullable!(size_t, maxSizeBound) max(){ return root.max; } 1134 1135 /// this method retrieves the successor of the given input. 1136 Nullable!(size_t, maxSizeBound) successor(alias boundaries = "()")(size_t value) 1137 { 1138 if(value >= capacity) return Nullable!(size_t, maxSizeBound)(); 1139 1140 // otherwise get the successor 1141 auto currentSuccessor = root.successor(value, capacity); 1142 1143 // in case of closed boundaries 1144 static if(boundaries[1] == ']') // if there is a successor (between the value and the upper bound) 1145 { 1146 if(!currentSuccessor.isNull) return currentSuccessor; // return the successor 1147 else return Nullable!(size_t, maxSizeBound)(capacity); // otherwise return the bound (capacity) 1148 } 1149 else return currentSuccessor; // in case of open boundaries return the successor (null or a value) 1150 } 1151 unittest 1152 { 1153 auto currentSeed = unpredictableSeed(); 1154 static if(vdebug){write("UT: vT, successor. "); writeln("seed: ", currentSeed);} 1155 rndGenInUse.seed(currentSeed); //initialize the random generator 1156 1157 auto uS = uniform(allowedArraySize, testedSize, rndGenInUse); 1158 VEBtree vT = new VEBtree(uS); 1159 1160 // testing the boundaries now: 1161 auto randomElement = uniform(allowedArraySize, uS); 1162 assert(vT.successor(randomElement).isNull); 1163 assert(vT.successor!"[]"(randomElement) == vT.capacity); 1164 1165 size_t n; 1166 uint[allowedArraySize] insertedVals; 1167 while(n < allowedArraySize) 1168 { 1169 auto valToInsert = uniform(0U, uS, rndGenInUse); 1170 if(vT.insert(valToInsert)) 1171 { 1172 insertedVals[n] = valToInsert; 1173 n++; 1174 } 1175 } 1176 1177 auto sortedInserted = assumeSorted(sort(insertedVals[])); 1178 1179 assert(vT.max == sortedInserted.back); 1180 assert(vT.min == sortedInserted.front); 1181 size_t j; 1182 1183 for(size_t i = 0; i <= testedSize; ++i) 1184 { 1185 const auto el = vT.successor(i); 1186 1187 if(el.isNull) 1188 { 1189 assert(i == vT.max); 1190 assert(sortedInserted.contains(i)); 1191 break; // quit the loop; 1192 } 1193 else 1194 { 1195 if(sortedInserted.contains(i)) ++j; 1196 assert(el == sortedInserted[j]); 1197 } 1198 } 1199 } 1200 1201 /// this method retrieves the predecessor of the given input. 1202 Nullable!(size_t, maxSizeBound) predecessor(alias boundaries = "()")(size_t value) 1203 { 1204 auto currentPredecessor = root.predecessor(value, capacity); 1205 static if(boundaries[0] == '[') 1206 { 1207 if(!currentPredecessor.isNull) 1208 return currentPredecessor; 1209 else 1210 return Nullable!(size_t, maxSizeBound)(0); 1211 } 1212 else return currentPredecessor; 1213 } 1214 /// 1215 unittest 1216 { 1217 auto currentSeed = unpredictableSeed(); 1218 static if(vdebug){write("UT: vT, predecessor. "); writeln("seed: ", currentSeed);} 1219 rndGenInUse.seed(currentSeed); //initialize the random generator 1220 1221 auto uS = uniform(allowedArraySize,testedSize, rndGenInUse); 1222 VEBtree vT = new VEBtree(uS); 1223 1224 // testing the boundaries now: 1225 auto randomElement = uniform(allowedArraySize, uS); 1226 assert(vT.predecessor(randomElement).isNull); 1227 assert(vT.predecessor!"[]"(randomElement) == 0); 1228 1229 size_t n; 1230 uint[allowedArraySize] insertedVals; 1231 while(n < allowedArraySize) 1232 { 1233 auto valToInsert = uniform(0U, uS, rndGenInUse); 1234 if(vT.insert(valToInsert)) 1235 { 1236 insertedVals[n] = valToInsert; 1237 n++; 1238 } 1239 } 1240 1241 auto sortedInserted = assumeSorted(sort(insertedVals[])); 1242 1243 assert(vT.max == sortedInserted.back); 1244 assert(vT.min == sortedInserted.front); 1245 size_t j = allowedArraySize - 1; 1246 1247 size_t i = testedSize + 1; 1248 do 1249 { 1250 --i; 1251 const auto el = vT.predecessor(i); 1252 if(el.isNull) 1253 { 1254 assert(i == vT.min); 1255 assert(sortedInserted.contains(i)); 1256 break; // quit the loop; 1257 1258 } 1259 else 1260 { 1261 if(sortedInserted.contains(i)) --j; 1262 assert(el == sortedInserted[j]); 1263 } 1264 1265 }while(i > 0); 1266 } 1267 1268 /// this method is used to determine, whether the tree is currently containing an element. 1269 @property bool empty() const { return root.isNull; } 1270 1271 /// this method returns the minimium. 1272 @property size_t front() 1273 in { assert(!this.empty); } 1274 body { return this.min; } 1275 1276 /// this method removes the minimum element 1277 void popFront(){ if(!empty) remove(min); } 1278 1279 /// bidirectional range also needs 1280 @property size_t back() 1281 in { assert(!this.empty); } 1282 body { return this.max; } 1283 1284 /// this method removes the maximum element 1285 void popBack() { if(!empty) remove(max); } 1286 1287 /// This method returns the amount of elements currently present in the tree. 1288 @property size_t length()const { return _elementCount; } 1289 1290 1291 /** 1292 forward range also needs save. This is a draft version of the save function, it uses the opslice of the struct 1293 to construct a new one via an array 1294 */ 1295 @property VEBtree save() { return new VEBtree(this[]); } 1296 1297 /** 1298 opSlice operator to get the underlying array. 1299 This is a draft version, as it uses the successor method of the class. So getting the underlying array is 1300 proportional to n. As this functionaly is not seen as crucial, it is enough for the first time. 1301 */ 1302 auto opSlice() 1303 { 1304 size_t[] retArray; 1305 retArray.length = this.length; 1306 if(!this.min.isNull) 1307 retArray[0] = this.min; 1308 for(size_t i = 1; i < retArray.length; ++i) 1309 { 1310 auto succ = successor(retArray[i-1]); 1311 if(!succ.isNull) retArray[i] = succ; 1312 } 1313 return retArray; 1314 } 1315 1316 /// dollar operator overload. 1317 @property size_t opDollar() { return capacity; } 1318 1319 /// ditto 1320 auto opSlice(size_t a, size_t b) 1321 { 1322 size_t[] retArray; 1323 size_t currMin; 1324 if(a in this) 1325 currMin = a; 1326 else 1327 if(!this.successor(a).isNull) 1328 currMin = this.successor(a); 1329 else // nothing to do 1330 return retArray; 1331 1332 retArray.length = b - currMin; 1333 retArray[0] = currMin; 1334 size_t counter = 1; 1335 while(true) 1336 { 1337 assert(counter <= retArray.length); 1338 const auto succ = this.successor(retArray[counter - 1]); 1339 if(succ.isNull || succ >= b) break; 1340 retArray[counter] = succ; 1341 ++counter; 1342 } 1343 retArray.length = counter; 1344 return retArray; 1345 } 1346 1347 /** 1348 this method serves as export of the tree to an array. () and [] is possible as template parameter to export the 1349 boundaries, even if they are not present. 1350 */ 1351 auto exportTree(alias boundaries = "()")() 1352 { 1353 size_t[] retArray; 1354 auto exportLength = this.length; 1355 1356 static if(boundaries[0] == '[') 1357 if(!(0 in this)) // if zero is not in the tree and we want to include the left boundary, the export grows 1358 ++exportLength; 1359 static if(boundaries[1] == ']') 1360 ++exportLength; // we want to include the capacity as value, so the export grows 1361 1362 if(exportLength == 0) return retArray; 1363 else retArray.length = exportLength; 1364 1365 static if(boundaries[0] == '[') retArray[0] = 0; 1366 else if(!this.empty) retArray[0] = this.min; 1367 1368 static if(boundaries[1] == ']') retArray[$-1] = capacity; 1369 else if(!this.empty) retArray[$-1] = this.max; 1370 1371 for(size_t i = 1; i < retArray.length; ++i) 1372 { 1373 auto succ = successor!boundaries(retArray[i-1]); 1374 if(succ.isNull || succ == capacity) break; 1375 retArray[i] = succ; 1376 } 1377 1378 return retArray; 1379 } 1380 // (optional) todo: implement some kind of cool output as a graphViz pic, similiar to the graphs in Cormen. 1381 } 1382 1383 /// 1384 unittest 1385 { 1386 VEBtree vT = new VEBtree(100); 1387 assert(vT.empty); 1388 auto result = vT.insert(2); 1389 assert(result); 1390 assert(!vT.empty); 1391 assert(2 in vT); 1392 VEBtree vT2 = vT.save(); 1393 assert(2 in vT2); 1394 result = vT2.insert(3); 1395 assert(result); 1396 assert(3 in vT2); 1397 assert(!(3 in vT)); 1398 assert(vT2.length == 2); 1399 1400 } 1401 1402 /// 1403 unittest 1404 { 1405 auto currentSeed = unpredictableSeed(); 1406 static if(vdebug){write("UT: vT, exportTree. "); writeln("seed: ", currentSeed);} 1407 rndGenInUse.seed(currentSeed); //initialize the random generator 1408 1409 const auto M = uniform(2U,testedSize, rndGenInUse); //set universe size to some integer. 1410 VEBtree vT = new VEBtree(M); //create the tree 1411 vT.fill(1000, rndGenInUse); 1412 1413 assert(vT.exportTree == vT[]); 1414 assert(vT.exportTree!"[)"[0] == 0); 1415 assert(vT.exportTree!"(]"[$-1] == vT.capacity); 1416 } 1417 /// 1418 unittest 1419 { 1420 assert(!__traits(compiles, new VEBtree())); 1421 VEBtree vT = new VEBtree(1000); 1422 assert(vT.capacity == 1024); 1423 assert(vT.min.isNull); 1424 assert(vT.insert(2)); 1425 vT.insert(5); 1426 assert(!(8 in vT)); 1427 assert(vT.insert(88)); 1428 assert(88 in vT); 1429 assert(vT.predecessor(4) == 2); 1430 assert(!(8 in vT)); 1431 assert(vT.insert(8)); 1432 assert(8 in vT); 1433 assert(vT.predecessor(75) == 8); 1434 assert(vT.predecessor(90) == 88); 1435 assert(vT.predecessor(7) == 5); 1436 assert(vT.predecessor(4) == 2); 1437 assert(vT.predecessor(2).isNull); 1438 assert(vT.predecessor!"[]"(2) == 0); 1439 assert(vT.successor(6) == 8); 1440 assert(vT.successor(5) == 8); 1441 assert(vT.successor(4) == 5); 1442 assert(vT.successor(1) == 2); 1443 assert(vT.successor(75) == 88); 1444 assert(vT.successor(90).isNull); 1445 assert(vT.successor!"[]"(90) == vT.capacity); 1446 assert(!(1029 in vT)); 1447 assert(vT.successor(1025).isNull); 1448 assert(vT.successor!"[]"(1025).isNull); 1449 1450 auto vT2 = new VEBtree(500); 1451 assert(vT2.empty); 1452 vT2.insert(50); 1453 vT2.insert(500); 1454 assert(vT2.max == 500); 1455 assert(vT2.min == 50); 1456 assert(vT2.successor(40) == 50); 1457 assert(vT2.successor(50) == 500); 1458 1459 vT2 = new VEBtree(500); 1460 assert(vT2.empty); 1461 vT2.insert(50); 1462 vT2.insert(500); 1463 assert(vT2.max == 500); 1464 assert(vT2.min == 50); 1465 assert(vT2.successor(40) == 50); 1466 assert(vT2.successor(50) == 500); 1467 1468 /* about 20 seconds in debug mode. 1469 auto vT3 = new VEBtree(uint.max); 1470 assert(vT3.insert(5)); 1471 assert(vT3.member(5)); 1472 assert(vT3.capacity == cast(ulong)uint.max + 1); 1473 //*/ 1474 1475 assert(!(1029 in vT)); 1476 assert(!(865 in vT)); 1477 assert(vT.insert(865)); 1478 assert(865 in vT); 1479 assert(!vT.insert(865)); 1480 assert(865 in vT); 1481 assert(!(866 in vT)); 1482 assert(!vT.remove(866)); 1483 assert(865 in vT); 1484 assert(vT.remove(865)); 1485 assert(!(865 in vT)); 1486 } 1487 1488 /// 1489 unittest 1490 { 1491 auto currentSeed = unpredictableSeed(); 1492 static if(vdebug){write("UT: rand, succ. "); writeln("seed: ", currentSeed);} 1493 rndGenInUse.seed(currentSeed); //initialize the random generator 1494 1495 const auto M = uniform(2U,testedSize, rndGenInUse); //set universe size to some integer. 1496 VEBtree vT = new VEBtree(M); //create the tree 1497 assert(vT.capacity == nPof2(M-1)); 1498 const auto m = vT.fill(40, rndGenInUse); //(try to) fill the tree with thousend values 1499 size_t n; 1500 Nullable!(size_t, maxSizeBound) i = vT.max; 1501 1502 // discover the thousend (or little less) values with the predecessor method 1503 while(!i.isNull) 1504 { 1505 ++n; 1506 i = vT.predecessor(i); 1507 if(n > m) break; 1508 } 1509 1510 size_t o; 1511 i = vT.min; 1512 while(!i.isNull) 1513 { 1514 ++o; 1515 i = vT.successor(i.get); 1516 if(o - 1 > m) break; 1517 } 1518 1519 // assert, that all members are discovered, iff when no predecessors are left 1520 assert(n == m); 1521 assert(o == m); 1522 } 1523 1524 /// 1525 unittest 1526 { 1527 auto currentSeed = unpredictableSeed(); 1528 static if(vdebug){write("UT: rand, pred "); writeln("seed: ", currentSeed);} 1529 rndGenInUse.seed(currentSeed); //initialize the random generator 1530 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1531 VEBtree vT = new VEBtree(M); 1532 vT.fill(1000, rndGenInUse); //fill the tree with some values 1533 Nullable!(size_t, maxSizeBound) i = vT.max; 1534 1535 // remove all members beginning from the maximum 1536 bool result; 1537 while(!i.isNull) 1538 { 1539 result = vT.remove(i); 1540 assert(result); 1541 const auto j = vT.predecessor(i); 1542 if(!j.isNull) 1543 assert(j != i); 1544 i = j; 1545 } 1546 1547 // assert, that all members are removed, iff when no predecessors are left. 1548 assert(vT.empty); 1549 } 1550 1551 /// 1552 unittest 1553 { 1554 auto currentSeed = unpredictableSeed(); 1555 static if(vdebug){write("UT: rand, remove "); writeln("seed: ", currentSeed);} 1556 rndGenInUse.seed(currentSeed); //initialize the random generator 1557 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1558 VEBtree vT = new VEBtree(M); 1559 vT.fill(1000, rndGenInUse); //fill the tree with some values 1560 Nullable!(size_t, maxSizeBound) i = vT.min; 1561 1562 // remove all members beginning from the minimum 1563 bool result; 1564 while(!i.isNull) 1565 { 1566 result = vT.remove(i); 1567 assert(result); 1568 const auto j = vT.successor(i); 1569 if(!j.isNull) 1570 assert(j != i); 1571 i = j; 1572 } 1573 1574 // assert, that all members are removed, iff when no successors are left. 1575 assert(vT.empty); 1576 } 1577 1578 /// 1579 unittest 1580 { 1581 const uint M = testedSize; 1582 VEBtree vT = new VEBtree(M); 1583 vT.insert(0x000f); 1584 assert(vT.predecessor(0x000f).isNull); 1585 vT.insert(0x00f0); 1586 assert(vT.predecessor(0x00f0) == 0x000f); 1587 vT.insert(0x0f00); 1588 assert(vT.predecessor(0x0f00) == 0x00f0); 1589 vT.insert(0xf000); 1590 assert(vT.predecessor(0xf000) == 0x0f00); 1591 1592 auto result = vT.remove(0xf000); 1593 assert(result); 1594 assert(vT.predecessor(0xf000) == 0x0f00); 1595 result = vT.remove(0x0f00); 1596 assert(result); 1597 assert(vT.predecessor(0x0f00) == 0x00f0); 1598 result = vT.remove(0x00f0); 1599 assert(result); 1600 assert(vT.predecessor(0x00f0) == 0x000f); 1601 result = vT.remove(0x000f); 1602 assert(result); 1603 assert(vT.predecessor(0x000f).isNull); 1604 } 1605 1606 /// 1607 unittest 1608 { 1609 const uint M = testedSize; 1610 VEBtree vT = new VEBtree(M); 1611 vT.insert(0xf000); 1612 assert(0xf000 in vT); 1613 vT.insert(0x0f00); 1614 assert(0x0f00 in vT); 1615 vT.insert(0x00f0); 1616 assert(0x00f0 in vT); 1617 vT.insert(0x000f); 1618 assert(0x000f in vT); 1619 1620 auto result = vT.remove(0xf000); 1621 assert(result); 1622 assert(!(0xf000 in vT)); 1623 result = vT.remove(0x0f00); 1624 assert(result); 1625 assert(!(0x0f00 in vT)); 1626 result = vT.remove(0x00f0); 1627 assert(result); 1628 assert(!(0x00f0 in vT)); 1629 result = vT.remove(0x000f); 1630 assert(result); 1631 assert(!(0x000f in vT)); 1632 } 1633 1634 /// 1635 unittest 1636 { 1637 //stress test 1638 auto currentSeed = unpredictableSeed(); 1639 static if(vdebug){write("UT: rand, stress "); writeln("seed: ", currentSeed);} 1640 rndGenInUse.seed(currentSeed); //initialize the random generator 1641 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 1642 // last test says: see below. 1643 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1644 VEBtree vT = new VEBtree(M); 1645 size_t[] arr; 1646 const auto howMuchFilled = vT.fill(arr, rndGenInUse); 1647 1648 assert(arr.length == howMuchFilled); 1649 1650 VEBtree vT2 = new VEBtree(M); 1651 1652 assert(vT2.capacity == vT.capacity); 1653 1654 auto rbt = redBlackTree!size_t(0); 1655 rbt.clear; 1656 1657 void fill1() 1658 { 1659 foreach(size_t i; arr) 1660 { 1661 vT2.insert(i); 1662 } 1663 1664 foreach(size_t i; arr) 1665 { 1666 vT2.remove(i); 1667 } 1668 assert(vT2.empty); 1669 1670 } 1671 1672 void fill2() 1673 { 1674 foreach(size_t i; arr) 1675 { 1676 rbt.insert(i); 1677 } 1678 } 1679 1680 /* 1681 this part is for speed test 1682 */ 1683 /* 1684 compiled with ldc2 vebtree.d -O -main -unittest 1685 results of stress tests: 1686 size of tree: 16777216 1687 howMuchFilled: 16252928 1688 VEB: 2 secs, 382 ms, 588 μs, and 8 hnsecs 1689 */ 1690 /* 1691 import std.stdio; 1692 writeln("size of tree: ", vT2.capacity); 1693 writeln("howMuchFilled: ", howMuchFilled); 1694 //auto r = benchmark!(fill1, fill2)(1); 1695 auto r = benchmark!(fill1)(1); 1696 //auto r = benchmark!(fill1)(1); 1697 auto f0Result = to!Duration(r[0]); 1698 //auto f1Result = to!Duration(r[1]); 1699 writeln("VEB: ", f0Result); //10ms 1700 writeln("rbt: ", f1Result); //40sec 1701 //assert(f0Result < f1Result); 1702 //*/ 1703 } 1704 1705 /// 1706 unittest 1707 { 1708 const uint currentSeed = unpredictableSeed(); 1709 static if(vdebug){write("UT: rand, member "); writeln("seed: ", currentSeed);} 1710 rndGenInUse.seed(currentSeed); //initialize the random generator 1711 const uint M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1712 uint[] sourceArr; 1713 sourceArr.length = M; 1714 // generate a random array as the source for the tree 1715 for(uint i = 0; i < M; i++) sourceArr[i] = uniform(0U, M, rndGenInUse); 1716 // constructor to test 1717 VEBtree vT = new VEBtree(sourceArr); 1718 // make the array values unique. 1719 auto uniqueArr = sort(sourceArr).uniq; 1720 // check, that all values are filled 1721 bool result; 1722 foreach(uint i; uniqueArr) 1723 { 1724 assert(i in vT); 1725 result = vT.remove(i); 1726 assert(result); 1727 } 1728 // check, that no other elements are present. 1729 assert(vT.empty); 1730 } 1731 1732 /// 1733 unittest 1734 { 1735 auto currentSeed = unpredictableSeed(); 1736 static if(vdebug){write("UT: rand, opSlice "); writeln("seed: ", currentSeed);} 1737 rndGenInUse.seed(currentSeed); //initialize the random generator 1738 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 1739 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1740 VEBtree vT = new VEBtree(M); 1741 1742 size_t[] arr; 1743 vT.fill(arr, rndGenInUse, 16); 1744 assert(setSymmetricDifference(vT[], sort(arr)).empty); 1745 } 1746 1747 /// 1748 unittest 1749 { 1750 const uint currentSeed = unpredictableSeed(); 1751 static if(vdebug){write("UT: rand, opslice[]. "); writeln("seed: ", currentSeed);} 1752 rndGenInUse.seed(currentSeed); //initialize the random generator 1753 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 1754 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1755 VEBtree vT = new VEBtree(M); 1756 size_t[] arr; 1757 vT.fill(arr, rndGenInUse, 16); 1758 const auto begin = 5; 1759 const auto end = 100; 1760 const auto filterRes = sort(arr).filter!(a => a >= begin && a < end).array; 1761 assert(setSymmetricDifference(filterRes, vT[begin..end]).empty); 1762 } 1763 1764 /// 1765 unittest { assert(isBidirectionalRange!VEBtree); } 1766 1767 /// 1768 unittest 1769 { 1770 VEBtree vT = new VEBtree(14); 1771 auto result = vT.insert(2); 1772 assert(result); 1773 result = vT.insert(5); 1774 assert(result); 1775 result = vT.insert(10); 1776 assert(result); 1777 assert(vT[] == [2, 5, 10]); 1778 } 1779 1780 /// 1781 unittest 1782 { 1783 /+ 1784 //another stress test 1785 auto currentSeed = unpredictableSeed(); 1786 static if(vdebug){write("UT: stress test 2 "); writeln("seed: ", currentSeed);} 1787 rndGenInUse.seed(currentSeed); //initialize the random generator 1788 1789 void fill16(){ VEBtree vT = new VEBtree(1 << 16); } 1790 void fill17(){ VEBtree vT = new VEBtree(1 << 17); } 1791 void fill18(){ VEBtree vT = new VEBtree(1 << 18); } 1792 void fill19(){ VEBtree vT = new VEBtree(1 << 19); } 1793 void fill20(){ VEBtree vT = new VEBtree(1 << 20); } 1794 void fill21(){ VEBtree vT = new VEBtree(1 << 21); } 1795 void fill22(){ VEBtree vT = new VEBtree(1 << 22); } 1796 void fill23(){ VEBtree vT = new VEBtree(1 << 23); } 1797 void fill24(){ VEBtree vT = new VEBtree(1 << 24); } 1798 void fill25(){ VEBtree vT = new VEBtree(1 << 25); } 1799 1800 /* 1801 This part is for speed test. 1802 */ 1803 /* 1804 import std.stdio; 1805 auto r = benchmark!(fill16, fill17, fill18, fill19, fill20, fill21, fill22, fill23, fill24, fill25)(1); 1806 //auto r = benchmark!(fill1)(1); 1807 auto f16Result = to!Duration(r[0]); 1808 auto f17Result = to!Duration(r[1]); 1809 auto f18Result = to!Duration(r[2]); 1810 auto f19Result = to!Duration(r[3]); 1811 auto f20Result = to!Duration(r[4]); 1812 auto f21Result = to!Duration(r[5]); 1813 auto f22Result = to!Duration(r[6]); 1814 auto f23Result = to!Duration(r[7]); 1815 auto f24Result = to!Duration(r[8]); 1816 auto f25Result = to!Duration(r[9]); 1817 writeln("VEB with M of ", 1 << 16, ": ", f16Result); 1818 writeln("VEB with M of ", 1 << 17, ": ", f17Result); 1819 writeln("VEB with M of ", 1 << 18, ": ", f18Result); 1820 writeln("VEB with M of ", 1 << 19, ": ", f19Result); 1821 writeln("VEB with M of ", 1 << 20, ": ", f20Result); 1822 writeln("VEB with M of ", 1 << 21, ": ", f21Result); 1823 writeln("VEB with M of ", 1 << 22, ": ", f22Result); 1824 writeln("VEB with M of ", 1 << 23, ": ", f23Result); 1825 writeln("VEB with M of ", 1 << 24, ": ", f24Result); 1826 writeln("VEB with M of ", 1 << 25, ": ", f25Result); 1827 //*/ 1828 +/ 1829 } 1830 1831 /// 1832 unittest 1833 { 1834 // This unittest is for check of adding of big numbers 1835 /* in debug mode about 1 min. 1836 const uint[] arr = [1, 2, 8, 2_147_483_647]; 1837 new VEBtree(arr); 1838 //*/ 1839 }