branch: externals/trie
commit f930fe988df66eb83189d17a89f84847bff76abc
Author: Toby Cubitt <toby-predict...@dr-qubit.org>
Commit: tsc25 <toby-predict...@dr-qubit.org>
Documentation updates related to wildcard searches and predictive features
that make use of them
---
trie.el | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------
1 file changed, 67 insertions(+), 8 deletions(-)
diff --git a/trie.el b/trie.el
index 2879b1d..9189681 100644
--- a/trie.el
+++ b/trie.el
@@ -1365,12 +1365,13 @@ non-nil. Calling `trie-stack-pop' pops the top element
(a key and
its associated data) from the stack.
PREFIX must be a sequence (vector, list or string) that forms the
-initial part of a TRIE key. (If PREFIX is a string, it must be
-possible to apply `string' to individual elements of TRIE keys.)
-The completions returned in the alist will be sequences of the
-same type as KEY. If PREFIX is a list of sequences, completions
-of all sequences in the list are included in the stack. All
-sequences in the list must be of the same type.
+initial part of a TRIE key, or a list of such sequences. (If
+PREFIX is a string, it must be possible to apply `string' to
+individual elements of TRIE keys.) The completions returned in
+the alist will be sequences of the same type as KEY. If PREFIX is
+a list of sequences, completions of all sequences in the list are
+included in the stack. All sequences in the list must be of the
+same type.
Note that any modification to TRIE *immediately* invalidates all
trie-stacks created before the modification (in particular,
@@ -1527,7 +1528,7 @@ syntax:
Matches zero or more characters.
? wildcard
- Matches a single character.
+ Matches any single character.
[...] character alternative
Matches any of the listed characters.
@@ -1754,7 +1755,65 @@ wildcards can be very slow indeed."
(defun trie-wildcard-stack (trie pattern &optional reverse)
- "blah"
+ "Return an object that allows matches to PATTERN to be accessed
+as if they were a stack.
+
+The stack is sorted in \"lexical\" order, i.e. the order defined
+by TRIE's comparison function, or in reverse order if REVERSE is
+non-nil. Calling `trie-stack-pop' pops the top element (a key and
+its associated data) from the stack.
+
+PATTERN must be a sequence (vector, list or string) containing
+either elements of the type used to reference data in the trie,
+or any the characters `*', `?', `[', `]', `^' or `\\'. The
+meaning and syntax of these special characters follows shell-glob
+syntax, with one major restriction on the `*' wildcard:
+
+ * wildcard
+ Matches zero or more characters. May *only* appear at the end
+ of the pattern.
+
+ ? wildcard
+ Matches any single character.
+
+ [...] character alternative
+ Matches any of the listed characters.
+
+ [^...] negated character alternative
+ Matches any character *other* then those listed.
+
+ []..] character alternative including `]'
+ Matches any of the listed characters, including `]'.
+
+ \\ quote literal
+ Causes the next element of the pattern sequence to be treated
+ literally; special characters lose their special meaning, for
+ anything else it has no effect.
+
+To include a `]' in a character alternative, place it immediately
+after the opening `['. To include a literal `\\', quote it with
+another `\\' (remember that `\\' also has to be quoted within
+elisp strings, so as a string this would be \"\\\\\\\\\"). The
+above syntax descriptions are written in terms of strings, but
+the special characters can be used in *any* sequence
+type. E.g. the character alternative \"[abc]\" would be \(?[ ?a
+?b ?c ?]\) as a list, or [?[ ?a ?b ?c ?]] as a vector. The
+\"characters\" in the alternative can of course be any data type
+that might be stored in the trie, not just actual characters.
+
+If PATTERN is a string, it must be possible to apply `string' to
+individual elements of the sequences stored in the trie. The
+matches returned in the alist will be sequences of the same type
+as KEY.
+
+
+Efficiency concerns:
+
+Wildcard searches on tries are very efficient compared to similar
+searches on other data structures. Due to the restrictions on the
+`*' wildcard, there is no significant difference between the
+efficiency of all legitimate patterns."
+
;; convert trie from print-form if necessary
(trie-transform-from-read-warn trie)
;; if stack functions aren't defined for trie type, throw error
