Documentation
¶
Overview ¶
Package sparse provides a compact and efficient sparse array implementation for addressable key ranges from [0..255].
It is optimized for use in radix tries and lookup structures where only a small subset of possible keys contain actual data.
Internally, an Array256 combines a fixed-size BitSet256 with a compact packed Items slice. The bitset tracks which key slots are occupied and enables fast index mapping via popcount (Rank), while the Items slice stores the associated payloads.
Lookup, insertion, and deletion operate in O(1) time (worst-case O(n) only for shifting/copying in extremely full arrays).
This module avoids memory allocations where possible and provides predictable performance even under heavy insert/delete workloads.
Index ¶
- type Array256
- func (a *Array256[T]) Clear(uint)
- func (a *Array256[T]) Copy() *Array256[T]
- func (a *Array256[T]) DeleteAt(i uint8) (value T, exists bool)
- func (a *Array256[T]) Get(i uint8) (value T, ok bool)
- func (a *Array256[T]) InsertAt(i uint8, value T) (exists bool)
- func (a *Array256[T]) Len() int
- func (a *Array256[T]) MustGet(i uint8) T
- func (a *Array256[T]) Set(uint)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Array256 ¶ added in v0.19.0
Array256 is a popcount-compressed sparse array for up to 256 item slots.
Internally, it consists of:
- a BitSet256, where each set bit marks a present slot (i.e., key i used)
- a compact Items slice, which stores the payloads only for the set bits
Each occupied index i ∈ [0..255] can be tested using .Test(i). The actual index within the Items slice is computed via .Rank(i)-1.
All insert/delete operations update both the bitset and item slice to preserve this mapping invariant. Direct mutation of the underlying bitset (via Set or Clear) is forbidden and will panic.
This structure allows extremely fast and compact prefix-based routing, highly efficient child-node containers in prefix tries, or memory-safe alternatives to map[uint8]T with deterministic iteration.
Example layout:
BitSet256: [0 1 0 0 0 1 ...] // bits 1 and 5 set Items: [T1, T2] // a.Items[0] ↔ key 1, a.Items[1] ↔ key 5
func (*Array256[T]) Clear ¶ added in v0.20.3
Clear panics. The bitset is internally coupled with Items[].
func (*Array256[T]) Copy ¶ added in v0.19.0
Copy returns a shallow copy of the Array. The elements are copied using assignment, this is no deep clone.
func (*Array256[T]) DeleteAt ¶ added in v0.19.0
DeleteAt removes the value at index i from the sparse array, shifting remaining items down in the slice and clearing the bit.
If the entry exists, it is returned together with true. If i is not present, the zero value and false are returned.
func (*Array256[T]) Get ¶ added in v0.19.0
Get returns the value at index i and whether it exists.
If the bit for i is not set, ok is false and value is the zero-value of T.
example: a.Get(5) -> a.Items[1]
⬇
BitSet256: [0|0|1|0|0|1|0|...|1] <- 3 bits set
Items: [*|*|*] <- len(Items) = 3
⬆
BitSet256.Test(5): true
BitSet256.Rank(5): 2,
func (*Array256[T]) InsertAt ¶ added in v0.19.0
InsertAt adds the value to the index i. If a value already exists there, it is overwritten and true is returned.
Otherwise, the value is inserted, the bit is marked, and false returned.
Source Files