Commit | Line | Data |
---|---|---|
0b2974ab | 1 | ;;; ring.el --- handle rings of items |
c88ab9ce | 2 | |
3a801d0c ER |
3 | ;; Copyright (C) 1992 Free Software Foundation, Inc. |
4 | ||
fd7fa35a | 5 | ;; Maintainer: FSF |
fd7fa35a ER |
6 | ;; Keywords: extensions |
7 | ||
c88ab9ce ER |
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 | |
fd7fa35a | 12 | ;; the Free Software Foundation; either version 2, or (at your option) |
c88ab9ce ER |
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 | |
b578f267 EN |
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. | |
c88ab9ce | 24 | |
fd7fa35a ER |
25 | ;;; Commentary: |
26 | ||
2356fa8a | 27 | ;; This code defines a ring data structure. A ring is a |
7263dc56 | 28 | ;; (hd-index length . vector) |
14b6a8e1 | 29 | ;; list. You can insert to, remove from, and rotate a ring. When the ring |
b578f267 EN |
30 | ;; fills up, insertions cause the oldest elts to be quietly dropped. |
31 | ;; | |
32 | ;; In ring-ref, 0 is the index of the newest element. Higher indexes | |
14b6a8e1 RS |
33 | ;; correspond to older elements; when the index equals the ring length, |
34 | ;; it wraps to the newest element again. | |
b578f267 | 35 | ;; |
14b6a8e1 RS |
36 | ;; hd-index = vector index of the oldest ring item. |
37 | ;; Newer items follow this item; at the end of the vector, | |
7263dc56 | 38 | ;; they wrap around to the start of the vector. |
14b6a8e1 | 39 | ;; length = number of items currently in the ring. |
7263dc56 | 40 | ;; This never exceeds the length of the vector itself. |
b578f267 EN |
41 | ;; |
42 | ;; These functions are used by the input history mechanism, but they can | |
43 | ;; be used for other purposes as well. | |
67ea382e | 44 | |
fd7fa35a ER |
45 | ;;; Code: |
46 | ||
7263dc56 RS |
47 | ;;; User Functions: |
48 | ||
73183f2b | 49 | ;;;###autoload |
7263dc56 | 50 | (defun ring-p (x) |
2356fa8a | 51 | "Return t if X is a ring; nil otherwise." |
67ea382e DL |
52 | (and (consp x) (integerp (car x)) |
53 | (consp (cdr x)) (integerp (car (cdr x))) | |
54 | (vectorp (cdr (cdr x))))) | |
55 | ||
73183f2b | 56 | ;;;###autoload |
67ea382e | 57 | (defun make-ring (size) |
41dc743d | 58 | "Make a ring that can contain SIZE elements." |
d3af54ac | 59 | (cons 0 (cons 0 (make-vector size nil)))) |
67ea382e | 60 | |
9c545670 | 61 | (defun ring-insert-at-beginning (ring item) |
14b6a8e1 | 62 | "Add to RING the item ITEM. Add it at the front, as the oldest item." |
7263dc56 RS |
63 | (let* ((vec (cdr (cdr ring))) |
64 | (veclen (length vec)) | |
65 | (hd (car ring)) | |
66 | (ln (car (cdr ring)))) | |
9c545670 | 67 | (setq ln (min veclen (1+ ln)) |
7263dc56 | 68 | hd (ring-minus1 hd veclen)) |
9c545670 RS |
69 | (aset vec hd item) |
70 | (setcar ring hd) | |
71 | (setcar (cdr ring) ln))) | |
72 | ||
67ea382e | 73 | (defun ring-plus1 (index veclen) |
2356fa8a | 74 | "Return INDEX+1, with wraparound." |
67ea382e DL |
75 | (let ((new-index (+ index 1))) |
76 | (if (= new-index veclen) 0 new-index))) | |
77 | ||
78 | (defun ring-minus1 (index veclen) | |
2356fa8a | 79 | "Return INDEX-1, with wraparound." |
67ea382e DL |
80 | (- (if (= 0 index) veclen index) 1)) |
81 | ||
82 | (defun ring-length (ring) | |
2356fa8a | 83 | "Return the number of elements in the RING." |
d3af54ac | 84 | (car (cdr ring))) |
67ea382e | 85 | |
d3af54ac | 86 | (defun ring-index (index head ringlen veclen) |
2356fa8a | 87 | "Convert nominal ring index INDEX to an internal index. |
7263dc56 RS |
88 | The internal index refers to the items ordered from newest to oldest. |
89 | HEAD is the index of the oldest element in the ring. | |
90 | RINGLEN is the number of elements currently in the ring. | |
91 | VECLEN is the size of the vector in the ring." | |
2ec5af11 PE |
92 | (setq index (mod index ringlen)) |
93 | (mod (1- (+ head (- ringlen index))) veclen)) | |
67ea382e | 94 | |
7263dc56 | 95 | (defun ring-empty-p (ring) |
2356fa8a JPW |
96 | "Return t if RING is empty; nil otherwise." |
97 | (zerop (car (cdr ring)))) | |
7263dc56 RS |
98 | |
99 | (defun ring-size (ring) | |
2356fa8a | 100 | "Return the size of RING, the maximum number of elements it can contain." |
7263dc56 RS |
101 | (length (cdr (cdr ring)))) |
102 | ||
103 | (defun ring-copy (ring) | |
2356fa8a | 104 | "Return a copy of RING." |
b27c6995 RS |
105 | (let* ((vec (cdr (cdr ring))) |
106 | (hd (car ring)) | |
107 | (ln (car (cdr ring)))) | |
7263dc56 RS |
108 | (cons hd (cons ln (copy-sequence vec))))) |
109 | ||
67ea382e | 110 | (defun ring-insert (ring item) |
9c545670 | 111 | "Insert onto ring RING the item ITEM, as the newest (last) item. |
7263dc56 RS |
112 | If the ring is full, dump the oldest item to make room." |
113 | (let* ((vec (cdr (cdr ring))) | |
114 | (veclen (length vec)) | |
115 | (hd (car ring)) | |
116 | (ln (car (cdr ring)))) | |
d3af54ac | 117 | (prog1 |
7263dc56 | 118 | (aset vec (mod (+ hd ln) veclen) item) |
d3af54ac | 119 | (if (= ln veclen) |
7263dc56 RS |
120 | (setcar ring (ring-plus1 hd veclen)) |
121 | (setcar (cdr ring) (1+ ln)))))) | |
d3af54ac ER |
122 | |
123 | (defun ring-remove (ring &optional index) | |
124 | "Remove an item from the RING. Return the removed item. | |
125 | If optional INDEX is nil, remove the oldest item. If it's | |
126 | numeric, remove the element indexed." | |
127 | (if (ring-empty-p ring) | |
128 | (error "Ring empty") | |
129 | (let* ((hd (car ring)) | |
7263dc56 RS |
130 | (ln (car (cdr ring))) |
131 | (vec (cdr (cdr ring))) | |
132 | (veclen (length vec)) | |
133 | (tl (mod (1- (+ hd ln)) veclen)) | |
134 | oldelt) | |
d3af54ac | 135 | (if (null index) |
7263dc56 | 136 | (setq index (1- ln))) |
d3af54ac ER |
137 | (setq index (ring-index index hd ln veclen)) |
138 | (setq oldelt (aref vec index)) | |
139 | (while (/= index tl) | |
7263dc56 RS |
140 | (aset vec index (aref vec (ring-plus1 index veclen))) |
141 | (setq index (ring-plus1 index veclen))) | |
d3af54ac ER |
142 | (aset vec tl nil) |
143 | (setcar (cdr ring) (1- ln)) | |
144 | oldelt))) | |
67ea382e | 145 | |
67ea382e | 146 | (defun ring-ref (ring index) |
2356fa8a | 147 | "Return RING's INDEX element. |
14b6a8e1 RS |
148 | INDEX = 0 is the most recently inserted; higher indices |
149 | correspond to older elements. | |
b27c6995 | 150 | INDEX need not be <= the ring length; the appropriate modulo operation |
14b6a8e1 | 151 | will be performed." |
d3af54ac | 152 | (if (ring-empty-p ring) |
14b6a8e1 | 153 | (error "Accessing an empty ring") |
d3af54ac ER |
154 | (let* ((hd (car ring)) (ln (car (cdr ring))) (vec (cdr (cdr ring)))) |
155 | (aref vec (ring-index index hd ln (length vec)))))) | |
c88ab9ce | 156 | |
6a475c99 | 157 | (defun ring-elements (ring) |
2356fa8a | 158 | "Return a list of the elements of RING." |
6a475c99 DL |
159 | (mapcar #'identity (cddr ring))) |
160 | ||
7263dc56 RS |
161 | ;;; provide ourself: |
162 | ||
41dc743d ER |
163 | (provide 'ring) |
164 | ||
6b61353c | 165 | ;;; arch-tag: e707682b-ed69-47c9-b20f-cf2c68cc92d2 |
c88ab9ce | 166 | ;;; ring.el ends here |