bitset: xojoc.pw/bitset Index | Examples | Files

package bitset

import "xojoc.pw/bitset"

Package bitset implements a BitSet data structure.

A BitSet is a mapping between unsigned integers and boolean values. You can Set, Clear, Toggle single bits or Union, Intersect, Difference sets.

Indexes start at 0. Ranges have the first index included and the second one excluded (like go slices).

BitSets are dynamicaly-sized they grow and shrink automatically.

All methods modify their receiver in place to avoid futile memory usage. If you want to keep the original BitSet simply Clone it.

Use Clone when you want to copy a BitSet. Plese note that this will *not* work:

var x BitSet
x.Add(1)
y := x  // wrong! use Clone
y.Add(2)

If you wonder why you should use this package and not math/big see: https://typed.pw/a/29

Code:

// Create new BitSet
s := &BitSet{}
// Bitsets automatically grow
s.Set(2)
s.Set(3)
fmt.Println(s.Get(0))
fmt.Println(s.Get(2))
// Out of range Get will return false
fmt.Println(s.Get(1000))
// Println automatically calls String method
fmt.Println(s)

t := &BitSet{}
t.Set(2)
t.Set(4)
s.Intersect(t)
fmt.Println(s)

Output:

false
true
false
0011
001

Index

Examples

Package Files

bitset.go

type BitSet Uses

type BitSet struct {
    // contains filtered or unexported fields
}

BitSet data structure.

func (*BitSet) Any Uses

func (s *BitSet) Any() bool

Any returns true if any bit is set, false otherwise.

func (*BitSet) AnyRange Uses

func (s *BitSet) AnyRange(i, j int) bool

AnyRange returns true if any bit between i (included) and j (excluded) is set, false otherwise. If i < 0 and j < 0 return true.

func (*BitSet) Cardinality Uses

func (s *BitSet) Cardinality() int

Cardinality counts the number of set bits.

func (*BitSet) Clear Uses

func (s *BitSet) Clear(i int)

Clear clears the bit at index i.

func (*BitSet) ClearRange Uses

func (s *BitSet) ClearRange(i, j int)

ClearRange clears the bits between i (included) and j (excluded).

func (BitSet) Clone Uses

func (s BitSet) Clone() *BitSet

Clone makes a copy of s.

func (*BitSet) Difference Uses

func (s *BitSet) Difference(t *BitSet)

Difference stores in s the true bits present in s and not in t.

Code:

a := &BitSet{}
a.Set(0)
a.Set(1)
a.Set(2)
b := &BitSet{}
b.Set(1)
fmt.Println(a)
fmt.Println(b)
a.Difference(b)
fmt.Println(a)

Output:

111
01
101

func (*BitSet) Equal Uses

func (s *BitSet) Equal(t *BitSet) bool

Equal returns true if s and t have the same bits set, false otherwise.

func (*BitSet) Get Uses

func (s *BitSet) Get(i int) bool

Get returns true if the bit at index i is set, false otherwise. If i < 0, returns true.

func (*BitSet) GetRange Uses

func (s *BitSet) GetRange(i, j int) bool

GetRange returns true if the bits between i (included) and j (excluded) are set, false otherwise. If i < 0 and j < 0 return true.

func (*BitSet) Intersect Uses

func (s *BitSet) Intersect(t *BitSet)

Intersect stores in s the true bits common to both s and t.

Code:

a := &BitSet{}
a.Set(0)
a.Set(3)
b := &BitSet{}
b.Set(0)
b.Set(1)
fmt.Println(a)
fmt.Println(b)
a.Intersect(b)
fmt.Println(a)

Output:

1001
11
1

func (*BitSet) Len Uses

func (s *BitSet) Len() int

Len returns the number of bits up to and including the highest bit set.

func (*BitSet) Next Uses

func (s *BitSet) Next(i int) int

Next returns the index of the next bit set after i. If no bit was found returns -1.

func (*BitSet) None Uses

func (s *BitSet) None() bool

None returns true if no bit is set, false otherwise.

func (*BitSet) NoneRange Uses

func (s *BitSet) NoneRange(i, j int) bool

NoneRange returns true if no bit between i (included) and j (excluded) is set, false otherwise. If i < 0 and j < 0 return true.

func (*BitSet) Prev Uses

func (s *BitSet) Prev(i int) int

Prev returns the index of the previous bit set before i. If no bit was found returns -1.

func (*BitSet) Set Uses

func (s *BitSet) Set(i int)

Set sets the bit at index i.

func (*BitSet) SetRange Uses

func (s *BitSet) SetRange(i, j int)

SetRange sets the bits between i (included) and j (excluded).

func (*BitSet) ShiftLeft Uses

func (s *BitSet) ShiftLeft(n int)

ShiftLeft moves each bit n positions to the left.

func (*BitSet) ShiftRight Uses

func (s *BitSet) ShiftRight(n int)

ShiftRight moves each bit n positions to the right.

func (BitSet) String Uses

func (s BitSet) String() string

String returns a string representation of s.

Code:

a := &BitSet{}
a.Set(0)
a.Set(2)
fmt.Println(a) // fmt automatically calls String

Output:

101

func (*BitSet) SubSet Uses

func (s *BitSet) SubSet(t *BitSet) bool

SubSet returns true if s is a sub set of t, false otherwise.

func (*BitSet) SuperSet Uses

func (s *BitSet) SuperSet(t *BitSet) bool

SuperSet returns true if s is a super set of t, false otherwise.

func (*BitSet) SymmetricDifference Uses

func (s *BitSet) SymmetricDifference(t *BitSet)

SymmetricDifference stores in s the true bits which are either in s or in t, but not in both.

Code:

a := &BitSet{}
a.Set(0)
a.Set(1)
b := &BitSet{}
b.Set(0)
b.Set(2)
fmt.Println(a)
fmt.Println(b)
a.SymmetricDifference(b)
fmt.Println(a)

Output:

11
101
011

func (*BitSet) Toggle Uses

func (s *BitSet) Toggle(i int)

Toggle inverts the bit at index i.

func (*BitSet) ToggleRange Uses

func (s *BitSet) ToggleRange(i, j int)

ToggleRange inverts the bits between i (included) and j (excluded).

func (*BitSet) Union Uses

func (s *BitSet) Union(t *BitSet)

Union stores in a the true bits from either s or t.

Code:

a := &BitSet{}
a.Set(0)
b := &BitSet{}
b.Set(3)
fmt.Println(a)
fmt.Println(b)
a.Union(b)
fmt.Println(a)

Output:

1
0001
1001

Updated 2017-03-17. Refresh now. Tools for package owners. This is an inactive package (no imports and no commits in at least two years).