bits.go at [e01b36769d]

File src/0dev.org/bits/bits.go artifact 415ad79153 part of check-in e01b36769d


// 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)
}