package bitset

Import Path
	github.com/bits-and-blooms/bitset (on go.dev)

Dependency Relation
	imports 9 packages, and imported by one package


Involved Source Files

	
		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.

	    popcnt.go
	    popcnt_19.go
	    select.go
	    trailing_zeros_19.go


Package-Level Type Names (total 2)


	/* sort by:  |  */
	
		A BitSet is a set of bits. The zero value of a BitSet is an empty set of length 0.

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

			
				Any returns true if any bit is set, false otherwise

			
				BinaryStorageSize returns the binary storage requirements (see WriteTo) in bytes.

			
				Bytes returns the bitset as array of words

			
				Clear bit i to 0

			
				ClearAll clears the entire BitSet

			
				Clone this BitSet

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

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

			
				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.

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

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

			
				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)

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

			
				DifferenceCardinality computes the cardinality of the differnce

			
				DumpAsBits dumps a bit set as a string of bits. Following the usual convention in Go,
				the least significant bits are printed last (index 0 is at the end of the string).

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

			
				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.

			
				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.

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

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

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

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

			
				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.

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

			
				IntersectionCardinality computes the cardinality of the union

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

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

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

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

			
				MarshalJSON marshals a BitSet as a JSON structure

			
				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)

			
				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.

			
				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.

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

			
				Rank returns the nunber of set bits up to and including the index
				that are set in the bitset.
				See https://en.wikipedia.org/wiki/Ranking#Ranking_in_statistics

			
				ReadFrom reads a BitSet from a stream written using WriteTo
				The format is:
				1. uint64 length
				2. []uint64 set
				Upon success, the number of bytes read is returned.
				If the current BitSet is not large enough to hold the data,
				it is extended. In case of error, the BitSet is either
				left unchanged or made empty if the error occurs too late
				to preserve the content.
				
				Performance: if this function is used to read from a disk or network
				connection, it might be beneficial to wrap the stream in a bufio.Reader.
				E.g.,
				
					f, err := os.Open("myfile")
					r := bufio.NewReader(f)

			
				Select returns the index of the jth set bit, where j is the argument.
				The caller is responsible to ensure that 0 <= j < Count(): when j is
				out of range, the function returns the length of the bitset (b.length).
				
				Note that this function differs in convention from the Rank function which
				returns 1 when ranking the smallest value. We follow the conventional
				textbook definition of Select and Rank.

			
				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.

			
				SetAll sets the entire BitSet

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

			
				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.

			
				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.

			
				String creates a string representation of the Bitmap

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

			
				SymmetricDifferenceCardinality computes the cardinality of the symmetric difference

			
				Test whether bit i is set.

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

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

			
				UnmarshalBinary decodes the binary form generated by MarshalBinary.

			
				UnmarshalJSON unmarshals a BitSet from JSON created using MarshalJSON

			
				WriteTo writes a BitSet to a stream. The format is:
				1. uint64 length
				2. []uint64 set
				Upon success, the number of bytes written is returned.
				
				Performance: if this function is used to write to a disk or network
				connection, it might be beneficial to wrap the stream in a bufio.Writer.
				E.g.,
				
					      f, err := os.Create("myfile")
						       w := bufio.NewWriter(f)

		
			*BitSet : github.com/gobwas/ws.HandshakeHeader
			 BitSet : github.com/goccy/go-json.Marshaler
			*BitSet : github.com/goccy/go-json.Unmarshaler
			*BitSet : encoding.BinaryMarshaler
			*BitSet : encoding.BinaryUnmarshaler
			 BitSet : encoding/json.Marshaler
			*BitSet : encoding/json.Unmarshaler
			*BitSet : expvar.Var
			*BitSet : fmt.Stringer
			*BitSet : io.ReaderFrom
			*BitSet : io.WriterTo
		
			func From(buf []uint64) *BitSet
			func FromWithLength(len uint, set []uint64) *BitSet
			func New(length uint) (bset *BitSet)
			func (*BitSet).Clear(i uint) *BitSet
			func (*BitSet).ClearAll() *BitSet
			func (*BitSet).Clone() *BitSet
			func (*BitSet).Compact() *BitSet
			func (*BitSet).Complement() (result *BitSet)
			func (*BitSet).DeleteAt(i uint) *BitSet
			func (*BitSet).Difference(compare *BitSet) (result *BitSet)
			func (*BitSet).Flip(i uint) *BitSet
			func (*BitSet).FlipRange(start, end uint) *BitSet
			func (*BitSet).InsertAt(idx uint) *BitSet
			func (*BitSet).Intersection(compare *BitSet) (result *BitSet)
			func (*BitSet).Set(i uint) *BitSet
			func (*BitSet).SetAll() *BitSet
			func (*BitSet).SetTo(i uint, value bool) *BitSet
			func (*BitSet).Shrink(lastbitindex uint) *BitSet
			func (*BitSet).SymmetricDifference(compare *BitSet) (result *BitSet)
			func (*BitSet).Union(compare *BitSet) (result *BitSet)
			func github.com/RoaringBitmap/roaring.(*Bitmap).ToBitSet() *BitSet
		
			func (*BitSet).Copy(c *BitSet) (count uint)
			func (*BitSet).CopyFull(c *BitSet)
			func (*BitSet).Difference(compare *BitSet) (result *BitSet)
			func (*BitSet).DifferenceCardinality(compare *BitSet) uint
			func (*BitSet).Equal(c *BitSet) bool
			func (*BitSet).InPlaceDifference(compare *BitSet)
			func (*BitSet).InPlaceIntersection(compare *BitSet)
			func (*BitSet).InPlaceSymmetricDifference(compare *BitSet)
			func (*BitSet).InPlaceUnion(compare *BitSet)
			func (*BitSet).Intersection(compare *BitSet) (result *BitSet)
			func (*BitSet).IntersectionCardinality(compare *BitSet) uint
			func (*BitSet).IsStrictSuperSet(other *BitSet) bool
			func (*BitSet).IsSuperSet(other *BitSet) bool
			func (*BitSet).SymmetricDifference(compare *BitSet) (result *BitSet)
			func (*BitSet).SymmetricDifferenceCardinality(compare *BitSet) uint
			func (*BitSet).Union(compare *BitSet) (result *BitSet)
			func (*BitSet).UnionCardinality(compare *BitSet) uint
			func github.com/RoaringBitmap/roaring.FromBitSet(bitset *BitSet) *roaring.Bitmap


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




Package-Level Functions (total 6)


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


	
		Cap returns the total possible capacity, or number of bits


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


	
		FromWithLength constructs from an array of words and length.


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


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