art

README

art — Adaptive Radix Tree for Go

A sorted map implementation using an Adaptive Radix Tree (ART). Fast lookups, path compression, and sorted iteration with Go 1.23 range-over-func.

See CHANGELOG.md for release notes.

The ulterior goals of this project are to get the genie to write code that is:

• Fast
• Reliable
• Readable (by humans & genies)

What is an Adaptive Radix Tree?

An Adaptive Radix Tree is a trie in which every inner node uses a variable-size container sized to its actual fanout. Instead of reserving 256 child slots at every level, ART picks among four node types — holding up to 4, 16, 48, or 256 children — and promotes or demotes a node as children are added and removed. Memory stays proportional to the branching that actually occurs in the data, not to the alphabet size.

Because keys are indexed byte by byte, ART iterates keys in sorted (byte-wise lexicographic) order for free, lookups take O(k) time in the key length k, and path compression collapses chains of single-child nodes so that long shared prefixes are stored once. These properties make ART a practical in-memory ordered map: small enough to compete with hash tables on lookup, yet ordered like a balanced BST.

The data structure was introduced by Leis, Kemper, and Neumann in "The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases" (ICDE 2013).

Features

• Put, Get, Delete with O(k) complexity where k is key length
• Sorted iteration via Go 1.23 range-over-func: All() and Range(start, end)
• Descending and open-ended iteration: AllDescending, RangeFrom, RangeTo, RangeDescending
• Sorted-map accessors: Min, Max, Ceiling, Floor, plus Len, Clear, Clone
• Path compression (shared key prefixes stored once)
• Terminal values (keys that are prefixes of other keys are stored correctly)
• Adaptive node types (node4 / node16 / node48 / node256) with automatic promote/demote
• LockedTree[V] wrapper for sync.RWMutex-guarded concurrent access
• artmap.Ordered[K, V] typed façade for cmp.Ordered keys (integers, floats, strings) with byte-order-preserving encoding
• Fuzz-tested against Go's built-in map (45M+ executions, 0 divergences as of last campaign)

Installation

go get github.com/KentBeck/AdaptiveRadixTree2

Requires Go 1.23 or later (for iter.Seq2 / range-over-func).

Quick start

package main

import (
	"fmt"

	"github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	tree := art.New[int]()
	tree.Put([]byte("apple"), 1)
	tree.Put([]byte("apricot"), 2)
	tree.Put([]byte("banana"), 3)

	if v, ok := tree.Get([]byte("apple")); ok {
		fmt.Println("apple ->", v)
	}

	fmt.Println("size:", tree.Len())

	if k, v, ok := tree.Min(); ok {
		fmt.Printf("min: %s -> %d\n", k, v)
	}
	if k, v, ok := tree.Max(); ok {
		fmt.Printf("max: %s -> %d\n", k, v)
	}

	// Sorted iteration (ascending).
	for k, v := range tree.All() {
		fmt.Printf("%s -> %d\n", k, v)
	}

	// Reverse iteration.
	for k, v := range tree.AllDescending() {
		fmt.Printf("%s -> %d\n", k, v)
	}

	// Range scan: keys in [start, end).
	for k, v := range tree.Range([]byte("ap"), []byte("b")) {
		fmt.Printf("%s -> %d\n", k, v)
	}

	// Open-ended range: all keys >= "b".
	for k, v := range tree.RangeFrom([]byte("b")) {
		fmt.Printf("%s -> %d\n", k, v)
	}

	tree.Delete([]byte("banana"))
}

API reference

art.Tree[V any]

• func New[V any]() *Tree[V] — create an empty tree.
• func (t *Tree[V]) Put(key []byte, value V) — insert or overwrite the value at key.
• func (t *Tree[V]) Get(key []byte) (V, bool) — look up key; ok is false if absent.
• func (t *Tree[V]) Delete(key []byte) bool — remove key; returns whether it was present.
• func (t *Tree[V]) Len() int — current number of entries, O(1).
• func (t *Tree[V]) Clear() — drop every entry in O(1).
• func (t *Tree[V]) Clone() *Tree[V] — independent structural copy.
• func (t *Tree[V]) Min() (key []byte, value V, ok bool) — smallest entry.
• func (t *Tree[V]) Max() (key []byte, value V, ok bool) — largest entry.
• func (t *Tree[V]) Ceiling(target []byte) (key []byte, value V, ok bool) — smallest key ≥ target.
• func (t *Tree[V]) Floor(target []byte) (key []byte, value V, ok bool) — largest key ≤ target.
• func (t *Tree[V]) All() iter.Seq2[[]byte, V] — every (key, value) pair in ascending order.
• func (t *Tree[V]) AllDescending() iter.Seq2[[]byte, V] — every pair in descending order.
• func (t *Tree[V]) Range(start, end []byte) iter.Seq2[[]byte, V] — pairs with key in [start, end), ascending.
• func (t *Tree[V]) RangeFrom(start []byte) iter.Seq2[[]byte, V] — pairs with key ≥ start, ascending.
• func (t *Tree[V]) RangeTo(end []byte) iter.Seq2[[]byte, V] — pairs with key < end, ascending.
• func (t *Tree[V]) RangeDescending(start, end []byte) iter.Seq2[[]byte, V] — pairs with key in [start, end), descending.

art.LockedTree[V any]

A sync.RWMutex-guarded wrapper around Tree[V] — see the Concurrency section below.

• func NewLocked[V any]() *LockedTree[V] — create an empty locked tree.
• func (t *LockedTree[V]) Put(key []byte, value V)
• func (t *LockedTree[V]) Get(key []byte) (V, bool)
• func (t *LockedTree[V]) Delete(key []byte) bool
• func (t *LockedTree[V]) Len() int
• func (t *LockedTree[V]) Clear()
• func (t *LockedTree[V]) Clone() *Tree[V] — returns an unlocked *Tree[V] snapshot.

artmap.Ordered[K, V]

For typed keys (any cmp.Ordered type: integers, floats, strings), the artmap subpackage provides Ordered[K, V], a façade that encodes keys with a byte-order-preserving codec on top of art.Tree[V]. It exposes the same sorted-map surface as Tree[V] — Put, Get, Delete, Len, Clone, Min, Max, Ceiling, Floor, All, AllDescending, Range, RangeFrom, RangeTo, RangeDescending — with K in place of []byte. See artmap/ordered.go for the exact signatures.

Range nil semantics:

• Range(nil, nil) is equivalent to All().
• Range(start, nil) yields all keys ≥ start.
• Range(nil, end) yields all keys < end.
• Range(start, end) with bytes.Compare(start, end) >= 0 yields nothing.
• The empty slice ([]byte{}) is a valid key and is distinct from nil.

Architecture

Node types. There are four inner node types (node4, node16, node48, node256) plus a leaf. Inner nodes grow and shrink based on child count. Each inner node may carry a prefix (for path compression) and an optional terminal leaf holding a value for a key that ends exactly at that node.

The innerNode interface. All four inner node types implement a minimal innerNode interface covering findChild and removeChild (plus kind() via the embedded node interface). Operations (Put, Get, Delete, iteration) are implemented as standalone functions with switch statements dispatching on node type.

File organization.

File	Purpose
types.go	Node structs, innerNode interface, node lifecycle (grow/shrink/addChild/replaceChild/removeChild), Tree[V] definition, New constructor, Len
put.go	Tree.Put + putInto dispatcher + putIntoNode4/16/48/256 helpers
get.go	Tree.Get with inline switch over node types
delete.go	Tree.Delete + deleteFrom switch + postDeleteReshape collapse logic
iterate.go	Tree.All, Tree.AllDescending, Tree.Range, Tree.RangeFrom, Tree.RangeTo, Tree.RangeDescending + iterate/iterateRange switches
sorted.go	Tree.Min, Tree.Max, Tree.Ceiling, Tree.Floor, Tree.Clone, Tree.Clear + shared *LeafOf / cloneNode helpers
locked.go	LockedTree[V] wrapper and NewLocked constructor
helpers.go	Shared pure functions: longestCommonPrefix, newNode4With, splitPrefixedInner, newLeaf
doc.go	Package doc comment
art_test.go	116 unit tests
art_fuzz_test.go	FuzzSortedMap differential fuzzer + 9 seed inputs
artmap/	Typed Ordered[K, V] façade over art.Tree[V] with byte-order-preserving key codec (codec.go, ordered.go)

Invariants.

• Children of node4 and node16 are stored sorted ascending by edge byte.
• A terminal leaf at an inner node has a key equal to that node's full path from the root.
• After Delete, a node with 0 children and no terminal is removed; a node with exactly 1 remaining child collapses (terminal-only, leaf-only, or prefix-merge into its sole child).

When to choose artmap

This project ships two related types: the raw-bytes art.Tree and the typed façade artmap.Ordered[K, V] built on top of it. Both are in-memory ordered maps with one clear sweet spot and two honest trade-offs against google/btree. Full numbers live in benchmarks.md; the short guidance is below.

If your keys are a single cmp.Ordered type (integers, floats, strings) rather than raw []byte, reach for artmap.Ordered[K, V]: it uses byte-order-preserving encoders so the underlying tree preserves the natural ascending order of K without the caller hand-encoding keys.

Workload shape	Recommended
Point-heavy reads / writes (cache, dedup, lookup, set-membership)	art.Tree / artmap.Ordered
Short random-access lookups on long or UUID-shaped keys	art.Tree / artmap.Ordered
Large ordered scans or windowed pagination (scan-heavy)	google/btree
Heavy mutation under GC pressure (tight alloc budget)	google/btree
Small dataset (< 10k keys)	Either — pick on language fit
Mostly-ordered iteration with occasional point ops	google/btree

The Range trade-off. On short ordered scans (the 1 %, 100k-entry window in the bench), google/btree is ~1.74× faster than art.Tree. Both are essentially zero-alloc on the scan, so the gap is pure traversal cost: the ART descent pays to locate the start and then walks through mostly-empty inner structure relative to the span it yields. Range, RangeFrom, RangeTo, RangeDescending, and AllDescending cover the common ordered-iteration shapes, but if ordered scans dominate your workload, google/btree is still the right pick.

The allocation trade-off. Put on art.Tree averages ~1.02 allocs/key at 10M; google/btree averages ~0.07 allocs/key — about 15× fewer allocations per key at build time. Under heavy GC pressure or on memory-tight hosts, the allocation count matters more than the ~25 % byte-total difference.

Quality

• CI: the test workflow (badge at the top of this README) runs build, vet, staticcheck, unit tests, and a short fuzz campaign on every push.
• Fuzz corpus: testdata/fuzz/FuzzSortedMap; cumulative executions have exceeded 45M across campaigns with zero divergences against the map[string]V + sorted-oracle reference.
• Mutation testing: ~95 % measured efficacy under gremlins (100 % of killable mutants at the v0.1.0 baseline; see CHANGELOG.md for per-release figures).

Concurrency

art.Tree[V] and artmap.Ordered[K, V] are not safe for concurrent use by multiple goroutines when any goroutine is writing. Concurrent reads (Get, All, Range, Min, Max, Ceiling, Floor, Len) are safe only while no goroutine is calling a mutating method (Put, Delete, Clear). The tree has no internal synchronization; races are undefined behaviour, not a panic.

For the common read-mostly case, wrap your tree with a sync.RWMutex you own:

var (
    mu   sync.RWMutex
    tree = art.New[int]()
)

mu.Lock(); tree.Put(key, v); mu.Unlock()

mu.RLock(); v, ok := tree.Get(key); mu.RUnlock()

As a convenience, the package ships art.LockedTree[V]: a thin sync.RWMutex-guarded wrapper exposing Put, Get, Delete, Len, Clear, and Clone. It is intentionally narrow — iteration is not wrapped, since holding an RLock across a user-controlled yield is easy to mis-use. Code that needs an ordered scan under a lock should Clone() the tree and iterate the unlocked snapshot.

t := art.NewLocked[int]()
t.Put([]byte("apple"), 1)
v, ok := t.Get([]byte("apple"))

snap := t.Clone()
for k, v := range snap.All() { /* safe: snap is not shared */ _, _ = k, v }

Copy-on-write, lock-free, and RCU variants are out of scope for this release; LockedTree is the supported concurrent surface.

Stability

art is pre-1.0 (currently v0.4.x). Until v1.0.0 is tagged, the public API may change in minor-version bumps; patch releases stay API-compatible. The target for tagging v1.0.0 is no earlier than 2026-07-23, giving the recent additions (the typed artmap.Ordered[K, V] façade, the descending and half-open Range* helpers, and the LockedTree[V] wrapper) time to settle before the signatures are locked down.

From v1.0 onward the project follows Semantic Versioning: breaking changes to the surface listed below only land in a new major version.

Frozen at v1.0. The exported surface of both packages as of v0.4.1:

• Package art (module root):
  • Types: Tree[V any], LockedTree[V any].
  • Constructors: New[V any]() *Tree[V], NewLocked[V any]() *LockedTree[V].
  • Tree[V] methods: Put, Get, Delete, Len, Clear, Clone, Min, Max, Ceiling, Floor, All, AllDescending, Range, RangeFrom, RangeTo, RangeDescending.
  • LockedTree[V] methods: Put, Get, Delete, Len, Clear, Clone.
• Package artmap:
  • Types: OrderedKey (alias for cmp.Ordered), Ordered[K OrderedKey, V any].
  • Constructor: New[K OrderedKey, V any]() *Ordered[K, V].
  • Ordered[K, V] methods: Put, Get, Delete, Len, Clone, Min, Max, Ceiling, Floor, All, AllDescending, Range, RangeFrom, RangeTo, RangeDescending.

Signatures and documented behaviour (including the Range nil / half-open semantics and the goroutine-safety contract above) of these symbols are covered by the SemVer compatibility promise from v1.0 forward.

Not frozen. The following remain free to change under a minor or patch release, before and after v1.0:

• Internal package layout — inner node types (node4/node16/node48/node256), file organization, and unexported helpers.
• Performance characteristics and specific benchmark numbers; improvements or regressions are not breaking changes.
• The artmap byte-order-preserving key encoding is an implementation detail — treat encoded keys as opaque and do not persist them across versions.
• Fuzz corpus layout under testdata/.

Breaking changes during the 0.x series are recorded in CHANGELOG.md.

Testing

go test ./...                                           # 116 unit tests + 9 fuzz seed runs
go test -run=^$ -fuzz=FuzzSortedMap -fuzztime=30s ./... # differential fuzz
go vet ./... && gofmt -l .                              # static checks

The fuzz harness cross-checks every operation against Go's built-in map[string]any plus a sorted-slice oracle, so any divergence in value, presence, or iteration order surfaces immediately.

Contributing

• Run the full test suite plus a fuzz campaign of at least 30 seconds before opening a PR.
• Keep go vet and gofmt clean.
• Prefer the existing file organization: one file per public operation.
• If you add a new operation, expect to add a method to innerNode and implement it on all four inner node types.

License

Licensed under the MIT License. See LICENSE for details.

Documentation

Overview

Package art implements an Adaptive Radix Tree: a variable-fanout trie that stores []byte keys in byte-wise sorted order.

A Tree[V] is a sorted map from []byte to V. Point operations (Put, Get, Delete) are O(k) in the key length, and in-order traversal is exposed via Go 1.23 range-over-func iterators.

Keys are ordered lexicographically by their raw bytes; shorter keys sort before longer keys that share the shorter key as a prefix. Keys passed to Put are copied, so callers may reuse their slices freely. A nil key and an empty-slice key are equivalent (both represent the empty key); the tree can hold at most one entry at the empty key.

Iteration:

• All yields every (key, value) pair in ascending key order.
• Range yields every (key, value) pair whose key lies in the half-open interval [start, end). A nil bound is unbounded on that side.

Sorted-map surface:

• Min and Max return the smallest and largest entry.
• Ceiling and Floor return the successor and predecessor of a target key (inclusive at equality).
• Clone returns an independent structural copy of the tree.
• Clear removes every entry in O(1).

Goroutine safety: a Tree is not safe for concurrent use by multiple goroutines when any goroutine is writing; concurrent reads are safe only while no goroutine is mutating the tree. Callers that need concurrent access should guard a Tree with their own sync.RWMutex or use the provided LockedTree wrapper. See the Tree type and the Concurrency section of the project README for the authoritative statement.

Minimal usage:

t := art.New[int]()
t.Put([]byte("apple"), 1)
t.Put([]byte("apricot"), 2)
t.Put([]byte("banana"), 3)

if v, ok := t.Get([]byte("apple")); ok {
	_ = v // 1
}

for k, v := range t.All() {
	_, _ = k, v // "apple"/1, "apricot"/2, "banana"/3
}

for k, v := range t.Range([]byte("ap"), []byte("b")) {
	_, _ = k, v // "apple"/1, "apricot"/2
}

t.Delete([]byte("apple"))
_ = t.Len() // 2

See CHANGELOG.md at the repository root for version-to-version changes and release notes.

Index

• type LockedTree
  • func NewLocked[V any]() *LockedTree[V]
  • func (t *LockedTree[V]) Clear()
  • func (t *LockedTree[V]) Clone() *Tree[V]
  • func (t *LockedTree[V]) Delete(key []byte) bool
  • func (t *LockedTree[V]) Get(key []byte) (V, bool)
  • func (t *LockedTree[V]) Len() int
  • func (t *LockedTree[V]) Put(key []byte, value V)
• type Tree
  • func New[V any]() *Tree[V]
  • func (t *Tree[V]) All() iter.Seq2[[]byte, V]
  • func (t *Tree[V]) AllDescending() iter.Seq2[[]byte, V]
  • func (t *Tree[V]) Ceiling(target []byte) (key []byte, value V, ok bool)
  • func (t *Tree[V]) Clear()
  • func (t *Tree[V]) Clone() *Tree[V]
  • func (t *Tree[V]) Delete(key []byte) bool
  • func (t *Tree[V]) Floor(target []byte) (key []byte, value V, ok bool)
  • func (t *Tree[V]) Get(key []byte) (value V, ok bool)
  • func (t *Tree[V]) Len() int
  • func (t *Tree[V]) Max() (key []byte, value V, ok bool)
  • func (t *Tree[V]) Min() (key []byte, value V, ok bool)
  • func (t *Tree[V]) Put(key []byte, value V)
  • func (t *Tree[V]) Range(start, end []byte) iter.Seq2[[]byte, V]
  • func (t *Tree[V]) RangeDescending(start, end []byte) iter.Seq2[[]byte, V]
  • func (t *Tree[V]) RangeFrom(start []byte) iter.Seq2[[]byte, V]
  • func (t *Tree[V]) RangeTo(end []byte) iter.Seq2[[]byte, V]

Examples

• Tree.All
• Tree.Ceiling
• Tree.Clear
• Tree.Clone
• Tree.Delete
• Tree.Floor
• Tree.Get
• Tree.Len
• Tree.Max
• Tree.Min
• Tree.Put
• Tree.Range

Types

type LockedTree

type LockedTree[V any] struct {
	// contains filtered or unexported fields
}

LockedTree is a thin sync.RWMutex-guarded wrapper around Tree for callers who want a drop-in concurrent sorted map with the obvious semantics: writes are serialized and readers run in parallel with each other.

The wrapper covers only the point operations (Put, Get, Delete, Len, Clear, Clone). Iteration is deliberately not wrapped because the caller controls when each yield returns, which makes a held RLock easy to hold for too long; callers that need an ordered scan should take a LockedTree.Clone and iterate the unlocked snapshot.

See the Concurrency section of the project README for the full discussion and trade-offs.

func NewLocked

func NewLocked[V any]() *LockedTree[V]

NewLocked returns an empty LockedTree.

func (*LockedTree[V]) Clear

func (t *LockedTree[V]) Clear()

Clear removes every entry.

func (*LockedTree[V]) Clone

func (t *LockedTree[V]) Clone() *Tree[V]

Clone returns an unlocked snapshot Tree. The snapshot does not share its mutex with the original, so callers can iterate the returned tree without holding any LockedTree lock.

func (*LockedTree[V]) Delete

func (t *LockedTree[V]) Delete(key []byte) bool

Delete removes key, returning whether it was present.

func (*LockedTree[V]) Get

func (t *LockedTree[V]) Get(key []byte) (V, bool)

Get returns the value stored under key, if any.

func (*LockedTree[V]) Len

func (t *LockedTree[V]) Len() int

Len returns the current number of entries.

func (*LockedTree[V]) Put

func (t *LockedTree[V]) Put(key []byte, value V)

Put associates value with key, replacing any previous value.

type Tree

type Tree[V any] struct {
	// contains filtered or unexported fields
}

Tree is a sorted map from []byte keys to V values, backed by an Adaptive Radix Tree.

A Tree is not safe for concurrent use by multiple goroutines when any goroutine is writing; concurrent reads are safe only while no goroutine is mutating the tree. Callers that need concurrent access should guard a Tree with their own sync.RWMutex or use the provided LockedTree wrapper. See the Concurrency section of the project README for the full discussion.

func New

func New[V any]() *Tree[V]

New returns an empty Tree.

func (*Tree[V]) All

func (t *Tree[V]) All() iter.Seq2[[]byte, V]

All returns an iterator over every (key, value) pair in the tree in ascending byte-wise key order. Breaking out of the range stops the traversal immediately.

The yielded key slice aliases the tree's internal storage. It is safe to retain while the corresponding entry remains in the tree, and must be treated as read-only; mutating it corrupts the tree. If the entry may be deleted (including by the caller during iteration) while a retained reference is in use, copy the key.

See Tree.AllDescending for the reverse walk.

Example

package main

import (
	"fmt"

	art "github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	t := art.New[int]()
	t.Put([]byte("banana"), 3)
	t.Put([]byte("apple"), 1)
	t.Put([]byte("apricot"), 2)
	for k, v := range t.All() {
		fmt.Printf("%s=%d\n", k, v)
	}
}

Output:
apple=1
apricot=2
banana=3

func (*Tree[V]) AllDescending

func (t *Tree[V]) AllDescending() iter.Seq2[[]byte, V]

AllDescending returns an iterator over every (key, value) pair in the tree in descending byte-wise key order. Breaking out of the range stops the traversal immediately.

The yielded key slice aliases the tree's internal storage under the same contract as Tree.All. See Tree.All for the forward walk.

func (*Tree[V]) Ceiling

func (t *Tree[V]) Ceiling(target []byte) (key []byte, value V, ok bool)

Ceiling returns the smallest key that compares byte-wise >= target, along with its value. If no such key exists, ok is false. A nil target and an empty-slice target are equivalent (both represent the empty key), so Ceiling of either returns the tree's Min when the tree is non-empty.

Example

package main

import (
	"fmt"

	art "github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	t := art.New[int]()
	t.Put([]byte("apple"), 1)
	t.Put([]byte("apricot"), 2)
	t.Put([]byte("banana"), 3)
	k, v, ok := t.Ceiling([]byte("apq"))
	fmt.Printf("%s=%d ok=%v\n", k, v, ok)
	_, _, ok = t.Ceiling([]byte("z"))
	fmt.Println(ok)
}

Output:
apricot=2 ok=true
false

func (*Tree[V]) Clear

func (t *Tree[V]) Clear()

Clear removes every entry from the tree in O(1) by dropping the root reference. After Clear, Tree.Len returns 0 and subsequent Put calls behave as on a newly constructed tree.

Example

package main

import (
	"fmt"

	art "github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	t := art.New[int]()
	t.Put([]byte("apple"), 1)
	t.Put([]byte("banana"), 2)
	t.Clear()
	fmt.Println(t.Len())
}

Output:
0

func (*Tree[V]) Clone

func (t *Tree[V]) Clone() *Tree[V]

Clone returns a structural copy of t. Writes to t or to the returned tree do not affect each other. Key bytes may be shared between the two trees, matching the read-only-key contract of Tree.All and Tree.Range.

Example

package main

import (
	"fmt"

	art "github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	t := art.New[int]()
	t.Put([]byte("apple"), 1)
	cp := t.Clone()
	cp.Put([]byte("banana"), 2)
	fmt.Println(t.Len(), cp.Len())
}

Output:
1 2

func (*Tree[V]) Delete

func (t *Tree[V]) Delete(key []byte) bool

Delete removes key from the tree, returning whether it was present. Traversal consumes each inner node's prefix and, if the key is exhausted at a node, targets that node's terminal value. After a successful remove the affected node is demoted to a smaller node type (or collapsed to its only child) whenever its child count crosses the next-smaller capacity. A nil key and an empty-slice key are equivalent (both represent the empty key).

Example

package main

import (
	"fmt"

	art "github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	t := art.New[int]()
	t.Put([]byte("apple"), 1)
	fmt.Println(t.Delete([]byte("apple")))
	fmt.Println(t.Delete([]byte("apple")))
}

Output:
true
false

func (*Tree[V]) Floor

func (t *Tree[V]) Floor(target []byte) (key []byte, value V, ok bool)

Floor returns the largest key that compares byte-wise <= target, along with its value. If no such key exists, ok is false. A nil target and an empty-slice target are equivalent (both represent the empty key); Floor of either returns the empty key's entry when present, and otherwise ok is false.

Example

package main

import (
	"fmt"

	art "github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	t := art.New[int]()
	t.Put([]byte("apple"), 1)
	t.Put([]byte("apricot"), 2)
	t.Put([]byte("banana"), 3)
	k, v, ok := t.Floor([]byte("apq"))
	fmt.Printf("%s=%d ok=%v\n", k, v, ok)
	_, _, ok = t.Floor([]byte(""))
	fmt.Println(ok)
}

Output:
apple=1 ok=true
false

func (*Tree[V]) Get

func (t *Tree[V]) Get(key []byte) (value V, ok bool)

Get returns the value previously stored under key, if any. If the key is absent the returned value is the zero value of V. A nil key and an empty-slice key are equivalent (both represent the empty key).

Example

package main

import (
	"fmt"

	art "github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	t := art.New[int]()
	t.Put([]byte("apple"), 1)
	hit, ok := t.Get([]byte("apple"))
	fmt.Println(hit, ok)
	miss, ok := t.Get([]byte("banana"))
	fmt.Println(miss, ok)
}

Output:
1 true
0 false

func (*Tree[V]) Len

func (t *Tree[V]) Len() int

Len returns the number of key-value pairs in the tree. It runs in O(1).

Example

package main

import (
	"fmt"

	art "github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	t := art.New[int]()
	fmt.Println(t.Len())
	t.Put([]byte("apple"), 1)
	t.Put([]byte("apricot"), 2)
	fmt.Println(t.Len())
	t.Delete([]byte("apple"))
	fmt.Println(t.Len())
}

Output:
0
2
1

func (*Tree[V]) Max

func (t *Tree[V]) Max() (key []byte, value V, ok bool)

Max returns the largest key in the tree, its value, and ok=true. If the tree is empty, ok is false and the returned key and value are their zero values.

Example

package main

import (
	"fmt"

	art "github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	t := art.New[int]()
	t.Put([]byte("banana"), 3)
	t.Put([]byte("apple"), 1)
	t.Put([]byte("apricot"), 2)
	k, v, ok := t.Max()
	fmt.Printf("%s=%d ok=%v\n", k, v, ok)
}

