bitset

package
v0.0.0-...-8135c48 Latest Latest
Warning

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

Go to latest
Published: Jul 16, 2016 License: BSD-3-Clause, MIT Imports: 8 Imported by: 0

README

bitset

Go language library to map between non-negative integers and boolean values

Master Branch Master Build Status Develop Branch Develop Build Status

Description

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 postive 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)
}
for i,e := v.NextSet(0); e; i,e = v.NextSet(i + 1) {
   frmt.Println("The following bit is set:",i);
}
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.

Discussions golang-nuts Google Group:

Godoc documentation is at: https://godoc.org/github.com/willf/bitset

Getting started

This application is written in the go language, please refer to the guides in https://golang.org for getting started.

This project include a Makefile that allows you to test and build the project with simple commands. To see all available options:

make help

Running all tests

Before committing the code, please check if it passes all tests using

make qa

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

Constants

This section is empty.

Variables

This section is empty.

Functions

func Cap

func Cap() uint

Cap returns the total possible capicity, or number of bits

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 New

func New(length uint) *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

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) 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 Returning the size of the destination BitSet like array copy

func (*BitSet) Count

func (b *BitSet) Count() uint

Count (number of set bits)

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

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) 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 length of the BitSet in words

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

func (*BitSet) None

func (b *BitSet) None() bool

None returns true if no bit is set, false otherwise

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

func (*BitSet) SetTo

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

SetTo sets bit i to value

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