trie

README

字典树的Go实现

一、安装

go get -u github.com/golang-infrastructure/go-trie

二、示例代码

前缀字典树：

2.1 基本单词查询

package main

import (
	"fmt"
	"github.com/golang-infrastructure/go-trie"
)

func main() {

	trie := trie.New[string]()

	err := trie.Add("china", "中国")
	if err != nil {
		fmt.Println(err)
		return
	}

	err = trie.Add("chinese", "中国人")
	if err != nil {
		fmt.Println(err)
		return
	}

	value, err := trie.Query("china")
	if err != nil {
		fmt.Println(err)
		return
	}
	fmt.Println(value)
	// Output:
	// 中国

}

2.2 Web路由

package main

import (
	"fmt"
	"github.com/golang-infrastructure/go-trie"
	"strings"
)

func main() {

	// 假装是一个Web路由
	trie := trie.New[func() error](func(s string) ([]string, error) {
		slice := make([]string, 0)
		for _, x := range strings.Split(s, "/") {
			if x != "" {
				slice = append(slice, x)
			}
		}
		return slice, nil
	})

	// 增加一个路由
	err := trie.Add("/foo/bar", func() error {
		fmt.Println("路由到了/foo/bar")
		return nil
	})
	if err != nil {
		fmt.Println(err)
		return
	}

	// 尝试寻找不存在的路由
	_, err = trie.Query("/foo")
	if err != nil {
		fmt.Println(err.Error())
	}

	// 尝试寻找存在的路由
	handler, err := trie.Query("//foo//bar/")
	if err != nil {
		fmt.Println(err.Error())
	}
	err = handler()
	if err != nil {
		fmt.Println(err.Error())
		return
	}
	// Output:
	// not found
	// 路由到了/foo/bar

}

三、API

PathSplitFunc

用于把传入的路径字符串切割为字典中的一个项，默认是按照字符来切割，使用者可根据自己的需求自定义切割方式

type PathSplitFunc func(s string) ([]string, error)

New

创建一个字典树

func New[T any](pathSplitFunc ...PathSplitFunc) *Trie[T]

Add

往字典树上添加一个单词，单词可以绑定一个值，但是如果要添加单词已经存在的话则添加失败，单词原来绑定的值不会被修改

func (x *Trie[T]) Add(path string, value T) error

Upsert

往字典树上添加一个单词，单词可以绑定一个值，如果单词已经存在的话则更新其绑定的值，如果不存在的话则新增

func (x *Trie[T]) Upsert(path string, value T) error 

Remove

从字典树上移除单词

func (x *Trie[T]) Remove(path string) error

Query

查询给定的单词绑定的值，如果给定的单词在字典树上不存在的话，则返回ErrNotFound错误

func (x *Trie[T]) Query(path string) (value T, err error)

QueryOrDefault

查询给定的单词绑定的值，如果给定的单词在字典树上不存在的话，则返回给定的默认值

func (x *Trie[T]) QueryOrDefault(path string, defaultValue T) (value T, err error)

FindTrieNode

根据给定的单词查找其对应的字典树上的节点，一般用不到，都是内部API使用

func (x *Trie[T]) FindTrieNode(path string) ([]string, *TrieNode[T], error)

ToSlice

把树上的所有单词和绑定的值以二元组键值对列表的形式返回

func (x *Trie[T]) ToSlice(delimiter ...string) []*tuple.Tuple2[string, T] 

QueryByPrefix

根据前缀查询单词

func (x *Trie[T]) QueryByPrefix(prefix string, delimiter ...string) []*tuple.Tuple2[string, T]

Contains

查询给定的单词是否在树上

func (x *Trie[T]) Contains(path string) (bool, error)

ExportToDotLanguage

把字典树导出为dot language方便可视化观察

func (x *Trie[T]) ExportToDotLanguage() string 

TODO

• 增加SyncTrie的文档及示例说明

Documentation

Index

• Constants
• Variables
• func DefaultPathSplitFunc(s string) ([]string, error)
• type PathSplitFunc
• type SyncTrie
  • func NewSync[T any](pathSplitFunc ...PathSplitFunc) *SyncTrie[T]
  • func (x *SyncTrie[T]) Add(path string, value T) error
  • func (x *SyncTrie[T]) Contains(path string) (bool, error)
  • func (x *SyncTrie[T]) ExportToDotLanguage() string
  • func (x *SyncTrie[T]) FindTrieNode(path string) ([]string, *TrieNode[T], error)
  • func (x *SyncTrie[T]) Query(path string) (value T, err error)
  • func (x *SyncTrie[T]) QueryByPrefix(prefix string, delimiter ...string) []*tuple.Tuple2[string, T]
  • func (x *SyncTrie[T]) QueryOrDefault(path string, defaultValue T) (value T, err error)
  • func (x *SyncTrie[T]) Remove(path string) error
  • func (x *SyncTrie[T]) ToSlice(delimiter ...string) []*tuple.Tuple2[string, T]
  • func (x *SyncTrie[T]) Upsert(path string, value T) error
• type Trie
  • func New[T any](pathSplitFunc ...PathSplitFunc) *Trie[T]
  • func (x *Trie[T]) Add(path string, value T) error
  • func (x *Trie[T]) Contains(path string) (bool, error)
  • func (x *Trie[T]) ExportToDotLanguage() string
  • func (x *Trie[T]) FindTrieNode(path string) ([]string, *TrieNode[T], error)
  • func (x *Trie[T]) Query(path string) (value T, err error)
  • func (x *Trie[T]) QueryByPrefix(prefix string, delimiter ...string) []*tuple.Tuple2[string, T]
  • func (x *Trie[T]) QueryOrDefault(path string, defaultValue T) (value T, err error)
  • func (x *Trie[T]) Remove(path string) error
  • func (x *Trie[T]) RootTrieNode() *TrieNode[T]
  • func (x *Trie[T]) ToSlice(delimiter ...string) []*tuple.Tuple2[string, T]
  • func (x *Trie[T]) Upsert(path string, value T) error
