[elpa] externals/trie a1f9faa 044/111: Re-filled to 72 chars/line, for mailing to gnu-emacs-sources list

[Stefan Monnier]

branch: externals/trie
commit a1f9faa2c1e667788750178cf78458d3869aaa2d
Author: Toby Cubitt <toby-predictive@dr-qubit.org>
Commit: tsc25 <toby-predictive@dr-qubit.org>

    Re-filled to 72 chars/line, for mailing to gnu-emacs-sources list
---
 trie.el | 395 ++++++++++++++++++++++++++++++++++++----------------------------
 1 file changed, 224 insertions(+), 171 deletions(-)

diff --git a/trie.el b/trie.el
index b4c8c76..e2b557f 100644
--- a/trie.el
+++ b/trie.el
@@ -32,17 +32,16 @@
 ;;
 ;; Quick Overview
 ;; --------------
-
 ;; A trie is a data structure used to store keys that are ordered
-;; sequences of elements (vectors, lists or strings in Elisp; strings are
-;; by far the most common), in such a way that both storage and retrieval
-;; are space- and time-efficient. But, more importantly, a variety of
-;; more advanced queries can also be performed efficiently: for example,
-;; returning all strings with a given prefix, searching for keys matching
-;; a given wildcard pattern or regular expression, or searching for all
-;; keys that match any of the above to within a given Lewenstein distance
-;; (though this last is not yet implemented in this package - code
-;; contributions welcome!).
+;; sequences of elements (vectors, lists or strings in Elisp; strings
+;; are by far the most common), in such a way that both storage and
+;; retrieval are space- and time-efficient. But, more importantly, a
+;; variety of more advanced queries can also be performed efficiently:
+;; for example, returning all strings with a given prefix, searching for
+;; keys matching a given wildcard pattern or regular expression, or
+;; searching for all keys that match any of the above to within a given
+;; Lewenstein distance (though this last is not yet implemented in this
+;; package - code contributions welcome!).
 ;;
 ;; You create a ternary search tree using `trie-create', create an
 ;; association using `trie-insert', retrieve an association using
@@ -58,11 +57,11 @@
 ;; create "lexically-ordered" stacks of query results.
 ;;
 ;; Note that there are two uses for a trie: as a lookup table, in which
