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 65 private enum vdebug = false; 66 67 version(unittest) 68 { 69 static if(vdebug){import std.stdio;} 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 // some different filling functions for the tree. This simply tries to fill the tree with random numbers. Duplicates 98 // will be ignored, the given tree is modified. 99 auto fill(ref VEBtree vT, size_t m, Random rndGenInUse) 100 { 101 size_t n; 102 for(size_t i = 0; i < m; ++i) 103 { 104 auto x = uniform(0, vT.expectedSize, rndGenInUse); 105 // the check for membership is done to add only on inserting to the counter, not just 106 // because visiting the the loop 107 if(!(x in vT)) 108 { 109 vT.insert(x); 110 ++n; 111 } 112 } 113 return n; 114 } 115 116 // Ditto. This method asserts, that a given filling percentage is achieved. 117 auto fill(ref VEBtree vT, ref size_t[] arr, Random rndGenInUse, size_t fillPercentage = 31) 118 { 119 size_t n; 120 arr.length = fillPercentage * vT.capacity/32; 121 while(n != fillPercentage * vT.capacity/32) 122 { 123 auto x = uniform(0, vT.capacity - 1, rndGenInUse); 124 // the check for membership is done to add only on inserting to the counter, not just 125 // because visiting the the loop 126 if(!(x in vT)) 127 { 128 vT.insert(x); 129 arr[n] = x; 130 ++n; 131 } 132 } 133 assert(n == fillPercentage*vT.capacity/32); 134 return n; 135 } 136 } 137 138 /** 139 the baseSize defines the cutoff limit, where the node goes into the bit array mode. It is parametrized on the size 140 of size_t and changes dynamically with the architecture used. 141 */ 142 enum baseSize = 8 * size_t.sizeof; 143 144 /** 145 the maxSizeBound defines the maximum the tree can be constructed with. It is parametrized on the size of size_t and 146 changes dynamically with the architecture used. 147 */ 148 enum maxSizeBound = (size_t(1) << baseSize/2) + 1; 149 150 /// Convinience function to return the ceiling to the next power of two of the given input. 151 @nogc nothrow size_t nPof2(size_t value) 152 in 153 { 154 assert(value != 0); 155 assert(bsr(value) < baseSize - 1); 156 } 157 body { return size_t(1) << (bsr(value) + 1); } 158 /// 159 unittest 160 { 161 const size_t currentSeed = unpredictableSeed(); 162 static if(vdebug){write("UT: nPof2. "); writeln("seed: ", currentSeed);} 163 rndGenInUse.seed(currentSeed); //initialize the random generator 164 const size_t M = uniform(1U,size_t.max/2, rndGenInUse); //set universe size to some integer. 165 166 const auto pOfM = nPof2(M); 167 assert((pOfM & (pOfM-1)) == 0); 168 const auto check = powersOfTwo.until(nPof2(M), OpenRight.no).array; 169 assert(M < check[$-1]); 170 assert(M > check[$-2]); 171 } 172 173 /** 174 This function returns the higher square root of the given input. It is needed in the initialization step 175 of the VEB tree to calculate the number of children of a given layer. And this is the universe size of the 176 summary of a node. The upper square root is defined by 2^{\lceil(\lg u)/2\rceil} 177 */ 178 @nogc nothrow size_t hSR(size_t value) 179 { 180 return size_t(1) << (bsr(value)/2 + ((bsr(value) & 1) || ((value != 0) && (value & (value - 1))))); 181 } 182 /// 183 unittest 184 { 185 const size_t currentSeed = unpredictableSeed(); 186 static if(vdebug){write("UT: hSR. "); 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 hSR = hSR(M); 190 191 assert((hSR & (hSR - 1)) == 0); 192 if(hSR < uint.max) assert(hSR >= sqrt(to!float(M))); 193 194 const auto check = powersOfTwo.until(hSR).array; 195 assert((check[$-1]) * (check[$-1]) < M); 196 } 197 198 /** 199 This function returns the lower square root of the given input. It is needed by the indexing functions 200 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 201 lower square root is defined by 2^{\lfloor(\lgu)/2\rfloor} 202 */ 203 @nogc nothrow size_t lSR(size_t value) { return size_t(1) << (bsr(value)/2); } 204 /// 205 unittest 206 { 207 const size_t currentSeed = unpredictableSeed(); 208 static if(vdebug){write("UT: lSR. "); writeln("seed: ", currentSeed);} 209 rndGenInUse.seed(currentSeed); //initialize the random generator 210 const size_t M = uniform(1U,size_t.max/2, rndGenInUse); //set universe size to some integer. 211 auto lSR = lSR(M); 212 213 assert((lSR & (lSR - 1)) == 0); 214 assert(lSR * lSR < M); 215 const auto check = powersOfTwo.find(lSR).array; 216 217 if(lSR < size_t.max/2) assert((check[1]) > sqrt(to!float(M))); 218 } 219 220 /* 221 This is an index function defined as \lfloor x/lSR(u)\rfloor. It is needed to find the appropriate cluster 222 of a element in the tree. It is a part of the ideal indexing function. 223 */ 224 private @nogc nothrow size_t high(size_t value, size_t uS) { return value >> (bsr(uS) / 2); } 225 // 226 unittest 227 { 228 const size_t currentSeed = unpredictableSeed(); 229 static if(vdebug){write("UT: high. "); writeln("seed: ", currentSeed);} 230 rndGenInUse.seed(currentSeed); //initialize the random generator 231 const size_t M = uniform(1U,size_t.max/2, rndGenInUse); //set universe size to some integer. 232 const size_t U = nPof2(M); 233 const size_t x = uniform(0U, U, rndGenInUse); 234 235 assert(high(x,U) == x / lSR(U)); 236 } 237 238 /* 239 This is an index function defined as fmod(value, lSR(uS)). It is needed to find the appropriate 240 value inside a cluster. It is part of the ideal indexing function 241 */ 242 private @nogc nothrow size_t low(size_t value, size_t uS) { return value & ((size_t(1) << (bsr(uS) / 2)) - 1); } 243 // 244 unittest 245 { 246 const size_t currentSeed = unpredictableSeed(); 247 static if(vdebug){write("UT: low. "); writeln("seed: ", currentSeed);} 248 rndGenInUse.seed(currentSeed); //initialize the random generator 249 const size_t M = uniform(1U,size_t.max/2, rndGenInUse); //set universe size to some integer. 250 const size_t U = nPof2(M); 251 const size_t x = uniform(0U, U, rndGenInUse); 252 253 assert(low(x, U) == (x & (lSR(U) - 1))); 254 } 255 256 /* 257 This is an index function to retain the searched value. It is defined as x * lSR(u) + y. Beyond this, the 258 relation holds: x = index(high(x), low(x)). This is the ideal indexing function of the tree. 259 */ 260 private @nogc nothrow size_t index(size_t uS, size_t x, size_t y){ return (x * lSR(uS) + y); } 261 // 262 unittest 263 { 264 const size_t currentSeed = unpredictableSeed(); 265 static if(vdebug){write("UT: index. "); writeln("seed: ", currentSeed);} 266 rndGenInUse.seed(currentSeed); //initialize the random generator 267 const size_t M = uniform(0U,size_t.max/2, rndGenInUse); //set universe size to some integer. 268 269 const size_t U = nPof2(M); 270 const size_t x = uniform(0U, U, rndGenInUse); 271 272 assert(index(U, high(x, U), low(x, U)) == x); 273 } 274 275 /** 276 This is the struct to represent a VEB tree node. As memebers it contains a value and a pointer to the children 277 array. As the pointer does not know the size of the array, it has to be passed in all methods, which require an 278 access to it. 279 Dependent from the (universe) size passed in a method the stored value will be interpretated in two different ways: 280 If the parameter passed shows, that the universe size is below the bit size of the stored value, then, it can be 281 handled as a bit array and all operations decay to operations defined in core.bitop. This case correspond to 282 the state of the node being a leaf. No children exist and the pointer should stay uninitialized 283 Otherwise, the value is interpretated as two values, the minimum and maximum stored at the same place in memory. The 284 minimum and maximum shows, which range is achievable through this node. The parameters passed to a function of the 285 node have to be well chosen, to hit the appropriate child. 286 The first element of the children array, if present is handled different. According to literature, it has the role 287 of the summary of the remaining children cluster. With it help it is possible to achieve a very small recursion 288 level during an access. 289 */ 290 struct VEBnode 291 { 292 /* 293 This pointer acts as an array to nodes like this one. As the universe size is not provided, the length of the 294 array can not be used to calculate the most of operations, so no explicit array is needed. The only remaining 295 property is whether the pointer is set at all. From this property the node can decide, whether it is a leaf or 296 an intermediate node. 297 */ 298 private VEBnode* ptrArr; // the first member behaves different, as the others, as it is the summary node. 299 300 /// property returning the summary node 301 @nogc nothrow @property ref inout(VEBnode) summary() inout 302 in { assert(!isLeaf); } 303 body { return ptrArr[0]; } 304 unittest 305 { 306 auto currentSeed = unpredictableSeed(); // 83_843; 898_797_859; 307 static if(vdebug){write("UT: vN, summary. "); writeln("seed: ", currentSeed);} 308 rndGenInUse.seed(currentSeed); //initialize the random generator 309 310 VEBnode vN = VEBnode(512); 311 assert(!vN.isLeaf); 312 vN.ptrArr[0]._val = 73; 313 assert(vN.summary._val == 73); 314 } 315 316 /// property returning the cluster array 317 @nogc nothrow @property inout(VEBnode*) cluster() inout 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 private 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 nothrow 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 nothrow @property bool isLeaf() const { return ptrArr == null; } 425 426 /** method to check whether the current node holds a value */ 427 @nogc nothrow @property bool isNull() const { return isLeaf ? (_val == 0) : (_min > _max); } 428 429 /** method executing the appropriate steps to nullify the current node */ 430 @nogc nothrow @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 @nogc nothrow @property Nullable!(size_t, maxSizeBound) min() const 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 @nogc nothrow @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 @nogc nothrow @property Nullable!(size_t, maxSizeBound) max() const 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 @nogc nothrow @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 @nogc nothrow bool opIn_r(size_t bitnum) const 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 @nogc nothrow bool member(size_t value, size_t uS) const 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 @nogc nothrow 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 @nogc nothrow 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 @nogc nothrow 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 @nogc nothrow 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 @nogc nothrow Nullable!(size_t, maxSizeBound) predecessor(size_t bitNum) const 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 @nogc nothrow Nullable!(size_t, maxSizeBound) predecessor(size_t value, size_t uS) const 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 @nogc nothrow Nullable!(size_t, maxSizeBound) successor(size_t bitNum) const 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 @nogc nothrow Nullable!(size_t, maxSizeBound) successor(size_t value, size_t uS) const 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 struct 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 /// this value tracks the total range of the tree to be able to move on it independent from its copies 903 private auto _range = iota(0UL); 904 905 /// default constructor of a VEB tree is disabled. 906 @disable this(); 907 908 private this(VEBnode* root_, size_t expectedSize_, size_t elementCount_, typeof(iota(0UL)) range_) @nogc 909 { 910 root = root_; 911 expectedSize = expectedSize_; 912 _elementCount = elementCount_; 913 _range = range_; 914 } 915 916 /** 917 to construct a VEB tree the wished size has to be provided. However, the size should be greater then one and 918 should not excess the maximum allowed size for the current architecture. 919 */ 920 nothrow this(size_t value) 921 in 922 { 923 assert(value > 1); 924 assert(value < maxSizeBound); 925 } 926 body 927 { 928 // set the expected size to the passed value 929 expectedSize = value; 930 // delegate the creation of the nodes with the apropriate power of two of the needed universe size 931 root = new VEBnode(nPof2(expectedSize - 1)); 932 933 assert(this.empty); 934 } 935 /// 936 unittest 937 { 938 auto currentSeed = unpredictableSeed(); 939 static if(vdebug){write("UT: vT, __ctor. "); writeln("seed: ", currentSeed);} 940 rndGenInUse.seed(currentSeed); //initialize the random generator 941 942 auto uS = uniform(1U << size_t(1),testedSize, rndGenInUse); 943 const VEBtree vT = VEBtree(uS); 944 assert(vT.empty); 945 if((uS & (uS - 1)) == 0) 946 assert(vT.capacity == uS); 947 else 948 assert(vT.capacity == (size_t(1) << (bsr(uS) + 1))); 949 950 assert(vT.expectedSize == uS); 951 952 const auto uS1 = uniform(1U << size_t(1),testedSize, rndGenInUse); 953 const auto uSsmall = uniform(1U << size_t(1),baseSize, rndGenInUse); 954 VEBtree vT1 = VEBtree(uS1); 955 const VEBtree vTsmall = VEBtree(uSsmall); 956 957 assert(vTsmall.root._val == 0); 958 assert(vTsmall.root.ptrArr == null); 959 960 if(uS1 > 8 * size_t.sizeof) 961 { 962 assert(vT1.root._val == 1); 963 assert(vT1.root.ptrArr != null); 964 965 //check every child for consistency. 966 // the size of a node is higher square root & the summary node. 967 968 // capacity is tested elsewhere. 969 // hSR is also tested elsewhere 970 const auto childsAmount_l1 = hSR(vT1.capacity) + 1; 971 const auto childsAmount_l2 = hSR(lSR(vT1.capacity)) > baseSize ? hSR(lSR(vT1.capacity)) + 1 : 0; 972 973 // the tree is just created, assert all children are nullified 974 for(size_t i; i < childsAmount_l1; ++i) 975 { 976 assert(vT1.root.ptrArr[i].isNull); 977 if(childsAmount_l1 > baseSize + 1) 978 { 979 for(size_t j; j < childsAmount_l2; ++j) 980 { 981 assert(vT1.root.ptrArr[i].ptrArr[j].isNull); 982 } 983 } 984 } 985 } 986 } 987 988 /// another possibility is to construct a VEB tree is by providing an array. 989 nothrow this(R)(R range) if(isIterable!R) 990 in 991 { 992 // check, whether the range is not too long. I. e. expressable with an uint. 993 assert(range.length < maxSizeBound); 994 } 995 body 996 { 997 import std.algorithm.comparison : max; 998 // first, we have to determine the size of the tree. 999 // it is either derived from the length of the given tree or its greatest element 1000 size_t limit; 1001 foreach(size_t i; range) limit = max(limit,i); 1002 // assert no element has exceeded the allowed range of baseSize/2 1003 assert(limit < maxSizeBound); 1004 // if the array is longer, then the greatest element, but the length passes, substitute the limit 1005 limit = max(limit, range.length); 1006 // call the constructor with the limit 1007 this(limit + 1); 1008 // put every element from the range into the tree 1009 foreach(size_t i; range) insert(i); 1010 } 1011 1012 /** 1013 this method returns the capacity of the tree. It is equal to the next power of 2 regarding the size used at 1014 initialization. 1015 */ 1016 @nogc nothrow size_t capacity() const { return nPof2(expectedSize - 1); } 1017 1018 /** 1019 this method is used to add an element to the tree. duplicate values will be ignored. the class provides an 1020 intermediate layer between the caller and the contained root and enrichs the input by the stored size. 1021 */ 1022 auto insert(size_t value) @nogc nothrow 1023 { 1024 if(value >= capacity) return false; 1025 const bool retVal = root.insert(value, capacity); 1026 if(retVal) 1027 { 1028 ++_elementCount; 1029 1030 if(length == 1) _range = iota(value, value + 1UL); 1031 else 1032 { 1033 if(value < _range.front) _range = iota(value, _range.back + 1UL); 1034 if(value > _range.back) _range = iota(_range.front, value + 1UL); 1035 } 1036 1037 } 1038 return retVal; 1039 } 1040 /// 1041 unittest 1042 { 1043 auto currentSeed = unpredictableSeed(); 1044 static if(vdebug){write("UT: vT, insert. "); writeln("seed: ", currentSeed);} 1045 rndGenInUse.seed(currentSeed); //initialize the random generator 1046 1047 auto uS = uniform(allowedArraySize,testedSize, rndGenInUse); 1048 VEBtree vT = VEBtree(uS); 1049 1050 size_t n; 1051 uint[allowedArraySize] insertedVals; 1052 while(n < allowedArraySize) 1053 { 1054 auto valToInsert = uniform(0U, uS, rndGenInUse); 1055 const bool inserted = vT.insert(valToInsert); 1056 if(inserted) 1057 { 1058 insertedVals[n] = valToInsert; 1059 n++; 1060 } 1061 } 1062 assert(vT._elementCount == insertedVals.length); 1063 1064 sort(insertedVals[]); 1065 assert(uniq(insertedVals[]).array.length == insertedVals.length); 1066 } 1067 1068 /// this method overrides the insert method to directly use arrays 1069 @nogc nothrow void insert(R)(R arr) if(isIterable!R){ foreach(size_t i; arr) insert(i); } 1070 1071 /// this method is used to remove elements from the tree. not existing values will be ignored. 1072 bool remove(size_t value) @nogc nothrow 1073 { 1074 const bool retVal = root.remove(value, capacity); 1075 if(retVal) 1076 { 1077 --_elementCount; 1078 if(length == 0) _range = iota(0UL); 1079 else 1080 { 1081 assert(!_range.empty); 1082 if(value == _range.front) popFront(); 1083 if(value == _range.back) popBack(); 1084 } 1085 } 1086 return retVal; 1087 } 1088 /// 1089 unittest 1090 { 1091 auto currentSeed = unpredictableSeed(); 1092 static if(vdebug){write("UT: vT, remove. "); writeln("seed: ", currentSeed);} 1093 rndGenInUse.seed(currentSeed); //initialize the random generator 1094 1095 auto uS = uniform(allowedArraySize,testedSize, rndGenInUse); 1096 VEBtree vT = VEBtree(uS); 1097 1098 size_t n; 1099 uint[allowedArraySize] insertedVals; 1100 1101 while(n < allowedArraySize) 1102 { 1103 auto valToInsert = uniform(0U, uS, rndGenInUse); 1104 if(vT.insert(valToInsert)) 1105 { 1106 insertedVals[n] = valToInsert; 1107 n++; 1108 } 1109 } 1110 1111 assert(vT._elementCount == insertedVals.length); 1112 1113 foreach(size_t i; insertedVals) assert(vT.remove(i)); 1114 assert(vT.length == 0); 1115 } 1116 1117 /// this method is used to determine, whether an element is currently present in the tree 1118 @nogc nothrow bool opIn_r(size_t value) const 1119 { 1120 if(value >= capacity) return false; 1121 return root.member(value, capacity); 1122 } 1123 /// 1124 unittest 1125 { 1126 auto currentSeed = unpredictableSeed(); 1127 static if(vdebug){write("UT: vT, member. "); writeln("seed: ", currentSeed);} 1128 rndGenInUse.seed(currentSeed); //initialize the random generator 1129 1130 auto uS = uniform(allowedArraySize,testedSize, rndGenInUse); 1131 VEBtree vT = VEBtree(uS); 1132 1133 size_t n; 1134 uint[allowedArraySize] insertedVals; 1135 while(n < allowedArraySize) 1136 { 1137 auto valToInsert = uniform(0U, uS, rndGenInUse); 1138 if(vT.insert(valToInsert)) 1139 { 1140 insertedVals[n] = valToInsert; 1141 n++; 1142 } 1143 } 1144 1145 sort(insertedVals[]); 1146 auto sortedInserted = assumeSorted(insertedVals[]); 1147 for(size_t i; i < testedSize; ++i) 1148 { 1149 if(sortedInserted.contains(i)) 1150 { 1151 assert(i in vT); 1152 } 1153 else 1154 { 1155 assert(!(i in vT), "i: " ~ to!string(i)); 1156 } 1157 } 1158 } 1159 1160 /// this method is used to determine the minimum of the tree 1161 @nogc nothrow @property Nullable!(size_t, maxSizeBound) min() const { return root.min; } 1162 1163 /// this method is used to determine the maximum of the tree 1164 @nogc nothrow @property Nullable!(size_t, maxSizeBound) max() const { return root.max; } 1165 1166 /// this method retrieves the successor of the given input. 1167 Nullable!(size_t, maxSizeBound) successor(alias boundaries = "()")(size_t value) const 1168 { 1169 if(value >= capacity) return Nullable!(size_t, maxSizeBound)(); 1170 1171 // otherwise get the successor 1172 auto currentSuccessor = root.successor(value, capacity); 1173 1174 // in case of closed boundaries 1175 static if(boundaries[1] == ']') // if there is a successor (between the value and the upper bound) 1176 { 1177 if(!currentSuccessor.isNull) return currentSuccessor; // return the successor 1178 else return Nullable!(size_t, maxSizeBound)(capacity); // otherwise return the bound (capacity) 1179 } 1180 else return currentSuccessor; // in case of open boundaries return the successor (null or a value) 1181 } 1182 unittest 1183 { 1184 auto currentSeed = unpredictableSeed(); 1185 static if(vdebug){write("UT: vT, successor. "); writeln("seed: ", currentSeed);} 1186 rndGenInUse.seed(currentSeed); //initialize the random generator 1187 1188 auto uS = uniform(allowedArraySize, testedSize, rndGenInUse); 1189 VEBtree vT = VEBtree(uS); 1190 1191 // testing the boundaries now: 1192 auto randomElement = uniform(allowedArraySize, uS); 1193 assert(vT.successor(randomElement).isNull); 1194 assert(vT.successor!"[]"(randomElement) == vT.capacity); 1195 1196 size_t n; 1197 uint[allowedArraySize] insertedVals; 1198 while(n < allowedArraySize) 1199 { 1200 auto valToInsert = uniform(0U, uS, rndGenInUse); 1201 if(vT.insert(valToInsert)) 1202 { 1203 insertedVals[n] = valToInsert; 1204 n++; 1205 } 1206 } 1207 1208 auto sortedInserted = assumeSorted(sort(insertedVals[])); 1209 1210 assert(vT.max == sortedInserted.back); 1211 assert(vT.min == sortedInserted.front); 1212 size_t j; 1213 1214 for(size_t i = 0; i <= testedSize; ++i) 1215 { 1216 const auto el = vT.successor(i); 1217 1218 if(el.isNull) 1219 { 1220 assert(i == vT.max); 1221 assert(sortedInserted.contains(i)); 1222 break; // quit the loop; 1223 } 1224 else 1225 { 1226 if(sortedInserted.contains(i)) ++j; 1227 assert(el == sortedInserted[j]); 1228 } 1229 } 1230 } 1231 1232 /// this method retrieves the predecessor of the given input. 1233 @nogc nothrow Nullable!(size_t, maxSizeBound) predecessor(alias boundaries = "()")(size_t value) const 1234 { 1235 auto currentPredecessor = root.predecessor(value, capacity); 1236 static if(boundaries[0] == '[') 1237 { 1238 if(!currentPredecessor.isNull) 1239 return currentPredecessor; 1240 else 1241 return Nullable!(size_t, maxSizeBound)(0); 1242 } 1243 else return currentPredecessor; 1244 } 1245 /// 1246 unittest 1247 { 1248 auto currentSeed = unpredictableSeed(); 1249 static if(vdebug){write("UT: vT, predecessor. "); writeln("seed: ", currentSeed);} 1250 rndGenInUse.seed(currentSeed); //initialize the random generator 1251 1252 auto uS = uniform(allowedArraySize,testedSize, rndGenInUse); 1253 VEBtree vT = VEBtree(uS); 1254 1255 // testing the boundaries now: 1256 auto randomElement = uniform(allowedArraySize, uS); 1257 assert(vT.predecessor(randomElement).isNull); 1258 assert(vT.predecessor!"[]"(randomElement) == 0); 1259 1260 size_t n; 1261 uint[allowedArraySize] insertedVals; 1262 while(n < allowedArraySize) 1263 { 1264 auto valToInsert = uniform(0U, uS, rndGenInUse); 1265 if(vT.insert(valToInsert)) 1266 { 1267 insertedVals[n] = valToInsert; 1268 n++; 1269 } 1270 } 1271 1272 auto sortedInserted = assumeSorted(sort(insertedVals[])); 1273 1274 assert(vT.max == sortedInserted.back); 1275 assert(vT.min == sortedInserted.front); 1276 size_t j = allowedArraySize - 1; 1277 1278 size_t i = testedSize + 1; 1279 do 1280 { 1281 --i; 1282 const auto el = vT.predecessor(i); 1283 if(el.isNull) 1284 { 1285 assert(i == vT.min); 1286 assert(sortedInserted.contains(i)); 1287 break; // quit the loop; 1288 1289 } 1290 else 1291 { 1292 if(sortedInserted.contains(i)) --j; 1293 assert(el == sortedInserted[j]); 1294 } 1295 1296 }while(i > 0); 1297 } 1298 1299 /// this method is used to determine, whether the tree is currently containing an element. 1300 @nogc nothrow @property bool empty() const { return _range.empty; } 1301 1302 /// this method returns the minimium. 1303 @nogc nothrow @property size_t front() { return _range.front; } 1304 1305 /// this method removes the minimum element 1306 void popFront() @nogc nothrow 1307 { 1308 auto s = successor(_range.front); 1309 if(s.isNull) _range = iota(maxSizeBound, 0UL); 1310 else _range = iota(s.get, _range.back + 1UL); 1311 } 1312 1313 /// bidirectional range also needs 1314 @nogc nothrow @property size_t back() { return _range.back; } 1315 1316 /// this method removes the maximum element 1317 @nogc nothrow void popBack() 1318 { 1319 if(!empty) 1320 { 1321 assert(!_range.empty); 1322 auto p = predecessor(_range.back); 1323 if(p.isNull) _range = iota(maxSizeBound, 0UL); 1324 else _range = iota(_range.front, p.get + 1UL); 1325 } 1326 } 1327 1328 /// Returns whether the element is in the tree 1329 auto opIndex(size_t index) const @nogc nothrow 1330 { 1331 if(index in this) return index; 1332 else return maxSizeBound; 1333 } 1334 1335 /// This method returns the amount of elements currently present in the tree. 1336 @nogc nothrow @property size_t length() const { return _elementCount; } 1337 1338 /** 1339 forward range also needs save. This is a draft version of the save function, it uses the opslice of the struct 1340 to construct a new one via an array 1341 */ 1342 @property VEBtree save() { return VEBtree(root, expectedSize, _elementCount, _range.save); } 1343 1344 /// dollar operator overload. 1345 @nogc nothrow @property size_t opDollar() 1346 { 1347 auto cMax = this.max; 1348 if(cMax.isNull) return capacity; 1349 else return cMax + 1; 1350 } 1351 1352 /** 1353 The single slice operation (slice-all) which is supported by the tree. Returns all elements in a new array. 1354 A convinience method. Uses exportTree with the boundaries set to the default ("()") 1355 */ 1356 size_t[] opSlice() const { return exportTree(); } 1357 1358 /// Makes a deep copy of the current object. 1359 VEBtree dup() const 1360 { 1361 auto retVal = VEBtree(expectedSize); 1362 1363 if(this.length == 0) return retVal; 1364 1365 auto curr = this.min; 1366 do 1367 { 1368 retVal.insert(curr.get); 1369 curr = successor(curr.get); 1370 }while(!curr.isNull); 1371 1372 return retVal; 1373 } 1374 1375 /** 1376 this method serves as export of the tree to an array. () and [] is possible as template parameter to export the 1377 boundaries, even if they are not present. 1378 */ 1379 auto exportTree(alias boundaries = "()")() const 1380 { 1381 size_t[] retArray; 1382 auto exportLength = this.length; 1383 1384 static if(boundaries[0] == '[') 1385 if(!(0 in this)) // if zero is not in the tree and we want to include the left boundary, the export grows 1386 ++exportLength; 1387 static if(boundaries[1] == ']') 1388 ++exportLength; // we want to include the capacity as value, so the export grows 1389 1390 if(exportLength == 0) return retArray; 1391 else retArray.length = exportLength; 1392 1393 static if(boundaries[0] == '[') retArray[0] = 0; 1394 else if(!this.empty) retArray[0] = this.min; 1395 1396 static if(boundaries[1] == ']') retArray[$-1] = capacity; 1397 else if(!this.empty) retArray[$-1] = this.max; 1398 1399 for(size_t i = 1; i < retArray.length; ++i) 1400 { 1401 const auto succ = successor!boundaries(retArray[i-1]); 1402 if(succ.isNull || succ == capacity) break; 1403 retArray[i] = succ; 1404 } 1405 1406 return retArray; 1407 } 1408 // (optional) todo: implement some kind of cool output as a graphViz pic, similiar to the graphs in Cormen. 1409 } 1410 1411 /// 1412 unittest 1413 { 1414 VEBtree vT = VEBtree(100); 1415 assert(vT.empty); 1416 const auto result = vT.insert(2); 1417 assert(result); 1418 assert(!vT.empty); 1419 assert(2 in vT); 1420 1421 VEBtree vT2 = vT.save(); 1422 auto const vT3 = vT.dup(); 1423 assert(2 in vT2); 1424 const result2 = vT2.insert(3); 1425 assert(result2); 1426 assert(3 in vT2); 1427 assert(3 in vT); 1428 assert(!(3 in vT3)); 1429 assert(vT2.length == 2); 1430 1431 } 1432 1433 /// 1434 unittest 1435 { 1436 auto currentSeed = unpredictableSeed(); 1437 static if(vdebug){write("UT: vT, exportTree. "); writeln("seed: ", currentSeed);} 1438 rndGenInUse.seed(currentSeed); //initialize the random generator 1439 1440 const auto M = uniform(2U,testedSize, rndGenInUse); //set universe size to some integer. 1441 VEBtree vT = VEBtree(M); //create the tree 1442 vT.fill(1000, rndGenInUse); 1443 1444 //assert(vT.exportTree == vT[]); 1445 assert(vT.exportTree!"[)".front == 0); 1446 assert(vT.exportTree!"(]".back == vT.capacity); 1447 } 1448 /// 1449 unittest 1450 { 1451 assert(!__traits(compiles, VEBtree())); 1452 VEBtree vT = VEBtree(1000); 1453 assert(vT.capacity == 1024); 1454 assert(vT.min.isNull); 1455 assert(vT.insert(2)); 1456 vT.insert(5); 1457 assert(!(8 in vT)); 1458 assert(vT.insert(88)); 1459 assert(88 in vT); 1460 assert(vT.predecessor(4) == 2); 1461 assert(!(8 in vT)); 1462 assert(vT.insert(8)); 1463 assert(8 in vT); 1464 assert(vT.predecessor(75) == 8); 1465 assert(vT.predecessor(90) == 88); 1466 assert(vT.predecessor(7) == 5); 1467 assert(vT.predecessor(4) == 2); 1468 assert(vT.predecessor(2).isNull); 1469 assert(vT.predecessor!"[]"(2) == 0); 1470 assert(vT.successor(6) == 8); 1471 assert(vT.successor(5) == 8); 1472 assert(vT.successor(4) == 5); 1473 assert(vT.successor(1) == 2); 1474 assert(vT.successor(75) == 88); 1475 assert(vT.successor(90).isNull); 1476 assert(vT.successor!"[]"(90) == vT.capacity); 1477 assert(!(1029 in vT)); 1478 assert(vT.successor(1025).isNull); 1479 assert(vT.successor!"[]"(1025).isNull); 1480 1481 auto vT2 = new VEBtree(500); 1482 assert(vT2.empty); 1483 vT2.insert(50); 1484 vT2.insert(500); 1485 assert(vT2.max == 500); 1486 assert(vT2.min == 50); 1487 assert(vT2.successor(40) == 50); 1488 assert(vT2.successor(50) == 500); 1489 1490 vT2 = new VEBtree(500); 1491 assert(vT2.empty); 1492 vT2.insert(50); 1493 vT2.insert(500); 1494 assert(vT2.max == 500); 1495 assert(vT2.min == 50); 1496 assert(vT2.successor(40) == 50); 1497 assert(vT2.successor(50) == 500); 1498 1499 /* about 20 seconds in debug mode. 1500 auto vT3 = new VEBtree(uint.max); 1501 assert(vT3.insert(5)); 1502 assert(vT3.member(5)); 1503 assert(vT3.capacity == cast(ulong)uint.max + 1); 1504 //*/ 1505 1506 assert(!(1029 in vT)); 1507 assert(!(865 in vT)); 1508 assert(vT.insert(865)); 1509 assert(865 in vT); 1510 assert(!vT.insert(865)); 1511 assert(865 in vT); 1512 assert(!(866 in vT)); 1513 assert(!vT.remove(866)); 1514 assert(865 in vT); 1515 assert(vT.remove(865)); 1516 assert(!(865 in vT)); 1517 } 1518 1519 /// 1520 unittest 1521 { 1522 auto currentSeed = unpredictableSeed(); 1523 static if(vdebug){write("UT: rand, succ. "); writeln("seed: ", currentSeed);} 1524 rndGenInUse.seed(currentSeed); //initialize the random generator 1525 1526 const auto M = uniform(2U,testedSize, rndGenInUse); //set universe size to some integer. 1527 VEBtree vT = VEBtree(M); //create the tree 1528 assert(vT.capacity == nPof2(M-1)); 1529 const auto m = vT.fill(40, rndGenInUse); //(try to) fill the tree with thousend values 1530 size_t n; 1531 Nullable!(size_t, maxSizeBound) i = vT.max; 1532 1533 // discover the thousend (or little less) values with the predecessor method 1534 while(!i.isNull) 1535 { 1536 ++n; 1537 i = vT.predecessor(i); 1538 if(n > m) break; 1539 } 1540 1541 size_t o; 1542 i = vT.min; 1543 while(!i.isNull) 1544 { 1545 ++o; 1546 i = vT.successor(i.get); 1547 if(o - 1 > m) break; 1548 } 1549 1550 // assert, that all members are discovered, iff when no predecessors are left 1551 assert(n == m); 1552 assert(o == m); 1553 } 1554 1555 /// 1556 unittest 1557 { 1558 auto currentSeed = unpredictableSeed(); 1559 static if(vdebug){write("UT: rand, pred "); writeln("seed: ", currentSeed);} 1560 rndGenInUse.seed(currentSeed); //initialize the random generator 1561 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1562 VEBtree vT = VEBtree(M); 1563 vT.fill(1000, rndGenInUse); //fill the tree with some values 1564 Nullable!(size_t, maxSizeBound) i = vT.max; 1565 1566 // remove all members beginning from the maximum 1567 bool result; 1568 while(!i.isNull) 1569 { 1570 result = vT.remove(i); 1571 assert(result); 1572 const auto j = vT.predecessor(i); 1573 if(!j.isNull) 1574 assert(j != i); 1575 i = j; 1576 } 1577 1578 // assert, that all members are removed, iff when no predecessors are left. 1579 assert(vT.empty); 1580 } 1581 1582 /// 1583 unittest 1584 { 1585 auto currentSeed = unpredictableSeed(); 1586 static if(vdebug){write("UT: rand, remove "); writeln("seed: ", currentSeed);} 1587 rndGenInUse.seed(currentSeed); //initialize the random generator 1588 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1589 VEBtree vT = VEBtree(M); 1590 vT.fill(1000, rndGenInUse); //fill the tree with some values 1591 Nullable!(size_t, maxSizeBound) i = vT.min; 1592 1593 // remove all members beginning from the minimum 1594 bool result; 1595 while(!i.isNull) 1596 { 1597 result = vT.remove(i); 1598 assert(result); 1599 const auto j = vT.successor(i); 1600 if(!j.isNull) 1601 assert(j != i); 1602 i = j; 1603 } 1604 1605 // assert, that all members are removed, iff when no successors are left. 1606 assert(vT.empty); 1607 } 1608 1609 /// 1610 unittest 1611 { 1612 const uint M = testedSize; 1613 VEBtree vT = VEBtree(M); 1614 vT.insert(0x000f); 1615 assert(vT.predecessor(0x000f).isNull); 1616 vT.insert(0x00f0); 1617 assert(vT.predecessor(0x00f0) == 0x000f); 1618 vT.insert(0x0f00); 1619 assert(vT.predecessor(0x0f00) == 0x00f0); 1620 vT.insert(0xf000); 1621 assert(vT.predecessor(0xf000) == 0x0f00); 1622 1623 auto result = vT.remove(0xf000); 1624 assert(result); 1625 assert(vT.predecessor(0xf000) == 0x0f00); 1626 result = vT.remove(0x0f00); 1627 assert(result); 1628 assert(vT.predecessor(0x0f00) == 0x00f0); 1629 result = vT.remove(0x00f0); 1630 assert(result); 1631 assert(vT.predecessor(0x00f0) == 0x000f); 1632 result = vT.remove(0x000f); 1633 assert(result); 1634 assert(vT.predecessor(0x000f).isNull); 1635 } 1636 1637 /// 1638 unittest 1639 { 1640 const uint M = testedSize; 1641 VEBtree vT = VEBtree(M); 1642 vT.insert(0xf000); 1643 assert(0xf000 in vT); 1644 vT.insert(0x0f00); 1645 assert(0x0f00 in vT); 1646 vT.insert(0x00f0); 1647 assert(0x00f0 in vT); 1648 vT.insert(0x000f); 1649 assert(0x000f in vT); 1650 1651 auto result = vT.remove(0xf000); 1652 assert(result); 1653 assert(!(0xf000 in vT)); 1654 result = vT.remove(0x0f00); 1655 assert(result); 1656 assert(!(0x0f00 in vT)); 1657 result = vT.remove(0x00f0); 1658 assert(result); 1659 assert(!(0x00f0 in vT)); 1660 result = vT.remove(0x000f); 1661 assert(result); 1662 assert(!(0x000f in vT)); 1663 } 1664 1665 /// 1666 unittest 1667 { 1668 //stress test 1669 auto currentSeed = unpredictableSeed(); 1670 static if(vdebug){write("UT: rand, stress "); writeln("seed: ", currentSeed);} 1671 rndGenInUse.seed(currentSeed); //initialize the random generator 1672 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 1673 // last test says: see below. 1674 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1675 VEBtree vT = VEBtree(M); 1676 size_t[] arr; 1677 const auto howMuchFilled = vT.fill(arr, rndGenInUse); 1678 1679 assert(arr.length == howMuchFilled); 1680 1681 VEBtree vT2 = VEBtree(M); 1682 1683 assert(vT2.capacity == vT.capacity); 1684 1685 auto rbt = redBlackTree!size_t(0); 1686 rbt.clear; 1687 1688 void fill1() 1689 { 1690 foreach(size_t i; arr) 1691 { 1692 vT2.insert(i); 1693 } 1694 1695 foreach(size_t i; arr) 1696 { 1697 vT2.remove(i); 1698 } 1699 assert(vT2.empty); 1700 1701 } 1702 1703 void fill2() 1704 { 1705 foreach(size_t i; arr) 1706 { 1707 rbt.insert(i); 1708 } 1709 } 1710 1711 /* 1712 this part is for speed test 1713 */ 1714 /* 1715 compiled with ldc2 vebtree.d -O -main -unittest 1716 results of stress tests: 1717 size of tree: 16777216 1718 howMuchFilled: 16252928 1719 VEB: 2 secs, 382 ms, 588 μs, and 8 hnsecs 1720 */ 1721 /* 1722 import std.stdio; 1723 1724 writeln("size of tree: ", vT2.capacity); 1725 writeln("howMuchFilled: ", howMuchFilled); 1726 //auto r = benchmark!(fill1, fill2)(1); 1727 auto r = benchmark!(fill1)(1); 1728 1729 auto f0Result = to!Duration(r[0]); 1730 //auto f1Result = to!Duration(r[1]); 1731 writeln("VEB: ", f0Result); //10ms 1732 //writeln("rbt: ", f1Result); //40sec 1733 //assert(f0Result < f1Result); 1734 //*/ 1735 } 1736 1737 /// 1738 unittest 1739 { 1740 const uint currentSeed = unpredictableSeed(); 1741 static if(vdebug){write("UT: rand, member "); writeln("seed: ", currentSeed);} 1742 rndGenInUse.seed(currentSeed); //initialize the random generator 1743 const uint M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1744 uint[] sourceArr; 1745 sourceArr.length = M; 1746 // generate a random array as the source for the tree 1747 for(uint i = 0; i < M; i++) sourceArr[i] = uniform(0U, M, rndGenInUse); 1748 // constructor to test 1749 VEBtree vT = VEBtree(sourceArr); 1750 // make the array values unique. 1751 auto uniqueArr = sort(sourceArr).uniq; 1752 // check, that all values are filled 1753 bool result; 1754 foreach(uint i; uniqueArr) 1755 { 1756 assert(i in vT); 1757 result = vT.remove(i); 1758 assert(result); 1759 } 1760 // check, that no other elements are present. 1761 assert(vT.empty); 1762 } 1763 1764 /// 1765 unittest 1766 { 1767 auto currentSeed = unpredictableSeed(); 1768 static if(vdebug){write("UT: rand, opSlice "); writeln("seed: ", currentSeed);} 1769 rndGenInUse.seed(currentSeed); //initialize the random generator 1770 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 1771 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1772 VEBtree vT = VEBtree(M); 1773 1774 size_t[] arr; 1775 vT.fill(arr, rndGenInUse, 16); 1776 //assert(setSymmetricDifference(vT[], sort(arr)).empty); 1777 } 1778 1779 /// 1780 unittest 1781 { 1782 assert(isBidirectionalRange!VEBtree); 1783 assert(isRandomAccessRange!VEBtree); 1784 } 1785 1786 /// 1787 unittest 1788 { 1789 VEBtree vT = VEBtree(14); 1790 auto result = vT.insert(2); 1791 assert(result); 1792 result = vT.insert(5); 1793 assert(result); 1794 result = vT.insert(10); 1795 assert(result); 1796 //assert(vT[] == [2, 5, 10]); 1797 } 1798 1799 /// 1800 unittest 1801 { 1802 /* 1803 //another stress test 1804 auto currentSeed = unpredictableSeed(); 1805 static if(vdebug){write("UT: stress test 2 "); writeln("seed: ", currentSeed);} 1806 rndGenInUse.seed(currentSeed); //initialize the random generator 1807 1808 void fill16(){ VEBtree vT = VEBtree(1 << 16); } 1809 void fill17(){ VEBtree vT = VEBtree(1 << 17); } 1810 void fill18(){ VEBtree vT = VEBtree(1 << 18); } 1811 void fill19(){ VEBtree vT = VEBtree(1 << 19); } 1812 void fill20(){ VEBtree vT = VEBtree(1 << 20); } 1813 void fill21(){ VEBtree vT = VEBtree(1 << 21); } 1814 void fill22(){ VEBtree vT = VEBtree(1 << 22); } 1815 void fill23(){ VEBtree vT = VEBtree(1 << 23); } 1816 void fill24(){ VEBtree vT = VEBtree(1 << 24); } 1817 void fill25(){ VEBtree vT = VEBtree(1 << 25); } 1818 void fill26(){ VEBtree vT = VEBtree(1 << 26); } 1819 void fill27(){ VEBtree vT = VEBtree(1 << 27); } 1820 void fill28(){ VEBtree vT = VEBtree(1 << 28); } 1821 void fill29(){ VEBtree vT = VEBtree(1 << 29); } 1822 void fill30(){ VEBtree vT = VEBtree(1 << 30); } 1823 1824 import std.stdio; 1825 auto r = benchmark!(fill16, fill17, fill18, fill19, fill20, fill21, fill22, fill23, fill24, fill25, fill26, fill27, 1826 fill28, fill29, fill30)(1); 1827 //auto r = benchmark!(fill1)(1); 1828 auto f16Result = to!Duration(r[0]); 1829 auto f17Result = to!Duration(r[1]); 1830 auto f18Result = to!Duration(r[2]); 1831 auto f19Result = to!Duration(r[3]); 1832 auto f20Result = to!Duration(r[4]); 1833 auto f21Result = to!Duration(r[5]); 1834 auto f22Result = to!Duration(r[6]); 1835 auto f23Result = to!Duration(r[7]); 1836 auto f24Result = to!Duration(r[8]); 1837 auto f25Result = to!Duration(r[9]); 1838 auto f26Result = to!Duration(r[10]); 1839 auto f27Result = to!Duration(r[11]); 1840 auto f28Result = to!Duration(r[12]); 1841 auto f29Result = to!Duration(r[13]); 1842 auto f30Result = to!Duration(r[14]); 1843 1844 writeln("VEB with M of ", 1 << 16, ": ", f16Result); 1845 writeln("VEB with M of ", 1 << 17, ": ", f17Result); 1846 writeln("VEB with M of ", 1 << 18, ": ", f18Result); 1847 writeln("VEB with M of ", 1 << 19, ": ", f19Result); 1848 writeln("VEB with M of ", 1 << 20, ": ", f20Result); 1849 writeln("VEB with M of ", 1 << 21, ": ", f21Result); 1850 writeln("VEB with M of ", 1 << 22, ": ", f22Result); 1851 writeln("VEB with M of ", 1 << 23, ": ", f23Result); 1852 writeln("VEB with M of ", 1 << 24, ": ", f24Result); 1853 writeln("VEB with M of ", 1 << 25, ": ", f25Result); 1854 writeln("VEB with M of ", 1 << 26, ": ", f26Result); 1855 writeln("VEB with M of ", 1 << 27, ": ", f27Result); 1856 writeln("VEB with M of ", 1 << 28, ": ", f28Result); 1857 writeln("VEB with M of ", 1 << 29, ": ", f29Result); 1858 writeln("VEB with M of ", 1 << 30, ": ", f30Result); 1859 //*/ 1860 1861 } 1862 1863 /// 1864 unittest 1865 { 1866 // This unittest is for check of adding of big numbers 1867 /* in debug mode about 1 min. 1868 const uint[] arr = [1, 2, 8, 2_147_483_647]; 1869 new VEBtree(arr); 1870 //*/ 1871 } 1872 1873 /// 1874 unittest 1875 { 1876 import std.algorithm : sort, uniq; 1877 //stress test 1878 auto currentSeed = unpredictableSeed(); 1879 static if(vdebug){write("UT: rand, ranges "); writeln("seed: ", currentSeed);} 1880 rndGenInUse.seed(currentSeed); //initialize the random generator 1881 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 1882 // last test says: see below. 1883 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 1884 auto const vT = VEBtree(M); 1885 /*testing the range methods*/ 1886 assert(vT.empty); 1887 1888 uint[] sourceArr; 1889 sourceArr.length = uniform(2U, M, rndGenInUse); 1890 for(uint i = 0; i < sourceArr.length; i++) 1891 sourceArr[i] = uniform(0U, M, rndGenInUse); 1892 1893 sort(sourceArr); 1894 const auto uniqueArr = sourceArr.uniq.array; 1895 1896 // constructor to test 1897 1898 auto vTnew = VEBtree(sourceArr); 1899 assert(!vTnew.empty); 1900 assert(vTnew.length == uniqueArr.length); 1901 const auto vT2 = vTnew.save; 1902 assert(vTnew.array == uniqueArr); 1903 assert(!vTnew.empty); 1904 assert(!vT2.empty); 1905 assert(vT2[] == uniqueArr); 1906 1907 /* Works. Duration in debug mode: about 35 seconds. 1908 auto vTT = new VEBtree(maxSizeBound - 1); 1909 assert(vTT.insert(42)); 1910 */ 1911 }