Version: v0.0.0-...-45a4409 Latest Latest This package is not in the latest version of its module.

Go to latest
Published: Mar 13, 2018 License: BSD-2-Clause

## README ¶

### Your basic bit ##### Set data structure for positive numbers

A bit array, or bit set, is an efficient set data structure. It consists of an array that compactly stores bits and it uses bit-level parallelism to perform operations quickly. ##### Installation

Once you have installed Go, run this command to install the `bit` package:

``````go get github.com/yourbasic/bit
``````
##### Documentation

There is an online reference for the package at godoc.org/github.com/yourbasic/bit.

The only accepted reason to modify the API of this package is to handle issues that can't be resolved in any other reasonable way.

Stefan Nilsson – korthaj

## Documentation ¶

### Overview ¶

Package bit provides a bit array implementation.

#### Bit set ¶

A bit set, or bit array, is an efficient set data structure that consists of an array of 64-bit words. Because it uses bit-level parallelism, limits memory access, and efficiently uses the data cache, a bit set often outperforms other data structures.

#### Tutorial ¶

The Basics example shows how to create, combine, compare and print bit sets.

Primes contains a short and simple, but still efficient, implementation of a prime number sieve.

Union is a more advanced example demonstrating how to build an efficient variadic Union function using the SetOr method.

Example (Basics)

Create, combine, compare and print bit sets.

```package main

import (
"fmt"
"github.com/yourbasic/bit"
)

func main() {
// Add all elements in the range [0, 100) to the empty set.
A := new(bit.Set).AddRange(0, 100) // {0..99}

// Create a new set containing the two elements 0 and 200,
// and then add all elements in the range [50, 150) to the set.
B := bit.New(0, 200).AddRange(50, 150) // {0 50..149 200}

// Compute the symmetric difference A △ B.
X := A.Xor(B)

// Compute A △ B as (A ∖ B) ∪ (B ∖ A).
Y := A.AndNot(B).Or(B.AndNot(A))

// Compare the results.
if X.Equal(Y) {
fmt.Println(X)
}
}
```
```Output:

{1..49 100..149 200}
```
Example (Primes)

Create the set of all primes less than n in O(n log log n) time. Try the code with n equal to a few hundred millions and be pleasantly surprised.

```package main

import (
"fmt"
"github.com/yourbasic/bit"
"math"
)

func main() {
// Sieve of Eratosthenes
const n = 50
sieve := bit.New().AddRange(2, n)
sqrtN := int(math.Sqrt(n))
for p := 2; p <= sqrtN; p = sieve.Next(p) {
for k := p * p; k < n; k += p {
sieve.Delete(k)
}
}
fmt.Println(sieve)
}
```
```Output:

{2 3 5 7 11 13 17 19 23 29 31 37 41 43 47}
```
Example (Union)

Implement an efficient variadic Union function using SetOr.

```package main

import (
"fmt"
"github.com/yourbasic/bit"
)

// Union returns the union of the given sets.
func Union(s ...*bit.Set) *bit.Set {
// Optimization: allocate initital set with adequate capacity.
max := -1
for _, x := range s {
if x.Size() > 0 && x.Max() > max { // Max is not defined for the empty set.
max = x.Max()
}
}
res := bit.New(max) // A negative number will not be included in the set.

for _, x := range s {
res.SetOr(res, x) // Reuses memory.
}
return res
}

// Implement an efficient variadic Union function using SetOr.
func main() {
a, b, c := bit.New(1, 2), bit.New(2, 3), bit.New(5)
fmt.Println(Union(a, b, c))
}
```
```Output:

{1..3 5}
```

### Constants ¶

View Source
```const (
MaxInt  = 1<<(BitsPerWord-1) - 1 // either 1<<31 - 1 or 1<<63 - 1
MinInt  = -MaxInt - 1            // either -1 << 31 or -1 << 63
MaxUint = 1<<BitsPerWord - 1     // either 1<<32 - 1 or 1<<64 - 1
)```

Implementation-specific integer limit values.

View Source
```const BitsPerWord = bitsPerWord // either 32 or 64
```

BitsPerWord is the implementation-specific size of int and uint in bits.

### Variables ¶

This section is empty.

### Functions ¶

#### func Count deprecated

`func Count(w uint64) int`

Count returns the number of nonzero bits in w.

Deprecated: In Go 1.9 this function is available in package math/bits as OnesCount64.

#### func LeadingZeros deprecated

`func LeadingZeros(w uint64) int`

LeadingZeros returns the number of leading zero bits in w; it returns 64 when w is zero.

Deprecated: In Go 1.9 this function is available in package math/bits as LeadingZeros64.

#### func TrailingZeros deprecated

`func TrailingZeros(w uint64) int`

TrailingZeros returns the number of trailing zero bits in w; it returns 64 when w is zero.

Deprecated: In Go 1.9 this function is available in package math/bits as TrailingZeros64.

### Types ¶

#### type Set ¶

```type Set struct {
// contains filtered or unexported fields
}```

Set represents a mutable set of non-negative integers. The zero value is an empty set ready to use. A set occupies approximately n bits, where n is the maximum value that has been stored in the set.

#### func New ¶

`func New(n ...int) *Set`

New creates a new set with the given elements. Negative numbers are not included in the set.

