Documentation
¶
Overview ¶
Package artmap provides a typed façade over the []byte-keyed art.Tree: an Ordered sorted map keyed by any Go cmp.Ordered type, using byte-order-preserving encoders so the underlying ART preserves the natural ordering of K.
Index ¶
- type Ordered
- func (o *Ordered[K, V]) All() iter.Seq2[K, V]
- func (o *Ordered[K, V]) AllDescending() iter.Seq2[K, V]
- func (o *Ordered[K, V]) Ceiling(target K) (key K, value V, ok bool)
- func (o *Ordered[K, V]) Clone() *Ordered[K, V]
- func (o *Ordered[K, V]) Delete(key K) bool
- func (o *Ordered[K, V]) Floor(target K) (key K, value V, ok bool)
- func (o *Ordered[K, V]) Get(key K) (V, bool)
- func (o *Ordered[K, V]) Len() int
- func (o *Ordered[K, V]) Max() (key K, value V, ok bool)
- func (o *Ordered[K, V]) Min() (key K, value V, ok bool)
- func (o *Ordered[K, V]) Put(key K, value V)
- func (o *Ordered[K, V]) Range(start, end K) iter.Seq2[K, V]
- func (o *Ordered[K, V]) RangeDescending(start, end K) iter.Seq2[K, V]
- func (o *Ordered[K, V]) RangeFrom(start K) iter.Seq2[K, V]
- func (o *Ordered[K, V]) RangeTo(end K) iter.Seq2[K, V]
- type OrderedKey
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Ordered ¶
type Ordered[K OrderedKey, V any] struct { // contains filtered or unexported fields }
Ordered is a sorted map from K to V, backed by an art.Tree. Keys are encoded via a byte-order-preserving encoder selected at New time (see OrderedKey) so range operations return entries in the natural ascending order of K.
An Ordered is not safe for concurrent use by multiple goroutines when any goroutine is writing, with the same contract as the underlying art.Tree. Callers that need concurrent access should guard an Ordered with their own sync.RWMutex or wrap art.Tree directly with art.LockedTree. See the Concurrency section of the project README for the full discussion.
Example (Float32) ¶
package main
import (
"fmt"
"github.com/KentBeck/AdaptiveRadixTree2/artmap"
)
func main() {
m := artmap.New[float32, int]()
m.Put(-0.5, 0)
m.Put(0.0, 1)
m.Put(2.5, 2)
for k := range m.All() {
fmt.Println(k)
}
}
Output: -0.5 0 2.5
Example (Float64) ¶
package main
import (
"fmt"
"github.com/KentBeck/AdaptiveRadixTree2/artmap"
)
func main() {
m := artmap.New[float64, int]()
m.Put(-1.5, 0)
m.Put(0.0, 1)
m.Put(3.14, 2)
v, _ := m.Get(3.14)
fmt.Println(v)
for k := range m.All() {
fmt.Println(k)
}
for k := range m.Range(-1.0, 3.14) {
fmt.Println("range:", k)
}
}
Output: 2 -1.5 0 3.14 range: 0
Example (Int32) ¶
package main
import (
"fmt"
"github.com/KentBeck/AdaptiveRadixTree2/artmap"
)
func main() {
m := artmap.New[int32, int]()
m.Put(-1, 0)
m.Put(0, 1)
m.Put(1, 2)
for k := range m.All() {
fmt.Println(k)
}
}
Output: -1 0 1
Example (Int64) ¶
package main
import (
"fmt"
"github.com/KentBeck/AdaptiveRadixTree2/artmap"
)
func main() {
m := artmap.New[int64, string]()
m.Put(-100, "neg")
m.Put(0, "zero")
m.Put(50, "fifty")
v, _ := m.Get(-100)
fmt.Println(v)
for k, v := range m.All() {
fmt.Println(k, v)
}
for k := range m.Range(-50, 100) {
fmt.Println("range:", k)
}
}
Output: neg -100 neg 0 zero 50 fifty range: 0 range: 50
Example (Int8) ¶
package main
import (
"fmt"
"github.com/KentBeck/AdaptiveRadixTree2/artmap"
)
func main() {
m := artmap.New[int8, int]()
m.Put(-128, 0)
m.Put(0, 1)
m.Put(127, 2)
for k := range m.All() {
fmt.Println(k)
}
}
Output: -128 0 127
Example (String) ¶
package main
import (
"fmt"
"github.com/KentBeck/AdaptiveRadixTree2/artmap"
)
func main() {
m := artmap.New[string, int]()
m.Put("banana", 2)
m.Put("apple", 1)
m.Put("cherry", 3)
v, _ := m.Get("apple")
fmt.Println(v)
for k, v := range m.All() {
fmt.Println(k, v)
}
for k := range m.Range("b", "d") {
fmt.Println("range:", k)
}
}
Output: 1 apple 1 banana 2 cherry 3 range: banana range: cherry
Example (Uint32) ¶
package main
import (
"fmt"
"github.com/KentBeck/AdaptiveRadixTree2/artmap"
)
func main() {
m := artmap.New[uint32, int]()
m.Put(100, 1)
m.Put(0, 0)
m.Put(4294967295, 2)
v, _ := m.Get(100)
fmt.Println(v)
for k := range m.All() {
fmt.Println(k)
}
for k := range m.Range(50, 200) {
fmt.Println("range:", k)
}
}
Output: 1 0 100 4294967295 range: 100
Example (Uint8) ¶
package main
import (
"fmt"
"github.com/KentBeck/AdaptiveRadixTree2/artmap"
)
func main() {
m := artmap.New[uint8, string]()
m.Put(255, "hi")
m.Put(0, "lo")
for k, v := range m.All() {
fmt.Println(k, v)
}
}
Output: 0 lo 255 hi
func New ¶
func New[K OrderedKey, V any]() *Ordered[K, V]
New returns an empty Ordered keyed by K. It panics if K's kind is not one of the cmp.Ordered kinds, which cannot happen for a well-typed caller.
func (*Ordered[K, V]) All ¶
All returns an iterator over every (key, value) pair in ascending key order. See art.Tree.All for the underlying contract.
func (*Ordered[K, V]) AllDescending ¶
AllDescending returns an iterator over every (key, value) pair in descending key order.
func (*Ordered[K, V]) Ceiling ¶
Ceiling returns the smallest key >= target and its value. ok is false if no such key exists.
func (*Ordered[K, V]) Clone ¶
Clone returns an independent structural copy. Writes to o or to the returned map do not affect each other.
func (*Ordered[K, V]) Floor ¶
Floor returns the largest key <= target and its value. ok is false if no such key exists.
func (*Ordered[K, V]) Max ¶
Max returns the largest key, its value, and ok=true. ok is false if the map is empty.
func (*Ordered[K, V]) Min ¶
Min returns the smallest key, its value, and ok=true. ok is false if the map is empty, in which case key and value are their zero values.
func (*Ordered[K, V]) Put ¶
func (o *Ordered[K, V]) Put(key K, value V)
Put associates value with key, replacing any previous value.
func (*Ordered[K, V]) Range ¶
Range returns an iterator over every (key, value) pair whose key lies in the half-open interval [start, end), in ascending key order. start >= end yields nothing. The encoded start and end are captured eagerly so the returned iterator is safe to range over multiple times.
func (*Ordered[K, V]) RangeDescending ¶
RangeDescending returns an iterator over entries whose key lies in [start, end), in descending key order. start >= end yields nothing.
type OrderedKey ¶
OrderedKey is the key constraint for Ordered. It is an alias for Go's cmp.Ordered: the set of types whose underlying type is a signed or unsigned integer, a floating-point type, or a string.
Every OrderedKey value is encoded as a []byte before being stored in the underlying art.Tree. The encoder is chosen at New time from the key's reflect.Kind and is byte-order-preserving: for any two values a, b of type K, cmp.Compare(a, b) and bytes.Compare(encode(a), encode(b)) agree in sign. Every encoder round-trips: decode(encode(k)) == k for every representable k.
Encoding rules:
- string (including ~string): the raw string bytes. Lexicographic byte order matches the lexicographic order on strings.
- uint8, uint16, uint32, uint64, uint, uintptr: fixed-width big-endian of the natural width; uint and uintptr use the platform word size.
- int8, int16, int32, int64, int: fixed-width big-endian after flipping the sign bit, so signed values sort in ascending signed order (negatives before non-negatives).
- float32, float64: the IEEE 754 bit-pattern with the sign bit flipped for non-negative values and all bits flipped for negative values, then big-endian. Positive zero sorts above negative zero. NaN bit patterns round-trip bitwise; their order relative to other floats is unspecified but deterministic.
Slice types such as []byte are not cmp.Ordered and therefore cannot be used with Ordered; call art.Tree directly for raw []byte keys.
Source Files