taldir

bitset.go (6062B)

---

 // go-qrcode
 // Copyright 2014 Tom Harwood
 
 // Package bitset implements an append only bit array.
 //
 // To create a Bitset and append some bits:
 //	                                  // Bitset Contents
 //	b := bitset.New()                 // {}
 //	b.AppendBools(true, true, false)  // {1, 1, 0}
 //	b.AppendBools(true)               // {1, 1, 0, 1}
 //	b.AppendValue(0x02, 4)            // {1, 1, 0, 1, 0, 0, 1, 0}
 //
 // To read values:
 //
 //	len := b.Len()                    // 8
 //	v := b.At(0)                      // 1
 //	v = b.At(1)                       // 1
 //	v = b.At(2)                       // 0
 //	v = b.At(8)                       // 0
 package bitset
 
 import (
 	"bytes"
 	"fmt"
 	"log"
 )
 
 const (
 	b0 = false
 	b1 = true
 )
 
 // Bitset stores an array of bits.
 type Bitset struct {
 	// The number of bits stored.
 	numBits int
 
 	// Storage for individual bits.
 	bits []byte
 }
 
 // New returns an initialised Bitset with optional initial bits v.
 func New(v ...bool) *Bitset {
 	b := &Bitset{numBits: 0, bits: make([]byte, 0)}
 	b.AppendBools(v...)
 
 	return b
 }
 
 // Clone returns a copy.
 func Clone(from *Bitset) *Bitset {
 	return &Bitset{numBits: from.numBits, bits: from.bits[:]}
 }
 
 // Substr returns a substring, consisting of the bits from indexes start to end.
 func (b *Bitset) Substr(start int, end int) *Bitset {
 	if start > end || end > b.numBits {
 		log.Panicf("Out of range start=%d end=%d numBits=%d", start, end, b.numBits)
 	}
 
 	result := New()
 	result.ensureCapacity(end - start)
 
 	for i := start; i < end; i++ {
 		if b.At(i) {
 			result.bits[result.numBits/8] |= 0x80 >> uint(result.numBits%8)
 		}
 		result.numBits++
 	}
 
 	return result
 }
 
 // NewFromBase2String constructs and returns a Bitset from a string. The string
 // consists of '1', '0' or ' ' characters, e.g. "1010 0101". The '1' and '0'
 // characters represent true/false bits respectively, and ' ' characters are
 // ignored.
 //
 // The function panics if the input string contains other characters.
 func NewFromBase2String(b2string string) *Bitset {
 	b := &Bitset{numBits: 0, bits: make([]byte, 0)}
 
 	for _, c := range b2string {
 		switch c {
 		case '1':
 			b.AppendBools(true)
 		case '0':
 			b.AppendBools(false)
 		case ' ':
 		default:
 			log.Panicf("Invalid char %c in NewFromBase2String", c)
 		}
 	}
 
 	return b
 }
 
 // AppendBytes appends a list of whole bytes.
 func (b *Bitset) AppendBytes(data []byte) {
 	for _, d := range data {
 		b.AppendByte(d, 8)
 	}
 }
 
 // AppendByte appends the numBits least significant bits from value.
 func (b *Bitset) AppendByte(value byte, numBits int) {
 	b.ensureCapacity(numBits)
 
 	if numBits > 8 {
 		log.Panicf("numBits %d out of range 0-8", numBits)
 	}
 
 	for i := numBits - 1; i >= 0; i-- {
 		if value&(1<<uint(i)) != 0 {
 			b.bits[b.numBits/8] |= 0x80 >> uint(b.numBits%8)
 		}
 
 		b.numBits++
 	}
 }
 
 // AppendUint32 appends the numBits least significant bits from value.
 func (b *Bitset) AppendUint32(value uint32, numBits int) {
 	b.ensureCapacity(numBits)
 
 	if numBits > 32 {
 		log.Panicf("numBits %d out of range 0-32", numBits)
 	}
 
 	for i := numBits - 1; i >= 0; i-- {
 		if value&(1<<uint(i)) != 0 {
 			b.bits[b.numBits/8] |= 0x80 >> uint(b.numBits%8)
 		}
 
 		b.numBits++
 	}
 }
 
 // ensureCapacity ensures the Bitset can store an additional |numBits|.
 //
 // The underlying array is expanded if necessary. To prevent frequent
 // reallocation, expanding the underlying array at least doubles its capacity.
 func (b *Bitset) ensureCapacity(numBits int) {
 	numBits += b.numBits
 
 	newNumBytes := numBits / 8
 	if numBits%8 != 0 {
 		newNumBytes++
 	}
 
 	if len(b.bits) >= newNumBytes {
 		return
 	}
 
 	b.bits = append(b.bits, make([]byte, newNumBytes+2*len(b.bits))...)
 }
 
 // Append bits copied from |other|.
 //
 // The new length is b.Len() + other.Len().
 func (b *Bitset) Append(other *Bitset) {
 	b.ensureCapacity(other.numBits)
 
 	for i := 0; i < other.numBits; i++ {
 		if other.At(i) {
 			b.bits[b.numBits/8] |= 0x80 >> uint(b.numBits%8)
 		}
 		b.numBits++
 	}
 }
 
 // AppendBools appends bits to the Bitset.
 func (b *Bitset) AppendBools(bits ...bool) {
 	b.ensureCapacity(len(bits))
 
 	for _, v := range bits {
 		if v {
 			b.bits[b.numBits/8] |= 0x80 >> uint(b.numBits%8)
 		}
 		b.numBits++
 	}
 }
 
 // AppendNumBools appends num bits of value value.
 func (b *Bitset) AppendNumBools(num int, value bool) {
 	for i := 0; i < num; i++ {
 		b.AppendBools(value)
 	}
 }
 
 // String returns a human readable representation of the Bitset's contents.
 func (b *Bitset) String() string {
 	var bitString string
 	for i := 0; i < b.numBits; i++ {
 		if (i % 8) == 0 {
 			bitString += " "
 		}
 
 		if (b.bits[i/8] & (0x80 >> byte(i%8))) != 0 {
 			bitString += "1"
 		} else {
 			bitString += "0"
 		}
 	}
 
 	return fmt.Sprintf("numBits=%d, bits=%s", b.numBits, bitString)
 }
 
 // Len returns the length of the Bitset in bits.
 func (b *Bitset) Len() int {
 	return b.numBits
 }
 
 // Bits returns the contents of the Bitset.
 func (b *Bitset) Bits() []bool {
 	result := make([]bool, b.numBits)
 
 	var i int
 	for i = 0; i < b.numBits; i++ {
 		result[i] = (b.bits[i/8] & (0x80 >> byte(i%8))) != 0
 	}
 
 	return result
 }
 
 // At returns the value of the bit at |index|.
 func (b *Bitset) At(index int) bool {
 	if index >= b.numBits {
 		log.Panicf("Index %d out of range", index)
 	}
 
 	return (b.bits[index/8] & (0x80 >> byte(index%8))) != 0
 }
 
 // Equals returns true if the Bitset equals other.
 func (b *Bitset) Equals(other *Bitset) bool {
 	if b.numBits != other.numBits {
 		return false
 	}
 
 	if !bytes.Equal(b.bits[0:b.numBits/8], other.bits[0:b.numBits/8]) {
 		return false
 	}
 
 	for i := 8 * (b.numBits / 8); i < b.numBits; i++ {
 		a := (b.bits[i/8] & (0x80 >> byte(i%8)))
 		b := (other.bits[i/8] & (0x80 >> byte(i%8)))
 
 		if a != b {
 			return false
 		}
 	}
 
 	return true
 }
 
 // ByteAt returns a byte consisting of upto 8 bits starting at index.
 func (b *Bitset) ByteAt(index int) byte {
 	if index < 0 || index >= b.numBits {
 		log.Panicf("Index %d out of range", index)
 	}
 
 	var result byte
 
 	for i := index; i < index+8 && i < b.numBits; i++ {
 		result <<= 1
 		if b.At(i) {
 			result |= 1
 		}
 	}
 
 	return result
 }