• type TrieNode
  • func NewTrieNode[T any](key string, parent *TrieNode[T]) *TrieNode[T]
  • func (x *TrieNode[T]) BuildFullPath(delimiter ...string) string
  • func (x *TrieNode[T]) Remove()
  • func (x *TrieNode[T]) RemoveChild(key string)

Constants

const DefaultDelimiter = ""

Variables

var (
	ErrNotFound = errors.New("not found")
)

Functions

func DefaultPathSplitFunc

func DefaultPathSplitFunc(s string) ([]string, error)

Types

type PathSplitFunc

type PathSplitFunc func(s string) ([]string, error)

PathSplitFunc 用于把传入的路径字符串切割为字典中的一个项，默认是按照字符来切割，使用者可根据自己的需求自定义切割方式

type SyncTrie

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

func NewSync

func NewSync[T any](pathSplitFunc ...PathSplitFunc) *SyncTrie[T]

func (*SyncTrie[T]) Add

func (x *SyncTrie[T]) Add(path string, value T) error

Add 仅当不存在时插入到树上，已经存在的话则忽略

func (*SyncTrie[T]) Contains

func (x *SyncTrie[T]) Contains(path string) (bool, error)

func (*SyncTrie[T]) ExportToDotLanguage

func (x *SyncTrie[T]) ExportToDotLanguage() string

func (*SyncTrie[T]) FindTrieNode

func (x *SyncTrie[T]) FindTrieNode(path string) ([]string, *TrieNode[T], error)

FindTrieNode 寻找路径绑定的节点

func (*SyncTrie[T]) Query

func (x *SyncTrie[T]) Query(path string) (value T, err error)

Query 查询路径的值

func (*SyncTrie[T]) QueryByPrefix

func (x *SyncTrie[T]) QueryByPrefix(prefix string, delimiter ...string) []*tuple.Tuple2[string, T]

QueryByPrefix 根据前缀查询

func (*SyncTrie[T]) QueryOrDefault

func (x *SyncTrie[T]) QueryOrDefault(path string, defaultValue T) (value T, err error)

QueryOrDefault 查询给定的路径的负载，如果不存在的话则返回默认值

func (*SyncTrie[T]) Remove

func (x *SyncTrie[T]) Remove(path string) error

Remove 从树上移除给定路径

func (*SyncTrie[T]) ToSlice

func (x *SyncTrie[T]) ToSlice(delimiter ...string) []*tuple.Tuple2[string, T]

ToSlice 把字典树转为字典列表

func (*SyncTrie[T]) Upsert

func (x *SyncTrie[T]) Upsert(path string, value T) error

Upsert 如果树上已经存在则更新，不存在则插入

type Trie

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

func New

func New[T any](pathSplitFunc ...PathSplitFunc) *Trie[T]

func (*Trie[T]) Add

func (x *Trie[T]) Add(path string, value T) error

Add 仅当不存在时插入到树上，已经存在的话则忽略

func (*Trie[T]) Contains

func (x *Trie[T]) Contains(path string) (bool, error)

func (*Trie[T]) ExportToDotLanguage

func (x *Trie[T]) ExportToDotLanguage() string

func (*Trie[T]) FindTrieNode

func (x *Trie[T]) FindTrieNode(path string) ([]string, *TrieNode[T], error)

FindTrieNode 寻找路径绑定的节点

func (*Trie[T]) Query

func (x *Trie[T]) Query(path string) (value T, err error)

Query 查询路径的值

func (*Trie[T]) QueryByPrefix

func (x *Trie[T]) QueryByPrefix(prefix string, delimiter ...string) []*tuple.Tuple2[string, T]

QueryByPrefix 根据前缀查询

func (*Trie[T]) QueryOrDefault

func (x *Trie[T]) QueryOrDefault(path string, defaultValue T) (value T, err error)

QueryOrDefault 查询给定的路径的负载，如果不存在的话则返回默认值

func (*Trie[T]) Remove

func (x *Trie[T]) Remove(path string) error

Remove 从树上移除给定路径

func (*Trie[T]) RootTrieNode

func (x *Trie[T]) RootTrieNode() *TrieNode[T]

RootTrieNode 返回字典树的根节点

func (*Trie[T]) ToSlice

func (x *Trie[T]) ToSlice(delimiter ...string) []*tuple.Tuple2[string, T]

ToSlice 把字典树转为字典列表

func (*Trie[T]) Upsert

func (x *Trie[T]) Upsert(path string, value T) error

Upsert 如果树上已经存在则更新，不存在则插入

type TrieNode

type TrieNode[T any] struct {
	Parent   *TrieNode[T]
	Children map[string]*TrieNode[T]
	Exists   bool

	Key   string
	Value T
}

func NewTrieNode

func NewTrieNode[T any](key string, parent *TrieNode[T]) *TrieNode[T]

func (*TrieNode[T]) BuildFullPath

func (x *TrieNode[T]) BuildFullPath(delimiter ...string) string

func (*TrieNode[T]) Remove

func (x *TrieNode[T]) Remove()

func (*TrieNode[T]) RemoveChild

func (x *TrieNode[T]) RemoveChild(key string)