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