[elpa] externals/trie b4d81bf 064/111: Trivial whitespace tidying.

[Stefan Monnier]

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

    Trivial whitespace tidying.
---
 trie.el | 252 ++++++++++++++++++++++++++++++----------------------------------
 1 file changed, 119 insertions(+), 133 deletions(-)

diff --git a/trie.el b/trie.el
index f49b1a6..4e5c016 100644
--- a/trie.el
+++ b/trie.el
@@ -1,4 +1,3 @@
-
 ;;; trie.el --- trie package
 
 
@@ -10,148 +9,142 @@
 ;;           trie, ternary search tree, tree, completion, regexp
 ;; Package-Requires: ((emacs "24.1") (tNFA "0.1.1") (heap "0.3"))
 ;; URL: http://www.dr-qubit.org/emacs.php
-
+;; Repository: http://www.dr-qubit.org/git/predictive.git
 
 ;; This file is part of Emacs.
 ;;
-;; GNU Emacs is free software: you can redistribute it and/or modify
-;; it under the terms of the GNU General Public License as published by
-;; the Free Software Foundation, either version 3 of the License, or
-;; (at your option) any later version.
+;; GNU Emacs is free software: you can redistribute it and/or modify it under
+;; the terms of the GNU General Public License as published by the Free
+;; Software Foundation, either version 3 of the License, or (at your option)
+;; any later version.
 ;;
-;; GNU Emacs is distributed in the hope that it will be useful,
-;; but WITHOUT ANY WARRANTY; without even the implied warranty of
-;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-;; GNU General Public License for more details.
+;; GNU Emacs is distributed in the hope that it will be useful, but WITHOUT
+;; ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+;; FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+;; more details.
 ;;
-;; You should have received a copy of the GNU General Public License
-;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
+;; You should have received a copy of the GNU General Public License along
+;; with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
 
 
 ;;; Commentary:
 ;;
 ;; 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!).
+;; 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!).
 ;;
 ;; You create a trie using `make-trie', create an association using
-;; `trie-insert', retrieve an association using `trie-lookup', and map
-;; over a trie using `trie-map', `trie-mapc', `trie-mapcar', or
-;; `trie-mapf'. You can find completions of a prefix sequence using
-;; `trie-complete', or search for keys matching a regular expression
-;; using `trie-regexp-search'. Using `trie-stack', you can create an
-;; object that allows the contents of the trie to be used like a stack,
-;; useful for building other algorithms on top of tries;
-;; `trie-stack-pop' pops elements off the stack one-by-one, in "lexical"
-;; order, whilst `trie-stack-push' pushes things onto the
-;; stack. Similarly, `trie-complete-stack', and `trie-regexp-stack'
-;; create "lexically-ordered" stacks of query results.
+;; `trie-insert', retrieve an association using `trie-lookup', and map over a
+;; trie using `trie-map', `trie-mapc', `trie-mapcar', or `trie-mapf'. You can
+;; find completions of a prefix sequence using `trie-complete', or search for
+;; keys matching a regular expression using `trie-regexp-search'. Using
+;; `trie-stack', you can create an object that allows the contents of the trie
+;; to be used like a stack, useful for building other algorithms on top of
+;; tries; `trie-stack-pop' pops elements off the stack one-by-one, in
+;; "lexical" order, whilst `trie-stack-push' pushes things onto the
+;; stack. Similarly, `trie-complete-stack', and `trie-regexp-stack' 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
-;; 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
-;; this package does the opposite: it implements associative arrays, and
-;; leaves it up to you to use them as lookup tables if you so desire.
+;; 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 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 this package does the opposite: it implements
+;; associative arrays, and leaves it up to you to use them as lookup tables if
+;; you so desire.
 ;;
 ;;
 ;; Different Types of Trie
 ;; -----------------------
-;; There are numerous ways to implement trie data structures internally,
-;; each with its own time- and space-efficiency 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!)
+;; There are numerous ways to implement trie data structures internally, each
+;; with its own time- and space-efficiency 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!)
 ;;
 ;;
