Commit | Line | Data |
---|---|---|
0b2974ab | 1 | ;;; ring.el --- handle rings of items |
c88ab9ce | 2 | |
d59c3137 | 3 | ;; Copyright (C) 1992, 2001, 2002, 2003, 2004, 2005, |
114f9c96 | 4 | ;; 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. |
3a801d0c | 5 | |
fd7fa35a | 6 | ;; Maintainer: FSF |
fd7fa35a ER |
7 | ;; Keywords: extensions |
8 | ||
c88ab9ce ER |
9 | ;; This file is part of GNU Emacs. |
10 | ||
d6cba7ae | 11 | ;; GNU Emacs is free software: you can redistribute it and/or modify |
c88ab9ce | 12 | ;; it under the terms of the GNU General Public License as published by |
d6cba7ae GM |
13 | ;; the Free Software Foundation, either version 3 of the License, or |
14 | ;; (at your option) any later version. | |
c88ab9ce ER |
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 | |
d6cba7ae | 22 | ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. |
c88ab9ce | 23 | |
fd7fa35a ER |
24 | ;;; Commentary: |
25 | ||
2356fa8a | 26 | ;; This code defines a ring data structure. A ring is a |
7263dc56 | 27 | ;; (hd-index length . vector) |
14b6a8e1 | 28 | ;; list. You can insert to, remove from, and rotate a ring. When the ring |
b578f267 EN |
29 | ;; fills up, insertions cause the oldest elts to be quietly dropped. |
30 | ;; | |
31 | ;; In ring-ref, 0 is the index of the newest element. Higher indexes | |
14b6a8e1 RS |
32 | ;; correspond to older elements; when the index equals the ring length, |
33 | ;; it wraps to the newest element again. | |
b578f267 | 34 | ;; |
14b6a8e1 RS |
35 | ;; hd-index = vector index of the oldest ring item. |
36 | ;; Newer items follow this item; at the end of the vector, | |
7263dc56 | 37 | ;; they wrap around to the start of the vector. |
14b6a8e1 | 38 | ;; length = number of items currently in the ring. |
7263dc56 | 39 | ;; This never exceeds the length of the vector itself. |
b578f267 EN |
40 | ;; |
41 | ;; These functions are used by the input history mechanism, but they can | |
42 | ;; be used for other purposes as well. | |
67ea382e | 43 | |
fd7fa35a ER |
44 | ;;; Code: |
45 | ||
7263dc56 RS |
46 | ;;; User Functions: |
47 | ||
73183f2b | 48 | ;;;###autoload |
7263dc56 | 49 | (defun ring-p (x) |
2356fa8a | 50 | "Return t if X is a ring; nil otherwise." |
67ea382e | 51 | (and (consp x) (integerp (car x)) |
efb67a5e JB |
52 | (consp (cdr x)) (integerp (cadr x)) |
53 | (vectorp (cddr x)))) | |
67ea382e | 54 | |
73183f2b | 55 | ;;;###autoload |
67ea382e | 56 | (defun make-ring (size) |
41dc743d | 57 | "Make a ring that can contain SIZE elements." |
d3af54ac | 58 | (cons 0 (cons 0 (make-vector size nil)))) |
67ea382e | 59 | |
9c545670 | 60 | (defun ring-insert-at-beginning (ring item) |
efb67a5e JB |
61 | "Add to RING the item ITEM, at the front, as the oldest item." |
62 | (let* ((vec (cddr ring)) | |
7263dc56 RS |
63 | (veclen (length vec)) |
64 | (hd (car ring)) | |
efb67a5e | 65 | (ln (cadr ring))) |
9c545670 | 66 | (setq ln (min veclen (1+ ln)) |
7263dc56 | 67 | hd (ring-minus1 hd veclen)) |
9c545670 RS |
68 | (aset vec hd item) |
69 | (setcar ring hd) | |
70 | (setcar (cdr ring) ln))) | |
71 | ||
67ea382e | 72 | (defun ring-plus1 (index veclen) |
2356fa8a | 73 | "Return INDEX+1, with wraparound." |
efb67a5e | 74 | (let ((new-index (1+ index))) |
67ea382e DL |
75 | (if (= new-index veclen) 0 new-index))) |
76 | ||
77 | (defun ring-minus1 (index veclen) | |
2356fa8a | 78 | "Return INDEX-1, with wraparound." |
efb67a5e | 79 | (- (if (zerop index) veclen index) 1)) |
67ea382e DL |
80 | |
81 | (defun ring-length (ring) | |
2356fa8a | 82 | "Return the number of elements in the RING." |
efb67a5e | 83 | (cadr ring)) |
67ea382e | 84 | |
d3af54ac | 85 | (defun ring-index (index head ringlen veclen) |
2356fa8a | 86 | "Convert nominal ring index INDEX to an internal index. |
7263dc56 RS |
87 | The internal index refers to the items ordered from newest to oldest. |
88 | HEAD is the index of the oldest element in the ring. | |
89 | RINGLEN is the number of elements currently in the ring. | |
90 | VECLEN is the size of the vector in the ring." | |
2ec5af11 PE |
91 | (setq index (mod index ringlen)) |
92 | (mod (1- (+ head (- ringlen index))) veclen)) | |
67ea382e | 93 | |
7263dc56 | 94 | (defun ring-empty-p (ring) |
2356fa8a | 95 | "Return t if RING is empty; nil otherwise." |
efb67a5e | 96 | (zerop (cadr ring))) |
7263dc56 RS |
97 | |
98 | (defun ring-size (ring) | |
2356fa8a | 99 | "Return the size of RING, the maximum number of elements it can contain." |
efb67a5e | 100 | (length (cddr ring))) |
7263dc56 RS |
101 | |
102 | (defun ring-copy (ring) | |
2356fa8a | 103 | "Return a copy of RING." |
efb67a5e JB |
104 | (let ((vec (cddr ring)) |
105 | (hd (car ring)) | |
106 | (ln (cadr ring))) | |
7263dc56 RS |
107 | (cons hd (cons ln (copy-sequence vec))))) |
108 | ||
67ea382e | 109 | (defun ring-insert (ring item) |
9c545670 | 110 | "Insert onto ring RING the item ITEM, as the newest (last) item. |
7263dc56 | 111 | If the ring is full, dump the oldest item to make room." |
efb67a5e | 112 | (let* ((vec (cddr ring)) |
7263dc56 RS |
113 | (veclen (length vec)) |
114 | (hd (car ring)) | |
efb67a5e | 115 | (ln (cadr ring))) |
d3af54ac | 116 | (prog1 |
7263dc56 | 117 | (aset vec (mod (+ hd ln) veclen) item) |
d3af54ac | 118 | (if (= ln veclen) |
7263dc56 RS |
119 | (setcar ring (ring-plus1 hd veclen)) |
120 | (setcar (cdr ring) (1+ ln)))))) | |
d3af54ac ER |
121 | |
122 | (defun ring-remove (ring &optional index) | |
123 | "Remove an item from the RING. Return the removed item. | |
124 | If optional INDEX is nil, remove the oldest item. If it's | |
125 | numeric, remove the element indexed." | |
126 | (if (ring-empty-p ring) | |
127 | (error "Ring empty") | |
128 | (let* ((hd (car ring)) | |
efb67a5e JB |
129 | (ln (cadr ring)) |
130 | (vec (cddr ring)) | |
7263dc56 RS |
131 | (veclen (length vec)) |
132 | (tl (mod (1- (+ hd ln)) veclen)) | |
133 | oldelt) | |
efb67a5e JB |
134 | (when (null index) |
135 | (setq index (1- ln))) | |
d3af54ac ER |
136 | (setq index (ring-index index hd ln veclen)) |
137 | (setq oldelt (aref vec index)) | |
138 | (while (/= index tl) | |
7263dc56 RS |
139 | (aset vec index (aref vec (ring-plus1 index veclen))) |
140 | (setq index (ring-plus1 index veclen))) | |
d3af54ac ER |
141 | (aset vec tl nil) |
142 | (setcar (cdr ring) (1- ln)) | |
143 | oldelt))) | |
67ea382e | 144 | |
67ea382e | 145 | (defun ring-ref (ring index) |
2356fa8a | 146 | "Return RING's INDEX element. |
14b6a8e1 RS |
147 | INDEX = 0 is the most recently inserted; higher indices |
148 | correspond to older elements. | |
b27c6995 | 149 | INDEX need not be <= the ring length; the appropriate modulo operation |
14b6a8e1 | 150 | will be performed." |
d3af54ac | 151 | (if (ring-empty-p ring) |
14b6a8e1 | 152 | (error "Accessing an empty ring") |
efb67a5e JB |
153 | (let ((hd (car ring)) |
154 | (ln (cadr ring)) | |
155 | (vec (cddr ring))) | |
d3af54ac | 156 | (aref vec (ring-index index hd ln (length vec)))))) |
c88ab9ce | 157 | |
6a475c99 | 158 | (defun ring-elements (ring) |
7f72ddd5 LT |
159 | "Return a list of the elements of RING, in order, newest first." |
160 | (let ((start (car ring)) | |
161 | (size (ring-size ring)) | |
162 | (vect (cddr ring)) | |
163 | lst) | |
164 | (dotimes (var (cadr ring) lst) | |
165 | (push (aref vect (mod (+ start var) size)) lst)))) | |
6a475c99 | 166 | |
0fbd1f76 | 167 | (defun ring-member (ring item) |
efb67a5e JB |
168 | "Return index of ITEM if on RING, else nil. |
169 | Comparison is done via `equal'. The index is 0-based." | |
170 | (catch 'found | |
171 | (dotimes (ind (ring-length ring) nil) | |
172 | (when (equal item (ring-ref ring ind)) | |
173 | (throw 'found ind))))) | |
0fbd1f76 RS |
174 | |
175 | (defun ring-next (ring item) | |
176 | "Return the next item in the RING, after ITEM. | |
177 | Raise error if ITEM is not in the RING." | |
178 | (let ((curr-index (ring-member ring item))) | |
179 | (unless curr-index (error "Item is not in the ring: `%s'" item)) | |
180 | (ring-ref ring (ring-plus1 curr-index (ring-length ring))))) | |
181 | ||
182 | (defun ring-previous (ring item) | |
183 | "Return the previous item in the RING, before ITEM. | |
184 | Raise error if ITEM is not in the RING." | |
185 | (let ((curr-index (ring-member ring item))) | |
186 | (unless curr-index (error "Item is not in the ring: `%s'" item)) | |
187 | (ring-ref ring (ring-minus1 curr-index (ring-length ring))))) | |
188 | ||
189 | (defun ring-insert+extend (ring item &optional grow-p) | |
efb67a5e | 190 | "Like `ring-insert', but if GROW-P is non-nil, then enlarge ring. |
0fbd1f76 RS |
191 | Insert onto ring RING the item ITEM, as the newest (last) item. |
192 | If the ring is full, behavior depends on GROW-P: | |
193 | If GROW-P is non-nil, enlarge the ring to accommodate the new item. | |
194 | If GROW-P is nil, dump the oldest item to make room for the new." | |
efb67a5e | 195 | (let* ((vec (cddr ring)) |
0fbd1f76 RS |
196 | (veclen (length vec)) |
197 | (hd (car ring)) | |
198 | (ringlen (ring-length ring))) | |
199 | (prog1 | |
200 | (cond ((and grow-p (= ringlen veclen)) ; Full ring. Enlarge it. | |
201 | (setq veclen (1+ veclen)) | |
202 | (setcdr ring (cons (setq ringlen (1+ ringlen)) | |
203 | (setq vec (vconcat vec (vector item))))) | |
204 | (setcar ring hd)) | |
205 | (t (aset vec (mod (+ hd ringlen) veclen) item))) | |
206 | (if (= ringlen veclen) | |
207 | (setcar ring (ring-plus1 hd veclen)) | |
208 | (setcar (cdr ring) (1+ ringlen)))))) | |
209 | ||
210 | (defun ring-remove+insert+extend (ring item &optional grow-p) | |
211 | "`ring-remove' ITEM from RING, then `ring-insert+extend' it. | |
212 | This ensures that there is only one ITEM on RING. | |
213 | ||
214 | If the RING is full, behavior depends on GROW-P: | |
215 | If GROW-P is non-nil, enlarge the ring to accommodate the new ITEM. | |
216 | If GROW-P is nil, dump the oldest item to make room for the new." | |
217 | (let (ind) | |
efb67a5e JB |
218 | (while (setq ind (ring-member ring item)) |
219 | (ring-remove ring ind))) | |
0fbd1f76 RS |
220 | (ring-insert+extend ring item grow-p)) |
221 | ||
222 | (defun ring-convert-sequence-to-ring (seq) | |
223 | "Convert sequence SEQ to a ring. Return the ring. | |
224 | If SEQ is already a ring, return it." | |
225 | (if (ring-p seq) | |
226 | seq | |
227 | (let* ((size (length seq)) | |
efb67a5e JB |
228 | (ring (make-ring size))) |
229 | (dotimes (count size) | |
230 | (when (or (ring-empty-p ring) | |
231 | (not (equal (ring-ref ring 0) (elt seq count)))) | |
232 | (ring-insert-at-beginning ring (elt seq count)))) | |
0fbd1f76 RS |
233 | ring))) |
234 | ||
7263dc56 RS |
235 | ;;; provide ourself: |
236 | ||
41dc743d ER |
237 | (provide 'ring) |
238 | ||
cbee283d | 239 | ;; arch-tag: e707682b-ed69-47c9-b20f-cf2c68cc92d2 |
c88ab9ce | 240 | ;;; ring.el ends here |