[elpa] externals/vertico af3d263 1/2: Optimize vertico--group-by with hash table

[Protesilaos Stavrou]

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

    Optimize vertico--group-by with hash table
---
 vertico.el | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/vertico.el b/vertico.el
index 555d80b..503a3a8 100644
--- a/vertico.el
+++ b/vertico.el
@@ -280,20 +280,22 @@
 (defun vertico--group-by (fun elems)
   "Group ELEMS by FUN."
   (when elems
-    (let ((groups))
+    (let ((group-list) (group-hash (make-hash-table :test #'equal)))
       (while elems
         (let* ((key (funcall fun (car elems) nil))
-               (group (cdr (assoc key groups))))
+               (group (gethash key group-hash)))
           (if group
               (setcdr group (setcdr (cdr group) elems)) ;; Append to tail of 
group
-            (push `(,key ,elems . ,elems) groups)) ;; New group (key head . 
tail)
+            (setq group (cons elems elems)) ;; (head . tail)
+            (push group group-list)
+            (puthash key group group-hash))
           (setq elems (cdr elems))))
-      (setcdr (cddar groups) nil) ;; Unlink last tail
-      (setq groups (nreverse groups))
-      (prog1 (cadar groups)
-        (while (cdr groups)
-          (setcdr (cddar groups) (cadadr groups)) ;; Link groups
-          (setq groups (cdr groups)))))))
+      (setcdr (cdar group-list) nil) ;; Unlink last tail
+      (setq group-list (nreverse group-list))
+      (prog1 (caar group-list)
+        (while (cdr group-list)
+          (setcdr (cdar group-list) (caadr group-list)) ;; Link groups
+          (setq group-list (cdr group-list)))))))
 
 (defun vertico--update-candidates (pt content bounds metadata)
   "Preprocess candidates given PT, CONTENT, BOUNDS and METADATA."