numtrie

Documentation

Overview

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.

Index

• Constants
• type Node
  • func New[T any]() *Node[T]
  • func (t *Node[T]) Add(num string, val *T) bool
  • func (t *Node[T]) Get(num string) (*T, int8)
  • func (t *Node[T]) GetExact(num string) *T

Examples

• Node.Get

Constants

const (
	// StatusMatchEmpty indicates that the input string contained no recognizable
	// digit characters and no match was found. [Node.Get] returns a nil value
	// for this status, even when a root/default value is present.
	StatusMatchEmpty int8 = -127 // 0b10000001

	// StatusMatchNo indicates that no match was found because the first digit
	// of the input does not correspond to any child of the trie root. [Node.Get]
	// returns a nil value for this status, even when a root/default value is
	// present.
	StatusMatchNo int8 = -125 // 0b10000011

	// StatusMatchFull indicates an exact match: every digit of the input was
	// consumed and the final trie node is a leaf (no children).
	StatusMatchFull int8 = 0 // 0b00000000

	// StatusMatchPartial indicates that every digit of the input was consumed
	// and the final trie node is not a leaf (it has children). The input is a
	// prefix of at least one longer stored key. The returned value is the last
	// non-nil value found along the path, or nil if no value was stored on it.
	StatusMatchPartial int8 = 1 // 0b00000001

	// StatusMatchPrefix indicates that the trie path was exhausted before all
	// input digits were consumed: a stored key is a prefix of the input. The last
	// non-nil value found along the path is returned (normally the value at the
	// matched leaf).
	StatusMatchPrefix int8 = 2 // 0b00000010

	// StatusMatchPartialPrefix indicates that the trie path was exhausted
	// before all input digits were consumed and the last matched node is not a
	// leaf. The returned value is the last non-nil value found along the path,
	// or nil if no value was stored on it.
	StatusMatchPartialPrefix int8 = 3 // 0b00000011
)

Status codes to be returned when searching for a number in the trie.

Types

type Node

type Node[T any] struct {
	// contains filtered or unexported fields
}

Node is a generic numerical-indexed trie node that stores a value of type T.

Each node holds up to 10 children, one per digit 0 to 9. Non-digit characters in keys are skipped during traversal, making the trie tolerant of formatted numbers (e.g. "+1-800-555-0100") and vanity letter sequences.

The zero value is not usable; create a root node with New.

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.

func New

func New[T any]() *Node[T]

New constructs an empty root Node[T] for building a numerical prefix trie.

func (*Node[T]) Add

func (t *Node[T]) Add(num string, val *T) bool

Add stores val at the trie position defined by num. Non-digit characters are skipped and letters are mapped to keypad digits. It returns true when the key was new, or false when an existing value was overwritten.

Storing a value at the empty key (Add("", v)) sets a default returned by Node.Get as the longest-prefix fallback for any input that matches at least one digit.

A nil val is rejected as a no-op: the trie is left unchanged and Add returns false, since the trie cannot store or distinguish a nil value from an absent one.

The trie stores the supplied pointer, not a copy of the pointed-to value: mutating that value after Add is visible through the trie, and a pointer stored under multiple keys is shared by all of them.

func (*Node[T]) Get

func (t *Node[T]) Get(num string) (*T, int8)

Get retrieves the longest-prefix match for num. Non-digit characters are skipped. The returned status indicates exact, partial, prefix, or no-match outcomes as described by the StatusMatch* constants.

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

For the two negative sentinels (StatusMatchEmpty and StatusMatchNo) the returned value is nil, even when a root/default value is present. A non-negative status does not by itself guarantee a non-nil value: StatusMatchFull and StatusMatchPrefix always carry a value, but StatusMatchPartial and StatusMatchPartialPrefix return nil when no value was stored on the matched path, so callers must always nil-check the returned pointer.

Example

package main

import (
	"fmt"

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

func main() {
	// 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

func (*Node[T]) GetExact

func (t *Node[T]) GetExact(num string) *T

GetExact retrieves the value stored at the exact trie position defined by num. Non-digit characters are skipped and letters are mapped to keypad digits, mirroring Node.Add. Unlike Node.Get, it performs no longest-prefix fallback: it returns nil when the position does not exist in the trie or when no value was stored exactly at that position.