README
¶
go-container-dense
Package dense provides types to represent dense sets of integers.
This used to live in code.google.com/p/lvd.go/container/dense
Documentation
¶
Overview ¶
Package dense provides types to represent dense sets of integers.
Index ¶
- type Set6
- func (s Set6) Complement() (r Set6)
- func (s Set6) Contains(elem int64) bool
- func (v Set6) Count() int
- func (s Set6) Equal(t Set6) bool
- func (s Set6) Intersection(t Set6) Set6
- func (s Set6) Intersects(t Set6) bool
- func (s Set6) IsEmpty() bool
- func (s Set6) Ordinal(elem int64) (n uint64, ok bool)
- func (s Set6) String() string
- func (s Set6) Union(t Set6) Set6
- type Set63
- func (s Set63) Complement() (r Set63)
- func (s Set63) Contains(elem int64) bool
- func (s Set63) Count() (n uint64)
- func (s Set63) Cover(maxSize int, minGrain uint64) Set63
- func (s Set63) Equal(t Set63) bool
- func (s Set63) ForEach(f func(int64) bool)
- func (s Set63) ForEachInterval(f func(b, e int64) bool)
- func (s Set63) Intersection(t Set63) Set63
- func (s Set63) Intersects(t Set63) bool
- func (s Set63) IsEmpty() bool
- func (s Set63) Ordinal(elem int64) (n uint64, ok bool)
- func (s Set63) Span() (begin, end int64)
- func (s Set63) String() string
- func (s Set63) Union(t Set63) Set63
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Set6 ¶
type Set6 uint64
A Set6 is a bit vector of 2^6 bits. It mainly exists to test the Set63.
func NewSet6 ¶
Construct a new Set6 out of the elements provided. All elements should be between 0 and 63 inclusive, a violation will cause a panic.
func (Set6) Complement ¶
func (Set6) Count ¶
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel test: http://play.golang.org/p/zggoyPDdlp
func (Set6) Intersection ¶
func (Set6) Intersects ¶
type Set63 ¶
type Set63 []cell63
A Set63 represents dense sets of integers [0...2^63-1].
The representation is efficient for 'lumpy' sets, sets where the probability for a number to be in the set is positively correlated with that of it's neighbours. The Set63 will store consecutive runs of elements in 'cells' of size a power of two. For non-lumpy sets, a Set63 behaves like a sorted slice of elements.
Many operations on a Set63 take time or space depending its the storage size, which is accessible as len(s).
The price to pay for the efficient implementation is that inserting or removing a single element is rather costly. The only way to do that is to take the union with a singleton, or the intersection with a singleton's complement.
func Interval ¶
Interval returns a Set63 that covers the contiguous closed interval [min, max]. If min > max returns nil.
func NewSet63 ¶
Construct a new Set63 out of the elements provided. All elements should be non-negative, a violation will cause a panic.
func (Set63) Complement ¶
Complement returns a Set63 containing all elements of [0...1<<63) that are not in s.
func (Set63) Cover ¶
Cover returns a new Set63 that contains at least all elements of s, but does not use more than maxSize units of storage if maxSize > 0, and does not use intervals smaller than minGrain. If mingrain > 1<<62, returns the unit set [0, 1<<63)
func (Set63) ForEachInterval ¶
ForEachInterval calls the function f with each contiguous closed interval [b, e] s until f returns false.
func (Set63) Intersection ¶
Intersection returns a Set63 containing all elements of s that are also in t.
func (Set63) Intersects ¶
Intersects returns whether s and t have any element in common.
func (Set63) Ordinal ¶
Ordinal returns the number of elements in s that are smaller than elem and a boolean indicating if elem is actually in the set. TBD return int?
func (Set63) Span ¶
Span returns the smallest and the largest element inclusive of s, or 0,-1 if s is empty.
Source Files