Example
```package main

import (
"fmt"
"github.com/yourbasic/bit"
)

func main() {
fmt.Println(bit.New(0, 1, 10, 10, -1))
}
```
```Output:

{0 1 10}
```

#### func (*Set) Add ¶

`func (s *Set) Add(n int) *Set`

Add adds n to s and returns a pointer to the updated set. A negative n will not be added.

#### func (*Set) AddRange ¶

`func (s *Set) AddRange(m, n int) *Set`

AddRange adds all integers from m to n-1 to s and returns a pointer to the updated set. Negative numbers will not be added.

#### func (*Set) And ¶

`func (s1 *Set) And(s2 *Set) *Set`

And creates a new set that consists of all elements that belong to both s1 and s2.

#### func (*Set) AndNot ¶

`func (s1 *Set) AndNot(s2 *Set) *Set`

AndNot creates a new set that consists of all elements that belong to s1, but not to s2.

#### func (*Set) Contains ¶

`func (s *Set) Contains(n int) bool`

Contains tells if n is an element of the set.

#### func (*Set) Delete ¶

`func (s *Set) Delete(n int) *Set`

Delete removes n from s and returns a pointer to the updated set.

#### func (*Set) DeleteRange ¶

`func (s *Set) DeleteRange(m, n int) *Set`

DeleteRange removes all integers from m to n-1 from s and returns a pointer to the updated set.

#### func (*Set) Empty ¶

`func (s *Set) Empty() bool`

Empty tells if the set is empty.

#### func (*Set) Equal ¶

`func (s1 *Set) Equal(s2 *Set) bool`

Equal tells if s1 and s2 contain the same elements.

#### func (*Set) Max ¶

`func (s *Set) Max() int`

Max returns the maximum element of the set; it panics if the set is empty.

#### func (*Set) Next ¶

`func (s *Set) Next(m int) int`

Next returns the next element n, n > m, in the set, or -1 if there is no such element.

#### func (*Set) Or ¶

`func (s1 *Set) Or(s2 *Set) *Set`

Or creates a new set that contains all elements that belong to either s1 or s2.

#### func (*Set) Prev ¶

`func (s *Set) Prev(m int) int`

Prev returns the previous element n, n < m, in the set, or -1 if there is no such element.

#### func (*Set) Set ¶

`func (s *Set) Set(s1 *Set) *Set`

Set sets s to s1 and then returns a pointer to the updated set s.

#### func (*Set) SetAnd ¶

`func (s *Set) SetAnd(s1, s2 *Set) *Set`

SetAnd sets s to the intersection s1 ∩ s2 and then returns a pointer to s.

#### func (*Set) SetAndNot ¶

`func (s *Set) SetAndNot(s1, s2 *Set) *Set`

SetAndNot sets s to the set difference s1 ∖ s2 and then returns a pointer to s.

#### func (*Set) SetOr ¶

`func (s *Set) SetOr(s1, s2 *Set) *Set`

SetOr sets s to the union s1 ∪ s2 and then returns a pointer to s.

#### func (*Set) SetXor ¶

`func (s *Set) SetXor(s1, s2 *Set) *Set`

SetXor sets s to the symmetric difference A ∆ B = (A ∪ B) ∖ (A ∩ B) and then returns a pointer to s.

#### func (*Set) Size ¶

`func (s *Set) Size() int`

Size returns the number of elements in the set. This method scans the set; to check if a set is empty, consider using the more efficient Empty method.

#### func (*Set) String ¶

`func (s *Set) String() string`

String returns a string representation of the set. The elements are listed in ascending order. Runs of at least three consecutive elements from a to b are given as a..b.

Example
```package main

import (
"fmt"
"github.com/yourbasic/bit"
)

func main() {
fmt.Println(bit.New(1, 2, 6, 5, 3))
}
```
```Output:

{1..3 5 6}
```

#### func (*Set) Subset ¶

`func (s1 *Set) Subset(s2 *Set) bool`

Subset tells if s1 is a subset of s2.

#### func (*Set) Visit ¶

`func (s *Set) Visit(do func(n int) (skip bool)) (aborted bool)`

Visit calls the do function for each element of s in numerical order. If do returns true, Visit returns immediately, skipping any remaining elements, and returns true. It is safe for do to add or delete elements e, e ≤ n. The behavior of Visit is undefined if do changes the set in any other way.

Example

Compute the sum of all elements in a set.

```package main

import (
"fmt"
"github.com/yourbasic/bit"
)

func main() {
s := bit.New(1, 2, 3, 4)
sum := 0
s.Visit(func(n int) (skip bool) {
sum += n
return
})
fmt.Println("sum", s, "=", sum)
}
```
```Output:

sum {1..4} = 10
```
Example (Abort)

Abort an iteration in mid-flight.

```package main

import (
"fmt"
"github.com/yourbasic/bit"
)

func main() {
s := bit.New(2, 3, 5, 7, 11, 13)

// Print all single digit numbers in s.
s.Visit(func(n int) (skip bool) {
if n >= 10 {
skip = true
return
}
fmt.Print(n, " ")
return
})
}
```
```Output:

2 3 5 7
```

#### func (*Set) Xor ¶

`func (s1 *Set) Xor(s2 *Set) *Set`

Xor creates a new set that contains all elements that belong to either s1 or s2, but not to both.