Commit | Line | Data |
---|---|---|
0b2974ab | 1 | ;;; ring.el --- handle rings of items |
c88ab9ce | 2 | |
d59c3137 | 3 | ;; Copyright (C) 1992, 2001, 2002, 2003, 2004, 2005, |
f0fa15c5 | 4 | ;; 2006, 2007 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 | |
fd7fa35a | 13 | ;; the Free Software Foundation; either version 2, 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 DL |
53 | (and (consp x) (integerp (car x)) |
54 | (consp (cdr x)) (integerp (car (cdr x))) | |
55 | (vectorp (cdr (cdr x))))) | |
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) |
14b6a8e1 | 63 | "Add to RING the item ITEM. Add it at the front, as the oldest item." |
7263dc56 RS |
64 | (let* ((vec (cdr (cdr ring))) |
65 | (veclen (length vec)) | |
66 | (hd (car ring)) | |
67 | (ln (car (cdr 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." |
67ea382e DL |
76 | (let ((new-index (+ index 1))) |
77 | (if (= new-index veclen) 0 new-index))) | |
78 | ||
79 | (defun ring-minus1 (index veclen) | |
2356fa8a | 80 | "Return INDEX-1, with wraparound." |
67ea382e DL |
81 | (- (if (= 0 index) veclen index) 1)) |
82 | ||
83 | (defun ring-length (ring) | |
2356fa8a | 84 | "Return the number of elements in the RING." |
d3af54ac | 85 | (car (cdr 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 JPW |
97 | "Return t if RING is empty; nil otherwise." |
98 | (zerop (car (cdr ring)))) | |
7263dc56 RS |
99 | |
100 | (defun ring-size (ring) | |
2356fa8a | 101 | "Return the size of RING, the maximum number of elements it can contain." |
7263dc56 RS |
102 | (length (cdr (cdr ring)))) |
103 | ||
104 | (defun ring-copy (ring) | |
2356fa8a | 105 | "Return a copy of RING." |
b27c6995 RS |
106 | (let* ((vec (cdr (cdr ring))) |
107 | (hd (car ring)) | |
108 | (ln (car (cdr 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 RS |
113 | If the ring is full, dump the oldest item to make room." |
114 | (let* ((vec (cdr (cdr ring))) | |
115 | (veclen (length vec)) | |
116 | (hd (car ring)) | |
117 | (ln (car (cdr 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)) | |
7263dc56 RS |
131 | (ln (car (cdr ring))) |
132 | (vec (cdr (cdr ring))) | |
133 | (veclen (length vec)) | |
134 | (tl (mod (1- (+ hd ln)) veclen)) | |
135 | oldelt) | |
d3af54ac | 136 | (if (null index) |
7263dc56 | 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") |
d3af54ac ER |
155 | (let* ((hd (car ring)) (ln (car (cdr ring))) (vec (cdr (cdr ring)))) |
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 | |
7263dc56 RS |
167 | ;;; provide ourself: |
168 | ||
41dc743d ER |
169 | (provide 'ring) |
170 | ||
ab5796a9 | 171 | ;;; arch-tag: e707682b-ed69-47c9-b20f-cf2c68cc92d2 |
c88ab9ce | 172 | ;;; ring.el ends here |