A Bitset in Go

bitset.go

package bitset

import (
	"fmt"
	"math"
)

type Bitset struct {
	data        []byte
	cardinality int
	capacity    int
}

type OutOfBoundsError struct {
	index int
}

func (error *OutOfBoundsError) Error() string {
	return fmt.Sprintf("Index out of bounds: %d", error.index)
}

func New(numberOfBits int) (bitset *Bitset) {
	bytesToAllocate := int(math.Ceil(float64(numberOfBits) / 8))
	return &Bitset{
		make([]byte, bytesToAllocate),
		0,
		numberOfBits,
	}
}

func (bitset *Bitset) Cardinality() int {
	return bitset.cardinality
}

func (bitset *Bitset) Capacity() int {
	return bitset.capacity
}

func (bitset *Bitset) Set(index int) error {
	if index >= bitset.Capacity() {
		return &OutOfBoundsError{index}
	}

	byteIndex := byteFromIndex(index)
	bitIndex := bitFromIndex(index)

	bit := byte(1 << uint32(bitIndex))
	previous := bitset.data[byteIndex] & bit

	if previous == 0 {
		bitset.data[byteIndex] |= bit
		bitset.cardinality += 1
	}

	return nil
}

func (bitset *Bitset) Clear(index int) error {
	if index >= bitset.Capacity() {
		return &OutOfBoundsError{index}
	}

	byteIndex := byteFromIndex(index)
	bitIndex := bitFromIndex(index)

	bit := byte(1 << uint32(bitIndex))
	previous := bitset.data[byteIndex] & bit

	if previous != 0 {
		bitset.data[byteIndex] &= ^bit
		bitset.cardinality -= 1
	}

	return nil
}

func (bitset *Bitset) Toggle(index int) error {
	if index >= bitset.Capacity() {
		return &OutOfBoundsError{index}
	}

	byteIndex := byteFromIndex(index)
	bitIndex := bitFromIndex(index)

	bit := byte(1 << uint32(bitIndex))
	previous := bitset.data[byteIndex] & bit

	bitset.data[byteIndex] ^= bit

	if previous == 0 {
		bitset.cardinality -= 1
	}

	return nil
}

func (bitset *Bitset) Test(index int) (bool, error) {
	if index >= bitset.Capacity() {
		return false, &OutOfBoundsError{index}
	}

	byteIndex := byteFromIndex(index)
	bitIndex := bitFromIndex(index)

	bit := byte(1 << uint32(bitIndex))
	value := bitset.data[byteIndex] & bit

	return value != 0, nil
}

func (bitset *Bitset) Flip() {
	for index, chunk := range bitset.data {
		bitset.data[index] = ^chunk
	}
}

func (bitset *Bitset) String() string {
	bits := make([]rune, bitset.Capacity())
	index := 0

	for _, chunk := range bitset.data {
		var bit uint8 = 0
		for ; bit < 8; bit++ {
			value := chunk & (1 << bit)
			if value == 0 {
				bits[index] = '0'
			} else {
				bits[index] = '1'
			}

			index += 1

			if index == len(bits) {
				return string(bits)
			}
		}
	}

	return string(bits)
}

func (bitset *Bitset) Any() bool {
	return bitset.cardinality > 0
}

func (bitset *Bitset) All() bool {
	return bitset.cardinality == bitset.Capacity()
}

func (bitset *Bitset) None() bool {
	return bitset.cardinality == 0
}

func byteFromIndex(index int) int {
	return index / 8
}

func bitFromIndex(index int) int {
	return index % 8
}