Commit | Line | Data |
---|---|---|
eec82323 | 1 | ;;; gnus-range.el --- range and sequence functions for Gnus |
16409b0b GM |
2 | |
3 | ;; Copyright (C) 1996, 1997, 1998, 1999, 2000 Free Software Foundation, Inc. | |
eec82323 | 4 | |
6748645f | 5 | ;; Author: Lars Magne Ingebrigtsen <larsi@gnus.org> |
eec82323 LMI |
6 | ;; Keywords: news |
7 | ||
8 | ;; This file is part of GNU Emacs. | |
9 | ||
10 | ;; GNU Emacs is free software; you can redistribute it and/or modify | |
11 | ;; it under the terms of the GNU General Public License as published by | |
12 | ;; the Free Software Foundation; either version 2, or (at your option) | |
13 | ;; any later version. | |
14 | ||
15 | ;; GNU Emacs is distributed in the hope that it will be useful, | |
16 | ;; but WITHOUT ANY WARRANTY; without even the implied warranty of | |
17 | ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
18 | ;; GNU General Public License for more details. | |
19 | ||
20 | ;; You should have received a copy of the GNU General Public License | |
21 | ;; along with GNU Emacs; see the file COPYING. If not, write to the | |
22 | ;; Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
23 | ;; Boston, MA 02111-1307, USA. | |
24 | ||
25 | ;;; Commentary: | |
26 | ||
27 | ;;; Code: | |
28 | ||
7df7482d RS |
29 | (eval-when-compile (require 'cl)) |
30 | ||
eec82323 LMI |
31 | ;;; List and range functions |
32 | ||
33 | (defun gnus-last-element (list) | |
34 | "Return last element of LIST." | |
35 | (while (cdr list) | |
36 | (setq list (cdr list))) | |
37 | (car list)) | |
38 | ||
39 | (defun gnus-copy-sequence (list) | |
40 | "Do a complete, total copy of a list." | |
41 | (let (out) | |
42 | (while (consp list) | |
43 | (if (consp (car list)) | |
44 | (push (gnus-copy-sequence (pop list)) out) | |
45 | (push (pop list) out))) | |
46 | (if list | |
47 | (nconc (nreverse out) list) | |
48 | (nreverse out)))) | |
49 | ||
50 | (defun gnus-set-difference (list1 list2) | |
51 | "Return a list of elements of LIST1 that do not appear in LIST2." | |
52 | (let ((list1 (copy-sequence list1))) | |
53 | (while list2 | |
54 | (setq list1 (delq (car list2) list1)) | |
55 | (setq list2 (cdr list2))) | |
56 | list1)) | |
57 | ||
58 | (defun gnus-sorted-complement (list1 list2) | |
6748645f | 59 | "Return a list of elements that are in LIST1 or LIST2 but not both. |
eec82323 LMI |
60 | Both lists have to be sorted over <." |
61 | (let (out) | |
62 | (if (or (null list1) (null list2)) | |
63 | (or list1 list2) | |
64 | (while (and list1 list2) | |
65 | (cond ((= (car list1) (car list2)) | |
66 | (setq list1 (cdr list1) | |
67 | list2 (cdr list2))) | |
68 | ((< (car list1) (car list2)) | |
69 | (setq out (cons (car list1) out)) | |
70 | (setq list1 (cdr list1))) | |
71 | (t | |
72 | (setq out (cons (car list2) out)) | |
73 | (setq list2 (cdr list2))))) | |
74 | (nconc (nreverse out) (or list1 list2))))) | |
75 | ||
76 | (defun gnus-intersection (list1 list2) | |
77 | (let ((result nil)) | |
78 | (while list2 | |
79 | (when (memq (car list2) list1) | |
80 | (setq result (cons (car list2) result))) | |
81 | (setq list2 (cdr list2))) | |
82 | result)) | |
83 | ||
84 | (defun gnus-sorted-intersection (list1 list2) | |
85 | ;; LIST1 and LIST2 have to be sorted over <. | |
86 | (let (out) | |
87 | (while (and list1 list2) | |
88 | (cond ((= (car list1) (car list2)) | |
89 | (setq out (cons (car list1) out) | |
90 | list1 (cdr list1) | |
91 | list2 (cdr list2))) | |
92 | ((< (car list1) (car list2)) | |
93 | (setq list1 (cdr list1))) | |
94 | (t | |
95 | (setq list2 (cdr list2))))) | |
96 | (nreverse out))) | |
97 | ||
98 | (defun gnus-set-sorted-intersection (list1 list2) | |
99 | ;; LIST1 and LIST2 have to be sorted over <. | |
100 | ;; This function modifies LIST1. | |
101 | (let* ((top (cons nil list1)) | |
102 | (prev top)) | |
103 | (while (and list1 list2) | |
104 | (cond ((= (car list1) (car list2)) | |
105 | (setq prev list1 | |
106 | list1 (cdr list1) | |
107 | list2 (cdr list2))) | |
108 | ((< (car list1) (car list2)) | |
109 | (setcdr prev (cdr list1)) | |
110 | (setq list1 (cdr list1))) | |
111 | (t | |
112 | (setq list2 (cdr list2))))) | |
113 | (setcdr prev nil) | |
114 | (cdr top))) | |
115 | ||
116 | (defun gnus-compress-sequence (numbers &optional always-list) | |
117 | "Convert list of numbers to a list of ranges or a single range. | |
118 | If ALWAYS-LIST is non-nil, this function will always release a list of | |
119 | ranges." | |
120 | (let* ((first (car numbers)) | |
121 | (last (car numbers)) | |
122 | result) | |
123 | (if (null numbers) | |
124 | nil | |
125 | (if (not (listp (cdr numbers))) | |
126 | numbers | |
127 | (while numbers | |
128 | (cond ((= last (car numbers)) nil) ;Omit duplicated number | |
129 | ((= (1+ last) (car numbers)) ;Still in sequence | |
130 | (setq last (car numbers))) | |
131 | (t ;End of one sequence | |
132 | (setq result | |
133 | (cons (if (= first last) first | |
134 | (cons first last)) | |
135 | result)) | |
136 | (setq first (car numbers)) | |
137 | (setq last (car numbers)))) | |
138 | (setq numbers (cdr numbers))) | |
139 | (if (and (not always-list) (null result)) | |
140 | (if (= first last) (list first) (cons first last)) | |
141 | (nreverse (cons (if (= first last) first (cons first last)) | |
142 | result))))))) | |
143 | ||
144 | (defalias 'gnus-uncompress-sequence 'gnus-uncompress-range) | |
145 | (defun gnus-uncompress-range (ranges) | |
146 | "Expand a list of ranges into a list of numbers. | |
147 | RANGES is either a single range on the form `(num . num)' or a list of | |
148 | these ranges." | |
149 | (let (first last result) | |
150 | (cond | |
151 | ((null ranges) | |
152 | nil) | |
153 | ((not (listp (cdr ranges))) | |
154 | (setq first (car ranges)) | |
155 | (setq last (cdr ranges)) | |
156 | (while (<= first last) | |
157 | (setq result (cons first result)) | |
158 | (setq first (1+ first))) | |
159 | (nreverse result)) | |
160 | (t | |
161 | (while ranges | |
162 | (if (atom (car ranges)) | |
163 | (when (numberp (car ranges)) | |
164 | (setq result (cons (car ranges) result))) | |
165 | (setq first (caar ranges)) | |
166 | (setq last (cdar ranges)) | |
167 | (while (<= first last) | |
168 | (setq result (cons first result)) | |
169 | (setq first (1+ first)))) | |
170 | (setq ranges (cdr ranges))) | |
171 | (nreverse result))))) | |
172 | ||
173 | (defun gnus-add-to-range (ranges list) | |
174 | "Return a list of ranges that has all articles from both RANGES and LIST. | |
175 | Note: LIST has to be sorted over `<'." | |
176 | (if (not ranges) | |
177 | (gnus-compress-sequence list t) | |
178 | (setq list (copy-sequence list)) | |
179 | (unless (listp (cdr ranges)) | |
180 | (setq ranges (list ranges))) | |
181 | (let ((out ranges) | |
182 | ilist lowest highest temp) | |
183 | (while (and ranges list) | |
184 | (setq ilist list) | |
185 | (setq lowest (or (and (atom (car ranges)) (car ranges)) | |
186 | (caar ranges))) | |
187 | (while (and list (cdr list) (< (cadr list) lowest)) | |
188 | (setq list (cdr list))) | |
189 | (when (< (car ilist) lowest) | |
190 | (setq temp list) | |
191 | (setq list (cdr list)) | |
192 | (setcdr temp nil) | |
193 | (setq out (nconc (gnus-compress-sequence ilist t) out))) | |
194 | (setq highest (or (and (atom (car ranges)) (car ranges)) | |
195 | (cdar ranges))) | |
196 | (while (and list (<= (car list) highest)) | |
197 | (setq list (cdr list))) | |
198 | (setq ranges (cdr ranges))) | |
199 | (when list | |
200 | (setq out (nconc (gnus-compress-sequence list t) out))) | |
201 | (setq out (sort out (lambda (r1 r2) | |
202 | (< (or (and (atom r1) r1) (car r1)) | |
203 | (or (and (atom r2) r2) (car r2)))))) | |
204 | (setq ranges out) | |
205 | (while ranges | |
206 | (if (atom (car ranges)) | |
207 | (when (cdr ranges) | |
208 | (if (atom (cadr ranges)) | |
209 | (when (= (1+ (car ranges)) (cadr ranges)) | |
210 | (setcar ranges (cons (car ranges) | |
211 | (cadr ranges))) | |
212 | (setcdr ranges (cddr ranges))) | |
a8151ef7 | 213 | (when (= (1+ (car ranges)) (caadr ranges)) |
eec82323 LMI |
214 | (setcar (cadr ranges) (car ranges)) |
215 | (setcar ranges (cadr ranges)) | |
216 | (setcdr ranges (cddr ranges))))) | |
217 | (when (cdr ranges) | |
218 | (if (atom (cadr ranges)) | |
219 | (when (= (1+ (cdar ranges)) (cadr ranges)) | |
220 | (setcdr (car ranges) (cadr ranges)) | |
221 | (setcdr ranges (cddr ranges))) | |
a8151ef7 LMI |
222 | (when (= (1+ (cdar ranges)) (caadr ranges)) |
223 | (setcdr (car ranges) (cdadr ranges)) | |
eec82323 LMI |
224 | (setcdr ranges (cddr ranges)))))) |
225 | (setq ranges (cdr ranges))) | |
226 | out))) | |
227 | ||
16409b0b GM |
228 | (defun gnus-remove-from-range (range1 range2) |
229 | "Return a range that has all articles from RANGE2 removed from RANGE1. | |
230 | The returned range is always a list. RANGE2 can also be a unsorted | |
231 | list of articles. RANGE1 is modified by side effects, RANGE2 is not | |
232 | modified." | |
233 | (if (or (null range1) (null range2)) | |
234 | range1 | |
235 | (let (out r1 r2 r1_min r1_max r2_min r2_max | |
236 | (range2 (gnus-copy-sequence range2))) | |
237 | (setq range1 (if (listp (cdr range1)) range1 (list range1)) | |
238 | range2 (sort (if (listp (cdr range2)) range2 (list range2)) | |
239 | (lambda (e1 e2) | |
240 | (< (if (consp e1) (car e1) e1) | |
241 | (if (consp e2) (car e2) e2)))) | |
242 | r1 (car range1) | |
243 | r2 (car range2) | |
244 | r1_min (if (consp r1) (car r1) r1) | |
245 | r1_max (if (consp r1) (cdr r1) r1) | |
246 | r2_min (if (consp r2) (car r2) r2) | |
247 | r2_max (if (consp r2) (cdr r2) r2)) | |
248 | (while (and range1 range2) | |
249 | (cond ((< r2_max r1_min) ; r2 < r1 | |
250 | (pop range2) | |
251 | (setq r2 (car range2) | |
252 | r2_min (if (consp r2) (car r2) r2) | |
253 | r2_max (if (consp r2) (cdr r2) r2))) | |
254 | ((and (<= r2_min r1_min) (<= r1_max r2_max)) ; r2 overlap r1 | |
255 | (pop range1) | |
256 | (setq r1 (car range1) | |
257 | r1_min (if (consp r1) (car r1) r1) | |
258 | r1_max (if (consp r1) (cdr r1) r1))) | |
259 | ((and (<= r2_min r1_min) (<= r2_max r1_max)) ; r2 overlap min r1 | |
260 | (pop range2) | |
261 | (setq r1_min (1+ r2_max) | |
262 | r2 (car range2) | |
263 | r2_min (if (consp r2) (car r2) r2) | |
264 | r2_max (if (consp r2) (cdr r2) r2))) | |
265 | ((and (<= r1_min r2_min) (<= r2_max r1_max)) ; r2 contained in r1 | |
266 | (if (eq r1_min (1- r2_min)) | |
267 | (push r1_min out) | |
268 | (push (cons r1_min (1- r2_min)) out)) | |
269 | (pop range2) | |
270 | (if (< r2_max r1_max) ; finished with r1? | |
271 | (setq r1_min (1+ r2_max)) | |
272 | (pop range1) | |
273 | (setq r1 (car range1) | |
274 | r1_min (if (consp r1) (car r1) r1) | |
275 | r1_max (if (consp r1) (cdr r1) r1))) | |
276 | (setq r2 (car range2) | |
277 | r2_min (if (consp r2) (car r2) r2) | |
278 | r2_max (if (consp r2) (cdr r2) r2))) | |
279 | ((and (<= r2_min r1_max) (<= r1_max r2_max)) ; r2 overlap max r1 | |
280 | (if (eq r1_min (1- r2_min)) | |
281 | (push r1_min out) | |
282 | (push (cons r1_min (1- r2_min)) out)) | |
283 | (pop range1) | |
284 | (setq r1 (car range1) | |
285 | r1_min (if (consp r1) (car r1) r1) | |
286 | r1_max (if (consp r1) (cdr r1) r1))) | |
287 | ((< r1_max r2_min) ; r2 > r1 | |
288 | (pop range1) | |
289 | (if (eq r1_min r1_max) | |
290 | (push r1_min out) | |
291 | (push (cons r1_min r1_max) out)) | |
292 | (setq r1 (car range1) | |
293 | r1_min (if (consp r1) (car r1) r1) | |
294 | r1_max (if (consp r1) (cdr r1) r1))))) | |
295 | (when r1 | |
296 | (if (eq r1_min r1_max) | |
297 | (push r1_min out) | |
298 | (push (cons r1_min r1_max) out)) | |
299 | (pop range1)) | |
300 | (while range1 | |
301 | (push (pop range1) out)) | |
302 | (nreverse out)))) | |
eec82323 LMI |
303 | |
304 | (defun gnus-member-of-range (number ranges) | |
305 | (if (not (listp (cdr ranges))) | |
306 | (and (>= number (car ranges)) | |
307 | (<= number (cdr ranges))) | |
308 | (let ((not-stop t)) | |
309 | (while (and ranges | |
310 | (if (numberp (car ranges)) | |
311 | (>= number (car ranges)) | |
312 | (>= number (caar ranges))) | |
313 | not-stop) | |
314 | (when (if (numberp (car ranges)) | |
315 | (= number (car ranges)) | |
316 | (and (>= number (caar ranges)) | |
317 | (<= number (cdar ranges)))) | |
318 | (setq not-stop nil)) | |
319 | (setq ranges (cdr ranges))) | |
320 | (not not-stop)))) | |
321 | ||
322 | (defun gnus-range-length (range) | |
323 | "Return the length RANGE would have if uncompressed." | |
324 | (length (gnus-uncompress-range range))) | |
325 | ||
326 | (defun gnus-sublist-p (list sublist) | |
327 | "Test whether all elements in SUBLIST are members of LIST." | |
328 | (let ((sublistp t)) | |
329 | (while sublist | |
330 | (unless (memq (pop sublist) list) | |
331 | (setq sublistp nil | |
332 | sublist nil))) | |
333 | sublistp)) | |
334 | ||
335 | (defun gnus-range-add (range1 range2) | |
16409b0b GM |
336 | "Add RANGE2 to RANGE1 (nondestructively)." |
337 | (unless (listp (cdr range1)) | |
338 | (setq range1 (list range1))) | |
339 | (unless (listp (cdr range2)) | |
340 | (setq range2 (list range2))) | |
341 | (let ((item1 (pop range1)) | |
342 | (item2 (pop range2)) | |
343 | range item selector) | |
344 | (while (or item1 item2) | |
345 | (setq selector | |
a1506d29 | 346 | (cond |
16409b0b GM |
347 | ((null item1) nil) |
348 | ((null item2) t) | |
349 | ((and (numberp item1) (numberp item2)) (< item1 item2)) | |
350 | ((numberp item1) (< item1 (car item2))) | |
351 | ((numberp item2) (< (car item1) item2)) | |
352 | (t (< (car item1) (car item2))))) | |
353 | (setq item | |
354 | (or | |
355 | (let ((tmp1 item) (tmp2 (if selector item1 item2))) | |
a1506d29 | 356 | (cond |
16409b0b GM |
357 | ((null tmp1) tmp2) |
358 | ((null tmp2) tmp1) | |
359 | ((and (numberp tmp1) (numberp tmp2)) | |
a1506d29 | 360 | (cond |
16409b0b GM |
361 | ((eq tmp1 tmp2) tmp1) |
362 | ((eq (1+ tmp1) tmp2) (cons tmp1 tmp2)) | |
363 | ((eq (1+ tmp2) tmp1) (cons tmp2 tmp1)) | |
364 | (t nil))) | |
365 | ((numberp tmp1) | |
a1506d29 | 366 | (cond |
16409b0b GM |
367 | ((and (>= tmp1 (car tmp2)) (<= tmp1 (cdr tmp2))) tmp2) |
368 | ((eq (1+ tmp1) (car tmp2)) (cons tmp1 (cdr tmp2))) | |
369 | ((eq (1- tmp1) (cdr tmp2)) (cons (car tmp2) tmp1)) | |
370 | (t nil))) | |
371 | ((numberp tmp2) | |
a1506d29 | 372 | (cond |
16409b0b GM |
373 | ((and (>= tmp2 (car tmp1)) (<= tmp2 (cdr tmp1))) tmp1) |
374 | ((eq (1+ tmp2) (car tmp1)) (cons tmp2 (cdr tmp1))) | |
375 | ((eq (1- tmp2) (cdr tmp1)) (cons (car tmp1) tmp2)) | |
376 | (t nil))) | |
377 | ((< (1+ (cdr tmp1)) (car tmp2)) nil) | |
378 | ((< (1+ (cdr tmp2)) (car tmp1)) nil) | |
a1506d29 | 379 | (t (cons (min (car tmp1) (car tmp2)) |
16409b0b GM |
380 | (max (cdr tmp1) (cdr tmp2)))))) |
381 | (progn | |
382 | (if item (push item range)) | |
383 | (if selector item1 item2)))) | |
384 | (if selector | |
385 | (setq item1 (pop range1)) | |
386 | (setq item2 (pop range2)))) | |
387 | (if item (push item range)) | |
388 | (reverse range))) | |
eec82323 LMI |
389 | |
390 | (provide 'gnus-range) | |
391 | ||
ab5796a9 | 392 | ;;; arch-tag: 4780bdd8-5a15-4aff-be28-18727895b6ad |
eec82323 | 393 | ;;; gnus-range.el ends here |