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 | |
21 | ;; along with GNU Emacs; see the file COPYING. If not, write to | |
22 | ;; the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. | |
23 | ||
fd7fa35a ER |
24 | ;;; Commentary: |
25 | ||
67ea382e | 26 | ;;; This code defines a ring data structure. A ring is a |
d3af54ac | 27 | ;;; (hd-index length . vector) |
67ea382e DL |
28 | ;;; list. You can insert to, remove from, and rotate a ring. When the ring |
29 | ;;; fills up, insertions cause the oldest elts to be quietly dropped. | |
30 | ;;; | |
41dc743d ER |
31 | ;;; In ring-ref, 0 is the index of the newest element. Higher indexes |
32 | ;;; correspond to older elements until they wrap. | |
33 | ;;; | |
d3af54ac ER |
34 | ;;; hd-index = index of the newest item on the ring. |
35 | ;;; length = number of ring items. | |
67ea382e DL |
36 | ;;; |
37 | ;;; These functions are used by the input history mechanism, but they can | |
38 | ;;; be used for other purposes as well. | |
39 | ||
fd7fa35a ER |
40 | ;;; Code: |
41 | ||
73183f2b | 42 | ;;;###autoload |
67ea382e | 43 | (defun ring-p (x) |
41dc743d | 44 | "Returns t if X is a ring; nil otherwise." |
67ea382e DL |
45 | (and (consp x) (integerp (car x)) |
46 | (consp (cdr x)) (integerp (car (cdr x))) | |
47 | (vectorp (cdr (cdr x))))) | |
48 | ||
73183f2b | 49 | ;;;###autoload |
67ea382e | 50 | (defun make-ring (size) |
41dc743d | 51 | "Make a ring that can contain SIZE elements." |
d3af54ac | 52 | (cons 0 (cons 0 (make-vector size nil)))) |
67ea382e DL |
53 | |
54 | (defun ring-plus1 (index veclen) | |
55 | "INDEX+1, with wraparound" | |
56 | (let ((new-index (+ index 1))) | |
57 | (if (= new-index veclen) 0 new-index))) | |
58 | ||
59 | (defun ring-minus1 (index veclen) | |
60 | "INDEX-1, with wraparound" | |
61 | (- (if (= 0 index) veclen index) 1)) | |
62 | ||
63 | (defun ring-length (ring) | |
41dc743d | 64 | "Number of elements in the ring." |
d3af54ac | 65 | (car (cdr ring))) |
67ea382e DL |
66 | |
67 | (defun ring-empty-p (ring) | |
d3af54ac ER |
68 | (= 0 (car (cdr ring)))) |
69 | ||
70 | (defun ring-index (index head ringlen veclen) | |
2ec5af11 PE |
71 | (setq index (mod index ringlen)) |
72 | (mod (1- (+ head (- ringlen index))) veclen)) | |
67ea382e DL |
73 | |
74 | (defun ring-insert (ring item) | |
75 | "Insert a new item onto the ring. If the ring is full, dump the oldest | |
76 | item to make room." | |
d3af54ac ER |
77 | (let* ((vec (cdr (cdr ring))) |
78 | (veclen (length vec)) | |
79 | (hd (car ring)) | |
80 | (ln (car (cdr ring)))) | |
81 | (prog1 | |
2ec5af11 | 82 | (aset vec (mod (+ hd ln) veclen) item) |
d3af54ac ER |
83 | (if (= ln veclen) |
84 | (setcar ring (ring-plus1 hd veclen)) | |
85 | (setcar (cdr ring) (1+ ln)))))) | |
86 | ||
87 | (defun ring-remove (ring &optional index) | |
88 | "Remove an item from the RING. Return the removed item. | |
89 | If optional INDEX is nil, remove the oldest item. If it's | |
90 | numeric, remove the element indexed." | |
91 | (if (ring-empty-p ring) | |
92 | (error "Ring empty") | |
93 | (let* ((hd (car ring)) | |
94 | (ln (car (cdr ring))) | |
95 | (vec (cdr (cdr ring))) | |
96 | (veclen (length vec)) | |
2ec5af11 | 97 | (tl (mod (1- (+ hd ln)) veclen)) |
d3af54ac ER |
98 | oldelt) |
99 | (if (null index) | |
100 | (setq index (1- ln))) | |
101 | (setq index (ring-index index hd ln veclen)) | |
102 | (setq oldelt (aref vec index)) | |
103 | (while (/= index tl) | |
104 | (aset vec index (aref vec (ring-plus1 index veclen))) | |
105 | (setq index (ring-plus1 index veclen))) | |
106 | (aset vec tl nil) | |
107 | (setcar (cdr ring) (1- ln)) | |
108 | oldelt))) | |
67ea382e | 109 | |
67ea382e | 110 | (defun ring-ref (ring index) |
41dc743d ER |
111 | "Returns RING's INDEX element. |
112 | INDEX need not be <= the ring length, the appropriate modulo operation | |
113 | will be performed. Element 0 is the most recently inserted; higher indices | |
114 | correspond to older elements until they wrap." | |
d3af54ac ER |
115 | (if (ring-empty-p ring) |
116 | (error "indexed empty ring") | |
117 | (let* ((hd (car ring)) (ln (car (cdr ring))) (vec (cdr (cdr ring)))) | |
118 | (aref vec (ring-index index hd ln (length vec)))))) | |
c88ab9ce | 119 | |
41dc743d ER |
120 | (provide 'ring) |
121 | ||
c88ab9ce | 122 | ;;; ring.el ends here |