bitset

package
v0.4.3 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Mar 1, 2023 License: MIT Imports: 10 Imported by: 0

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 positive 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

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Base64StdEncoding

func Base64StdEncoding()

Base64StdEncoding Marshal/Unmarshal BitSet with base64.StdEncoding(Default: base64.URLEncoding)

func Cap

func Cap() uint

Cap returns the total possible capacity, or number of bits

func LittleEndian

func LittleEndian()

LittleEndian Marshal/Unmarshal Binary as Little Endian(Default: binary.BigEndian)

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 From

func From(buf []uint64) *BitSet

From is a constructor used to create a BitSet from an array of integers

func FromWithLength

func FromWithLength(len uint, set []uint64) *BitSet

FromWithLength constructs from an array of integers and length.

func New

func New(length uint) (bset *BitSet)

New creates a new BitSet with a hint that length bits will be required

func (*BitSet) All

func (b *BitSet) All() bool

All returns true if all bits are set, false otherwise. Returns true for empty sets.

func (*BitSet) Any

func (b *BitSet) Any() bool

Any returns true if any bit is set, false otherwise

func (*BitSet) BinaryStorageSize

func (b *BitSet) BinaryStorageSize() int

BinaryStorageSize returns the binary storage requirements

func (*BitSet) Bytes

func (b *BitSet) Bytes() []uint64

Bytes returns the bitset as array of integers

func (*BitSet) Clear

func (b *BitSet) Clear(i uint) *BitSet

Clear bit i to 0

func (*BitSet) ClearAll

func (b *BitSet) ClearAll() *BitSet

ClearAll clears the entire BitSet

func (*BitSet) Clone

func (b *BitSet) Clone() *BitSet

Clone this BitSet

func (*BitSet) Compact

func (b *BitSet) Compact() *BitSet

Compact shrinks BitSet to so that we preserve all set bits, while minimizing memory usage. Compact calls Shrink.

func (*BitSet) Complement

func (b *BitSet) Complement() (result *BitSet)

Complement computes the (local) complement of a biset (up to length bits)

func (*BitSet) Copy

func (b *BitSet) Copy(c *BitSet) (count uint)

Copy into a destination BitSet using the Go array copy semantics: the number of bits copied is the minimum of the number of bits in the current BitSet (Len()) and the destination Bitset. We return the number of bits copied in the destination BitSet.

func (*BitSet) CopyFull

func (b *BitSet) CopyFull(c *BitSet)

CopyFull copies into a destination BitSet such that the destination is identical to the source after the operation, allocating memory if necessary.

func (*BitSet) Count

func (b *BitSet) Count() uint

Count (number of set bits). Also known as "popcount" or "population count".

func (*BitSet) DeleteAt

func (b *BitSet) DeleteAt(i uint) *BitSet

DeleteAt deletes the bit at the given index position from within the bitset All the bits residing on the left of the deleted bit get shifted right by 1 The running time of this operation may potentially be relatively slow, O(length)

func (*BitSet) Difference

func (b *BitSet) Difference(compare *BitSet) (result *BitSet)

Difference of base set and other set This is the BitSet equivalent of &^ (and not)

func (*BitSet) DifferenceCardinality

func (b *BitSet) DifferenceCardinality(compare *BitSet) uint

DifferenceCardinality computes the cardinality of the differnce

func (*BitSet) DumpAsBits

func (b *BitSet) DumpAsBits() string

DumpAsBits dumps a bit set as a string of bits

func (*BitSet) Equal

func (b *BitSet) Equal(c *BitSet) bool

Equal tests the equivalence of two BitSets. False if they are of different sizes, otherwise true only if all the same bits are set

func (*BitSet) Flip

func (b *BitSet) Flip(i uint) *BitSet

Flip bit at i. If i>= Cap(), this function will panic. Warning: using a very large value for 'i' may lead to a memory shortage and a panic: the caller is responsible for providing sensible parameters in line with their memory capacity.

func (*BitSet) FlipRange

func (b *BitSet) FlipRange(start, end uint) *BitSet

FlipRange bit in [start, end). If end>= Cap(), this function will panic. Warning: using a very large value for 'end' may lead to a memory shortage and a panic: the caller is responsible for providing sensible parameters in line with their memory capacity.

func (*BitSet) InPlaceDifference

func (b *BitSet) InPlaceDifference(compare *BitSet)

InPlaceDifference computes the difference of base set and other set This is the BitSet equivalent of &^ (and not)

func (*BitSet) InPlaceIntersection

func (b *BitSet) InPlaceIntersection(compare *BitSet)

InPlaceIntersection destructively computes the intersection of base set and the compare set. This is the BitSet equivalent of & (and)

func (*BitSet) InPlaceSymmetricDifference

func (b *BitSet) InPlaceSymmetricDifference(compare *BitSet)

InPlaceSymmetricDifference creates the destructive SymmetricDifference of base set and other set This is the BitSet equivalent of ^ (xor)

func (*BitSet) InPlaceUnion

func (b *BitSet) InPlaceUnion(compare *BitSet)

InPlaceUnion creates the destructive union of base set and compare set. This is the BitSet equivalent of | (or).

func (*BitSet) InsertAt

func (b *BitSet) InsertAt(idx uint) *BitSet

InsertAt takes an index which indicates where a bit should be inserted. Then it shifts all the bits in the set to the left by 1, starting from the given index position, and sets the index position to 0.

Depending on the size of your BitSet, and where you are inserting the new entry, this method could be extremely slow and in some cases might cause the entire BitSet to be recopied.

func (*BitSet) Intersection

func (b *BitSet) Intersection(compare *BitSet) (result *BitSet)

Intersection of base set and other set This is the BitSet equivalent of & (and)

