bit

README

bit: Bitsets for Go

DEPRECATED: use github.com/jba/bitset instead.

This repo includes a radix-tree implementation that uses Hash Array Mapped Tries as well as a more traditional dense implementation.

Documentation

Overview

Package bit implements operations on sets of bits.

TODO: use sync.Pool?

Index

• type Set
  • func NewSet(capacity int) *Set
  • func (s *Set) Add(i int)
  • func (s *Set) Capacity() int
  • func (s *Set) ChangeCapacity(newCapacity int)
  • func (s *Set) Clear()
  • func (s *Set) Contains(i int) bool
  • func (s1 *Set) IntersectWith(s2 *Set)
  • func (s *Set) Remove(i int)
  • func (s *Set) Size() int
• type Set256
  • func (s *Set256) Add(n uint8)
  • func (Set256) Capacity() int
  • func (s *Set256) Clear()
  • func (s *Set256) Contains(n uint8) bool
  • func (s *Set256) Elements(a []uint8, start uint8) int
  • func (s *Set256) Elements64(a []uint64, start uint8, high uint64) int
  • func (s *Set256) Empty() bool
  • func (s1 *Set256) Equal(s2 *Set256) bool
  • func (c *Set256) IntersectN(bs []*Set256)
  • func (b *Set256) Position(n uint8) (int, bool)
  • func (s *Set256) Remove(n uint8)
  • func (s *Set256) Size() int
  • func (s Set256) String() string
• type Set64
  • func (s *Set64) Add(u uint8)
  • func (Set64) Capacity() int
  • func (s *Set64) Clear()
  • func (s *Set64) Contains(u uint8) bool
  • func (s Set64) Elements(a []uint8, start uint8) int
  • func (s Set64) Elements64(a []uint64, start uint8, high uint64) int
  • func (s Set64) Empty() bool
  • func (s1 *Set64) IntersectWith(s2 Set64)
  • func (s Set64) Position(n uint8) (int, bool)
  • func (s *Set64) Remove(u uint8)
  • func (s Set64) Size() int
  • func (s Set64) String() string
  • func (s1 *Set64) UnionWith(s2 Set64)
• type SparseSet
  • func NewSparseSet(els ...uint64) *SparseSet
  • func (s *SparseSet) Add(n uint64)
  • func (s *SparseSet) Clear()
  • func (s *SparseSet) Contains(n uint64) bool
  • func (s *SparseSet) Elements(a []uint64, start uint64) int
  • func (s *SparseSet) Empty() bool
  • func (s1 *SparseSet) Equal(s2 *SparseSet) bool
  • func (s *SparseSet) Intersect(ss ...*SparseSet)
  • func (s *SparseSet) MemSize() uint64
  • func (s *SparseSet) Remove(n uint64)
  • func (s *SparseSet) Size() int
  • func (s SparseSet) String() string

Types

type Set

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

Set is a standard bitset, represented "densely"; in other words, using one bit per element. See SparseSet in this package for a more compact storage scheme for sparse bitsets.

func NewSet

func NewSet(capacity int) *Set

NewSet creates a set capable of representing values in the range [0, capacity), at least. It may allow values greater than capacity-1. Call the Capacity method to find out. NewSet panics if capacity is negative.

func (*Set) Add

func (s *Set) Add(i int)

TODO: arg should be uint

func (*Set) Capacity

func (s *Set) Capacity() int

func (*Set) ChangeCapacity

func (s *Set) ChangeCapacity(newCapacity int)

func (*Set) Clear

func (s *Set) Clear()

func (*Set) Contains

func (s *Set) Contains(i int) bool

TODO: arg should be uint

func (*Set) IntersectWith

func (s1 *Set) IntersectWith(s2 *Set)

func (*Set) Remove

func (s *Set) Remove(i int)

TODO: arg should be uint

func (*Set) Size

func (s *Set) Size() int

type Set256

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

