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