Use hash tables instead of arrays

1 files changed, 36 insertions, 36 deletions

diff --git a/apheleia.el b/apheleia.el
index f2bc615..8218dc1 100644
--- a/apheleia.el
+++ b/apheleia.el
@@ -33,25 +33,25 @@
 
 (cl-defun apheleia--edit-distance-table (s1 s2)
   "Align strings S1 and S2 for minimum edit distance.
-Return the dynamic programming table as a vector of vectors which
-can be indexed by integers I1 and I2. The entry at (I1, I2) is
-the edit distance between the first I1 characters of S1 and the
-first I2 characters of S2."
-  (let ((table (make-vector (length s1) nil)))
+Return the dynamic programming table as has table which maps cons
+of integers (I1 . I2) to the edit distance between the first I1
+characters of S1 and the first I2 characters of S2."
+  (let ((table (make-hash-table :test #'equal)))
+    (dotimes (i1 (1+ (length s1)))
+      (puthash (cons i1 0) i1 table))
+    (dotimes (i2 (1+ (length s2)))
+      (puthash (cons 0 i2) i2 table))
     (dotimes (i1 (length s1))
-      (let ((row (aset table i1 (make-vector (length s2) nil))))
-        (dotimes (i2 (length s2))
-          (aset
-           row i2
-           (cond
-            ((zerop i1) i2)
-            ((zerop i2) i1)
-            (t
-             (min
-              (thread-first table (aref     i1 ) (aref (1- i2)) (1+))
-              (thread-first table (aref (1- i1)) (aref     i2 ) (1+))
-              (thread-first table (aref (1- i1)) (aref (1- i2))
-                            (+ (if (/= (aref s1 i1) (aref s2 i2)) 1 0))))))))))
+      ;; Iterate from 1 to length+1.
+      (cl-incf i1)
+      (dotimes (i2 (length s2))
+        (cl-incf i2)
+        (let ((ins (1+ (gethash (cons i1 (1- i2)) table)))
+              (del (1+ (gethash (cons (1- i1) i2) table)))
+              (sub (gethash (cons (1- i1) (1- i2)) table)))
+          (unless (= (aref s1 (1- i1)) (aref s2 (1- i2)))
+            (cl-incf sub))
+          (puthash (cons i1 i2) (min ins del sub) table))))
     table))
 
 (defun apheleia--align-point (s1 s2 p1)
@@ -60,24 +60,24 @@ If S1 and S2 are the same, then P1 and P2 will also be the same.
 Otherwise, the text of S2 surrounding P2 is \"similar\" to the
 text of S1 surrounding P1."
   (let* ((table (apheleia--edit-distance-table s1 s2))
-         (i1 0)
-         (i2 0))
-    (while (< i1 p1)
-      (let* ((costs
-              (list
-               (thread-first table (aref     i1 ) (aref (1- i2)) (1+))
-               (thread-first table (aref (1- i1)) (aref     i2 ) (1+))
-               (thread-first table (aref (1- i1)) (aref (1- i2))
-                             (+ (if (/= (aref s1 i1) (aref s2 i2)) 1 0)))))
-             (min-cost (apply #'min costs)))
-        (cond
-         ((= min-cost (nth 0 costs))
-          (cl-incf i1)
-          (cl-incf i2))
-         ((= min-cost (nth 1 costs))
-          (cl-incf i2))
-         ((= min-cost (nth 2 costs))
-          (cl-incf i1)))))
+         (i1 (length s1))
+         (i2 (length s2)))
+    (while (> i1 p1)
+      (let ((ins (1+ (gethash (cons i1 (1- i2)) table)))
+            (del (1+ (gethash (cons (1- i1) i2) table)))
+            (sub (gethash (cons (1- i1) (1- i2)) table)))
+        (unless (= (aref s1 (1- i1)) (aref s2 (1- i2)))
+          (cl-incf sub))
+        (let ((cost (min ins del sub)))
+          (cond
+           ((= cost ins)
+            (cl-decf i2))
+           ((= cost del)
+            (cl-decf i1))
+           ((= cost sub)
+            (cl-decf i1)
+            (cl-decf i2))))
+        ))
     i2))
 
 (defun apheleia--map-rcs-patch (func)