Commit | Line | Data |
---|---|---|
c88ab9ce ER |
1 | ;;; sort.el --- commands to sort text in an Emacs buffer. |
2 | ||
eea8d4ef ER |
3 | ;; Copyright (C) 1986, 1987 Free Software Foundation, Inc. |
4 | ||
e5167999 ER |
5 | ;; Author: Howie Kaye |
6 | ;; Maintainer: FSF | |
d7b4d18f | 7 | ;; Keywords: unix |
e5167999 | 8 | |
d32200ac RS |
9 | ;; This file is part of GNU Emacs. |
10 | ||
11 | ;; GNU Emacs is free software; you can redistribute it and/or modify | |
12 | ;; it under the terms of the GNU General Public License as published by | |
e5167999 | 13 | ;; the Free Software Foundation; either version 2, or (at your option) |
d32200ac RS |
14 | ;; any later version. |
15 | ||
16 | ;; GNU Emacs is distributed in the hope that it will be useful, | |
17 | ;; but WITHOUT ANY WARRANTY; without even the implied warranty of | |
18 | ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
19 | ;; GNU General Public License for more details. | |
20 | ||
21 | ;; You should have received a copy of the GNU General Public License | |
22 | ;; along with GNU Emacs; see the file COPYING. If not, write to | |
23 | ;; the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. | |
24 | ||
e5167999 | 25 | ;;; Code: |
d32200ac RS |
26 | |
27 | (defun sort-subr (reverse nextrecfun endrecfun &optional startkeyfun endkeyfun) | |
28 | "General text sorting routine to divide buffer into records and sort them. | |
29 | Arguments are REVERSE NEXTRECFUN ENDRECFUN &optional STARTKEYFUN ENDKEYFUN. | |
30 | ||
31 | We consider this portion of the buffer to be divided into disjoint pieces | |
32 | called sort records. A portion of each sort record (perhaps all of it) | |
33 | is designated as the sort key. The records are rearranged in the buffer | |
34 | in order by their sort keys. The records may or may not be contiguous. | |
35 | ||
36 | Usually the records are rearranged in order of ascending sort key. | |
37 | If REVERSE is non-nil, they are rearranged in order of descending sort key. | |
38 | ||
39 | The next four arguments are functions to be called to move point | |
40 | across a sort record. They will be called many times from within sort-subr. | |
41 | ||
42 | NEXTRECFUN is called with point at the end of the previous record. | |
43 | It moves point to the start of the next record. | |
44 | It should move point to the end of the buffer if there are no more records. | |
45 | The first record is assumed to start at the position of point when sort-subr | |
46 | is called. | |
47 | ||
48 | ENDRECFUN is is called with point within the record. | |
49 | It should move point to the end of the record. | |
50 | ||
51 | STARTKEYFUN may moves from the start of the record to the start of the key. | |
52 | It may return either return a non-nil value to be used as the key, or | |
53 | else the key will be the substring between the values of point after | |
d9a55d32 RS |
54 | STARTKEYFUN and ENDKEYFUN are called. If STARTKEYFUN is nil, the key |
55 | starts at the beginning of the record. | |
d32200ac RS |
56 | |
57 | ENDKEYFUN moves from the start of the sort key to the end of the sort key. | |
58 | ENDKEYFUN may be nil if STARTKEYFUN returns a value or if it would be the | |
59 | same as ENDRECFUN." | |
60 | (save-excursion | |
61 | (message "Finding sort keys...") | |
62 | (let* ((sort-lists (sort-build-lists nextrecfun endrecfun | |
63 | startkeyfun endkeyfun)) | |
64 | (old (reverse sort-lists))) | |
65 | (if (null sort-lists) | |
66 | () | |
67 | (or reverse (setq sort-lists (nreverse sort-lists))) | |
68 | (message "Sorting records...") | |
69 | (setq sort-lists | |
70 | (if (fboundp 'sortcar) | |
71 | (sortcar sort-lists | |
d9a55d32 RS |
72 | (cond ((numberp (car (car sort-lists))) |
73 | ;; This handles both ints and floats. | |
d32200ac RS |
74 | '<) |
75 | ((consp (car (car sort-lists))) | |
76 | 'buffer-substring-lessp) | |
77 | (t | |
78 | 'string<))) | |
79 | (sort sort-lists | |
d9a55d32 | 80 | (cond ((numberp (car (car sort-lists))) |
d32200ac RS |
81 | (function |
82 | (lambda (a b) | |
83 | (< (car a) (car b))))) | |
84 | ((consp (car (car sort-lists))) | |
85 | (function | |
86 | (lambda (a b) | |
87 | (buffer-substring-lessp (car a) (car b))))) | |
88 | (t | |
89 | (function | |
90 | (lambda (a b) | |
91 | (string< (car a) (car b))))))))) | |
92 | (if reverse (setq sort-lists (nreverse sort-lists))) | |
93 | (message "Reordering buffer...") | |
94 | (sort-reorder-buffer sort-lists old))) | |
95 | (message "Reordering buffer... Done")) | |
96 | nil) | |
97 | ||
98 | ;; Parse buffer into records using the arguments as Lisp expressions; | |
e453d35a | 99 | ;; return a list of records. Each record looks like (KEY STARTPOS . ENDPOS) |
d32200ac RS |
100 | ;; where KEY is the sort key (a number or string), |
101 | ;; and STARTPOS and ENDPOS are the bounds of this record in the buffer. | |
102 | ||
103 | ;; The records appear in the list lastmost first! | |
104 | ||
105 | (defun sort-build-lists (nextrecfun endrecfun startkeyfun endkeyfun) | |
106 | (let ((sort-lists ()) | |
107 | (start-rec nil) | |
108 | done key) | |
109 | ;; Loop over sort records. | |
110 | ;(goto-char (point-min)) -- it is the caller's responsibility to | |
111 | ;arrange this if necessary | |
112 | (while (not (eobp)) | |
113 | (setq start-rec (point)) ;save record start | |
114 | (setq done nil) | |
115 | ;; Get key value, or move to start of key. | |
116 | (setq key (catch 'key | |
117 | (or (and startkeyfun (funcall startkeyfun)) | |
118 | ;; If key was not returned as value, | |
119 | ;; move to end of key and get key from the buffer. | |
120 | (let ((start (point))) | |
121 | (funcall (or endkeyfun | |
122 | (prog1 endrecfun (setq done t)))) | |
123 | (if (fboundp 'buffer-substring-lessp) | |
124 | (cons start (point)) | |
125 | (buffer-substring start (point))))))) | |
126 | ;; Move to end of this record (start of next one, or end of buffer). | |
127 | (cond ((prog1 done (setq done nil))) | |
128 | (endrecfun (funcall endrecfun)) | |
129 | (nextrecfun (funcall nextrecfun) (setq done t))) | |
130 | (if key (setq sort-lists (cons | |
131 | ;; consing optimization in case in which key | |
132 | ;; is same as record. | |
133 | (if (and (consp key) | |
134 | (equal (car key) start-rec) | |
135 | (equal (cdr key) (point))) | |
136 | (cons key key) | |
d9a55d32 RS |
137 | (cons key (cons start-rec (point)))) |
138 | sort-lists))) | |
d32200ac RS |
139 | (and (not done) nextrecfun (funcall nextrecfun))) |
140 | sort-lists)) | |
141 | ||
142 | (defun sort-reorder-buffer (sort-lists old) | |
143 | (let ((inhibit-quit t) | |
144 | (last (point-min)) | |
145 | (min (point-min)) (max (point-max))) | |
146 | ;; Make sure insertions done for reordering | |
147 | ;; do not go after any markers at the end of the sorted region, | |
148 | ;; by inserting a space to separate them. | |
149 | (goto-char (point-max)) | |
150 | (insert-before-markers " ") | |
151 | (narrow-to-region min (1- (point-max))) | |
152 | (while sort-lists | |
153 | (goto-char (point-max)) | |
154 | (insert-buffer-substring (current-buffer) | |
155 | last | |
156 | (nth 1 (car old))) | |
157 | (goto-char (point-max)) | |
158 | (insert-buffer-substring (current-buffer) | |
159 | (nth 1 (car sort-lists)) | |
d9a55d32 RS |
160 | (cdr (cdr (car sort-lists)))) |
161 | (setq last (cdr (cdr (car old))) | |
d32200ac RS |
162 | sort-lists (cdr sort-lists) |
163 | old (cdr old))) | |
164 | (goto-char (point-max)) | |
165 | (insert-buffer-substring (current-buffer) | |
166 | last | |
167 | max) | |
168 | ;; Delete the original copy of the text. | |
169 | (delete-region min max) | |
170 | ;; Get rid of the separator " ". | |
171 | (goto-char (point-max)) | |
172 | (narrow-to-region min (1+ (point))) | |
173 | (delete-region (point) (1+ (point))))) | |
174 | ||
f9f9507e | 175 | ;;;###autoload |
d32200ac RS |
176 | (defun sort-lines (reverse beg end) |
177 | "Sort lines in region alphabetically; argument means descending order. | |
178 | Called from a program, there are three arguments: | |
179 | REVERSE (non-nil means reverse order), BEG and END (region to sort)." | |
180 | (interactive "P\nr") | |
181 | (save-excursion | |
182 | (save-restriction | |
183 | (narrow-to-region beg end) | |
184 | (goto-char (point-min)) | |
185 | (sort-subr reverse 'forward-line 'end-of-line)))) | |
186 | ||
f9f9507e | 187 | ;;;###autoload |
d32200ac RS |
188 | (defun sort-paragraphs (reverse beg end) |
189 | "Sort paragraphs in region alphabetically; argument means descending order. | |
190 | Called from a program, there are three arguments: | |
191 | REVERSE (non-nil means reverse order), BEG and END (region to sort)." | |
192 | (interactive "P\nr") | |
193 | (save-excursion | |
194 | (save-restriction | |
195 | (narrow-to-region beg end) | |
196 | (goto-char (point-min)) | |
197 | (sort-subr reverse | |
198 | (function (lambda () (skip-chars-forward "\n \t\f"))) | |
199 | 'forward-paragraph)))) | |
200 | ||
f9f9507e | 201 | ;;;###autoload |
d32200ac RS |
202 | (defun sort-pages (reverse beg end) |
203 | "Sort pages in region alphabetically; argument means descending order. | |
204 | Called from a program, there are three arguments: | |
205 | REVERSE (non-nil means reverse order), BEG and END (region to sort)." | |
206 | (interactive "P\nr") | |
207 | (save-excursion | |
208 | (save-restriction | |
209 | (narrow-to-region beg end) | |
210 | (goto-char (point-min)) | |
211 | (sort-subr reverse | |
212 | (function (lambda () (skip-chars-forward "\n"))) | |
213 | 'forward-page)))) | |
214 | \f | |
215 | (defvar sort-fields-syntax-table nil) | |
216 | (if sort-fields-syntax-table nil | |
217 | (let ((table (make-syntax-table)) | |
218 | (i 0)) | |
219 | (while (< i 256) | |
220 | (modify-syntax-entry i "w" table) | |
221 | (setq i (1+ i))) | |
222 | (modify-syntax-entry ?\ " " table) | |
223 | (modify-syntax-entry ?\t " " table) | |
224 | (modify-syntax-entry ?\n " " table) | |
225 | (modify-syntax-entry ?\. "_" table) ; for floating pt. numbers. -wsr | |
226 | (setq sort-fields-syntax-table table))) | |
227 | ||
f9f9507e | 228 | ;;;###autoload |
d32200ac RS |
229 | (defun sort-numeric-fields (field beg end) |
230 | "Sort lines in region numerically by the ARGth field of each line. | |
231 | Fields are separated by whitespace and numbered from 1 up. | |
232 | Specified field must contain a number in each line of the region. | |
2af3a0e3 | 233 | With a negative arg, sorts by the ARGth field counted from the right. |
d32200ac RS |
234 | Called from a program, there are three arguments: |
235 | FIELD, BEG and END. BEG and END specify region to sort." | |
236 | (interactive "p\nr") | |
237 | (sort-fields-1 field beg end | |
238 | (function (lambda () | |
239 | (sort-skip-fields (1- field)) | |
240 | (string-to-int | |
241 | (buffer-substring | |
242 | (point) | |
243 | (save-excursion | |
244 | ;; This is just wrong! Even without floats... | |
245 | ;; (skip-chars-forward "[0-9]") | |
246 | (forward-sexp 1) | |
247 | (point)))))) | |
248 | nil)) | |
249 | ||
2af3a0e3 | 250 | (defun sort-float-fields (field beg end) |
251 | "Sort lines in region numerically by the ARGth field of each line. | |
252 | Fields are separated by whitespace and numbered from 1 up. Specified field | |
253 | must contain a floating point number in each line of the region. With a | |
254 | negative arg, sorts by the ARGth field counted from the right. Called from a | |
255 | program, there are three arguments: FIELD, BEG and END. BEG and END specify | |
256 | region to sort." | |
257 | (interactive "p\nr") | |
258 | (sort-fields-1 field beg end | |
259 | (function (lambda () | |
260 | (sort-skip-fields (1- field)) | |
261 | (string-to-float | |
262 | (buffer-substring | |
263 | (point) | |
264 | (save-excursion | |
265 | (re-search-forward | |
266 | "[+-]?[0-9]*\.?[0-9]*\\([eE][+-]?[0-9]+\\)?") | |
267 | (point)))))) | |
268 | nil)) | |
269 | ||
f9f9507e | 270 | ;;;###autoload |
d32200ac RS |
271 | (defun sort-fields (field beg end) |
272 | "Sort lines in region lexicographically by the ARGth field of each line. | |
273 | Fields are separated by whitespace and numbered from 1 up. | |
2af3a0e3 | 274 | With a negative arg, sorts by the ARGth field counted from the right. |
d32200ac RS |
275 | Called from a program, there are three arguments: |
276 | FIELD, BEG and END. BEG and END specify region to sort." | |
277 | (interactive "p\nr") | |
278 | (sort-fields-1 field beg end | |
279 | (function (lambda () | |
280 | (sort-skip-fields (1- field)) | |
281 | nil)) | |
282 | (function (lambda () (skip-chars-forward "^ \t\n"))))) | |
283 | ||
284 | (defun sort-fields-1 (field beg end startkeyfun endkeyfun) | |
2af3a0e3 | 285 | (let ((tbl (syntax-table))) |
286 | (if (zerop field) (setq field 1)) | |
d32200ac RS |
287 | (unwind-protect |
288 | (save-excursion | |
289 | (save-restriction | |
290 | (narrow-to-region beg end) | |
291 | (goto-char (point-min)) | |
292 | (set-syntax-table sort-fields-syntax-table) | |
2af3a0e3 | 293 | (sort-subr nil |
d32200ac RS |
294 | 'forward-line 'end-of-line |
295 | startkeyfun endkeyfun))) | |
296 | (set-syntax-table tbl)))) | |
297 | ||
298 | (defun sort-skip-fields (n) | |
2af3a0e3 | 299 | (let ((bol (point)) |
300 | (eol (save-excursion (end-of-line 1) (point)))) | |
301 | (if (> n 0) (forward-word n) | |
302 | (end-of-line) | |
303 | (forward-word (1+ n))) | |
304 | (if (or (and (>= (point) eol) (> n 0)) | |
305 | ;; this is marginally wrong; if the first line of the sort | |
306 | ;; at bob has the wrong number of fields the error won't be | |
307 | ;; reported until the next short line. | |
308 | (and (< (point) bol) (< n 0))) | |
d32200ac | 309 | (error "Line has too few fields: %s" |
2af3a0e3 | 310 | (buffer-substring bol eol))) |
d32200ac RS |
311 | (skip-chars-forward " \t"))) |
312 | ||
313 | \f | |
f9f9507e | 314 | ;;;###autoload |
d32200ac RS |
315 | (defun sort-regexp-fields (reverse record-regexp key-regexp beg end) |
316 | "Sort the region lexicographically as specifed by RECORD-REGEXP and KEY. | |
317 | RECORD-REGEXP specifies the textual units which should be sorted. | |
318 | For example, to sort lines RECORD-REGEXP would be \"^.*$\" | |
319 | KEY specifies the part of each record (ie each match for RECORD-REGEXP) | |
320 | is to be used for sorting. | |
321 | If it is \"\\digit\" then the digit'th \"\\(...\\)\" match field from | |
322 | RECORD-REGEXP is used. | |
323 | If it is \"\\&\" then the whole record is used. | |
324 | Otherwise, it is a regular-expression for which to search within the record. | |
325 | If a match for KEY is not found within a record then that record is ignored. | |
326 | ||
327 | With a negative prefix arg sorts in reverse order. | |
328 | ||
329 | For example: to sort lines in the region by the first word on each line | |
330 | starting with the letter \"f\", | |
331 | RECORD-REGEXP would be \"^.*$\" and KEY would be \"\\=\\<f\\w*\\>\"" | |
2af3a0e3 | 332 | ;; using negative prefix arg to mean "reverse" is now inconsistent with |
333 | ;; other sort-.*fields functions but then again this was before, since it | |
334 | ;; didn't use the magnitude of the arg to specify anything. | |
d32200ac RS |
335 | (interactive "P\nsRegexp specifying records to sort: |
336 | sRegexp specifying key within record: \nr") | |
337 | (cond ((or (equal key-regexp "") (equal key-regexp "\\&")) | |
338 | (setq key-regexp 0)) | |
339 | ((string-match "\\`\\\\[1-9]\\'" key-regexp) | |
340 | (setq key-regexp (- (aref key-regexp 1) ?0)))) | |
341 | (save-excursion | |
342 | (save-restriction | |
343 | (narrow-to-region beg end) | |
344 | (goto-char (point-min)) | |
345 | (let (sort-regexp-record-end) ;isn't dynamic scoping wonderful? | |
346 | (re-search-forward record-regexp) | |
347 | (setq sort-regexp-record-end (point)) | |
348 | (goto-char (match-beginning 0)) | |
349 | (sort-subr reverse | |
350 | (function (lambda () | |
351 | (and (re-search-forward record-regexp nil 'move) | |
352 | (setq sort-regexp-record-end (match-end 0)) | |
353 | (goto-char (match-beginning 0))))) | |
354 | (function (lambda () | |
355 | (goto-char sort-regexp-record-end))) | |
356 | (function (lambda () | |
357 | (let ((n 0)) | |
358 | (cond ((numberp key-regexp) | |
359 | (setq n key-regexp)) | |
360 | ((re-search-forward | |
361 | key-regexp sort-regexp-record-end t) | |
362 | (setq n 0)) | |
363 | (t (throw 'key nil))) | |
364 | (condition-case () | |
365 | (if (fboundp 'buffer-substring-lessp) | |
366 | (cons (match-beginning n) | |
367 | (match-end n)) | |
368 | (buffer-substring (match-beginning n) | |
369 | (match-end n))) | |
370 | ;; if there was no such register | |
371 | (error (throw 'key nil))))))))))) | |
372 | ||
373 | \f | |
374 | (defvar sort-columns-subprocess t) | |
375 | ||
f9f9507e | 376 | ;;;###autoload |
d32200ac RS |
377 | (defun sort-columns (reverse &optional beg end) |
378 | "Sort lines in region alphabetically by a certain range of columns. | |
379 | For the purpose of this command, the region includes | |
380 | the entire line that point is in and the entire line the mark is in. | |
381 | The column positions of point and mark bound the range of columns to sort on. | |
382 | A prefix argument means sort into reverse order. | |
383 | ||
384 | Note that `sort-columns' rejects text that contains tabs, | |
385 | because tabs could be split across the specified columns | |
386 | and it doesn't know how to handle that. Also, when possible, | |
387 | it uses the `sort' utility program, which doesn't understand tabs. | |
388 | Use \\[untabify] to convert tabs to spaces before sorting." | |
389 | (interactive "P\nr") | |
390 | (save-excursion | |
391 | (let (beg1 end1 col-beg1 col-end1 col-start col-end) | |
392 | (goto-char (min beg end)) | |
393 | (setq col-beg1 (current-column)) | |
394 | (beginning-of-line) | |
395 | (setq beg1 (point)) | |
396 | (goto-char (max beg end)) | |
397 | (setq col-end1 (current-column)) | |
398 | (forward-line) | |
399 | (setq end1 (point)) | |
400 | (setq col-start (min col-beg1 col-end1)) | |
401 | (setq col-end (max col-beg1 col-end1)) | |
402 | (if (search-backward "\t" beg1 t) | |
403 | (error "sort-columns does not work with tabs. Use M-x untabify.")) | |
404 | (if (not (eq system-type 'vax-vms)) | |
405 | ;; Use the sort utility if we can; it is 4 times as fast. | |
406 | (call-process-region beg1 end1 "sort" t t nil | |
407 | (if reverse "-rt\n" "-t\n") | |
408 | (concat "+0." col-start) | |
409 | (concat "-0." col-end)) | |
410 | ;; On VMS, use Emacs's own facilities. | |
411 | (save-excursion | |
412 | (save-restriction | |
413 | (narrow-to-region beg1 end1) | |
414 | (goto-char beg1) | |
415 | (sort-subr reverse 'forward-line 'end-of-line | |
416 | (function (lambda () (move-to-column col-start) nil)) | |
417 | (function (lambda () (move-to-column col-end) nil))))))))) | |
2af3a0e3 | 418 | |
f9f9507e | 419 | ;;;###autoload |
2af3a0e3 | 420 | (defun reverse-region (beg end) |
421 | "Reverse the order of lines in a region. | |
422 | From a program takes two point or marker arguments, BEG and END." | |
423 | (interactive "r") | |
424 | (if (> beg end) | |
425 | (let (mid) (setq mid end end beg beg mid))) | |
426 | (save-excursion | |
427 | ;; put beg at the start of a line and end and the end of one -- | |
428 | ;; the largest possible region which fits this criteria | |
429 | (goto-char beg) | |
430 | (or (bolp) (forward-line 1)) | |
431 | (setq beg (point)) | |
432 | (goto-char end) | |
433 | ;; the test for bolp is for those times when end is on an empty line; | |
434 | ;; it is probably not the case that the line should be included in the | |
435 | ;; reversal; it isn't difficult to add it afterward. | |
436 | (or (and (eolp) (not (bolp))) (progn (forward-line -1) (end-of-line))) | |
437 | (setq end (point-marker)) | |
438 | ;; the real work. this thing cranks through memory on large regions. | |
439 | (let (ll (do t)) | |
440 | (while do | |
441 | (goto-char beg) | |
442 | (setq ll (cons (buffer-substring (point) (progn (end-of-line) (point))) | |
443 | ll)) | |
444 | (setq do (/= (point) end)) | |
445 | (delete-region beg (if do (1+ (point)) (point)))) | |
446 | (while (cdr ll) | |
447 | (insert (car ll) "\n") | |
448 | (setq ll (cdr ll))) | |
449 | (insert (car ll))))) | |
49116ac0 JB |
450 | |
451 | (provide 'sort) | |
452 | ||
c88ab9ce | 453 | ;;; sort.el ends here |