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 }