branch: externals/compat
commit b9bf90e71c32ac3250f9a6a37eb809d836beb159
Author: Daniel Mendler <[email protected]>
Commit: Daniel Mendler <[email protected]>
compat-25: Optimize sort, improve test
O(n²) -> O(nlogn)
---
compat-25.el | 11 +++++++----
compat-tests.el | 13 +++++++++++--
2 files changed, 18 insertions(+), 6 deletions(-)
diff --git a/compat-25.el b/compat-25.el
index 157fc31048..ef0c78b398 100644
--- a/compat-25.el
+++ b/compat-25.el
@@ -49,10 +49,13 @@ usage: (bool-vector &rest OBJECTS)"
((listp seq)
(sort seq predicate))
((vectorp seq)
- (let ((cseq (sort (append seq nil) predicate)))
- (dotimes (i (length cseq))
- (setf (aref seq i) (nth i cseq)))
- (apply #'vector cseq)))
+ (let ((list (sort (append seq nil) predicate))
+ (p list)
+ (i 0))
+ (while p
+ (aset seq i (car p))
+ (setq i (1+ i) p (cdr p)))
+ (apply #'vector list)))
((signal 'wrong-type-argument 'list-or-vector-p))))
;;;; Defined in editfns.c
diff --git a/compat-tests.el b/compat-tests.el
index 3156b87ba3..69684582db 100644
--- a/compat-tests.el
+++ b/compat-tests.el
@@ -1060,10 +1060,19 @@
(should-equal '(1 2 3 4) (flatten-tree '(((1 nil)) 2 (((3 nil nil) 4))))))
(ert-deftest sort ()
+ (should-equal (list 1 2 3) (sort (list 1 2 3) #'<))
+ (should-equal (list 1 2 3) (sort (list 1 3 2) #'<))
+ (should-equal (list 1 2 3) (sort (list 3 2 1) #'<))
(should-equal (list 1 2 3) (compat-call sort (list 1 2 3) #'<))
+ (should-equal (list 1 2 3) (compat-call sort (list 1 3 2) #'<))
(should-equal (list 1 2 3) (compat-call sort (list 3 2 1) #'<))
- (should-equal '[1 2 3] (compat-call sort '[1 2 3] #'<))
- (should-equal '[1 2 3] (compat-call sort '[3 2 1] #'<)))
+ (should-equal [1 2 3] (compat-call sort [1 2 3] #'<))
+ (should-equal [1 2 3] (compat-call sort [1 3 2] #'<))
+ (should-equal [1 2 3] (compat-call sort [3 2 1] #'<))
+ ;; Test side effect
+ (let ((vec [4 5 8 3 1 2 3 2 3 4]))
+ (compat-call sort vec #'>)
+ (should-equal vec [8 5 4 4 3 3 3 2 2 1])))
(ert-deftest replace-string-in-region ()
(with-temp-buffer
