Package radixtrie

import "gitlab.com/zoralab/cerigo/algo/radixtrie"

Package radixtrie is the data structure algorithm optimized for fast lookup.

The radix trie is a representation of a space-optimized trie where each descendant nodes are chunks of bytes instead of a character. Every edge nodes has a payload that is deliverable to a query.

This package included concurrent application. Each public API has mutex locking to avoid data race conditions. It is available on Cerigo starting from version v0.0.3.

Special thanks to the following knowledge contributors:

  1. Chi Team (https://github.com/go-chi/chi/blob/master/tree.go)
  2. Armon Dadgar (https://github.com/armon/go-radix/blob/master/radix.go)
  3. Ben Hoyt (https://benhoyt.com/writings/go-routing/)
  4. Jay Ching (https://github.com/imjching) - algorithm optimization

Placeholder Supported

This radixtrie algorithm accepts placeholder patterns using {} braces. It will runs through all non-placeholder nodes before using placeholder one. Example, for a trie that has:

  1. team Arm
  2. team {name}

The following query using Get(...) function will:

  1. team Arm – gets team Arm payload
  2. team arm – gets team {name} payload
  3. team Leg – gets team {name} payload

Limitations

There are a number of limitations you need to pay attention to when using radixtrie package.

1. Use Get(...) for Placeholder Query

Get(...) function is designed to query with placeholder. Other query functions like Match(...) are meant for their dedicated query methods like faster non-placeholder query.

2. No Multiple Placeholders for A Character Index

2 placeholders shall not exist at the same character index. In another word, the following will not work:

  1. team {name} – accepted when first Insert
  2. team {tag} – error when Insert (ErrorPlaceholderExists)

3. No Neighboring Placeholders

2 placeholders shall not be next to each other. This is mainly because there is no intuitive way to know which character belongs to which one. In another word, this will not work:

  1. team {name}{tag} – error when Insert (ErrorTailingPlaceholder)

4. Searching for Use Cases for Delete

As of to-date, our studies found out that it is better to discard and rebuild the Trie for delete function. The reason being having a proper synchonization with your list of insertion codes instead of cherry-picking an existing running ones and creates potential mutation.

However, we are still open for delete function and seeking for more of its use cases for development considerations. Feel free to raise an issue in our Gitlab pages at: https://gitlab.com/zoralab/cerigo/-/issues

Constants

Error messages are the consistent message used to create error object.

const (
	ErrorBadPayload         = "given payload is empty"

	ErrorEmptyID            = "given ID tag is empty"

	ErrorNodeExists         = "node already exists and update is disallowed"

	ErrorPlaceholderExists  = "placeholder already exists"

	ErrorBrokenPlaceholder  = "broken placeholder without closure"

	ErrorTailingPlaceholder = "tailing placeholder over existing one"
)

Trie

type Trie struct {
	Name string
	// contains filtered or unexported fields
}

Trie is the structure of the redux tree search algorithm.

It has important fields requiring initialization. Hence, use New() function to create one instead of the conventional &struct{} method.

Func New() *Trie

New is to create a new Trie object safely with initialized hidden fields.

Upon creation, the default value for Name is root. You may change its name accordingly. This is useful for identification and Map(...) labeling purposes.

Func (t *Trie) Get(id string) (payload interface{}, placeholderMap map[string]string, ok bool)

Get is to query the payload based on given ID using placeholder feature.

This function returns payload, non-nil placeholder-value map, and boolean search verdict.

In the event of a successful search:

  1. The payload is returned as given.
  2. The placeholder-value map returns a list of mapped placeholder-value.
  3. The search verdict will be true.

In the event of a failed search:

  1. The payload is nil.
  2. The placeholder-value map returns a created map with empty list.
  3. The search verdict will be false.

Func (t *Trie) Insert(id string, payload interface{}, update bool) error

Insert is to insert a node into the tree.

You MUST supply valid ID and payload and they shall not be empty or nil. In the case of updating a node, you need to supply update as true in order to update the node’s payload with the given one.

Func (t *Trie) Map() string

Map is to printout existing Trie mapping.

This is for visualizing the current Trie nodes. They are properly indicated to show the edge nodes (endpoint). Every endpoints has a payload.

Func (t *Trie) Match(id string) (payload interface{}, ok bool)

Match is to query the payload based on given ID without using placeholder.

This functon assumes the Trie is completely inserted without ANY placeholder. The algorithm uses a simpler version for getting the payload for simple Trie.

In the event of a successful match:

  1. the payload is returned as given.
  2. the search verdict will be true.

In the event of a failed match:

  1. the payload is nil.
  2. the search verdict will be false.