-;; case only the presence or absence of a key in the trie is significant,
-;; or as an associative array, in which case each key carries some
-;; associated data. Libraries for other data structure often only
-;; implement lookup tables, leaving it up to you to implement an
-;; associative array on top of this (by storing key+data pairs in the
+;; case only the presence or absence of a key in the trie is
+;; significant, or as an associative array, in which case each key
+;; carries some associated data. Libraries for other data structure
+;; often only implement lookup tables, leaving it up to you to implement
+;; an associative array on top of this (by storing key+data pairs in the
 ;; data structure's keys, then defining a comparison function that only
 ;; compares the key part). For a trie, however, the underlying data
 ;; structures naturally support associative arrays at no extra cost, so
@@ -72,39 +71,38 @@
 ;;
 ;; Different Types of Trie
 ;; -----------------------
-
 ;; There are numerous ways to implement trie data structures internally,
 ;; each with its own time and space trade-offs. By viewing a trie as a
 ;; tree whose nodes are themselves lookup tables for key elements, this
-;; package is able to support all types of trie in a uniform manner. This
-;; relies on there existing (or you writing!) an Elisp implementation of
-;; the corresponding type of lookup table. The best type of trie to use
-;; will depend on what trade-offs are appropriate for your particular
-;; application. The following gives an overview of the advantages and
-;; disadvantages of various types of trie. (Not all of the underlying
-;; lookup tables have been implemented in Elisp yet, so using some of the
-;; trie types described below would require writing the missing Elisp
-;; package!)
+;; package is able to support all types of trie in a uniform
+;; manner. This relies on there existing (or you writing!) an Elisp
+;; implementation of the corresponding type of lookup table. The best
+;; type of trie to use will depend on what trade-offs are appropriate
+;; for your particular application. The following gives an overview of
+;; the advantages and disadvantages of various types of trie. (Not all
+;; of the underlying lookup tables have been implemented in Elisp yet,
+;; so using some of the trie types described below would require writing
+;; the missing Elisp package!)
 ;;
 ;;
 ;; One of the most effective all-round implementations of a trie is a
-;; ternary search tree, which can be viewed as a tree of binary trees. If
-;; basic binary search trees are used for the nodes of the trie, we get a
-;; standard ternary search tree. If self-balancing binary trees are used
-;; (e.g. AVL or red-black trees), we get a self-balancing ternary search
-;; tree. If splay trees are used, we get yet another self-organising
-;; variant of a ternary search tree. All ternary search trees have, in
-;; common, good space-efficiency. The time-efficiency of the various trie
-;; operations is also good, assuming the underlying binary trees are
-;; balanced. Under that assumption, all variants of ternary search trees
-;; described below have the same asymptotic time-complexity for all trie
-;; operations.
+;; ternary search tree, which can be viewed as a tree of binary
+;; trees. If basic binary search trees are used for the nodes of the
+;; trie, we get a standard ternary search tree. If self-balancing binary
+;; trees are used (e.g. AVL or red-black trees), we get a self-balancing
+;; ternary search tree. If splay trees are used, we get yet another
+;; self-organising variant of a ternary search tree. All ternary search
+;; trees have, in common, good space-efficiency. The time-efficiency of
+;; the various trie operations is also good, assuming the underlying
+;; binary trees are balanced. Under that assumption, all variants of
+;; ternary search trees described below have the same asymptotic
+;; time-complexity for all trie operations.
 ;;
 ;; Self-balancing trees ensure the underlying binary trees are always
 ;; close to perfectly balanced, with the usual trade-offs between the
 ;; different the types of self-balancing binary tree: AVL trees are
-;; slightly more efficient for lookup operations than red-black trees, at
-;; a cost of slightly less efficienct insertion operations, and less
+;; slightly more efficient for lookup operations than red-black trees,
+;; at a cost of slightly less efficienct insertion operations, and less
 ;; efficient deletion operations. Splay trees give good average-case
 ;; complexity and are simpler to implement than AVL or red-black trees
 ;; (which can mean they're faster in practice!), at the expense of poor
@@ -112,8 +110,8 @@
 ;;
 ;; If your tries are going to be static (i.e. created once and rarely
 ;; modified), then using perfectly balanced binary search trees might be
-;; appropriate. Perfectly balancing the binary trees is very inefficient,
-;; but it only has to be when the trie is first created or
+;; appropriate. Perfectly balancing the binary trees is very
+;; inefficient, but it only has to be when the trie is first created or
 ;; modified. Lookup operations will then be as efficient as possible for
 ;; ternary search trees, and the implementation will also be simpler (so
 ;; probably faster) than a self-balancing tree, without the space and
@@ -122,8 +120,8 @@
 ;; On the other hand, adding data to a binary search tree in a random
 ;; order usually results in a reasonably balanced tree. If this is the
 ;; likely scenario, using a basic binary tree without bothering to
-;; balance it at all might be quite efficient, and, being even simpler to
-;; implement, could be quite fast overall.
+;; balance it at all might be quite efficient, and, being even simpler
+;; to implement, could be quite fast overall.
 ;;
 ;;
 ;; A digital trie is a different implementation of a trie, which can be
@@ -143,24 +141,24 @@
 ;; for your specific needs.
 ;;
 ;;
-;; This package uses the AVL tree package avl-tree.el and the heap
-;; package heap.el.
+;; This package uses the AVL tree package avl-tree.el, the tagged NFA
+;; package tNFA.el, and the heap package heap.el.
 
 
 ;;; Change Log:
 ;;
 ;; Version 0.2
-;; * Replaced wildcard searches with regexp searches, using the tNFA.el tagged
-;;   non-deterministic finite state automata library. This is both more
-;;   general *and* more efficient.
+;; * Replaced wildcard searches with regexp searches, using the tNFA.el
+;;   tagged non-deterministic finite state automata library. This is
+;;   both more general *and* more efficient.
 ;; * Bug fix in `trie--do-regexp-search'
 ;;
 ;; Version 0.1
 ;; * Initial release (complete rewrite from scratch of tstree.el!)
-;; * Ternary search trees are now implemented as a tree of avl trees, which
-;;   has numerous advantages: self-balancing trees guarantee O(log n)
-;;   complexity regardless of how the tree is built; deletion is now done
-;;   properly.
+;; * Ternary search trees are now implemented as a tree of avl trees,
+;;   which has numerous advantages: self-balancing trees guarantee
+;;   O(log n) complexity regardless of how the tree is built; deletion
+;;   is now done properly.
 ;; * unlike tstree.el, trie.el is general enough to implement all sorts
 ;;   of tries, not just ternary search trees (though these remain the
 ;;   default).
@@ -172,10 +170,10 @@
 ;;   lexical or arbitrary order, the ranking function being passed as an
 ;;   optional argument in the latter case. And functions can no longer
 ;;   operate over multiple data structures at once; i.e. they no longer
-;;   accept lists of trees as arguments. (These features belong in higher
-;;   level libraries, and the efficiency loss is negligible.)
-;; * `trie-wildcard-search' implements efficient shell-glob-like wildcard
-;;   searches of tries!
+;;   accept lists of trees as arguments. (These features belong in
+;;   higher level libraries, and the efficiency loss is negligible.)
+;; * `trie-wildcard-search' implements efficient shell-glob-like
+;;   wildcard searches of tries!
 
 
 
@@ -192,7 +190,8 @@
 ;;;                   Pre-defined trie types
 
 ;; --- avl-tree ---
-(put 'avl :trie-createfun (lambda (cmpfun seq) (avl-tree-create cmpfun)))
+(put 'avl :trie-createfun
+     (lambda (cmpfun seq) (avl-tree-create cmpfun)))
 (put 'avl :trie-insertfun 'avl-tree-enter)
 (put 'avl :trie-deletefun 'avl-tree-delete)
 (put 'avl :trie-lookupfun 'avl-tree-member)
@@ -224,37 +223,48 @@
                  &aux
                  (createfun
                   (or (get type :trie-createfun)
-                      (error "trie--create: unknown trie TYPE, %s" type)))
+                      (error "trie--create:\
+ unknown trie TYPE, %s" type)))
                  (insertfun
                   (or (get type :trie-insertfun)
-                      (error "trie--create: unknown trie TYPE, %s" type)))
+                      (error "trie--create:\
+ unknown trie TYPE, %s" type)))
                  (deletefun
                   (or (get type :trie-deletefun)
-                      (error "trie--create: unknown trie TYPE, %s" type)))
+                      (error "trie--create:\
+ unknown trie TYPE, %s" type)))
                  (lookupfun
                   (or (get type :trie-lookupfun)
-                      (error "trie--create: unknown trie TYPE, %s" type)))
+                      (error "trie--create:\
+ unknown trie TYPE, %s" type)))
                  (mapfun
                   (or (get type :trie-mapfun)
-                      (error "trie--create: unknown trie TYPE, %s" type)))
+                      (error "trie--create:\
+ unknown trie TYPE, %s" type)))
                  (emptyfun
                   (or (get type :trie-emptyfun)
-                      (error "trie--create: unknown trie TYPE, %s" type)))
+                      (error "trie--create:\
+ unknown trie TYPE, %s" type)))
                  (stack-createfun
                   (or (get type :trie-stack-createfun)
-                      (error "trie--create: unknown trie TYPE, %s" type)))
+                      (error "trie--create:\
+ unknown trie TYPE, %s" type)))
                  (stack-popfun
                   (or (get type :trie-stack-popfun)
-                      (error "trie--create: unknown trie TYPE, %s" type)))
+                      (error "trie--create:\
+ unknown trie TYPE, %s" type)))
                  (stack-emptyfun
                   (or (get type :trie-stack-emptyfun)
-                      (error "trie--create: unknown trie TYPE, %s" type)))
+                      (error "trie--create:\
+ unknown trie TYPE, %s" type)))
                  (transform-for-print
                   (or (get type :trie-transform-for-print)
-                      (error "trie--create: unknown trie TYPE, %s" type)))
+                      (error "trie--create:\
+ unknown trie TYPE, %s" type)))
                  (transform-from-read
                   (or (get type :trie-transform-from-read)
-                      (error "trie--create: unknown trie TYPE, %s" type)))
+                      (error "trie--create:\
+ unknown trie TYPE, %s" type)))
                  (cmpfun (trie--wrap-cmpfun comparison-function))
                  (root (trie--node-create-root createfun cmpfun))
                  ))
@@ -335,15 +345,16 @@
   `(eq (trie--node-split ,node) trie--terminator))
 
 (defmacro trie--node-p (node)
-  ;; Return t if NODE is a TRIE trie--node, nil otherwise.
-  ;; Have to define this ourselves, because we created a defstruct without any
-  ;; identifying tags (i.e. (:type vector)) for efficiency, but this means we
-  ;; can only perform a rudimentary and very unreliable test.
+  ;; Return t if NODE is a TRIE trie--node, nil otherwise.  Have to
+  ;; define this ourselves, because we created a defstruct without any
+  ;; identifying tags (i.e. (:type vector)) for efficiency, but this
+  ;; means we can only perform a rudimentary and very unreliable test.
   `(and (vectorp ,node) (= (length ,node) 2)))
 
 
 (defun trie--node-find (node seq lookupfun)
-  ;; Returns the node below NODE corresponding to SEQ, or nil if none found.
+  ;; Returns the node below NODE corresponding to SEQ, or nil if none
+  ;; found.
   (let ((len (length seq))
        (i -1))
     ;; descend trie until we find SEQ or run out of trie
@@ -357,8 +368,8 @@
 
 
 (defmacro trie--find-data-node (node lookupfun)
-  ;; Return data node from NODE's subtree, or nil if NODE has no data node in
-  ;; its subtree.
+  ;; Return data node from NODE's subtree, or nil if NODE has no data
+  ;; node in its subtree.
   `(funcall ,lookupfun
            (trie--node-subtree ,node)
            (trie--node-create-dummy trie--terminator)
@@ -366,8 +377,8 @@
 
 
 (defmacro trie--find-data (node lookupfun)
-  ;; Return data associated with sequence corresponding to NODE, or nil if
-  ;; sequence has no associated data.
+  ;; Return data associated with sequence corresponding to NODE, or nil
+  ;; if sequence has no associated data.
   `(let ((node (trie--find-data-node ,node ,lookupfun)))
      (when node (trie--node-data node))))
 
@@ -602,7 +613,8 @@ original usable form.
 
 
 Warning: to avoid nasty dynamic scoping bugs, the supplied
-functions must *never* bind any variables with names commencing \"--\".")
+functions must *never* bind any variables with names commencing
+\"--\".")
 
 
 
@@ -617,7 +629,8 @@ functions must *never* bind any variables with names 
commencing \"--\".")
 (defun trie-empty (trie)
   "Return t if the TRIE is empty, nil otherwise."
   (trie-transform-from-read-warn trie)
-  (funcall (trie--emptyfun trie) (trie--node-subtree (trie--root trie))))
+  (funcall (trie--emptyfun trie)
+          (trie--node-subtree (trie--root trie))))
 
 
 (defun trie-construct-sortfun (cmpfun &optional reverse)
@@ -629,15 +642,19 @@ reversed if REVERSE is non-nil."
         (let (cmp)
           (catch 'compared
             (dotimes (i (min (length a) (length b)))
-              (cond ((,cmpfun (elt b i) (elt a i)) (throw 'compared t))
-                    ((,cmpfun (elt a i) (elt b i)) (throw 'compared nil))))
+              (cond ((,cmpfun (elt b i) (elt a i))
+                     (throw 'compared t))
+                    ((,cmpfun (elt a i) (elt b i))
+                     (throw 'compared nil))))
             (< (length a) (length b)))))
     `(lambda (a b)
        (let (cmp)
         (catch 'compared
           (dotimes (i (min (length a) (length b)))
-            (cond ((,cmpfun (elt a i) (elt b i)) (throw 'compared t))
-                  ((,cmpfun (elt b i) (elt a i)) (throw 'compared nil))))
+            (cond ((,cmpfun (elt a i) (elt b i))
+                   (throw 'compared t))
+                  ((,cmpfun (elt b i) (elt a i))
+                   (throw 'compared nil))))
           (< (length a) (length b)))))))
 
 
@@ -686,8 +703,8 @@ bind any variables with names commencing \"--\"."
     (setq node (funcall (trie--insertfun trie)
                        (trie--node-subtree node)
                        (trie--node-create-data data)
-                       ;; if using existing data node, wrap UPDATEFUN if
-                       ;; any was supplied
+                       ;; if using existing data node, wrap UPDATEFUN
+                       ;; if any was supplied
                        (when (and --trie-insert--old-node-flag
                                   --trie-insert--updatefun)
                          (lambda (new old)
@@ -736,20 +753,22 @@ any variables with names commencing \"--\"."
                             --trie--do-delete--deletefun
                             --trie--do-delete--emptyfun
                             --trie--do-delete--cmpfun)
-  ;; Delete --TRIE--DO-DELETE--SEQ starting from trie node NODE, and return
-  ;; non-nil if we deleted a node. If --TRIE--DO-DELETE--TEST is supplied, it
-  ;; is called with two arguments, the key being deleted and the associated
-  ;; data, and the deletion is only carried out if it returns non-nil.
+  ;; Delete --TRIE--DO-DELETE--SEQ starting from trie node NODE, and
+  ;; return non-nil if we deleted a node. If --TRIE--DO-DELETE--TEST is
+  ;; supplied, it is called with two arguments, the key being deleted
+  ;; and the associated data, and the deletion is only carried out if it
+  ;; returns non-nil.
 
   ;; The absurd argument names are to lessen the likelihood of dynamical
-  ;; scoping bugs caused by a supplied function binding a variable with the
-  ;; same name as one of the arguments, which would cause a nasty bug when the
-  ;; lambda's (below) are called.
+  ;; scoping bugs caused by a supplied function binding a variable with
+  ;; the same name as one of the arguments, which would cause a nasty
+  ;; bug when the lambda's (below) are called.
   (declare (special --trie-deleted--node)
           (special --trie-delete--key))
-  ;; if --TRIE--DO-DELETE--SEQ is empty, try to delete data node and return
-  ;; non-nil if we did (return value of --TRIE--DO-DELETE--DELETEFUN is the
-  ;; deleted data, which is always non-nil for a trie)
+  ;; if --TRIE--DO-DELETE--SEQ is empty, try to delete data node and
+  ;; return non-nil if we did (return value of
+  ;; --TRIE--DO-DELETE--DELETEFUN is the deleted data, which is always
+  ;; non-nil for a trie)
   (if (= (length --trie--do-delete--seq) 0)
       (setq --trie-deleted--node
            (funcall --trie--do-delete--deletefun
@@ -760,8 +779,9 @@ any variables with names commencing \"--\"."
                         (funcall --trie--do-delete--test
                                  --trie-delete--key (trie--node-data n))))
                     nil))
-    ;; otherwise, delete on down (return value of --TRIE--DO-DELETE--DELETEFUN
-    ;; is the deleted data, which is always non-nil for a trie)
+    ;; otherwise, delete on down (return value of
+    ;; --TRIE--DO-DELETE--DELETEFUN is the deleted data, which is always
+    ;; non-nil for a trie)
     (funcall --trie--do-delete--deletefun
             (trie--node-subtree node)
             (trie--node-create-dummy (elt --trie--do-delete--seq 0))
@@ -791,7 +811,8 @@ to be distinguished from an element with a null 
association. (See
 also `trie-member-p', which does this for you.)"
   ;; convert trie from print-form if necessary
   (trie-transform-from-read-warn trie)
-  ;; find node corresponding to key, then find data node, then return data
+  ;; find node corresponding to key, then find data node, then return
+  ;; data
   (let (node)
     (or (and (setq node (trie--node-find (trie--root trie) key
                                         (trie--lookupfun trie)))
@@ -819,24 +840,29 @@ also `trie-member-p', which does this for you.)"
                   &optional --trie--mapc--reverse)
   ;; Apply TRIE--MAPC--FUNCTION to all elements in a trie beneath
   ;; TRIE--MAPC--ROOT, which should correspond to the sequence
-  ;; TRIE--MAPC--SEQ. TRIE--MAPC--FUNCTION is passed two arguments: the trie
-  ;; node itself and the sequence it corresponds to. It is applied in
-  ;; ascending order, or descending order if TRIE--MAPC--REVERSE is non-nil.
+  ;; TRIE--MAPC--SEQ. TRIE--MAPC--FUNCTION is passed two arguments: the
+  ;; trie node itself and the sequence it corresponds to. It is applied
+  ;; in ascending order, or descending order if TRIE--MAPC--REVERSE is
+  ;; non-nil.
 
   ;; The absurd argument names are to lessen the likelihood of dynamical
-  ;; scoping bugs caused by a supplied function binding a variable with the
-  ;; same name as one of the arguments.
+  ;; scoping bugs caused by a supplied function binding a variable with
+  ;; the same name as one of the arguments.
   (funcall
    --trie--mapc--mapfun
    (lambda (--trie--mapc--node)
      ;; data node: apply function
      (if (trie--node-data-p --trie--mapc--node)
-        (funcall --trie--mapc--function --trie--mapc--node --trie--mapc--seq)
+        (funcall --trie--mapc--function
+                 --trie--mapc--node
+                 --trie--mapc--seq)
        ;; internal node: append split value to seq and keep descending
-       (trie--mapc --trie--mapc--function --trie--mapc--mapfun
+       (trie--mapc --trie--mapc--function
+                  --trie--mapc--mapfun
                   --trie--mapc--node
-                  (trie--seq-append (copy-sequence --trie--mapc--seq)
-                                    (trie--node-split --trie--mapc--node))
+                  (trie--seq-append
+                   (copy-sequence --trie--mapc--seq)
+                   (trie--node-split --trie--mapc--node))
                   --trie--mapc--reverse)))
    ;; --TRIE--MAPC--MAPFUN target
    (trie--node-subtree --trie--mapc--root)
@@ -873,8 +899,9 @@ vector."
        --trie--mapc-internal--function
        --trie--mapc-internal--mapfun
        --trie--mapc-internal--node
-       (trie--seq-append (copy-sequence --trie--mapc-internal--seq)
-                         (trie--node-split --trie--mapc-internal--node)))))
+       (trie--seq-append
+        (copy-sequence --trie--mapc-internal--seq)
+        (trie--node-split --trie--mapc-internal--node)))))
    (trie--node-subtree --trie--mapc-internal--root)))
 
 
@@ -897,7 +924,7 @@ bind any variables with names commencing \"--\"."
   ;; convert from print-form if necessary
   (trie-transform-from-read-warn trie)
   ;; map FUNCTION over TRIE
-  (let ((--trie-map--function function)) ; try to avoid dynamic scoping bugs
+  (let ((--trie-map--function function)) ; avoid dynamic scoping bugs
     (trie--mapc
      (lambda (node seq)
        (setf (trie--node-data node)
@@ -926,7 +953,7 @@ bind any variables with names commencing \"--\"."
   ;; convert from print-form if necessary
   (trie-transform-from-read-warn trie)
   ;; map FUNCTION over TRIE
-  (let ((--trie-mapc--function function)) ; try to avoid dynamic scoping bugs
+  (let ((--trie-mapc--function function)) ; avoid dynamic scoping bugs
     (trie--mapc
      (lambda (node seq)
        (funcall --trie-mapc--function seq (trie--node-data node)))
@@ -958,7 +985,7 @@ commencing \"--\"."
   ;; convert from print-form if necessary
   (trie-transform-from-read-warn trie)
   ;; map FUNCTION over TRIE, combining results with COMBINATOR
-  (let ((--trie-mapf--function function) ; try to avoid dynamic scoping bugs
+  (let ((--trie-mapf--function function) ; avoid dynamic scoping bugs
        --trie-mapf--accumulate)
     (trie--mapc
      (lambda (node seq)
@@ -975,7 +1002,8 @@ commencing \"--\"."
 
 
 (defun trie-mapcar (function trie &optional type reverse)
-  "Apply FUNCTION to all elements in TRIE, and make a list of the results.
+  "Apply FUNCTION to all elements in TRIE,
+and make a list of the results.
 
 FUNCTION should take two arguments: a sequence stored in the trie
 and its associated data.
@@ -1031,9 +1059,10 @@ bind any variables with names commencing \"--\"."
                         (cond ((eq type 'list) ())
                               ((eq type 'string) "")
                               (t []))
-                        (funcall stack-createfun
-                                 (trie--node-subtree (trie--root trie))
-                                 reverse)))
+                        (funcall
+                         stack-createfun
+                         (trie--node-subtree (trie--root trie))
+                         reverse)))
                  reverse
                  comparison-function lookupfun
                  stack-createfun stack-popfun stack-emptyfun)))
@@ -1078,7 +1107,7 @@ bind any variables with names commencing \"--\"."
 
 
 (defun trie-stack (trie &optional type reverse)
-  "Return an object that allows TRIE to be accessed as if it were a stack.
+  "Return an object that allows TRIE to be accessed as a stack.
 
 The stack is sorted in \"lexical\" order, i.e. the order defined
 by the trie's comparison function, or in reverse order if REVERSE
@@ -1148,7 +1177,8 @@ element stored in the trie.)"
   ;; return nilflag if stack is empty
   (if (trie-stack-empty-p trie-stack)
       nilflag
-    ;; if elements have been pushed onto the stack, return first of those
+    ;; if elements have been pushed onto the stack, return first of
+    ;; those
     (if (trie--stack-pushed trie-stack)
        (car (trie--stack-pushed trie-stack))
       ;; otherwise, return first element from trie-stack
@@ -1165,11 +1195,11 @@ element stored in the trie.)"
        (null (trie--stack-pushed trie-stack))))
 
 
-(defun trie--stack-repopulate (store reverse
-                              comparison-function lookupfun
-                              stack-createfun stack-popfun stack-emptyfun)
-  ;; Recursively push children of the node at the head of STORE onto the front
-  ;; of STORE, until a data node is reached.
+(defun trie--stack-repopulate
+  (store reverse comparison-function lookupfun
+        stack-createfun stack-popfun stack-emptyfun)
+  ;; Recursively push children of the node at the head of STORE onto the
+  ;; front of STORE, until a data node is reached.
 
   ;; nothing to do if stack is empty
   (when store
@@ -1182,7 +1212,8 @@ element stored in the trie.)"
       (while (not (trie--node-data-p node))
        (push
         (cons (trie--seq-append seq (trie--node-split node))
-              (funcall stack-createfun (trie--node-subtree node) reverse))
+              (funcall stack-createfun
+                       (trie--node-subtree node) reverse))
         store)
        (setq node (funcall stack-popfun (cdar store))
              seq (caar store))
@@ -1200,18 +1231,19 @@ element stored in the trie.)"
 
 ;; Implementation Note
 ;; -------------------
-;; For queries ranked in anything other than lexical order, we use a partial
-;; heap-sort to find the k=MAXNUM highest ranked matches among the n possibile
-;; matches. This has worst-case time complexity O(n log k), and is both simple
-;; and elegant. An optimal algorithm (e.g. partial quick-sort discarding the
-;; irrelevant partition at each step) would have complexity O(n + k log k),
-;; but is probably not worth the extra coding effort, and would have worse
-;; space complexity unless coded to work "in-place", which would be highly
-;; non-trivial. (I haven't done any benchmarking, though, so feel free to do
-;; so and let me know the results!)
+;; For queries ranked in anything other than lexical order, we use a
+;; partial heap-sort to find the k=MAXNUM highest ranked matches among
+;; the n possibile matches. This has worst-case time complexity O(n log
+;; k), and is both simple and elegant. An optimal algorithm
+;; (e.g. partial quick-sort discarding the irrelevant partition at each
+;; step) would have complexity O(n + k log k), but is probably not worth
+;; the extra coding effort, and would have worse space complexity unless
+;; coded to work "in-place", which would be highly non-trivial. (I
+;; haven't done any benchmarking, though, so feel free to do so and let
+;; me know the results!)
 
 (defmacro trie--construct-accumulator (maxnum filter resultfun)
-  ;; Does what it says on the tin! | sed -e 's/on/in/' -e 's/tin/macro name/'
+  ;; Does what it says on the tin! | sed -e 's/tin/macro name/'
   `(cond
     ;; filter, maxnum, resultfun
     ((and ,filter ,maxnum ,resultfun)
@@ -1278,7 +1310,7 @@ element stored in the trie.)"
 
 
 (defmacro trie--construct-ranked-accumulator (maxnum filter)
-  ;; Does what it says on the tin! | sed -e 's/on/in/' -e 's/tin/macro name/'
+  ;; Does what it says on the tin! | sed -e 's/tin/macro name/'
   `(cond
     ;; filter, maxnum
     ((and ,filter ,maxnum)
@@ -1307,14 +1339,15 @@ element stored in the trie.)"
 
 (defmacro trie--accumulate-results
   (rankfun maxnum reverse filter resultfun accfun duplicates &rest body)
-  ;; Accumulate results of running BODY code, and return them in appropriate
-  ;; order. BODY should call ACCFUN to accumulate a result, passing it two
-  ;; arguments: a trie data node, and the corresponding sequence. BODY can
-  ;; throw 'trie-accumulate--done to terminate the accumulation and return the
-  ;; results. A non-null DUPLICATES flag signals that the accumulated results
-  ;; might contain duplicates, which should be deleted. Note that DUPLICATES
-  ;; is ignored if RANKFUN is null. The other arguments should be passed
-  ;; straight through from the query function.
+  ;; Accumulate results of running BODY code, and return them in
+  ;; appropriate order. BODY should call ACCFUN to accumulate a result,
+  ;; passing it two arguments: a trie data node, and the corresponding
+  ;; sequence. BODY can throw 'trie-accumulate--done to terminate the
+  ;; accumulation and return the results. A non-null DUPLICATES flag
+  ;; signals that the accumulated results might contain duplicates,
+  ;; which should be deleted. Note that DUPLICATES is ignored if RANKFUN
+  ;; is null. The other arguments should be passed straight through from
+  ;; the query function.
 
   ;; rename functions to help avoid dynamic-scoping bugs
   `(let* ((--trie-accumulate--rankfun ,rankfun)
@@ -1354,14 +1387,16 @@ element stored in the trie.)"
               (if (equal (car (heap-root trie--accumulate))
                          (caar completions))
                   (heap-delete-root trie--accumulate)
-                (push (heap-delete-root trie--accumulate) completions)))
+                (push (heap-delete-root trie--accumulate)
+                      completions)))
           ;; skip duplicate checking if flag is not set
           (while (not (heap-empty trie--accumulate))
             (if ,resultfun
                 (let ((res (heap-delete-root trie--accumulate)))
                   (push (funcall ,resultfun (car res) (cdr res))
                         completions))
-              (push (heap-delete-root trie--accumulate) completions))))
+              (push (heap-delete-root trie--accumulate)
+                    completions))))
         completions))
 
       ;; for lexical query, reverse result list if MAXNUM supplied
@@ -1418,9 +1453,10 @@ default key-data cons cell."
   ;; convert trie from print-form if necessary
   (trie-transform-from-read-warn trie)
   ;; wrap prefix in a list if necessary
-  ;; FIXME: the test for a list of prefixes, below, will fail if the PREFIX
-  ;;        sequence is a list, and the elements of PREFIX are themselves
-  ;;        lists (there might be no easy way to fully fix this...)
+  ;; FIXME: the test for a list of prefixes, below, will fail if the
+  ;;        PREFIX sequence is a list, and the elements of PREFIX are
+  ;;        themselves lists (there might be no easy way to fully fix
+  ;;        this...)
   (if (or (atom prefix)
          (and (listp prefix) (not (sequencep (car prefix)))))
       (setq prefix (list prefix))
@@ -1584,16 +1620,19 @@ default key-data cons cell."
   (when rankfun
     (setq rankfun
          `(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 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...)
             (unless (or (atom (car a))
-                        (and (listp (car a)) (not (sequencep (caar a)))))
+                        (and (listp (car a))
+                             (not (sequencep (caar a)))))
               (setq a (cons (caar a) (cdr a))))
             (unless (or (atom (car b))
-                        (and (listp (car b)) (not (sequencep (caar b)))))
+                        (and (listp (car b))
+                             (not (sequencep (caar b)))))
               (setq b (cons (caar b) (cdr b))))
             ;; call rankfun on massaged arguments
             (,rankfun a b))))
@@ -1614,13 +1653,14 @@ default key-data cons cell."
 
 
 
-(defun trie--do-regexp-search (--trie--regexp-search--node
-                              tNFA seq pos reverse
+(defun trie--do-regexp-search
+  (--trie--regexp-search--node tNFA seq pos reverse
                               comparison-function lookupfun mapfun)
-  ;; Search everything below the node --TRIE--REGEXP-SEARCH-NODE for matches
-  ;; to the regexp encoded in tNFA. SEQ is the sequence corresponding to NODE,
-  ;; POS is it's length. REVERSE is the usual query argument, and the
-  ;; remaining arguments are the corresponding trie functions.
+  ;; Search everything below the node --TRIE--REGEXP-SEARCH-NODE for
+  ;; matches to the regexp encoded in tNFA. SEQ is the sequence
+  ;; corresponding to NODE, POS is it's length. REVERSE is the usual
+  ;; query argument, and the remaining arguments are the corresponding
+  ;; trie functions.
   (declare (special accumulator))
 
   ;; if NFA has matched, check if trie contains current string
@@ -1658,7 +1698,8 @@ default key-data cons cell."
                     (trie--do-regexp-search
                      node state
                      (trie--seq-append seq (trie--node-split node))
-                     (1+ pos) reverse comparison-function lookupfun mapfun))))
+                     (1+ pos) reverse comparison-function
+                     lookupfun mapfun))))
               (trie--node-subtree --trie--regexp-search--node)
               reverse)))
 
@@ -1718,7 +1759,8 @@ elements that matched the corresponding groups, in order."
     (trie--regexp-stack-create trie regexp reverse)))
 
 
-(defun trie--regexp-stack-construct-store (trie regexp &optional reverse)
+(defun trie--regexp-stack-construct-store
+  (trie regexp &optional reverse)
   ;; Construct store for regexp stack based on TRIE.
   (let ((seq (cond ((stringp regexp) "") ((listp regexp) ()) (t [])))
        store)
@@ -1740,9 +1782,10 @@ elements that matched the corresponding groups, in 
order."
 (defun trie--regexp-stack-repopulate
   (store reverse comparison-function lookupfun
         stack-createfun stack-popfun stack-emptyfun)
-  ;; Recursively push matching children of the node at the head of STORE onto
-  ;; STORE, until a data node is reached. REVERSE is the usual query argument,
-  ;; and the remaining arguments are the corresponding trie functions.
+  ;; Recursively push matching children of the node at the head of STORE
+  ;; onto STORE, until a data node is reached. REVERSE is the usual
+  ;; query argument, and the remaining arguments are the corresponding
+  ;; trie functions.
   (let (state seq node pos groups n s)
     (while
        (progn
@@ -1793,19 +1836,24 @@ elements that matched the corresponding groups, in 
order."
            ;; if node stack is empty, dump it and keep repopulating
            (if (funcall stack-emptyfun node)
                t  ; return t to keep looping
-             ;; otherwise, add node stack back, and add next node from stack
+             ;; otherwise, add node stack back, and add next node from
+             ;; stack
              (push (list seq node state pos) store)
              (setq node (funcall stack-popfun node)
-                   state (tNFA-next-state state (trie--node-split node) pos))
+                   state (tNFA-next-state state
+                                          (trie--node-split node) pos))
              (when state
-               ;; matching data node: add data to the stack and we're done
+               ;; matching data node: add data to the stack and we're
+               ;; done
                (if (trie--node-data-p node)
                    (progn
                      (push (cons seq (trie--node-data node)) store)
                      nil)  ; return nil to exit loop
-                 ;; normal node: add it to the stack and keep repopulating
-                 (push (list (trie--seq-append seq (trie--node-split node))
-                             node state (1+ pos))
+                 ;; normal node: add it to the stack and keep
+                 ;; repopulating
+                 (push (list
+                        (trie--seq-append seq (trie--node-split node))
+                        node state (1+ pos))
                        store)))))
           ))))
   store)
@@ -1814,4 +1862,9 @@ elements that matched the corresponding groups, in order."
 
 (provide 'trie)
 
+
+;;; Local Variables:
+;;; fill-column: 72
+;;; End:
+
 ;;; trie.el ends here