bitset

package module
v0.8.0 Latest Latest
Warning

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

 Go to latest Published: Feb 15, 2026 License: MIT Imports: 5 Imported by: 0

README

bitset

Go Reference MIT License Build Status Code Coverage

Installation

go get github.com/ergosit/bitset

License

This package is licensed under the terms of the MIT License (see LICENSE file).

Documentation

Overview

Package bitset implements a compact bitset with arbitrary allowed ranges of non-negative integers up to 7, 15, 31, or 63, depending on the underlying type. Its non-variadic methods have constant time complexity.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func New 

func New[
	BS Bitset[BitStorage, Value],
	BitStorage types.Unsigned,
	Value types.Integer,
]() BS

New creates a new Bitset that can contain the full range of values: 

[0; <leftmost bit in BitStorage>]

E.g., for uint8 BitStorage the range is [0; 7], for uint64 — [0; 63].

func NewWithAllowedBits added in v0.6.0 

func NewWithAllowedBits[
	BS Bitset[BitStorage, Value],
	BitStorage types.Unsigned,
	Value types.Integer,
](allowedBits BitStorage) BS

NewWithAllowedBits creates a new Bitset with the given allowed bits. E.g.: 

type Bitset = bitset.Bitset[uint8, int]
set, _ := bitset.NewWithAllowedBits[Bitset](0b0_1_1_1_0_0_1_1)
//                                            - ^ ^ ^ - - ^ ^
//                                              6 5 4     1 0

will create a Bitset with the following ranges: 

[0; 1], [4; 6]

func NewWithAllowedRanges added in v0.6.0 

func NewWithAllowedRanges[
	BS Bitset[BitStorage, Value],
	BitStorage types.Unsigned,
	Value types.Integer,
](minVal, maxVal Value, minAndMaxVals ...Value) (BS, error)

NewWithAllowedRanges creates a new Bitset that can contain the given allowed range of values: 

[min; max]

and extra optional ranges that must be passed as pairs of values. E.g.: 

type Bitset = bitset.Bitset[uint64, uint8]
set, _ := bitset.NewWithAllowedRanges[Bitset](0, 2, 5, 6, 32, 60)

will create a Bitset with the following ranges: 

[0; 2], [5; 6], [32; 60]

It returns an error if the ranges overlap or is invalid. For invalid ranges see the RangeToBits returned errors.

func RangeToBits added in v0.6.0 

func RangeToBits[
	BitStorage types.Unsigned,
	Value types.Integer,
](minVal, maxVal Value) (BitStorage, error)

RangeToBits converts the given range to the bit sequence. It returns an error if:

  • minVal or maxVal is negative;
  • minVal is greater than maxVal;
  • maxVal is greater than the leftmost bit position in BitStorage.

Types

type Bitset 

type Bitset[
	BitStorage types.Unsigned,
	Value types.Integer,
] struct {
	// contains filtered or unexported fields
}

Bitset is a set implemented on a fixed-size sequence of N bits, where N is the size in bits of the given BitStorage type.

It can contain values of the given Value type that correspond to a position in the bit sequence, from the rightmost bit (0) to the leftmost bit (N-1). These values must be within the allowed ranges specified when creating Bitset via the New* functions. Therefore, a zero Bitset cannot contain a single value.

It guarantees that its size will be no more than twice the size of BitStorage.

All operations on it have constant time complexity except for variadic methods that have linear time complexity.

Note that although the first type parameter, BitStorage, is constrained by an unsigned integer type, the second one, Value, can take any integer type. This is done because some values suitable for storing in Bitset may have a signed integer type, e.g., the constants in the time package, etc. But it is still impossible to put negative values in Bitset.

func (*Bitset[BitStorage, Value]) Add 

func (set *Bitset[BitStorage, Value]) Add(value Value) error

Add sets the given value in Bitset or returns an error if the value is out of bounds.

func (*Bitset[BitStorage, Value]) AddRange 

func (set *Bitset[BitStorage, Value]) AddRange(minVal, maxVal Value) error

AddRange sets the given range of values in Bitset or returns an error if the range is out of bounds or invalid; see the RangeToBits returned error.

