branch: elpa/flx
commit 46dd7d7edbbd2846feb5552b5434c92e945bbf72
Author: PythonNut <python...@users.noreply.github.com>
Commit: PythonNut <python...@users.noreply.github.com>
Improve readability
---
flx.el | 112 +++++++++++++++++++++++++++++++++++++++++------------------------
1 file changed, 71 insertions(+), 41 deletions(-)
diff --git a/flx.el b/flx.el
index 4a2c15fbaa..0e476ec615 100644
--- a/flx.el
+++ b/flx.el
@@ -245,18 +245,30 @@ See documentation for logic."
(puthash str res cache))
res))))
-(defun flx-find-best-match (greater-than
- q-index
- query-length
+(defun flx-find-best-match (str-info
heatmap
- match-cache
- str-info
- query)
+ greater-than
+ query
+ query-length
+ q-index
+ match-cache)
+ "Recursively compute the best match for a string, passed as STR-INFO and
+HEATMAP, according to QUERY.
+
+This function uses MATCH-CACHE to memoize its return values.
+For other parameters, see `flx-score'"
+
+ ;; Here, we use a simple N'ary hashing scheme
+ ;; You could use (/ hash-key query-length) to get greater-than
+ ;; Or, (mod hash-key query-length) to get q-index
+ ;; We use this instead of a cons key for the sake of efficiency
(let* ((hash-key (+ q-index
(* (or greater-than 0)
query-length)))
(hash-value (gethash hash-key match-cache)))
(if hash-value
+ ;; Here, we use the value 'no-match to distinguish a cache miss
+ ;; from a nil (i.e. non-matching) return value
(if (eq hash-value 'no-match)
nil
hash-value)
@@ -264,41 +276,52 @@ See documentation for logic."
(gethash (aref query q-index) str-info)
greater-than))
(match)
- (score)
+ (temp-score)
(best-score most-negative-fixnum))
+ ;; Matches are of the form:
+ ;; ((match_indexes) . (score . contiguous-count))
(if (>= q-index (1- query-length))
+ ;; At the tail end of the recursion, simply
+ ;; generate all possible matches with their scores
+ ;; and return the list to parent.
(setq match (mapcar (lambda (index)
(cons (list index)
(cons (aref heatmap index) 0)))
indexes))
(dolist (index indexes)
- (dolist (elem (flx-find-best-match index (1+ q-index)
- query-length
+ (dolist (elem (flx-find-best-match str-info
heatmap
- match-cache
- str-info
- query))
- (setq score (if (= (1- (caar elem)) index)
- (+ (cadr elem)
- (aref heatmap index)
- (* (min (cddr elem)
- 3)
- 15)
- 60)
- (+ (cadr elem)
- (aref heatmap index))))
-
- ;; we only care about the optimal score
- (when (> score best-score)
- (setq best-score score
+ index
+ query
+ query-length
+ (1+ q-index)
+ match-cache))
+ (setq temp-score
+ (if (= (1- (caar elem)) index)
+ (+ (cadr elem)
+ (aref heatmap index)
+
+ ;; boost contiguous matches
+ (* (min (cddr elem)
+ 3)
+ 15)
+ 60)
+ (+ (cadr elem)
+ (aref heatmap index))))
+
+ ;; We only care about the optimal match, so only
+ ;; forward the match with the best score to parent
+ (when (> temp-score best-score)
+ (setq best-score temp-score
match (list (cons (cons index (car elem))
- (cons score
+ (cons temp-score
(if (= (1- (caar elem))
index)
(1+ (cddr elem))
0)))))))))
+ ;; Calls are cached to avoid exponential time complexity
(puthash hash-key
(if match match 'no-match)
match-cache)
@@ -315,22 +338,29 @@ See documentation for logic."
(full-match-boost (and (< 1 query-length)
(< query-length 5)))
- ;; Dynamic Programming table
+ ;; Dynamic Programming table for memoizing flx-find-best-match
(match-cache (make-hash-table :test 'eql :size 10))
- (res (flx-find-best-match nil 0
- query-length
- heatmap
- match-cache
- str-info
- query)))
- ;; postprocess candidate
- (and res
- (cons (if (and full-match-boost
- (= (length (caar res))
- (length str)))
- (+ (cl-cadar res) 10000)
- (cl-cadar res))
- (caar res))))))
+
+ (optimal-match (flx-find-best-match str-info
+ heatmap
+ nil
+ query
+ query-length
+ 0
+ match-cache)))
+ ;; Postprocess candidate
+ (and optimal-match
+ (cons
+ ;; This is the computed score, adjusted to boost the scores
+ ;; of exact matches.
+ (if (and full-match-boost
+ (= (length (caar optimal-match))
+ (length str)))
+ (+ (cl-cadar optimal-match) 10000)
+ (cl-cadar optimal-match))
+
+ ;; This is the list of match positions
+ (caar optimal-match))))))
(defun flx-propertize (obj score &optional add-score)
"Return propertized copy of obj according to score.
