trie

README

• R-way Trie
• Ternary Search Trie

var dict = map[string]string{
	"a":         "一个",
	"an":        "一个",
	"abandon":   "遗弃",
	"abnormal":  "反常的",
	"apollo":    "阿波罗",
	"archive":   "存档",
	"are":       "是",
	"am":        "是",
	"automatic": "自动的",
	"best":      "最佳的",
	"bit":       "一点",
	"bite":      "咬",
	"bitcoin":   "比特币",
	"byte":      "字节",
}

func ExampleTrie() {
	trie := NewTrie[string](alphabet.NewAlphabet(alphabet.ASCII))
	for k, v := range dict {
		trie.Upsert(k, v)
	}
	result := trie.KeysWithPrefix("")
	sort.Strings(result)
	fmt.Println("all keys:", result)

	pattern := "b.te"
	result = trie.KeysMatch(pattern)
	sort.Strings(result)
	fmt.Printf("keys match '%s': %v\n", pattern, result)

	prefix := "bi"
	result = trie.KeysWithPrefix(prefix)
	sort.Strings(result)
	fmt.Printf("keys with prefix '%s': %v\n", prefix, result)

	str := "bitcoins"
	fmt.Printf("longest key with prefix '%s': %s\n", str, trie.LongestPrefixOf(str))

	// Output:
	// all keys: [a abandon abnormal am an apollo archive are automatic best bit bitcoin bite byte]
	// keys match 'b.te': [bite byte]
	// keys with prefix 'bi': [bit bitcoin bite]
	// longest key with prefix 'bitcoins': bitcoin
}

func ExampleTernary() {
	trie := NewTernary[string]()
	for k, v := range dict {
		trie.Upsert(k, v)
	}
	result := trie.KeysWithPrefix("")
	sort.Strings(result)
	fmt.Println("all keys:", result)

	pattern := "b.te"
	result = trie.KeysMatch(pattern)
	sort.Strings(result)
	fmt.Printf("keys match '%s': %v\n", pattern, result)

	prefix := "bi"
	result = trie.KeysWithPrefix(prefix)
	sort.Strings(result)
	fmt.Printf("keys with prefix '%s': %v\n", prefix, result)

	str := "bitcoins"
	fmt.Printf("longest key with prefix '%s': %s\n", str, trie.LongestPrefixOf(str))

	// Output:
	// all keys: [a abandon abnormal am an apollo archive are automatic best bit bitcoin bite byte]
	// keys match 'b.te': [bite byte]
	// keys with prefix 'bi': [bit bitcoin bite]
	// longest key with prefix 'bitcoins': bitcoin
}

Documentation

Index

• type Ternary
  • func NewTernary[T any]() *Ternary[T]
  • func (t *Ternary[T]) Compress()
  • func (t *Ternary[T]) Delete(key string)
  • func (t *Ternary[T]) Find(key string) *T
  • func (t *Ternary[T]) KeysMatch(p string) []string
  • func (t *Ternary[T]) KeysWithPrefix(prefix string) []string
  • func (t *Ternary[T]) LongestPrefixOf(s string) string
  • func (t *Ternary[T]) Upsert(key string, val T) bool
• type Trie
  • func NewTrie[T any](alp alphabet.IAlp) *Trie[T]
  • func (t *Trie[T]) Delete(key string)
  • func (t *Trie[T]) Find(key string) *T
  • func (t *Trie[T]) KeysMatch(p string) []string
  • func (t *Trie[T]) KeysWithPrefix(prefix string) []string
  • func (t *Trie[T]) LongestPrefixOf(s string) string
  • func (t *Trie[T]) Upsert(key string, v T)

Examples

• Ternary
• Trie

Types

type Ternary

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

Example

trie := NewTernary[string]()
for k, v := range dict {
	trie.Upsert(k, v)
}
result := trie.KeysWithPrefix("")
sort.Strings(result)
fmt.Println("all keys:", result)

pattern := "b.te"
result = trie.KeysMatch(pattern)
sort.Strings(result)
fmt.Printf("keys match '%s': %v\n", pattern, result)

prefix := "bi"
result = trie.KeysWithPrefix(prefix)
sort.Strings(result)
fmt.Printf("keys with prefix '%s': %v\n", prefix, result)

str := "bitcoins"
fmt.Printf("longest key with prefix '%s': %s\n", str, trie.LongestPrefixOf(str))

Output:

all keys: [a abandon abnormal am an apollo archive are automatic best bit bitcoin bite byte]
keys match 'b.te': [bite byte]
keys with prefix 'bi': [bit bitcoin bite]
longest key with prefix 'bitcoins': bitcoin

func NewTernary

func NewTernary[T any]() *Ternary[T]

func (*Ternary[T]) Compress

func (t *Ternary[T]) Compress()

func (*Ternary[T]) Delete

func (t *Ternary[T]) Delete(key string)

func (*Ternary[T]) Find

func (t *Ternary[T]) Find(key string) *T

func (*Ternary[T]) KeysMatch

func (t *Ternary[T]) KeysMatch(p string) []string

func (*Ternary[T]) KeysWithPrefix

func (t *Ternary[T]) KeysWithPrefix(prefix string) []string

func (*Ternary[T]) LongestPrefixOf

func (t *Ternary[T]) LongestPrefixOf(s string) string

func (*Ternary[T]) Upsert

func (t *Ternary[T]) Upsert(key string, val T) bool

type Trie

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

Example

trie := NewTrie[string](alphabet.NewAlphabet(alphabet.ASCII))
for k, v := range dict {
	trie.Upsert(k, v)
}
result := trie.KeysWithPrefix("")
sort.Strings(result)
fmt.Println("all keys:", result)

pattern := "b.te"
result = trie.KeysMatch(pattern)
sort.Strings(result)
fmt.Printf("keys match '%s': %v\n", pattern, result)

prefix := "bi"
result = trie.KeysWithPrefix(prefix)
sort.Strings(result)
fmt.Printf("keys with prefix '%s': %v\n", prefix, result)

str := "bitcoins"
fmt.Printf("longest key with prefix '%s': %s\n", str, trie.LongestPrefixOf(str))

Output:

all keys: [a abandon abnormal am an apollo archive are automatic best bit bitcoin bite byte]
keys match 'b.te': [bite byte]
keys with prefix 'bi': [bit bitcoin bite]
longest key with prefix 'bitcoins': bitcoin

func NewTrie

func NewTrie[T any](alp alphabet.IAlp) *Trie[T]

func (*Trie[T]) Delete

func (t *Trie[T]) Delete(key string)

func (*Trie[T]) Find

func (t *Trie[T]) Find(key string) *T

func (*Trie[T]) KeysMatch

func (t *Trie[T]) KeysMatch(p string) []string

func (*Trie[T]) KeysWithPrefix

func (t *Trie[T]) KeysWithPrefix(prefix string) []string

func (*Trie[T]) LongestPrefixOf

func (t *Trie[T]) LongestPrefixOf(s string) string

func (*Trie[T]) Upsert

func (t *Trie[T]) Upsert(key string, v T)