sparsebitvector

package module
v0.0.0-...-4c0b810 Latest Latest
Warning

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

 Go to latest Published: Sep 9, 2015 License: NCSA Imports: 1 Imported by: 0

README

sparsebitvector

TravisCI GoDoc

This library provides a SparseBitVector implementation in go based on the similarly named class provided by LLVM.

See:

Usage

go get github.com/neilisaac/sparsebitvector

import "github.com/neilisaac/sparsebitvector"

vec := sparsebitvector.New(1, 2, 1000000)

vec.Set(1000001)
vec.Unset(1)

vec.IntersectWith(sparsebitvector.New(1, 1000001))

for value := range vec.Iterate() {
    fmt.Println("vec contains", value)
}
Supported operations
  • Set set a bit to true
  • Unset set a bit to false (called reset in LLVM)
  • Test check whether a bit is true
  • TestAndSet set a bit to true and return true if it was changed
  • Clear set all bits to false
  • Iterate returns a channel that publishes all true bits
  • Equals compare to another SparseBitVector
  • Contains returns true if another SparseBitVector's bits are all true
  • UnionAndIntersectionSize return the size of the union and intersection with another SparseBitVector
  • UnionSize
  • IntersectionSize
  • UnionWith union itself with another SparseBitVector
  • IntersectWith intersect itself with another SparseBitVector
  • IntersectWithComplement intersect itself with the bitwise inverse of another SparseBitVector
TODO
  • Union returning a new bit vector
  • Intersection returning a new bit vector
  • Intersects returning true if any bit is present in the intersection

Documentation

Index

Constants

View Source 
const ElementSize = bitsperword * wordsperelement

ElementSize is the number of bits per FiniteBitVector

Variables

This section is empty.

Functions

This section is empty.

Types

type FiniteBitVector 

type FiniteBitVector [wordsperelement]elementwordtype

FiniteBitVector provides a bit vector of length elementsize.

func NewFiniteBitVector 

func NewFiniteBitVector(set ...uint) *FiniteBitVector

NewFiniteBitVector initializes a FiniteBitVector from the given elements.

func (*FiniteBitVector) Clear 

func (vec *FiniteBitVector) Clear()

Clear sets all bits in the Element to false.

func (*FiniteBitVector) Contains 

func (vec *FiniteBitVector) Contains(vec2 *FiniteBitVector) bool

Contains returns true iff vec contains all of vec2's true bits.

func (*FiniteBitVector) Count 

func (vec *FiniteBitVector) Count() (count int)

Count returns the number of true bits within the ELement.

func (*FiniteBitVector) Equals 

func (vec *FiniteBitVector) Equals(vec2 *FiniteBitVector) bool

Equals returns true iff vec and vec2 contain equivalent true bits.

func (*FiniteBitVector) FindNext 

func (vec *FiniteBitVector) FindNext(index int) int

FindNext retruns the next true bit starting from index, or -1 if none exist. The initial call should pass index 0. Successive calls should pass previous+1.

func (*FiniteBitVector) IntersectWith 

func (vec *FiniteBitVector) IntersectWith(vec2 *FiniteBitVector)

IntersectWith sets vec to the intersection of itself and vec2.

func (*FiniteBitVector) IntersectWithComplement 

func (vec *FiniteBitVector) IntersectWithComplement(vec2 *FiniteBitVector)

IntersectWithComplement sets vec to the intersection of itself and ~vec2.

func (*FiniteBitVector) IntersectionSize 

func (vec *FiniteBitVector) IntersectionSize(vec2 *FiniteBitVector) int

IntersectionSize returns the number of true bits of the intersection with vec2.

func (*FiniteBitVector) Set 

func (vec *FiniteBitVector) Set(key uint)

Set sets a bit to true.

func (*FiniteBitVector) String 

func (vec *FiniteBitVector) String() string

func (*FiniteBitVector) Test 

func (vec *FiniteBitVector) Test(key uint) bool

Test returns true iff the given bit is true.

func (*FiniteBitVector) TestAndSet 

func (vec *FiniteBitVector) TestAndSet(key uint) bool

TestAndSet sets a bit to true and returns true iff it was changed.