-;; 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
+;; 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.
 ;;
-;; 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
-;; 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
-;; worst-case complexity.
+;; 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 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 worst-case complexity.
 ;;
 ;; 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
-;; 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
-;; time overhead required to keep track of rebalancing.
+;; 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 time overhead required to keep
+;; track of rebalancing.
 ;;
-;; 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.
+;; 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.
 ;;
 ;;
-;; A digital trie is a different implementation of a trie, which can be
-;; viewed as a tree of arrays, and has different space- and
-;; time-complexities than a ternary search tree. Roughly speaking, a
-;; digital trie has worse space-complexity, but better
-;; time-complexity. Using hash tables instead of arrays for the nodes
-;; gives something similar to a digital trie, potentially with better
-;; space-complexity and the same amortised time-complexity, but at the
-;; expense of occasional significant inefficiency when inserting and
-;; deleting (whenever a hash table has to be resized). Indeed, an array
-;; can be viewed as a perfect hash table, but as such it requires the
-;; number of possible values to be known in advance.
+;; A digital trie is a different implementation of a trie, which can be viewed
+;; as a tree of arrays, and has different space- and time-complexities than a
+;; ternary search tree. Roughly speaking, a digital trie has worse
+;; space-complexity, but better time-complexity. Using hash tables instead of
+;; arrays for the nodes gives something similar to a digital trie, potentially
+;; with better space-complexity and the same amortised time-complexity, but at
+;; the expense of occasional significant inefficiency when inserting and
+;; deleting (whenever a hash table has to be resized). Indeed, an array can be
+;; viewed as a perfect hash table, but as such it requires the number of
+;; possible values to be known in advance.
 ;;
-;; Finally, if you really need optimal efficiency from your trie, you
-;; could even write a custom type of underlying lookup table, optimised
-;; for your specific needs.
+;; Finally, if you really need optimal efficiency from your trie, you could
+;; even write a custom type of underlying lookup table, optimised for your
+;; specific needs.
 ;;
-;; This package uses the AVL tree package avl-tree.el, the tagged NFA
-;; package tNFA.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.5
 ;; * removed `trie--avl-transform-for-print' and
-;;   `trie--avl-transform-from-read', since Emacs has supported
-;;   printing and reading circular data structures for a long time now,
-;;   rendering these transormers obsolete (note that `print-circle'
-;;   *must* be enabled now when printing an avl trie)
+;;   `trie--avl-transform-from-read', since Emacs has supported printing and
+;;   reading circular data structures for a long time now, rendering these
+;;   transormers obsolete (note that `print-circle' *must* be enabled now when
+;;   printing an avl trie)
 ;;
 ;; Version 0.2.4
 ;; * minor bug-fix to `trie--edebug-pretty-print' to print "nil" instead
@@ -168,32 +161,30 @@
 ;; * bug-fix to result accumulation in `trie--do-regexp-search'
 ;;
 ;; 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.
-;; * Unlike tstree.el, trie.el is general enough to implement all sorts
-;;   of tries, not just ternary search trees (though these remain the
-;;   default).
-;; * Up to "tstree"->"trie" renaming, many functions are drop-in
-;;   replacements for tstree.el functions. However, insertion and rank
-;;   functions are no longer stored in the data structure, so
-;;   corresponidng arguments are no longer optional. A single
-;;   `trie-complete' function now deals with sorting completions in both
-;;   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
+;; * 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).
+;; * Up to "tstree"->"trie" renaming, many functions are drop-in replacements
+;;   for tstree.el functions. However, insertion and rank functions are no
+;;   longer stored in the data structure, so corresponidng arguments are no
+;;   longer optional. A single `trie-complete' function now deals with sorting
+;;   completions in both 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!
+;; * `trie-wildcard-search' implements efficient shell-glob-like wildcard
+;;   searches of tries!
 
 
 
@@ -1957,9 +1948,4 @@ elements that matched the corresponding groups, in order."
 
 (provide 'trie)
 
-
-;;; Local Variables:
-;;; fill-column: 72
-;;; End:
-
 ;;; trie.el ends here