trie.go RawHistoryFolder

1package vimkeys
2
3import "errors"
4
5// Node describes the trie state at the end of a walked sequence.
6type Node struct {
7	Action      string
8	Exact       bool
9	HasChildren bool
10}
11
12// ErrConflict is returned when inserting a duplicate binding.
13var ErrConflict = errors.New("vimkeys: duplicate binding")
14
15const maxCount = 9999
16
17type trieNode struct {
18	children  map[Key]*trieNode
19	action    string
20	hasAction bool
21}
22
23// Trie stores Vim key sequence bindings.
24type Trie struct {
25	root  *trieNode
26	depth int
27}
28
29// NewTrie creates an empty binding trie.
30func NewTrie() *Trie {
31	return &Trie{root: newTrieNode()}
32}
33
34func newTrieNode() *trieNode {
35	return &trieNode{children: make(map[Key]*trieNode)}
36}
37
38// Insert adds a binding for seq. Duplicate sequences return ErrConflict.
39// Nil or empty sequences return ErrEmptyBinding.
40func (t *Trie) Insert(seq Sequence, action string) error {
41	if len(seq) == 0 {
42		return ErrEmptyBinding
43	}
44	node := t.root
45	for _, key := range seq {
46		child, ok := node.children[key]
47		if !ok {
48			child = newTrieNode()
49			node.children[key] = child
50		}
51		node = child
52	}
53	if node.hasAction {
54		return ErrConflict
55	}
56	node.hasAction = true
57	node.action = action
58	if depth := len(seq); depth > t.depth {
59		t.depth = depth
60	}
61	return nil
62}
63
64// Walk reports the trie node reached by seq and whether the path exists.
65func (t *Trie) Walk(seq Sequence) (Node, bool) {
66	node := t.root
67	for _, key := range seq {
68		child, ok := node.children[key]
69		if !ok {
70			return Node{}, false
71		}
72		node = child
73	}
74	return Node{
75		Action:      node.action,
76		Exact:       node.hasAction,
77		HasChildren: len(node.children) > 0,
78	}, true
79}
80
81// MaxDepth returns the longest inserted sequence length.
82func (t *Trie) MaxDepth() int {
83	return t.depth
84}