1package structs
2
3import "fmt"
4
5// Bitmap is a simple uncompressed bitmap
6type Bitmap []byte
7
8// NewBitmap returns a bitmap with up to size indexes
9func NewBitmap(size uint) (Bitmap, error) {
10	if size == 0 {
11		return nil, fmt.Errorf("bitmap must be positive size")
12	}
13	if size&7 != 0 {
14		return nil, fmt.Errorf("bitmap must be byte aligned")
15	}
16	b := make([]byte, size>>3)
17	return Bitmap(b), nil
18}
19
20// Copy returns a copy of the Bitmap
21func (b Bitmap) Copy() (Bitmap, error) {
22	if b == nil {
23		return nil, fmt.Errorf("can't copy nil Bitmap")
24	}
25
26	raw := make([]byte, len(b))
27	copy(raw, b)
28	return Bitmap(raw), nil
29}
30
31// Size returns the size of the bitmap
32func (b Bitmap) Size() uint {
33	return uint(len(b) << 3)
34}
35
36// Set is used to set the given index of the bitmap
37func (b Bitmap) Set(idx uint) {
38	bucket := idx >> 3
39	mask := byte(1 << (idx & 7))
40	b[bucket] |= mask
41}
42
43// Unset is used to unset the given index of the bitmap
44func (b Bitmap) Unset(idx uint) {
45	bucket := idx >> 3
46	// Mask should be all ones minus the idx position
47	offset := 1 << (idx & 7)
48	mask := byte(offset ^ 0xff)
49	b[bucket] &= mask
50}
51
52// Check is used to check the given index of the bitmap
53func (b Bitmap) Check(idx uint) bool {
54	bucket := idx >> 3
55	mask := byte(1 << (idx & 7))
56	return (b[bucket] & mask) != 0
57}
58
59// Clear is used to efficiently clear the bitmap
60func (b Bitmap) Clear() {
61	for i := range b {
62		b[i] = 0
63	}
64}
65
66// IndexesInRange returns the indexes in which the values are either set or unset based
67// on the passed parameter in the passed range
68func (b Bitmap) IndexesInRange(set bool, from, to uint) []int {
69	var indexes []int
70	for i := from; i <= to && i < b.Size(); i++ {
71		c := b.Check(i)
72		if c && set || !c && !set {
73			indexes = append(indexes, int(i))
74		}
75	}
76
77	return indexes
78}
79