func (*BitSet) IntersectionCardinality

func (b *BitSet) IntersectionCardinality(compare *BitSet) uint

IntersectionCardinality computes the cardinality of the union

func (*BitSet) IsStrictSuperSet

func (b *BitSet) IsStrictSuperSet(other *BitSet) bool

IsStrictSuperSet returns true if this is a strict superset of the other set

func (*BitSet) IsSuperSet

func (b *BitSet) IsSuperSet(other *BitSet) bool

IsSuperSet returns true if this is a superset of the other set

func (*BitSet) Len

func (b *BitSet) Len() uint

Len returns the number of bits in the BitSet. Note the difference to method Count, see example.

Example
var b BitSet
b.Set(8)
fmt.Println("len", b.Len())
fmt.Println("count", b.Count())
Output:

len 9
count 1

func (*BitSet) MarshalBinary

func (b *BitSet) MarshalBinary() ([]byte, error)

MarshalBinary encodes a BitSet into a binary form and returns the result.

func (*BitSet) MarshalJSON

func (b *BitSet) MarshalJSON() ([]byte, error)

MarshalJSON marshals a BitSet as a JSON structure

func (*BitSet) NextClear

func (b *BitSet) NextClear(i uint) (uint, bool)

NextClear returns the next clear bit from the specified index, including possibly the current index along with an error code (true = valid, false = no bit found i.e. all bits are set)

func (*BitSet) NextSet

func (b *BitSet) NextSet(i uint) (uint, bool)

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) {...}

Users concerned with performance may want to use NextSetMany to retrieve several values at once.

func (*BitSet) NextSetMany

func (b *BitSet) NextSetMany(i uint, buffer []uint) (uint, []uint)

NextSetMany returns many next bit sets from the specified index, including possibly the current index and up to cap(buffer). If the returned slice has len zero, then no more set bits were found

buffer := make([]uint, 256) // this should be reused
j := uint(0)
j, buffer = bitmap.NextSetMany(j, buffer)
for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j,buffer) {
 for k := range buffer {
  do something with buffer[k]
 }
 j += 1
}

It is possible to retrieve all set bits as follow:

indices := make([]uint, bitmap.Count())
bitmap.NextSetMany(0, indices)

However if bitmap.Count() is large, it might be preferable to use several calls to NextSetMany, for performance reasons.

func (*BitSet) None

func (b *BitSet) None() bool

None returns true if no bit is set, false otherwise. Returns true for empty sets.

func (*BitSet) ReadFrom

func (b *BitSet) ReadFrom(stream io.Reader) (int64, error)

ReadFrom reads a BitSet from a stream written using WriteTo

func (*BitSet) Set

func (b *BitSet) Set(i uint) *BitSet

Set bit i to 1, the capacity of the bitset is automatically increased accordingly. If i>= Cap(), this function will panic. Warning: using a very large value for 'i' may lead to a memory shortage and a panic: the caller is responsible for providing sensible parameters in line with their memory capacity.

func (*BitSet) SetBitsetFrom

func (b *BitSet) SetBitsetFrom(buf []uint64)

SetBitsetFrom fills the bitset with an array of integers without creating a new BitSet instance

func (*BitSet) SetTo

func (b *BitSet) SetTo(i uint, value bool) *BitSet

SetTo sets bit i to value. If i>= Cap(), this function will panic. Warning: using a very large value for 'i' may lead to a memory shortage and a panic: the caller is responsible for providing sensible parameters in line with their memory capacity.

func (*BitSet) Shrink

func (b *BitSet) Shrink(lastbitindex uint) *BitSet

Shrink shrinks BitSet so that the provided value is the last possible set value. It clears all bits > the provided index and reduces the size and length of the set.

Note that the parameter value is not the new length in bits: it is the maximal value that can be stored in the bitset after the function call. The new length in bits is the parameter value + 1. Thus it is not possible to use this function to set the length to 0, the minimal value of the length after this function call is 1.

A new slice is allocated to store the new bits, so you may see an increase in memory usage until the GC runs. Normally this should not be a problem, but if you have an extremely large BitSet its important to understand that the old BitSet will remain in memory until the GC frees it.

func (*BitSet) String

func (b *BitSet) String() string

String creates a string representation of the Bitmap

func (*BitSet) SymmetricDifference

func (b *BitSet) SymmetricDifference(compare *BitSet) (result *BitSet)

SymmetricDifference of base set and other set This is the BitSet equivalent of ^ (xor)

func (*BitSet) SymmetricDifferenceCardinality

func (b *BitSet) SymmetricDifferenceCardinality(compare *BitSet) uint

SymmetricDifferenceCardinality computes the cardinality of the symmetric difference

func (*BitSet) Test

func (b *BitSet) Test(i uint) bool

Test whether bit i is set.

func (*BitSet) Union

func (b *BitSet) Union(compare *BitSet) (result *BitSet)

Union of base set and other set This is the BitSet equivalent of | (or)

func (*BitSet) UnionCardinality

func (b *BitSet) UnionCardinality(compare *BitSet) uint

UnionCardinality computes the cardinality of the uniton of the base set and the compare set.

func (*BitSet) UnmarshalBinary

func (b *BitSet) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes the binary form generated by MarshalBinary.

func (*BitSet) UnmarshalJSON

func (b *BitSet) UnmarshalJSON(data []byte) error

UnmarshalJSON unmarshals a BitSet from JSON created using MarshalJSON

func (*BitSet) WriteTo

func (b *BitSet) WriteTo(stream io.Writer) (int64, error)

WriteTo writes a BitSet to a stream

type Error

type Error string

Error is used to distinguish errors (panics) generated in this package.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL