numtrie

numtrie provides a generic, digit-indexed trie (prefix tree) for associating values of any type with numerical keys, with built-in support for partial/prefix matching and alphabetical (vanity) phone-number keys.

Table of contents

Part of nurago, a collection of independent Go packages for backend services.

import "github.com/tecnickcom/nurago/pkg/numtrie"

Package numtrie provides a generic, digit-indexed trie (prefix tree) for associating values of any type with numerical keys, with built-in support for partial/prefix matching and alphabetical (vanity) phone-number keys.

Lookup is O(k) in the number of digits k, with prefix traversal and partial-match support.

Usage

Node is a generic trie node parameterised on the value type. Build the trie once with Node.Add, then query it repeatedly with [Node.Get]:

// Build a routing table.
root := numtrie.New[Route]()
root.Add("1",      &defaultUSRoute)
root.Add("1212",   &newYorkRoute)
root.Add("44",     &ukRoute)
root.Add("44207",  &londonRoute)

// Longest-prefix lookup for an incoming call.
val, status := root.Get("+1-212-555-0100")
if val != nil {
	// val == &newYorkRoute (longest matching prefix: "1212")
}

Allocation

Each node holds a fixed 10-slot children array (one slot per digit 0 to 9) rather than a per-node map, so a node is a single allocation. Insertion allocates one node per new digit position; re-inserting at an existing position allocates nothing, and lookups (Node.Get and Node.GetExact) never allocate.

Match Status Codes

The status int8 returned by Node.Get is a compact bit field:

Bit 7 (sign): set   → no digits matched at all (empty input or no root child)
Bit 1:        set   → input extends beyond the matched trie path (prefix match)
Bit 0:        set   → matched node has children (partial match)

The six named constants encode every meaningful combination:

StatusMatchEmpty         (-127): no digit characters in input
StatusMatchNo            (-125): first digit not in trie
StatusMatchFull          (   0): exact match, leaf node
StatusMatchPartial       (   1): exact match, non-leaf node
StatusMatchPrefix        (   2): stored key is prefix of input, leaf node
StatusMatchPartialPrefix (   3): stored key is prefix of input, non-leaf node

When bit 7 is set the status is a standalone sentinel (StatusMatchEmpty or StatusMatchNo): only bit 7 is significant and the low bits carry no meaning. Node.Get returns a nil value for both of these, even when a root/default value is present.

A non-negative status does not by itself guarantee a non-nil value: callers must always nil-check the returned pointer. StatusMatchFull and StatusMatchPrefix (the two leaf outcomes) always carry a value, but StatusMatchPartial and StatusMatchPartialPrefix return nil whenever no value was stored on the matched path.

Concurrency

A Node is not safe for concurrent modification: Node.Add mutates the trie in place. Once the trie is fully built it may be queried concurrently by any number of goroutines via Node.Get and Node.GetExact, provided no Node.Add runs concurrently.

When To Use

  • You route on number prefixes, such as dialing codes or bank identifiers.
  • Lookups must return the value for the longest matching prefix, not an exact match.
  • Keys may arrive as vanity phone numbers containing letters.

Example

// create a new numerical-indexed trie that holds sting values
node := numtrie.New[string]()

valA := "gamma"
node.Add("702", &valA)

valB := "foxtrot"
node.Add("702153", &valB)

// StatusMatchEmpty (-127 = 0b10000001) indicates that the input string is
// empty and no match was found.
got, status := node.Get("")
if got != nil {
	fmt.Println(*got, status)
} else {
	fmt.Println(got, status)
}

// StatusMatchNo (-125 = 0b10000011) indicates that no match was found. The
// first number digit doesn't match any value at the trie root.
got, status = node.Get("111")
if got != nil {
	fmt.Println(*got, status)
} else {
	fmt.Println(got, status)
}

// StatusMatchFull (0 = 0b00000000) indicates that a full exact match was
// found. The full number matches a trie leaf.
got, status = node.Get("702153")
if got != nil {
	fmt.Println(*got, status)
}

// StatusMatchPartial (1 = 0b00000001) indicates that the full number
// matches a trie node that is not a leaf.
got, status = node.Get("702")
if got != nil {
	fmt.Println(*got, status)
}

// StatusMatchPrefix (2 = 0b00000010) indicates that only a prefix of the
// number matches a trie leaf. The remaining digits are not present in the
// trie.
got, status = node.Get("702153-99")
if got != nil {
	fmt.Println(*got, status)
}

// StatusMatchPartialPrefix (3 = 0b00000011) indicates that only a prefix of
// the number matches a trie node that is not a leaf. The remaining digits
// are not present in the trie.
got, status = node.Get("702-99")
if got != nil {
	fmt.Println(*got, status)
}

// StatusMatchPartialPrefix (3 = 0b00000011) indicates that only a prefix of
// the number matches a trie node that is not a leaf. The remaining digits
// are not present in the trie. The last non-nil value on the trie path is
// returned.
// The match is with 7021 but the node at 1 is nil, so the last non-nil
// value at node 702 is returned.
got, status = node.Get("702166")
if got != nil {
	fmt.Println(*got, status)
}

// Output:
// <nil> -127
// <nil> -125
// foxtrot 0
// gamma 1
// foxtrot 2
// gamma 3
// gamma 3

Full source is in example_numtrie_test.go. More runnable examples are on pkg.go.dev.

Dependencies

This package reaches no external module: it uses only the Go standard library.