numtrie

Documentation

Overview

Package numtrie provides a numerical-indexed trie data structure. The trie allows to store and retrieve values of any type associated with a numerical key. It supports partial matches and alphabetical phone numbers.

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)

Examples

• Node.Get

Constants

const (
	// StatusMatchEmpty indicates that the input string is empty and no match
	// was found.
	StatusMatchEmpty int8 = -127 // 0b10000001

	// StatusMatchNo indicates that no match was found. The first number digit
	// doesn't match any value at the trie root.
	StatusMatchNo int8 = -125 // 0b10000011

	// StatusMatchFull indicates that a full exact match was found. The full
	// number matches a trie leaf.
	StatusMatchFull int8 = 0 // 0b00000000

	// StatusMatchPartial indicates that the full number matches a trie node
	// that is not a leaf.
	StatusMatchPartial int8 = 1 // 0b00000001

	// StatusMatchPrefix indicates that only a prefix of the number matches a
	// trie leaf. The remaining digits are not present in the trie.
	StatusMatchPrefix int8 = 2 // 0b00000010

	// StatusMatchPartialPrefix 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.
	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 numerical-indexed trie node that stores a value of any type.

func New

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

New creates a new Node.

func (*Node[T]) Add

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

Add adds a value to the trie with the given numerical key. It returns false if the value overrides an existing non-nil one.

func (*Node[T]) Get

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

Get retrieves a value from the trie with the given numerical key. It supports partial matches. It returns the last non-nil value found in the trie path for the specified number. The return value should always be checked for the nil value. The second return value provides information about the match status:

• StatusMatchEmpty (-127 = 0b10000001) indicates that the input string is empty and no match was found.
• StatusMatchNo (-125 = 0b10000011) indicates that no match was found. The first number digit doesn't match any value at the trie root.
• StatusMatchFull (0 = 0b00000000) indicates that a full exact match was found. The full number matches a trie leaf.
• StatusMatchPartial (1 = 0b00000001) indicates that the full number matches a trie node that is not a leaf.
• StatusMatchPrefix (2 = 0b00000010) indicates that only a prefix of the number matches a trie leaf. The remaining digits are not present in the trie.
• 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.

Example

package main

import (
	"fmt"

	"github.com/Vonage/gosrvlib/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