[elpa] externals/vertico b7d55f0 1/2: vertico--sort: Use bucket sort as suggested by Stefan Monnier

[Protesilaos Stavrou]

branch: externals/vertico
commit b7d55f096fc9e07b91b368fda7f865abbb148a39
Author: Daniel Mendler <mail@daniel-mendler.de>
Commit: Daniel Mendler <mail@daniel-mendler.de>

    vertico--sort: Use bucket sort as suggested by Stefan Monnier
    
    Drop the threshold
---
 vertico.el | 58 +++++++++++++++++++++++++++++++---------------------------
 1 file changed, 31 insertions(+), 27 deletions(-)

diff --git a/vertico.el b/vertico.el
index e8aaac7..7fc2262 100644
--- a/vertico.el
+++ b/vertico.el
@@ -44,10 +44,6 @@
   :group 'convenience
   :prefix "vertico-")
 
-(defcustom vertico-sort-threshold 20000
-  "Candidates will only be sorted if there are fewer than this threshold."
-  :type 'integer)
-
 (defcustom vertico-count-format (cons "%-6s " "%s/%s")
   "Format string used for the candidate count."
   :type '(choice (const nil) (cons string string)))
@@ -140,9 +136,9 @@
 
 (defun vertico--sort-predicate (x y)
   "Sorting predicate which compares X and Y."
-  (or (< (cdr x) (cdr y))
-      (and (= (cdr x) (cdr y))
-           (string< (car x) (car y)))))
+  (or (< (length x) (length y))
+      (and (= (length x) (length y))
+           (string< x y))))
 
 (defun vertico--sort (input candidates)
   "Sort CANDIDATES by history, length and alphabetically, given current INPUT."
@@ -186,22 +182,31 @@
         (unless (gethash elem vertico--history-hash)
           (puthash elem index vertico--history-hash))
         (setq index (1+ index))))))
-  ;; Decorate each candidate with (index<<13) + length. This way we sort first 
by index and then by
-  ;; length. We assume that the candidates are shorter than 2**13 characters 
and that the history is
-  ;; shorter than 2**16 entries.
-  (let ((cand candidates))
-    (while cand
-      (setcar cand (cons (car cand)
-                         (+ (lsh (gethash (car cand) vertico--history-hash 
#xFFFF) 13)
-                            (length (car cand)))))
-      (pop cand)))
-  (setq candidates (sort candidates #'vertico--sort-predicate))
-  ;; Drop decoration from the candidates
-  (let ((cand candidates))
-    (while cand
-      (setcar cand (caar cand))
-      (pop cand)))
-  candidates)
+  ;; Separate history candidates from candidates first.
+  ;; Move the remaining candidates into buckets according to length.
+  (let* ((max-bucket 40)
+         (buckets (make-vector (1+ max-bucket) nil))
+         (hcands))
+    (dolist (cand candidates)
+      (if-let (idx (gethash cand vertico--history-hash))
+          (push (cons idx cand) hcands)
+        (let ((idx (min max-bucket (length cand))))
+          (aset buckets idx (cons cand (aref buckets idx))))))
+    ;; Sort history candidates
+    (setq hcands (sort hcands #'car-less-than-car))
+    (let ((cand hcands))
+      (while cand
+        (setcar cand (cdar cand))
+        (pop cand)))
+    (nconc
+     ;; Sorted History candidates
+     hcands
+     ;; Sort bucket candidates
+     (mapcan
+      (lambda (bucket) (sort bucket #'string<))
+      (nbutlast (append buckets nil)))
+     ;; Last bucket needs special treatment
+     (sort (aref buckets max-bucket) #'vertico--sort-predicate))))
 
 (defun vertico--annotate (metadata candidates)
   "Annotate CANDIDATES with annotation function specified by METADATA."
@@ -271,10 +276,9 @@
          (base (or (when-let (z (last all)) (prog1 (cdr z) (setcdr z nil))) 0))
          (def (or (car-safe minibuffer-default) minibuffer-default))
          (total (length all)))
-    (when (<= total vertico-sort-threshold)
-      (setq all (if-let (sort (completion-metadata-get metadata 
'display-sort-function))
-                    (funcall sort all)
-                  (vertico--sort content all))))
+    (setq all (if-let (sort (completion-metadata-get metadata 
'display-sort-function))
+                  (funcall sort all)
+                (vertico--sort content all)))
     ;; Move special candidates: "field" appears at the top, before "field/", 
before default value
     (when (stringp def)
       (setq all (vertico--move-to-front def all)))