README
¶
bitset
Go language library to map between non-negative integers and boolean values
Description
Package bitset implements bitsets, a mapping between non-negative integers and boolean values. It should be more efficient than map[uint] bool.
It provides methods for setting, clearing, flipping, and testing individual integers.
But it also provides set intersection, union, difference, complement, and symmetric operations, as well as tests to check whether any, all, or no bits are set, and querying a bitset's current length and number of postive bits.
BitSets are expanded to the size of the largest set bit; the memory allocation is approximately Max bits, where Max is the largest set bit. BitSets are never shrunk. On creation, a hint can be given for the number of bits that will be used.
Many of the methods, including Set, Clear, and Flip, return a BitSet pointer, which allows for chaining.
Example use:
import "bitset"
var b BitSet
b.Set(10).Set(11)
if b.Test(1000) {
b.Clear(1000)
}
for i,e := v.NextSet(0); e; i,e = v.NextSet(i + 1) {
frmt.Println("The following bit is set:",i);
}
if B.Intersection(bitset.New(100).Set(10)).Count() > 1 {
fmt.Println("Intersection works.")
}
As an alternative to BitSets, one should check out the 'big' package, which provides a (less set-theoretical) view of bitsets.
Discussions golang-nuts Google Group:
Godoc documentation is at: https://godoc.org/github.com/willf/bitset
Getting started
This application is written in the go language, please refer to the guides in https://golang.org for getting started.
This project include a Makefile that allows you to test and build the project with simple commands. To see all available options:
make help
Running all tests
Before committing the code, please check if it passes all tests using
make qa
Documentation
¶
Overview ¶
Package bitset implements bitsets, a mapping between non-negative integers and boolean values. It should be more efficient than map[uint] bool.
It provides methods for setting, clearing, flipping, and testing individual integers.
But it also provides set intersection, union, difference, complement, and symmetric operations, as well as tests to check whether any, all, or no bits are set, and querying a bitset's current length and number of postive bits.
BitSets are expanded to the size of the largest set bit; the memory allocation is approximately Max bits, where Max is the largest set bit. BitSets are never shrunk. On creation, a hint can be given for the number of bits that will be used.
Many of the methods, including Set,Clear, and Flip, return a BitSet pointer, which allows for chaining.
Example use:
import "bitset"
var b BitSet
b.Set(10).Set(11)
if b.Test(1000) {
b.Clear(1000)
}
if B.Intersection(bitset.New(100).Set(10)).Count() > 1 {
fmt.Println("Intersection works.")
}
As an alternative to BitSets, one should check out the 'big' package, which provides a (less set-theoretical) view of bitsets.
Index ¶
- func Cap() uint
- type BitSet
- func (b *BitSet) All() bool
- func (b *BitSet) Any() bool
- func (b *BitSet) BinaryStorageSize() int
- func (b *BitSet) Bytes() []uint64
- func (b *BitSet) Clear(i uint) *BitSet
- func (b *BitSet) ClearAll() *BitSet
- func (b *BitSet) Clone() *BitSet
- func (b *BitSet) Complement() (result *BitSet)
- func (b *BitSet) Copy(c *BitSet) (count uint)
- func (b *BitSet) Count() uint
- func (b *BitSet) Difference(compare *BitSet) (result *BitSet)
- func (b *BitSet) DifferenceCardinality(compare *BitSet) uint
- func (b *BitSet) DumpAsBits() string
- func (b *BitSet) Equal(c *BitSet) bool
- func (b *BitSet) Flip(i uint) *BitSet
- func (b *BitSet) InPlaceDifference(compare *BitSet)
- func (b *BitSet) InPlaceIntersection(compare *BitSet)
- func (b *BitSet) InPlaceSymmetricDifference(compare *BitSet)
- func (b *BitSet) InPlaceUnion(compare *BitSet)
- func (b *BitSet) Intersection(compare *BitSet) (result *BitSet)
- func (b *BitSet) IntersectionCardinality(compare *BitSet) uint
- func (b *BitSet) IsStrictSuperSet(other *BitSet) bool
- func (b *BitSet) IsSuperSet(other *BitSet) bool
- func (b *BitSet) Len() uint
- func (b *BitSet) MarshalBinary() ([]byte, error)
- func (b *BitSet) MarshalJSON() ([]byte, error)
- func (b *BitSet) NextSet(i uint) (uint, bool)
- func (b *BitSet) None() bool
- func (b *BitSet) ReadFrom(stream io.Reader) (int64, error)
- func (b *BitSet) Set(i uint) *BitSet
- func (b *BitSet) SetTo(i uint, value bool) *BitSet
- func (b *BitSet) SymmetricDifference(compare *BitSet) (result *BitSet)
- func (b *BitSet) SymmetricDifferenceCardinality(compare *BitSet) uint
- func (b *BitSet) Test(i uint) bool
- func (b *BitSet) Union(compare *BitSet) (result *BitSet)
- func (b *BitSet) UnionCardinality(compare *BitSet) uint
- func (b *BitSet) UnmarshalBinary(data []byte) error
- func (b *BitSet) UnmarshalJSON(data []byte) error
- func (b *BitSet) WriteTo(stream io.Writer) (int64, error)
- type Error
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type BitSet ¶
type BitSet struct {
// contains filtered or unexported fields
}
A BitSet is a set of bits. The zero value of a BitSet is an empty set of length 0.
func (*BitSet) BinaryStorageSize ¶
BinaryStorageSize returns the binary storage requirements
func (*BitSet) Complement ¶
Complement computes the (local) complement of a biset (up to length bits)
func (*BitSet) Copy ¶
Copy into a destination BitSet Returning the size of the destination BitSet like array copy
func (*BitSet) Difference ¶
Difference of base set and other set This is the BitSet equivalent of &^ (and not)
func (*BitSet) DifferenceCardinality ¶
DifferenceCardinality computes the cardinality of the differnce
func (*BitSet) DumpAsBits ¶
DumpAsBits dumps a bit set as a string of bits
func (*BitSet) Equal ¶
Equal tests the equvalence of two BitSets. False if they are of different sizes, otherwise true only if all the same bits are set
func (*BitSet) InPlaceDifference ¶
InPlaceDifference computes the difference of base set and other set This is the BitSet equivalent of &^ (and not)
func (*BitSet) InPlaceIntersection ¶
InPlaceIntersection destructively computes the intersection of base set and the compare set. This is the BitSet equivalent of & (and)
func (*BitSet) InPlaceSymmetricDifference ¶
InPlaceSymmetricDifference creates the destructive SymmetricDifference of base set and other set This is the BitSet equivalent of ^ (xor)
func (*BitSet) InPlaceUnion ¶
InPlaceUnion creates the destructive union of base set and compare set. This is the BitSet equivalent of | (or).
func (*BitSet) Intersection ¶
Intersection of base set and other set This is the BitSet equivalent of & (and)
func (*BitSet) IntersectionCardinality ¶
IntersectionCardinality computes the cardinality of the union
func (*BitSet) IsStrictSuperSet ¶
IsStrictSuperSet returns true if this is a strict superset of the other set
func (*BitSet) IsSuperSet ¶
IsSuperSet returns true if this is a superset of the other set
func (*BitSet) MarshalBinary ¶
MarshalBinary encodes a BitSet into a binary form and returns the result.
func (*BitSet) MarshalJSON ¶
MarshalJSON marshals a BitSet as a JSON structure
func (*BitSet) NextSet ¶
NextSet returns the next bit set from the specified index, including possibly the current index along with an error code (true = valid, false = no set bit found) for i,e := v.NextSet(0); e; i,e = v.NextSet(i + 1) {...}
func (*BitSet) SymmetricDifference ¶
SymmetricDifference of base set and other set This is the BitSet equivalent of ^ (xor)
func (*BitSet) SymmetricDifferenceCardinality ¶
SymmetricDifferenceCardinality computes the cardinality of the symmetric difference
func (*BitSet) UnionCardinality ¶
UnionCardinality computes the cardinality of the uniton of the base set and the compare set.
func (*BitSet) UnmarshalBinary ¶
UnmarshalBinary decodes the binary form generated by MarshalBinary.
func (*BitSet) UnmarshalJSON ¶
UnmarshalJSON unmarshals a BitSet from JSON created using MarshalJSON
Source Files