1 2 module roaring.roaring; 3 4 import roaring.c; 5 6 Bitmap bitmapOf(const uint[] args ...) 7 { 8 return Bitmap.fromArray(args); 9 } 10 11 Bitmap bitmapOf(const uint[] bits) 12 { 13 return Bitmap.fromArray(bits); 14 } 15 16 Bitmap bitmapOf(T)(T rng) 17 { 18 auto r = new Bitmap; 19 foreach (bit; rng) r.add(bit); 20 return r; 21 } 22 23 unittest 24 { 25 import std.range : iota; 26 import std.conv : to; 27 const r1 = bitmapOf(0, 1, 2, 3, 4); 28 const r2 = bitmapOf([0, 1, 2, 3, 4]); 29 const r3 = bitmapOf(5.iota); 30 assert("{0, 1, 2, 3, 4}" == to!string(r1)); 31 assert((r1 == r2) && (r1 == r3)); 32 } 33 34 Bitmap readBitmap(const char[] buf) 35 { 36 return Bitmap.read(buf); 37 } 38 39 char[] writeBitmap(const Bitmap r) 40 { 41 return r.write(); 42 } 43 44 unittest 45 { 46 import core.exception : OutOfMemoryError; 47 const r1 = bitmapOf(5, 1, 2, 3, 5, 6); 48 char[] buf = writeBitmap(r1); 49 const r2 = readBitmap(buf); 50 assert(r1 == r2); 51 try { 52 buf.length = 0; 53 readBitmap(buf) || assert(false); 54 } 55 catch (OutOfMemoryError e) { 56 // pass 57 } 58 } 59 60 BitRange range(const Bitmap r) 61 { 62 return new BitRange(r.bitmap); 63 } 64 65 class BitRange 66 { 67 @nogc @property @safe 68 bool empty() const pure 69 { 70 return !this.it.has_value; 71 } 72 73 @nogc @property @safe 74 uint front() const pure 75 { 76 return this.it.current_value; 77 } 78 79 @nogc 80 void popFront() 81 { 82 if (it.has_value) roaring_advance_uint32_iterator(this.it); 83 } 84 85 @nogc 86 private this(const roaring_bitmap_t *bmp) 87 { 88 this.it = roaring_create_iterator(bmp); 89 } 90 91 @nogc 92 private ~this() 93 { 94 if (this.it) roaring_free_uint32_iterator(this.it); 95 } 96 97 private roaring_uint32_iterator_t *it; 98 } 99 100 unittest 101 { 102 import std.algorithm : filter, sum; 103 assert(6 == bitmapOf(1, 2, 3, 4, 5).range.filter!(a => a % 2 == 0).sum); 104 } 105 106 107 108 class Bitmap 109 { 110 /// Creates an empty bitmap 111 this() 112 { 113 this(roaring_bitmap_create()); 114 } 115 116 ~this() 117 { 118 roaring_bitmap_free(this.bitmap); 119 this.bitmap = null; 120 } 121 122 /** Creates an empty bitmap with a predefined capacity 123 PARAMS 124 uint cap: The predefined capacity 125 */ 126 this(const uint cap) 127 { 128 this(roaring_bitmap_create_with_capacity(cap)); 129 } 130 131 private this(roaring_bitmap_t *r) 132 { 133 this.bitmap = r; 134 } 135 136 private static Bitmap fromArray(const uint[] bits) 137 { 138 Bitmap r = new Bitmap(cast(uint)bits.length); 139 roaring_bitmap_add_many(r.bitmap, bits.length, bits.ptr); 140 return r; 141 } 142 143 private static Bitmap fromRange(const ulong min, const ulong max, const uint step) 144 { 145 auto rr = roaring_bitmap_from_range(min, max, step); 146 return new Bitmap(rr); 147 } 148 149 private static Bitmap read(const char[] buf) 150 { 151 import core.exception : OutOfMemoryError; 152 auto rr = roaring_bitmap_portable_deserialize_safe(buf.ptr, buf.length); 153 if (!rr) { 154 throw new OutOfMemoryError; 155 } 156 return new Bitmap(rr); 157 } 158 159 private char[] write() const 160 { 161 char[] buf = new char[sizeInBytes]; 162 const size = roaring_bitmap_portable_serialize(this.bitmap, buf.ptr); 163 return buf[0..size]; 164 } 165 166 @nogc @property @safe 167 uint length() const pure 168 { 169 return cast(uint)roaring_bitmap_get_cardinality(this.bitmap); 170 } 171 172 @nogc @property @safe 173 void copyOnWrite(bool enable) pure 174 { 175 this.bitmap.copy_on_write = enable; 176 } 177 178 @nogc @property @safe 179 bool copyOnWrite() const pure 180 { 181 return this.bitmap.copy_on_write; 182 } 183 184 unittest 185 { 186 Bitmap r = new Bitmap; 187 r.copyOnWrite = true; 188 assert(r.copyOnWrite == true); 189 } 190 191 uint[] toArray() const 192 { 193 uint[] a = new uint[length]; 194 roaring_bitmap_to_uint32_array(this.bitmap, a.ptr); 195 return a[]; 196 } 197 198 unittest 199 { 200 const r = bitmapOf(5, 1, 2, 3, 5, 6); 201 uint[] a = r.toArray; 202 assert(a.length == 5); 203 } 204 205 @nogc @safe 206 void add(const uint x) 207 { 208 roaring_bitmap_add(this.bitmap, x); 209 } 210 211 unittest 212 { 213 Bitmap r = new Bitmap; 214 r.add(5); 215 assert(5 in r); 216 } 217 218 /** 219 * Remove value x 220 * 221 */ 222 @nogc @safe 223 void remove(const uint x) 224 { 225 roaring_bitmap_remove(this.bitmap, x); 226 } 227 228 unittest 229 { 230 Bitmap r = bitmapOf(5); 231 r.remove(5); 232 assert(5 !in r); 233 } 234 235 /** 236 * Check if value x is present 237 */ 238 @nogc @safe 239 bool contains(const uint x) const pure 240 { 241 return roaring_bitmap_contains(this.bitmap, x); 242 } 243 244 /** 245 * Return the largest value (if not empty) 246 * 247 */ 248 @nogc @property @safe 249 uint maximum() const pure 250 { 251 return roaring_bitmap_maximum(this.bitmap); 252 } 253 254 /** 255 * Return the smallest value (if not empty) 256 * 257 */ 258 @nogc @property @safe 259 uint minimum() const pure 260 { 261 return roaring_bitmap_minimum(this.bitmap); 262 } 263 264 unittest 265 { 266 const r2 = bitmapOf(100, 10, uint.max); 267 assert(r2.minimum == 10); 268 assert(r2.maximum == uint.max); 269 } 270 271 @nogc @property @safe 272 size_t sizeInBytes() const pure 273 { 274 return roaring_bitmap_portable_size_in_bytes(this.bitmap); 275 } 276 277 unittest 278 { 279 assert(bitmapOf(5).sizeInBytes > 4); 280 } 281 282 /** 283 * Returns the number of integers that are smaller or equal to x. 284 */ 285 @nogc @safe 286 ulong rank(const uint rank) const pure 287 { 288 return roaring_bitmap_rank(this.bitmap, rank); 289 } 290 291 unittest 292 { 293 const r = bitmapOf(5, 1, 2, 3, 5, 6); 294 assert(r.rank(4) == 3); 295 } 296 297 @nogc @safe 298 bool optimize() 299 { 300 return roaring_bitmap_run_optimize(this.bitmap); 301 } 302 303 unittest 304 { 305 auto r1 = bitmapOf(5, 1, 2, 3, 5, 6); 306 r1.copyOnWrite = true; 307 //check optimization 308 auto size1 = r1.sizeInBytes; 309 r1.optimize; 310 assert(r1.sizeInBytes < size1); 311 } 312 313 int opApply(int delegate(ref uint value) dg) const 314 { 315 const bmp = this.bitmap; 316 auto it = roaring_create_iterator(bmp); 317 int dgReturn = 0; 318 while (it.has_value) { 319 dgReturn = dg(it.current_value); 320 if (dgReturn) break; 321 roaring_advance_uint32_iterator(it); 322 } 323 roaring_free_uint32_iterator(it); 324 return dgReturn; 325 } 326 327 unittest 328 { 329 const bitmap = bitmapOf(5, 1, 2, 3, 5, 6); 330 ulong sum; 331 foreach (bit; bitmap) { 332 sum += bit; 333 } 334 assert(sum == 17); 335 } 336 337 // TODO: un-duplicate this method with ^^^ 338 int opApply(int delegate(ref uint index, ref uint value) dg) const 339 { 340 const bmp = this.bitmap; 341 auto it = roaring_create_iterator(bmp); 342 int dgReturn = 0; 343 uint index = 0; 344 while (it.has_value) { 345 dgReturn = dg(index, it.current_value); 346 if (dgReturn) break; 347 index += 1; 348 roaring_advance_uint32_iterator(it); 349 } 350 roaring_free_uint32_iterator(it); 351 return dgReturn; 352 } 353 354 unittest 355 { 356 const bitmap = bitmapOf(5, 1, 2, 3, 5, 6); 357 ulong bitSum; 358 int iSum; 359 foreach (i, bit; bitmap) { 360 bitSum += bit; 361 iSum += i; 362 } 363 assert(bitSum == 17); 364 assert(iSum == 10); 365 } 366 367 Bitmap opBinary(const string op)(const Bitmap b) const 368 if (op == "&" || op == "|" || op == "^") 369 { 370 roaring_bitmap_t *result; 371 static if (op == "&") result = roaring_bitmap_and(this.bitmap, b.bitmap); 372 else static if (op == "|") result = roaring_bitmap_or(this.bitmap, b.bitmap); 373 else static if (op == "^") result = roaring_bitmap_xor(this.bitmap, b.bitmap); 374 else static assert(0, "Operator " ~ op ~ " not implemented."); 375 376 return new Bitmap(result); 377 } 378 379 unittest 380 { 381 const r1 = bitmapOf(5, 1, 2, 3, 5, 6); 382 const r2 = bitmapOf(6, 7, 8); 383 assert((r1 | r2) == bitmapOf(1, 2, 3, 5, 6, 7, 8)); 384 assert((r1 & r2) == bitmapOf(6)); 385 assert((r1 ^ r2) == bitmapOf(1, 2, 3, 5, 7, 8)); 386 } 387 388 @nogc @safe 389 bool opBinaryRight(const string op)(const uint x) const 390 if (op == "in") 391 { 392 static if (op == "in") return roaring_bitmap_contains(this.bitmap, x); 393 else static assert(0, "Operator " ~ op ~ " not implemented."); 394 } 395 396 unittest 397 { 398 import std.range : iota; 399 Bitmap r1 = bitmapOf(iota(100, 1000)); 400 assert(500 in r1); 401 } 402 403 bool opBinaryRight(const string op)(const Bitmap b) const 404 if (op == "in") 405 { 406 static if (op == "in") return roaring_bitmap_is_subset(b.bitmap, this.bitmap); 407 else static assert(0, "Operator " ~ op ~ " not implemented."); 408 } 409 410 unittest 411 { 412 import std.range : iota; 413 Bitmap r1 = bitmapOf(iota(100, 1000)); 414 Bitmap r2 = bitmapOf(iota(200, 400)); 415 assert(r2 in r1); 416 } 417 418 uint opIndex(uint rank) const 419 { 420 import core.exception : RangeError; 421 uint v; 422 if (!roaring_bitmap_select(this.bitmap, rank, &v)) { 423 throw new RangeError; 424 } 425 return v; 426 } 427 428 unittest 429 { 430 import core.exception : RangeError; 431 const bitmap = bitmapOf(5, 1, 2, 3, 5, 6); 432 assert(5 == bitmap[3]); 433 // accessing an index > cardinality(set) throws a RangeError 434 try { 435 bitmap[999] || assert(false); 436 } 437 catch (RangeError e) { 438 // pass 439 } 440 } 441 442 Bitmap opSlice(int start, int end) const 443 { 444 import core.exception : RangeError; 445 if (start < 0 || start >= opDollar) { 446 throw new RangeError; 447 } 448 Bitmap r = new Bitmap; 449 foreach (i, bit; this) { 450 if (i < start) continue; 451 if (i >= end) break; 452 r.add(this[i]); 453 } 454 return r; 455 } 456 457 @nogc @property @safe 458 uint opDollar() const pure 459 { 460 return length; 461 } 462 463 unittest 464 { 465 import core.exception : RangeError; 466 const bitmap = bitmapOf(5, 1, 2, 3, 5, 6); 467 assert(bitmapOf(3, 5, 6) == bitmap[2..$]); 468 469 import core.exception : RangeError; 470 // accessing an index < 0 throws a RangeError 471 try { 472 bitmap[-1..$] || assert(false); 473 } 474 catch (RangeError e) { 475 // pass 476 } 477 478 import core.exception : RangeError; 479 // accessing an index > $ throws a RangeError 480 try { 481 bitmap[$..$] || assert(false); 482 } 483 catch (RangeError e) { 484 // pass 485 } 486 } 487 488 override bool opEquals(Object b) const 489 { 490 import std.stdio : writeln; 491 if (this is b) return true; 492 if (b is null) return false; 493 if (typeid(this) == typeid(b)) { 494 return roaring_bitmap_equals(this.bitmap, (cast(Bitmap)b).bitmap); 495 } 496 return false; 497 } 498 499 unittest 500 { 501 const r1 = Bitmap.fromRange(10, 20, 3); 502 const r2 = Bitmap.fromArray([10, 13, 16, 19]); 503 assert(r1 == r2); 504 505 const r3 = Bitmap.fromArray([10]); 506 assert(r1 != r3); 507 508 assert(r1 != new Object); 509 } 510 511 void opOpAssign(const string op)(const uint x) 512 if (op == "|" || op == "-") 513 { 514 static if (op == "|") roaring_bitmap_add(this.bitmap, x); 515 else static if (op == "-") roaring_bitmap_remove(this.bitmap, x); 516 } 517 518 unittest 519 { 520 Bitmap r1 = new Bitmap; 521 r1 |= 500; 522 assert(500 in r1); 523 } 524 525 void toString(scope void delegate(const(char)[]) sink) const 526 { 527 import std.format : format; 528 import std.range : enumerate; 529 sink("{"); 530 foreach (i, bit; this) { 531 if (i == 0) sink(format("%d", bit)); 532 else sink(format(", %d", bit)); 533 } 534 sink("}"); 535 } 536 537 unittest 538 { 539 import std.conv : to; 540 const bitmap = bitmapOf(5, 1, 2, 3, 5, 6); 541 assert("{1, 2, 3, 5, 6}" == to!string(bitmap)); 542 } 543 544 private roaring_bitmap_t* bitmap; 545 } 546 547 unittest 548 { 549 import std.stdio : writefln, writeln; 550 import roaring.roaring : Bitmap, bitmapOf; 551 552 // create a new roaring bitmap instance 553 auto r1 = new Bitmap; 554 555 // add some bits to the bitmap 556 r1.add(5); 557 558 // create from an array 559 auto ra = bitmapOf([1, 2, 3]); 560 561 // create from a range 562 import std.range : iota; 563 assert(bitmapOf(0, 1, 2, 3) == bitmapOf(4.iota)); 564 565 // create a new roaring bitmap instance from some numbers 566 auto r2 = bitmapOf(1, 3, 5, 15); 567 568 // check whether a value is contained 569 assert(r2.contains(5)); 570 assert(5 in r2); // r2 contains 5 571 assert(99 !in r2); // r2 does not contain 99 572 573 // get minimum and maximum values in a bitmap 574 assert(r2.minimum == 1); 575 assert(r2.maximum == 15); 576 577 // remove a value from the bitmap 578 r2.remove(5); 579 assert(!r2.contains(5)); 580 581 // compute how many bits there are: 582 assert(3 == r2.length); 583 584 // check whether a bitmap is subset of another 585 const sub = bitmapOf(1, 5); 586 const sup = bitmapOf(1, 2, 3, 4, 5, 6); 587 assert(sub in sup); 588 589 // iterate on a bitmap 590 const r3 = bitmapOf(1, 5, 10, 20); 591 ulong s = 0; 592 foreach (bit; r3) { 593 s += bit; 594 } 595 assert(s == 36); 596 597 // iterate on a bitmap and index 598 foreach(i, bit; r3) { 599 writefln("%d: %d", i, bit); 600 } 601 602 import roaring.roaring : readBitmap, writeBitmap; 603 // serialize the bitmap 604 char[] buf = writeBitmap(r3); 605 // deserialize from a char array 606 const r3Copy = readBitmap(buf); 607 assert(r3 == r3Copy); 608 609 // find the intersection of bitmaps 610 const r4 = bitmapOf(1, 5, 6); 611 const r5 = bitmapOf(1, 2, 3, 4, 5); 612 assert((r4 & r5) == bitmapOf(1, 5)); 613 // find the union of bitmaps 614 assert((r4 | r5) == bitmapOf(1, 2, 3, 4, 5, 6)); 615 616 const r6 = bitmapOf(0, 10, 20, 30, 40, 50); 617 // get the bit for the index 618 assert(20 == r6[2]); 619 // slice a bitmap 620 assert(bitmapOf(30, 40, 50) == r6[3..$]); 621 622 // convert the bitmap to a string 623 writeln("Bitmap: ", r6); 624 import std.conv : to; 625 assert("{0, 10, 20, 30, 40, 50}" == to!string(r6)); 626 627 // the bit range! 628 import std.algorithm : filter, sum; 629 import roaring.roaring : range, BitRange; 630 // sum of bits in r6 which are bit % 20==0 631 assert(60 == r6.range.filter!(b => b % 20 == 0).sum); 632 633 // if your bitmaps have long runs, you can compress them 634 auto r7 = bitmapOf(1000.iota); 635 writeln("size before optimize = ", r7.sizeInBytes); 636 r7.optimize(); 637 writeln("size after optimize = ", r7.sizeInBytes); 638 }