README
¶
go-sparseset
This library provides an implementation of sparse sets and utilities to operate on sparse sets, including, efficient traversal, joining, sorting, etc.
Values are stored contiguously in memory therefore traversing a set is particularly fast because it takes advantage of the underlying CPU caching.
// Construction
set := sparseset.New[string](4096, 1<<20)
*set.Add(id) = value
...
// Properties.
length := set.Length()
// Removal.
set.Remove(id)
// Lookup.
if value, ok := set.Get(id); ok {
// Do something with value...
} else {
// Set does not contain id...
}
// Traversal.
for iterator := sparseset.Iterate(set); ; {
key, value, ok := iterator.Next()
if !ok {
break
}
// Do something with key and value...
}
// Joining 2 sets.
for iterator := sparseset.Join(set1, set2); ; {
key, value1, value2, ok := iterator.Next()
if !ok {
break
}
// Do something with key, value1, and value2...
}
// Joining 3 sets.
for iterator := sparseset.Join3(set1, set2, set3); ; {
key, value1, value2, value3, ok := iterator.Next()
if !ok {
break
}
// Do something with key, value1, value2, and value3...
}
Documentation
¶
Index ¶
- func Lookup[A, B any](key int, setA *Set[A], setB *Set[B]) (*A, *B, bool)
- func Lookup3[A, B, C any](key int, setA *Set[A], setB *Set[B], setC *Set[C]) (*A, *B, *C, bool)
- func SortStableFunc[T any](set *Set[T], compare func(int, *T, int, *T) int)
- type Iterator
- type IteratorResult
- type Join3Iterator
- type Join4Iterator
- type JoinIterator
- type Options
- type PagedArray
- type Set
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func SortStableFunc ¶
SortStableFunc sorts the Set according to 'compare'. The 'compare' function receives the 'left-hand-side' ID and Value and the 'right-hand-side' ID and Value. The 'compare' function should call methods on the Set (e.g., Set.Get()) since SortStableFunc modifies the Set.
Types ¶
type Iterator ¶
type Iterator[A any] struct { // contains filtered or unexported fields }
Iterator can be used to traverse the keys and values of a Set. This iterator is read-only (see thread-safety notes on Set).
This is thread-compatible.
func EmptyIterator ¶
func Iterate ¶
Iterate returns an iterator that can be used to traverse all the keys and values of the set.
TODO: Avoid allocating memory for the Iterator itself.
func (*Iterator[A]) Collect ¶
func (i *Iterator[A]) Collect() []IteratorResult[A]
Collect traverses the remaining elements and stores them in an array. This is more convenient than Next() but it performs memory allocations to create and resize the array. If memory allocations are considered expensive (e.g., memory pressure, garbage collection, etc), then Next() should be preferred.
func (*Iterator[A]) Next ¶
Next returns the next value for this iterator. Returns a key, a value and a boolean. If the boolean is true, then the key and value are valid, otherwise the key and value invalid (e.g., default initialized). If the boolean is false, then the end of the iteration has been reached and subsequent calls to Next() will not return any new elements.
type IteratorResult ¶
type Join3Iterator ¶
type Join3Iterator[A, B, C any] struct { // contains filtered or unexported fields }
func EmptyJoin3Iterator ¶
func EmptyJoin3Iterator[A, B, C any]() *Join3Iterator[A, B, C]
func Join3 ¶
func Join3[A, B, C any](set1 *Set[A], set2 *Set[B], set3 *Set[C]) *Join3Iterator[A, B, C]
func (*Join3Iterator[A, B, C]) Next ¶
func (i *Join3Iterator[A, B, C]) Next() (int, *A, *B, *C, bool)
type Join4Iterator ¶
type Join4Iterator[A, B, C, D any] struct { // contains filtered or unexported fields }
func EmptyJoin4Iterator ¶
func EmptyJoin4Iterator[A, B, C, D any]() *Join4Iterator[A, B, C, D]
func (*Join4Iterator[A, B, C, D]) Next ¶
func (i *Join4Iterator[A, B, C, D]) Next() (int, *A, *B, *C, *D, bool)
type JoinIterator ¶
type JoinIterator[A, B any] struct { // contains filtered or unexported fields }
func EmptyJoinIterator ¶
func EmptyJoinIterator[A, B any]() *JoinIterator[A, B]
func (*JoinIterator[A, B]) Next ¶
func (i *JoinIterator[A, B]) Next() (int, *A, *B, bool)
type PagedArray ¶
type PagedArray[Value constraints.Ordered] struct { // contains filtered or unexported fields }
func NewPagedArray ¶
func NewPagedArray[Value constraints.Ordered](pageSize int, nullValue Value) *PagedArray[Value]
func (*PagedArray[Value]) Clear ¶
func (a *PagedArray[Value]) Clear()
func (*PagedArray[Value]) Get ¶
func (a *PagedArray[Value]) Get(index int) Value
func (*PagedArray[Value]) Length ¶
func (a *PagedArray[Value]) Length() int
func (*PagedArray[Value]) NullValue ¶
func (a *PagedArray[Value]) NullValue() Value
func (*PagedArray[Value]) Set ¶
func (a *PagedArray[Value]) Set(index int, value Value)
func (*PagedArray[Value]) Unset ¶
func (a *PagedArray[Value]) Unset(index int)
TODO: Reclaim pages at the end of the array that are empty.
type Set ¶
type Set[Value any] struct { // contains filtered or unexported fields }
Set is a sparse set with a value store.
The Set can be accessed via read-only operations and iterators concurrently, but it cannot be concurrently accessed by readers and writers, and cannot be concurrently accessed by multiple writers.
This is thread-compatible.
Example ¶
const pageSize = 1 << 10
const nullValue = 1 << 20
set := sparseset.New[string](pageSize, nullValue)
*set.Add(10) = "hello"
*set.Add(20) = "world"
// Properties.
fmt.Printf("Length %d\n", set.Length())
// Removal.
set.Remove(20)
// Lookup.
if value, ok := set.Get(10); ok {
fmt.Printf("Value %d = %s\n", 10, *value)
} else {
fmt.Println("Set does not contain id")
}
// Traversal.
for iterator := sparseset.Iterate(set); ; {
key, value, ok := iterator.Next()
if !ok {
break
}
fmt.Printf("Traverse %d = %s\n", key, *value)
}
// Joining 2 sets.
set2 := sparseset.New[int](pageSize, nullValue)
*set2.Add(10) = 1
*set2.Add(20) = 2
for iterator := sparseset.Join(set, set2); ; {
key, value1, value2, ok := iterator.Next()
if !ok {
break
}
fmt.Printf("Join %d = %s, %d\n", key, *value1, *value2)
}
Output: Length 2 Value 10 = hello Traverse 10 = hello Join 10 = hello, 1
Source Files