New function for subr.el: sort-on

[John Wiegley]

This can be more memory efficient than using `sort' with a predicate, since it
computes each value used by the predicate only once. If the predicate only
needs to access sub-elements, and not do any computation, there may be no
advantage.

--8<---------------cut here---------------start------------->8---
(defsubst sort-on (seq predicate accessor)
  "Sort SEQ using PREDICATE applied to values returned by ACCESSOR.
This implements the so-called Schwartzian transform, which has
the performance advantage of applying ACCESSOR at most once per
element in the list, as opposed to using `sort' with a PREDICATE
that applies the ACCESSOR.
Note: this function is only a win over `sort' if ACCESSOR is
compute-intensive; otherwise, it uses more intermediate cons
cells than regular `sort', and so represents a memory for CPU
tradeoff."
  (mapcar #'cdr (sort (mapcar #'(lambda (x) (cons (funcall accessor x) x)) seq)
                      #'(lambda (x y) (funcall predicate (car x) (car y))))))

(defun sort-on* (seq predicate accessor)
  "Sort SEQ using PREDICATE applied to values returned by ACCESSOR.
This is a destructive version of `sort-on', which attempts to
reuse storage as much as possible."
  (let ((seq2 seq))
    (while seq2
      (setcar seq2 (cons (funcall accessor (car seq2)) (car seq2)))
      (setq seq2 (cdr seq2))))
  (setq seq (sort* seq #'(lambda (x y) (funcall predicate (car x) (car y)))))
  (let ((seq2 seq))
    (while seq2
      (setcar seq2 (cdar seq2))
      (setq seq2 (cdr seq2)))
    seq))
--8<---------------cut here---------------end--------------->8---

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2