// Package bits provides a bit vector interface and several implementations
package bits
import (
"strconv"
)
// The Vector interface defines methods on the bit vector
type Vector interface {
// Retrieves the bit at the designated position
Peek(uint) bool
// Sets the bit at the designated position
Poke(uint, bool)
// Flips the bit at the designated position
Flip(uint)
// Returns the total number of elements supported by the vector
Len() uint
}
// A Vector type that simply stores booleans in a slice
type boolvector []bool
// Retrieves the bit at the designated position
func (v boolvector) Peek(pos uint) bool {
return v[pos]
}
// Sets the bit at the designated position
func (v boolvector) Poke(pos uint, val bool) {
v[pos] = val
}
// Flips the bit at the designated position
func (v boolvector) Flip(pos uint) {
v[pos] = !v[pos]
}
// Returns the total number of elements supported by the vector
func (v boolvector) Len() uint {
return uint(len(v))
}
func NewBool(size uint) Vector {
var slice []bool = make([]bool, size)
return boolvector(slice)
}
type vector []uint
// Retrieves the bit at the designated position
func (v vector) Peek(pos uint) bool {
var slot, offset uint = at(pos)
return (v[slot] & (1 << offset)) > 0
}
// Sets the bit at the designated position
func (v vector) Poke(pos uint, val bool) {
var slot, offset uint = at(pos)
if val {
v[slot] |= (1 << offset)
} else {
v[slot] &^= (1 << offset)
}
}
// Flips the bit at the designated position
func (v vector) Flip(pos uint) {
var slot, offset uint = at(pos)
v[slot] ^= (1 << offset)
}
// Returns the total number of elements supported by the vector
func (v vector) Len() uint {
return uint(len(v) * strconv.IntSize)
}
func at(pos uint) (uint, uint) {
return pos / strconv.IntSize, pos % strconv.IntSize
}
// Create a new bit vector sized up to the desired number of elements
func NewBit(size uint) Vector {
var length uint = size / strconv.IntSize
if size%strconv.IntSize > 0 {
// Allocate one additional slot if the desired
// size is does not divide by 32/64
length++
}
var slice []uint = make([]uint, length)
return vector(slice)
}