func (*Bitset[BitStorage, Value]) AllowedBits added in v0.6.0 

func (set *Bitset[BitStorage, Value]) AllowedBits() BitStorage

AllowedBits returns the allowed bits.

func (*Bitset[BitStorage, Value]) Backward 

func (set *Bitset[BitStorage, Value]) Backward() iter.Seq[Value]

Backward iterates over all values in Bitset from the leftmost bit to the rightmost one.

Bitset can be modified during the iteration. If a new value is (un)set then it will (not) appear if its position has not been viewed yet.

func (*Bitset[BitStorage, Value]) BackwardFrom 

func (set *Bitset[BitStorage, Value]) BackwardFrom(value Value) iter.Seq[Value]

BackwardFrom has the same semantic as Bitset.Backward but starts iteration with the bit closest to the right of the given value; it will be the given value if Bitset contains it.

func (*Bitset[BitStorage, Value]) Forward 

func (set *Bitset[BitStorage, Value]) Forward() iter.Seq[Value]

Forward iterates over all values in Bitset from the rightmost bit to the leftmost one.

Bitset can be modified during the iteration. If a new value is (un)set then it will (not) appear if its position has not been viewed yet.

func (*Bitset[BitStorage, Value]) ForwardFrom 

func (set *Bitset[BitStorage, Value]) ForwardFrom(value Value) iter.Seq[Value]

ForwardFrom has the same semantic as Bitset.Forward but starts iteration with the bit closest to the left of the given value; it will be the given value if Bitset contains it.

func (*Bitset[BitStorage, Value]) Has 

func (set *Bitset[BitStorage, Value]) Has(value Value) bool

Has returns true if Bitset contains the given value.

func (*Bitset[BitStorage, Value]) NextAfter added in v0.8.0 

func (set *Bitset[BitStorage, Value]) NextAfter(value Value) (next Value, found bool)

NextAfter returns the next set value in Bitset after the given value, and true if it found the value, or a zero value and false.

func (*Bitset[BitStorage, Value]) NextWith added in v0.8.0 

func (set *Bitset[BitStorage, Value]) NextWith(value Value) (cur Value, found bool)

NextWith returns the next set value in Bitset starting with the given value, and true if it found the value, or a zero value and false.

func (*Bitset[BitStorage, Value]) Remove 

func (set *Bitset[BitStorage, Value]) Remove(value Value) error

Remove unsets the given value in Bitset or returns an error if the value is out of bounds.

func (*Bitset[BitStorage, Value]) RemoveAll 

func (set *Bitset[BitStorage, Value]) RemoveAll()

RemoveAll removes all stored values in Bitset.

func (*Bitset[BitStorage, Value]) RemoveRange 

func (set *Bitset[BitStorage, Value]) RemoveRange(minVal, maxVal Value) error

RemoveRange unsets the given range of values in Bitset or returns an error if the range is out of bounds or invalid; see the RangeToBits returned error.

func (*Bitset[BitStorage, Value]) SetAllValues added in v0.8.0 

func (set *Bitset[BitStorage, Value]) SetAllValues()

SetAllValues sets all the allowed values in Bitset. This is the same as: 

_ = set.SetValueBits(set.AllowedBits())

func (*Bitset[BitStorage, Value]) SetAllowedRanges added in v0.6.0 

func (set *Bitset[BitStorage, Value]) SetAllowedRanges(
	minVal, maxVal Value,
	minAndMaxVals ...Value,
) error

SetAllowedRanges uses the given ranges in Bitset, removing those values that do not fit in the new ranges.

It returns an error if the ranges overlap or is invalid; see the RangeToBits returned errors.

func (*Bitset[BitStorage, Value]) SetValueBits added in v0.6.0 

func (set *Bitset[BitStorage, Value]) SetValueBits(valueBits BitStorage) error

SetValueBits sets the given bits as values in Bitset or returns an error if the values are out of bounds.

func (*Bitset[BitStorage, Value]) ValuesAsBits added in v0.6.0 

func (set *Bitset[BitStorage, Value]) ValuesAsBits() BitStorage

ValuesAsBits returns the set of values as bit sequence.

Source Files

View all Source files

Directories

Path Synopsis
internal
bits
types

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.