A Set256 represents a set of integers in the range [0, 256). It does so more efficiently than a Set of capacity 256. For efficiency, the methods of Set256 perform no bounds checking on their arguments.

func (*Set256) Add

func (s *Set256) Add(n uint8)

func (Set256) Capacity

func (Set256) Capacity() int

func (*Set256) Clear

func (s *Set256) Clear()

func (*Set256) Contains

func (s *Set256) Contains(n uint8) bool

func (*Set256) Elements

func (s *Set256) Elements(a []uint8, start uint8) int

Fill a with set elements, starting from start. Return the number added.

func (*Set256) Elements64

func (s *Set256) Elements64(a []uint64, start uint8, high uint64) int

func (*Set256) Empty

func (s *Set256) Empty() bool

func (*Set256) Equal

func (s1 *Set256) Equal(s2 *Set256) bool

func (*Set256) IntersectN

func (c *Set256) IntersectN(bs []*Set256)

c cannot be one of sets

func (*Set256) Position

func (b *Set256) Position(n uint8) (int, bool)

Position returns the 0-based position of n in the set. If the set is {3, 8, 15}, then the position of 8 is 1. If n is not in the set, returns 0, false. If not a member, return where it would go. The second return value reports whether n is a member of b.

func (*Set256) Remove

func (s *Set256) Remove(n uint8)

func (*Set256) Size

func (s *Set256) Size() int

func (Set256) String

func (s Set256) String() string

type Set64

type Set64 uint64

Set64 is an efficient representation of a bitset that can represent integers in the range [0, 64). For efficiency, the methods of Set64 perform no bounds checking on their arguments.

func (*Set64) Add

func (s *Set64) Add(u uint8)

func (Set64) Capacity

func (Set64) Capacity() int

func (*Set64) Clear

func (s *Set64) Clear()

func (*Set64) Contains

func (s *Set64) Contains(u uint8) bool

func (Set64) Elements

func (s Set64) Elements(a []uint8, start uint8) int

func (Set64) Elements64

func (s Set64) Elements64(a []uint64, start uint8, high uint64) int

TODO: why exported?

func (Set64) Empty

func (s Set64) Empty() bool

func (*Set64) IntersectWith

func (s1 *Set64) IntersectWith(s2 Set64)

func (Set64) Position

func (s Set64) Position(n uint8) (int, bool)

Position returns the 0-based position of n in the set. If the set is {3, 8, 15}, then the position of 8 is 1. If n is not in the set, Position returns the position n would be at if it were a member. The second return value reports whether n is a member of s.

func (*Set64) Remove

func (s *Set64) Remove(u uint8)

func (Set64) Size

func (s Set64) Size() int

func (Set64) String

func (s Set64) String() string

func (*Set64) UnionWith

func (s1 *Set64) UnionWith(s2 Set64)

type SparseSet

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

func NewSparseSet

func NewSparseSet(els ...uint64) *SparseSet

func (*SparseSet) Add

func (s *SparseSet) Add(n uint64)

func (*SparseSet) Clear

func (s *SparseSet) Clear()

func (*SparseSet) Contains

func (s *SparseSet) Contains(n uint64) bool

func (*SparseSet) Elements

func (s *SparseSet) Elements(a []uint64, start uint64) int

func (*SparseSet) Empty

func (s *SparseSet) Empty() bool

func (*SparseSet) Equal

func (s1 *SparseSet) Equal(s2 *SparseSet) bool

func (*SparseSet) Intersect

func (s *SparseSet) Intersect(ss ...*SparseSet)

TODO: rethink s becomes the intersection of the ss. It must not be one of the ss, and it is not part of the intersection.

func (*SparseSet) MemSize

func (s *SparseSet) MemSize() uint64

func (*SparseSet) Remove

func (s *SparseSet) Remove(n uint64)

func (*SparseSet) Size

func (s *SparseSet) Size() int

func (SparseSet) String

func (s SparseSet) String() string