func (*FiniteBitVector) TestAndUnset 

func (vec *FiniteBitVector) TestAndUnset(key uint) bool

TestAndUnset sets a bit to false and returns true iff it was changed.

func (*FiniteBitVector) UnionAndIntersectionSize 

func (vec *FiniteBitVector) UnionAndIntersectionSize(vec2 *FiniteBitVector) (int, int)

UnionAndIntersectionSize returns the number of true bits of the union and intersection with vec2.

func (*FiniteBitVector) UnionWith 

func (vec *FiniteBitVector) UnionWith(vec2 *FiniteBitVector)

UnionWith sets vec to the union of itself and vec2.

func (*FiniteBitVector) Unset 

func (vec *FiniteBitVector) Unset(key uint)

Unset sets a bit to false.

type KeyType 

type KeyType uint64

KeyType defines SparseBitVector's keyspace.

type SparseBitVector 

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

SparseBitVector implementation based on that from LLVM: https://github.com/llvm-mirror/llvm/blob/master/include/llvm/ADT/SparseBitVector.h

func New 

func New(set ...KeyType) *SparseBitVector

New creates and instance of a SparseBitVector, optionally initialized by set.

func (*SparseBitVector) Clear 

func (sbv *SparseBitVector) Clear()

Clear sets all bits to false.

func (*SparseBitVector) Contains 

func (sbv *SparseBitVector) Contains(sbv2 *SparseBitVector) bool

Contains returns true iff sbv contains all of sbv2's true bits.

func (*SparseBitVector) Count 

func (sbv *SparseBitVector) Count() int

Count returns the number of distinct bits that are true.

func (*SparseBitVector) Equals 

func (sbv *SparseBitVector) Equals(sbv2 *SparseBitVector) bool

Equals returns true iff sbv and sbv2 contain equivalent true bits.

func (*SparseBitVector) IntersectWith 

func (sbv *SparseBitVector) IntersectWith(sbv2 *SparseBitVector)

IntersectWith sets sbv to the intersection of itself and sbv2.

func (*SparseBitVector) IntersectWithComplement 

func (sbv *SparseBitVector) IntersectWithComplement(sbv2 *SparseBitVector)

IntersectWithComplement sets sbv to the intersection of itself and the inverse of sbv2.

func (*SparseBitVector) IntersectionSize 

func (sbv *SparseBitVector) IntersectionSize(sbv2 *SparseBitVector) int

IntersectionSize returns the number of true bits of the intersection with sbv2.

func (*SparseBitVector) Iterate 

func (sbv *SparseBitVector) Iterate() <-chan KeyType

Iterate returns a channel which publishes all true bits in ascending order. The behaviour is undefined for bits modified while iterating.

func (*SparseBitVector) Set 

func (sbv *SparseBitVector) Set(key KeyType)

Set sets a particular bit to true in a SparseBitVector.

func (*SparseBitVector) String 

func (sbv *SparseBitVector) String() string

func (*SparseBitVector) Test 

func (sbv *SparseBitVector) Test(key KeyType) bool

Test checks whether a particular bit is true.

func (*SparseBitVector) TestAndSet 

func (sbv *SparseBitVector) TestAndSet(key KeyType) bool

TestAndSet checks whether a bit was previously true before setting it to true.

func (*SparseBitVector) UnionAndIntersectionSize 

func (sbv *SparseBitVector) UnionAndIntersectionSize(sbv2 *SparseBitVector) (int, int)

UnionAndIntersectionSize returns the number of true bits of the union and intersection with sbv2.

func (*SparseBitVector) UnionSize 

func (sbv *SparseBitVector) UnionSize(sbv2 *SparseBitVector) int

UnionSize returns the number of true bits of the union with sbv2.

func (*SparseBitVector) UnionWith 

func (sbv *SparseBitVector) UnionWith(sbv2 *SparseBitVector)

UnionWith returns the number of true bits of the union and intersection with sbv2.

func (*SparseBitVector) Unset 

func (sbv *SparseBitVector) Unset(key KeyType)

Unset sets a particular bit to false.

Source Files

View all Source files

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.