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:
- Chi Team (https://github.com/go-chi/chi/blob/master/tree.go)
- Armon Dadgar (https://github.com/armon/go-radix/blob/master/radix.go)
- Ben Hoyt (https://benhoyt.com/writings/go-routing/)
- 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:
team Arm
team {name}
The following query using Get(...)
function will:
team Arm
– getsteam Arm
payloadteam arm
– getsteam {name}
payloadteam Leg
– getsteam {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:
team {name}
– accepted when first Insertteam {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:
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:
- The payload is returned as given.
- The placeholder-value map returns a list of mapped placeholder-value.
- The search verdict will be
true
.
In the event of a failed search:
- The payload is
nil
. - The placeholder-value map returns a created map with empty list.
- 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:
- the payload is returned as given.
- the search verdict will be
true
.
In the event of a failed match:
- the payload is
nil
. - the search verdict will be
false
.