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