[elpa] externals/dict-tree 5cf96da 123/154: Implement iterator generators on collection data structures.

[Stefan Monnier]

branch: externals/dict-tree
commit 5cf96da28c4adc7cfdeb7bf15ff68826564734ed
Author: Toby S. Cubitt <toby-predictive@dr-qubit.org>
Commit: Toby S. Cubitt <toby-predictive@dr-qubit.org>

    Implement iterator generators on collection data structures.
---
 dict-tree.el | 234 +++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 218 insertions(+), 16 deletions(-)

diff --git a/dict-tree.el b/dict-tree.el
index 03e881d..7b91fea 100644
--- a/dict-tree.el
+++ b/dict-tree.el
@@ -267,6 +267,43 @@ If START or END is negative, it counts from the end."
         (setq b (cons (caar b) (dictree--cell-data (cdr b)))))
        (,rankfun a b))))
 
+;; return wrapped sortfun to ignore regexp grouping data
+(trie--if-lexical-binding
+    (defun dictree--wrap-regexp-sortfun (cmpfun &optional reverse)
+       (let ((sortfun (trie-construct-sortfun cmpfun reverse)))
+         (lambda (a b)
+           ;; if car of argument contains a key+group list rather than a
+           ;; straight key, remove group list
+           ;; FIXME: the test for straight key, below, will fail if the key
+           ;;        is a list, and the first element of the key is itself a
+           ;;        list (there might be no easy way to fully fix this...)
+           (if (or (atom (car a))
+                   (and (listp (car a)) (not (sequencep (caar a)))))
+               (setq a (car a))
+             (setq a (caar a)))
+           (if (or (atom (car b))
+                   (and (listp (car b)) (not (sequencep (caar b)))))
+               (setq b (car b))
+             (setq b (caar b)))
+           (funcall sortfun a b))))
+  (defun dictree--wrap-regexp-sortfun (cmpfun &optional reverse)
+    (let ((sortfun (trie-construct-sortfun cmpfun reverse)))
+      `(lambda (a b)
+        ;; if car of argument contains a key+group list rather than a
+        ;; straight key, remove group list
+        ;; FIXME: the test for straight key, below, will fail if the key
+        ;;        is a list, and the first element of the key is itself a
+        ;;        list (there might be no easy way to fully fix this...)
+        (if (or (atom (car a))
+                (and (listp (car a)) (not (sequencep (caar a)))))
+            (setq a (car a))
+          (setq a (caar a)))
+        (if (or (atom (car b))
+                (and (listp (car b)) (not (sequencep (caar b)))))
+            (setq b (car b))
+          (setq b (caar b)))
+        (,sortfun a b)))))
+
 
 ;; return wrapped rankfun to ignore fuzzy query distance data
 (trie--if-lexical-binding
@@ -280,6 +317,15 @@ If START or END is negative, it counts from the end."
        (,rankfun (cons (nth 0 (car a)) (dictree--cell-data (cdr a)))
                 (cons (nth 0 (car b)) (dictree--cell-data (cdr b)))))))
 
+;; return wrapped sortfun to ignore fuzzy query distance data
+(trie--if-lexical-binding
+    (defun dictree--wrap-fuzzy-sortfun (cmpfun &optional reverse)
+      (let ((sortfun (trie-construct-sortfun cmpfun reverse)))
+       (lambda (a b) (funcall sortfun (car a) (car b)))))
+  (defun dictree--wrap-fuzzy-sortfun (cmpfun &optional reverse)
+    (let ((sortfun (trie-construct-sortfun cmpfun reverse)))
+      `(lambda (a b) (,sortfun (car a) (car b))))))
+
 
 ;; return wrapped combfun to deal with data wrapping
 (trie--if-lexical-binding
@@ -430,8 +476,9 @@ If START or END is negative, it counts from the end."
                 (dictionary-list
                  &optional
                  filename
-                 (name (file-name-sans-extension
-                        (file-name-nondirectory filename)))
+                 (name (when filename
+                         (file-name-sans-extension
+                          (file-name-nondirectory filename))))
                  autosave
                  _unlisted
                  (combine-function #'+)
@@ -470,15 +517,13 @@ If START or END is negative, it counts from the end."
   ;; Return a list of all the tries on which DICT is based. If DICT is a
   ;; meta-dict, this recursively descends the hierarchy, gathering all
   ;; the tries from the base dictionaries.
-  (let (accumulate)
-    (dictree--do-trielist dict)
-    accumulate))
+  (dictree--do-trielist dict))
 
 (defun dictree--do-trielist (dict)
-  (declare (special accumulate))
   (if (dictree-meta-dict-p dict)
-      (mapc #'dictree--do-trielist (dictree--meta-dict-dictlist dict))
-    (setq accumulate (cons (dictree--trie dict) accumulate))))
+      (apply #'nconc (mapcar #'dictree--do-trielist
+                            (dictree--meta-dict-dictlist dict)))
+    (list (dictree--trie dict))))
 
 
 (defun dictree--merge (list1 list2 cmpfun &optional combfun maxnum)
@@ -1950,8 +1995,8 @@ Interactively, DICT is read from the mini-buffer."
                  &aux
                  (combfun (dictree--wrap-combfun
                            (dictree--meta-dict-combine-function dict)))
-                 (sortfun (trie-construct-sortfun
-                           (dictree-comparison-function dict)))
+                 (sortfun (dictree--wrap-regexp-sortfun
+                           (dictree-comparison-function dict) 'reverse))
                  (heap (heap-create
                         (dictree--construct-meta-stack-heapfun
                          sortfun reverse)
@@ -1969,7 +2014,7 @@ Interactively, DICT is read from the mini-buffer."
                  &aux
                  (combfun (dictree--wrap-combfun
                            (dictree--meta-dict-combine-function dict)))
-                 (sortfun (trie-construct-sortfun
+                 (sortfun (dictree--wrap-fuzzy-sortfun
                            (dictree-comparison-function dict)))
                  (heap (heap-create
                         (dictree--construct-meta-stack-heapfun
@@ -1988,7 +2033,7 @@ Interactively, DICT is read from the mini-buffer."
                  &aux
                  (combfun (dictree--wrap-combfun
                            (dictree--meta-dict-combine-function dict)))
-                 (sortfun (trie-construct-sortfun
+                 (sortfun (dictree--wrap-fuzzy-sortfun
                            (dictree-comparison-function dict)))
                  (heap (heap-create
                         (dictree--construct-meta-stack-heapfun
@@ -2056,10 +2101,10 @@ 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 DICT key. (If PREFIX is a string, it must be
 possible to apply `string' to individual elements of DICT 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.
+The returned keys will be sequences of the same type as
+PREFIX. 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 DICT *immediately* invalidates all
 dictree-stacks created before the modification (in particular,
@@ -2304,6 +2349,163 @@ Returns nil if the stack is empty."
 
 
 ;; ----------------------------------------------------------------
+;;                    dictree iterator generators
+
+;; dictree-stacks *are* iterators (with additional push and
+;; inspect-first-element operations). If we're running on a modern Emacs that
+;; includes the `generator' library, we can trivially define dictree iterator
+;; generators in terms of dictree-stacks.
+
+(heap--when-generators
+ (iter-defun dictree-iter (dict &optional type reverse)
+   "Return a dictree iterator object.
+
+Calling `iter-next' on this object will retrieve the next
+element (a cons cell containing a key and its associated data)
+from DICT in \"lexicographic\" order, i.e. the order defined by
+the DICT's comparison function, or in reverse order if REVERSE is
+non-nil.
+
+Optional argument TYPE (one of the symbols `vector', `list' or
+`string') sets the type of sequence used for the keys.
+
+Note that any modification to DICT *immediately* invalidates all
+iterators created from DICT before the modification (in
+particular, calling `iter-next' will give unpredictable
+results). If DICT is a meta-dict, this includes any modifications
+to its constituent dicts."
+   (let ((stack (dictree-stack dict type reverse)))
+     (while (not (dictree-stack-empty-p stack))
+       (iter-yield (dictree-stack-pop stack))))))
+
+
+(heap--when-generators
+ (iter-defun dictree-complete-iter (dict prefix &optional reverse)
+   "Return an iterator object for completions of PREFIX in DICT.
+
+Calling `iter-next' on this object will retrieve the next
+completion of PREFIX (a cons cell containing a key and its
+associated data) from DICT in \"lexicographic\" order, i.e. the
+order defined by DICT's comparison function, or in reverse order
+if REVERSE is non-nil.
+
+PREFIX must be a sequence (vector, list or string) that forms the
+initial part of a DICT key. (If PREFIX is a string, it must be
+possible to apply `string' to individual elements of DICT keys.)
+The returned keys will be sequences of the same type as
+PREFIX. 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 DICT *immediately* invalidates all
+iterators created from DICT before the modification (in
+particular, calling `iter-next' will give unpredictable
+results). If DICT is a meta-dict, this includes any modifications
+to its constituent dicts."
+   (let ((stack (dictree-complete-stack dict prefix reverse)))
+     (while (not (dictree-stack-empty-p stack))
+       (iter-yield (dictree-stack-pop stack))))))
+
+
+(heap--when-generators
+ (iter-defun dictree-regexp-iter (dict regexp &optional reverse)
+   "Return an iterator object for REGEXP matches in DICT.
+
+Calling `iter-next' on this object will retrieve the next match
+\(a cons cell containing a key and its associated data\) in
+\"lexicographic\" order, i.e. the order defined by DICT's
+comparison function, or in reverse order if REVERSE is non-nil.
+
+REGEXP is a regular expression, but it need not necessarily be a
+string. It must be a sequence (vector, list of string) whose
+elements are either elements of the same type as elements of the
+keys in DICT (which behave as literals in the regexp), or any of
+the usual regexp special characters and backslash constructs. If
+REGEXP is a string, it must be possible to apply `string' to
+individual elements of the keys stored in DICT. The matches
+returned in the alist will be sequences of the same type as KEY.
+
+Back-references and non-greedy postfix operators are *not*
+supported, and the matches are always anchored, so `$' and `^'
+lose their special meanings.
+
+If the regexp contains any non-shy grouping constructs, subgroup
+match data is included in the results. In this case, the car of
+each match is no longer just a key. Instead, it is a list whose
+first element is the matching key, and whose remaining elements
+are cons cells whose cars and cdrs give the start and end indices
+of the elements that matched the corresponding groups, in order.
+
+Note that any modification to DICT *immediately* invalidates all
+iterators created from DICT before the modification (in
+particular, calling `iter-next' will give unpredictable
+results). If DICT is a meta-dict, this includes any modifications
+to its constituent dicts."
+   (let ((stack (dictree-regexp-stack dict regexp reverse)))
+     (while (not (dictree-stack-empty-p stack))
+       (iter-yield (dictree-stack-pop stack))))))
+
+(heap--when-generators
+ (iter-defun dictree-fuzzy-match-iter (dict string distance &optional reverse)
+   "Return an iterator object for fuzzy matches to STRING in DICT.
+
+Calling `iter-next' on this object will retrieve the next match
+\(a cons cell containing a key and its associated data\) in
+\"lexicographic\" order, i.e. the order defined by DICT's
+comparison function, or in reverse order if REVERSE is non-nil.
+
+STRING must be a sequence (vector, list or string), and DISTANCE
+must be an integer. (If STRING is a string, it must be possible
+to apply `string' to individual elements of DICT keys.) The
+returned keys will be sequences of the same type as STRING that
+are within Lewenstein distance DISTANCE of STRING. If STRING is a
+list of sequences, keys withing DISTANCE of any 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 DICT *immediately* invalidates all
+iterators created from DICT before the modification (in
+particular, calling `iter-next' will give unpredictable
+results). If DICT is a meta-dict, this includes any modifications
+to its constituent dicts."
+   (let ((stack (dictree-fuzzy-match-stack dict string distance reverse)))
+     (while (not (dictree-stack-empty-p stack))
+       (iter-yield (dictree-stack-pop stack))))))
+
+
+(heap--when-generators
+ (iter-defun dictree-fuzzy-complete-iter (dict prefix distance &optional 
reverse)
+   "Return an iterator object for fuzzy completions of PREFIX in DICT.
+
+Calling `iter-next' on this object will retrieve the next fuzzy
+completion in \"lexicographic\" order, i.e. the order defined by
+DICT's comparison function, or in reverse order if REVERSE is
+non-nil. Each returned element has the form:
+
+    ((KEY . DIST) . DATA)
+
+PREFIX must be a sequence (vector, list or string), and DISTANCE
+must be an integer. (If PREFIX is a string, it must be possible
+to apply `string' to individual elements of DICT keys.) The
+returned keys will be sequences of the same type as STRING that
+are completions of prefixes within Lewenstein distance DISTANCE
+of PREFIX. If PREFIX is a list of sequences, completions within
+DISTANCE of any prefix in the list are included in the stack. All
+sequences in the list must be of the same type.
+
+Note that any modification to DICT *immediately* invalidates all
+iterators created from DICT before the modification (in
+particular, calling `iter-next' will give unpredictable
+results). If DICT is a meta-dict, this includes any modifications
+to its constituent dicts."
+   (let ((stack (dictree-fuzzy-complete-stack dict prefix distance reverse)))
+     (while (not (dictree-stack-empty-p stack))
+       (iter-yield (dictree-stack-pop stack))))))
+
+
+
+
+;; ----------------------------------------------------------------
 ;;             Functions for building advanced queries
 
 (defun dictree--query