Mercurial > emacs
annotate lisp/emacs-lisp/ring.el @ 70166:1204092d4458
*** empty log message ***
author | Kim F. Storm <storm@cua.dk> |
---|---|
date | Fri, 21 Apr 2006 14:06:42 +0000 |
parents | 067115a6e738 |
children | 1d4b1a32fd66 c5406394f567 |
rev | line source |
---|---|
2424
dbdccee84df3
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
905
diff
changeset
|
1 ;;; ring.el --- handle rings of items |
658
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
2 |
68648
067115a6e738
Update years in copyright notice; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
64751
diff
changeset
|
3 ;; Copyright (C) 1992, 2002, 2003, 2004, 2005, |
067115a6e738
Update years in copyright notice; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
64751
diff
changeset
|
4 ;; 2006 Free Software Foundation, Inc. |
846
20674ae6bf52
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
811
diff
changeset
|
5 |
811
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
6 ;; Maintainer: FSF |
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
7 ;; Keywords: extensions |
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
8 |
658
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
9 ;; This file is part of GNU Emacs. |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
10 |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
11 ;; GNU Emacs is free software; you can redistribute it and/or modify |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
12 ;; it under the terms of the GNU General Public License as published by |
811
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
13 ;; the Free Software Foundation; either version 2, or (at your option) |
658
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
14 ;; any later version. |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
15 |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
16 ;; GNU Emacs is distributed in the hope that it will be useful, |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
17 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
18 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
19 ;; GNU General Public License for more details. |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
20 |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
21 ;; You should have received a copy of the GNU General Public License |
14169 | 22 ;; along with GNU Emacs; see the file COPYING. If not, write to the |
64085 | 23 ;; Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
24 ;; Boston, MA 02110-1301, USA. | |
658
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
25 |
811
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
26 ;;; Commentary: |
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
27 |
51873
000e2717e1a5
2003-07-11 John Paul Wallington <jpw@gnu.org>
John Paul Wallington <jpw@pobox.com>
parents:
29055
diff
changeset
|
28 ;; This code defines a ring data structure. A ring is a |
25467 | 29 ;; (hd-index length . vector) |
17212 | 30 ;; list. You can insert to, remove from, and rotate a ring. When the ring |
14169 | 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 | |
17212 | 34 ;; correspond to older elements; when the index equals the ring length, |
35 ;; it wraps to the newest element again. | |
14169 | 36 ;; |
17212 | 37 ;; hd-index = vector index of the oldest ring item. |
38 ;; Newer items follow this item; at the end of the vector, | |
25467 | 39 ;; they wrap around to the start of the vector. |
17212 | 40 ;; length = number of items currently in the ring. |
25467 | 41 ;; This never exceeds the length of the vector itself. |
14169 | 42 ;; |
43 ;; These functions are used by the input history mechanism, but they can | |
44 ;; be used for other purposes as well. | |
124 | 45 |
811
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
46 ;;; Code: |
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
47 |
25467 | 48 ;;; User Functions: |
49 | |
905 | 50 ;;;###autoload |
25467 | 51 (defun ring-p (x) |
51873
000e2717e1a5
2003-07-11 John Paul Wallington <jpw@gnu.org>
John Paul Wallington <jpw@pobox.com>
parents:
29055
diff
changeset
|
52 "Return t if X is a ring; nil otherwise." |
124 | 53 (and (consp x) (integerp (car x)) |
54 (consp (cdr x)) (integerp (car (cdr x))) | |
55 (vectorp (cdr (cdr x))))) | |
56 | |
905 | 57 ;;;###autoload |
124 | 58 (defun make-ring (size) |
2574
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
59 "Make a ring that can contain SIZE elements." |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
60 (cons 0 (cons 0 (make-vector size nil)))) |
124 | 61 |
8031
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
62 (defun ring-insert-at-beginning (ring item) |
17212 | 63 "Add to RING the item ITEM. Add it at the front, as the oldest item." |
25467 | 64 (let* ((vec (cdr (cdr ring))) |
65 (veclen (length vec)) | |
66 (hd (car ring)) | |
67 (ln (car (cdr ring)))) | |
8031
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
68 (setq ln (min veclen (1+ ln)) |
25467 | 69 hd (ring-minus1 hd veclen)) |
8031
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
70 (aset vec hd item) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
71 (setcar ring hd) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
72 (setcar (cdr ring) ln))) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
73 |
124 | 74 (defun ring-plus1 (index veclen) |
51873
000e2717e1a5
2003-07-11 John Paul Wallington <jpw@gnu.org>
John Paul Wallington <jpw@pobox.com>
parents:
29055
diff
changeset
|
75 "Return INDEX+1, with wraparound." |
124 | 76 (let ((new-index (+ index 1))) |
77 (if (= new-index veclen) 0 new-index))) | |
78 | |
79 (defun ring-minus1 (index veclen) | |
51873
000e2717e1a5
2003-07-11 John Paul Wallington <jpw@gnu.org>
John Paul Wallington <jpw@pobox.com>
parents:
29055
diff
changeset
|
80 "Return INDEX-1, with wraparound." |
124 | 81 (- (if (= 0 index) veclen index) 1)) |
82 | |
83 (defun ring-length (ring) | |
51873
000e2717e1a5
2003-07-11 John Paul Wallington <jpw@gnu.org>
John Paul Wallington <jpw@pobox.com>
parents:
29055
diff
changeset
|
84 "Return the number of elements in the RING." |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
85 (car (cdr ring))) |
124 | 86 |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
87 (defun ring-index (index head ringlen veclen) |
51873
000e2717e1a5
2003-07-11 John Paul Wallington <jpw@gnu.org>
John Paul Wallington <jpw@pobox.com>
parents:
29055
diff
changeset
|
88 "Convert nominal ring index INDEX to an internal index. |
25467 | 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." | |
4516
95b9760d19e3
(ring-mod): Remove, since floor and mod
Paul Eggert <eggert@twinsun.com>
parents:
2582
diff
changeset
|
93 (setq index (mod index ringlen)) |
95b9760d19e3
(ring-mod): Remove, since floor and mod
Paul Eggert <eggert@twinsun.com>
parents:
2582
diff
changeset
|
94 (mod (1- (+ head (- ringlen index))) veclen)) |
124 | 95 |
25467 | 96 (defun ring-empty-p (ring) |
51873
000e2717e1a5
2003-07-11 John Paul Wallington <jpw@gnu.org>
John Paul Wallington <jpw@pobox.com>
parents:
29055
diff
changeset
|
97 "Return t if RING is empty; nil otherwise." |
000e2717e1a5
2003-07-11 John Paul Wallington <jpw@gnu.org>
John Paul Wallington <jpw@pobox.com>
parents:
29055
diff
changeset
|
98 (zerop (car (cdr ring)))) |
25467 | 99 |
100 (defun ring-size (ring) | |
51873
000e2717e1a5
2003-07-11 John Paul Wallington <jpw@gnu.org>
John Paul Wallington <jpw@pobox.com>
parents:
29055
diff
changeset
|
101 "Return the size of RING, the maximum number of elements it can contain." |
25467 | 102 (length (cdr (cdr ring)))) |
103 | |
104 (defun ring-copy (ring) | |
51873
000e2717e1a5
2003-07-11 John Paul Wallington <jpw@gnu.org>
John Paul Wallington <jpw@pobox.com>
parents:
29055
diff
changeset
|
105 "Return a copy of RING." |
25468 | 106 (let* ((vec (cdr (cdr ring))) |
107 (hd (car ring)) | |
108 (ln (car (cdr ring)))) | |
25467 | 109 (cons hd (cons ln (copy-sequence vec))))) |
110 | |
124 | 111 (defun ring-insert (ring item) |
8031
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
112 "Insert onto ring RING the item ITEM, as the newest (last) item. |
25467 | 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)))) | |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
118 (prog1 |
25467 | 119 (aset vec (mod (+ hd ln) veclen) item) |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
120 (if (= ln veclen) |
25467 | 121 (setcar ring (ring-plus1 hd veclen)) |
122 (setcar (cdr ring) (1+ ln)))))) | |
124 | 123 |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
124 (defun ring-remove (ring &optional index) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
125 "Remove an item from the RING. Return the removed item. |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
126 If optional INDEX is nil, remove the oldest item. If it's |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
127 numeric, remove the element indexed." |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
128 (if (ring-empty-p ring) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
129 (error "Ring empty") |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
130 (let* ((hd (car ring)) |
25467 | 131 (ln (car (cdr ring))) |
132 (vec (cdr (cdr ring))) | |
133 (veclen (length vec)) | |
134 (tl (mod (1- (+ hd ln)) veclen)) | |
135 oldelt) | |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
136 (if (null index) |
25467 | 137 (setq index (1- ln))) |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
138 (setq index (ring-index index hd ln veclen)) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
139 (setq oldelt (aref vec index)) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
140 (while (/= index tl) |
25467 | 141 (aset vec index (aref vec (ring-plus1 index veclen))) |
142 (setq index (ring-plus1 index veclen))) | |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
143 (aset vec tl nil) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
144 (setcar (cdr ring) (1- ln)) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
145 oldelt))) |
124 | 146 |
147 (defun ring-ref (ring index) | |
51873
000e2717e1a5
2003-07-11 John Paul Wallington <jpw@gnu.org>
John Paul Wallington <jpw@pobox.com>
parents:
29055
diff
changeset
|
148 "Return RING's INDEX element. |
17212 | 149 INDEX = 0 is the most recently inserted; higher indices |
150 correspond to older elements. | |
25468 | 151 INDEX need not be <= the ring length; the appropriate modulo operation |
17212 | 152 will be performed." |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
153 (if (ring-empty-p ring) |
17212 | 154 (error "Accessing an empty ring") |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
155 (let* ((hd (car ring)) (ln (car (cdr ring))) (vec (cdr (cdr ring)))) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
156 (aref vec (ring-index index hd ln (length vec)))))) |
658
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
157 |
29055 | 158 (defun ring-elements (ring) |
63727
fe0423976eb0
(ring-elements): Make it return a list of the elements of RING in
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
159 "Return a list of the elements of RING, in order, newest first." |
fe0423976eb0
(ring-elements): Make it return a list of the elements of RING in
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
160 (let ((start (car ring)) |
fe0423976eb0
(ring-elements): Make it return a list of the elements of RING in
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
161 (size (ring-size ring)) |
fe0423976eb0
(ring-elements): Make it return a list of the elements of RING in
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
162 (vect (cddr ring)) |
fe0423976eb0
(ring-elements): Make it return a list of the elements of RING in
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
163 lst) |
fe0423976eb0
(ring-elements): Make it return a list of the elements of RING in
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
164 (dotimes (var (cadr ring) lst) |
fe0423976eb0
(ring-elements): Make it return a list of the elements of RING in
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
165 (push (aref vect (mod (+ start var) size)) lst)))) |
29055 | 166 |
25467 | 167 ;;; provide ourself: |
168 | |
2574
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
169 (provide 'ring) |
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
170 |
52401 | 171 ;;; arch-tag: e707682b-ed69-47c9-b20f-cf2c68cc92d2 |
658
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
172 ;;; ring.el ends here |