Output:
banana=3 ok=true

func (*Tree[V]) Min

func (t *Tree[V]) Min() (key []byte, value V, ok bool)

Min returns the smallest key in the tree, its value, and ok=true. If the tree is empty, ok is false and the returned key and value are their zero values.

Example

package main

import (
	"fmt"

	art "github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	t := art.New[int]()
	t.Put([]byte("banana"), 3)
	t.Put([]byte("apple"), 1)
	t.Put([]byte("apricot"), 2)
	k, v, ok := t.Min()
	fmt.Printf("%s=%d ok=%v\n", k, v, ok)
}

Output:
apple=1 ok=true

func (*Tree[V]) Put

func (t *Tree[V]) Put(key []byte, value V)

Put associates value with key, replacing any previous value. An inner node's prefix is consumed from the key as traversal descends; keys that end at such a node's exact path are stored in its terminal slot. A nil key and an empty-slice key are equivalent (both represent the empty key); the tree can hold at most one entry at the empty key.

Example

package main

import (
	"fmt"

	art "github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	t := art.New[int]()
	t.Put([]byte("apple"), 1)
	v, _ := t.Get([]byte("apple"))
	fmt.Println(v)
}

Output:
1

func (*Tree[V]) Range

func (t *Tree[V]) Range(start, end []byte) iter.Seq2[[]byte, V]

Range returns an iterator over every (key, value) pair whose key lies in the half-open interval [start, end), in ascending byte-wise key order. A nil bound is treated as unbounded on that side, so Range(nil, nil) is equivalent to All. Breaking out of the range stops the traversal immediately.

The yielded key slice aliases the tree's internal storage under the same contract as Tree.All: safe to retain while the entry remains in the tree, must be treated as read-only, and must be copied if retained past a possible deletion of the entry.

See Tree.RangeFrom and Tree.RangeTo for open-ended variants and Tree.RangeDescending for the reverse walk of the same interval.

Example

package main

import (
	"fmt"

	art "github.com/KentBeck/AdaptiveRadixTree2"
)

func main() {
	t := art.New[int]()
	t.Put([]byte("apple"), 1)
	t.Put([]byte("apricot"), 2)
	t.Put([]byte("banana"), 3)
	for k, v := range t.Range([]byte("ap"), []byte("b")) {
		fmt.Printf("%s=%d\n", k, v)
	}
}

Output:
apple=1
apricot=2

func (*Tree[V]) RangeDescending

func (t *Tree[V]) RangeDescending(start, end []byte) iter.Seq2[[]byte, V]

RangeDescending returns an iterator over every (key, value) pair whose key lies in the half-open interval [start, end), in descending byte-wise key order. The bounds have the same semantics as Tree.Range — start is inclusive, end is exclusive, and a nil bound is unbounded on that side — so RangeDescending(nil, nil) is equivalent to Tree.AllDescending and start >= end yields nothing. Breaking out of the range stops the traversal immediately.

The yielded key slice aliases the tree's internal storage under the same contract as Tree.All. See Tree.Range for the ascending walk of the same interval.

func (*Tree[V]) RangeFrom

func (t *Tree[V]) RangeFrom(start []byte) iter.Seq2[[]byte, V]

RangeFrom returns an iterator over every (key, value) pair whose key is byte-wise >= start, in ascending order. A nil start is equivalent to Tree.All. This is the shorthand for Range(start, nil) and matches google/btree's AscendGreaterOrEqual.

The yielded key slice aliases the tree's internal storage under the same contract as Tree.All.

func (*Tree[V]) RangeTo

func (t *Tree[V]) RangeTo(end []byte) iter.Seq2[[]byte, V]

RangeTo returns an iterator over every (key, value) pair whose key is byte-wise < end, in ascending order. A nil end is equivalent to Tree.All. This is the shorthand for Range(nil, end) and matches google/btree's AscendLessThan.

The yielded key slice aliases the tree's internal storage under the same contract as Tree.All.