Mercurial > emacs
annotate lisp/emacs-lisp/ring.el @ 96766:19a21a87b52a
Change from author without assignment thankfully tiny.
author | Glenn Morris <rgm@gnu.org> |
---|---|
date | Thu, 17 Jul 2008 16:32:15 +0000 |
parents | 90a2847062be |
children | a9dc0e7c3f2b |
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 |
74466 | 3 ;; Copyright (C) 1992, 2001, 2002, 2003, 2004, 2005, |
79704 | 4 ;; 2006, 2007, 2008 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 |
94655
90a2847062be
Switch to recommended form of GPLv3 permissions notice.
Glenn Morris <rgm@gnu.org>
parents:
93975
diff
changeset
|
11 ;; GNU Emacs is free software: you can redistribute it and/or modify |
658
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 |
94655
90a2847062be
Switch to recommended form of GPLv3 permissions notice.
Glenn Morris <rgm@gnu.org>
parents:
93975
diff
changeset
|
13 ;; the Free Software Foundation, either version 3 of the License, or |
90a2847062be
Switch to recommended form of GPLv3 permissions notice.
Glenn Morris <rgm@gnu.org>
parents:
93975
diff
changeset
|
14 ;; (at your option) any later version. |
658
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 |
94655
90a2847062be
Switch to recommended form of GPLv3 permissions notice.
Glenn Morris <rgm@gnu.org>
parents:
93975
diff
changeset
|
22 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. |
658
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
23 |
811
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
24 ;;; Commentary: |
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
25 |
51873
000e2717e1a5
2003-07-11 John Paul Wallington <jpw@gnu.org>
John Paul Wallington <jpw@pobox.com>
parents:
29055
diff
changeset
|
26 ;; This code defines a ring data structure. A ring is a |
25467 | 27 ;; (hd-index length . vector) |
17212 | 28 ;; list. You can insert to, remove from, and rotate a ring. When the ring |
14169 | 29 ;; fills up, insertions cause the oldest elts to be quietly dropped. |
30 ;; | |
31 ;; In ring-ref, 0 is the index of the newest element. Higher indexes | |
17212 | 32 ;; correspond to older elements; when the index equals the ring length, |
33 ;; it wraps to the newest element again. | |
14169 | 34 ;; |
17212 | 35 ;; hd-index = vector index of the oldest ring item. |
36 ;; Newer items follow this item; at the end of the vector, | |
25467 | 37 ;; they wrap around to the start of the vector. |
17212 | 38 ;; length = number of items currently in the ring. |
25467 | 39 ;; This never exceeds the length of the vector itself. |
14169 | 40 ;; |
41 ;; These functions are used by the input history mechanism, but they can | |
42 ;; be used for other purposes as well. | |
124 | 43 |
811
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
44 ;;; Code: |
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
45 |
25467 | 46 ;;; User Functions: |
47 | |
905 | 48 ;;;###autoload |
25467 | 49 (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
|
50 "Return t if X is a ring; nil otherwise." |
124 | 51 (and (consp x) (integerp (car x)) |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
52 (consp (cdr x)) (integerp (cadr x)) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
53 (vectorp (cddr x)))) |
124 | 54 |
905 | 55 ;;;###autoload |
124 | 56 (defun make-ring (size) |
2574
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
57 "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
|
58 (cons 0 (cons 0 (make-vector size nil)))) |
124 | 59 |
8031
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
60 (defun ring-insert-at-beginning (ring item) |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
61 "Add to RING the item ITEM, at the front, as the oldest item." |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
62 (let* ((vec (cddr ring)) |
25467 | 63 (veclen (length vec)) |
64 (hd (car ring)) | |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
65 (ln (cadr ring))) |
8031
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
66 (setq ln (min veclen (1+ ln)) |
25467 | 67 hd (ring-minus1 hd veclen)) |
8031
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
68 (aset vec hd item) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
69 (setcar ring hd) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
70 (setcar (cdr ring) ln))) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
71 |
124 | 72 (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
|
73 "Return INDEX+1, with wraparound." |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
74 (let ((new-index (1+ index))) |
124 | 75 (if (= new-index veclen) 0 new-index))) |
76 | |
77 (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
|
78 "Return INDEX-1, with wraparound." |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
79 (- (if (zerop index) veclen index) 1)) |
124 | 80 |
81 (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
|
82 "Return the number of elements in the RING." |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
83 (cadr ring)) |
124 | 84 |
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 (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
|
86 "Convert nominal ring index INDEX to an internal index. |
25467 | 87 The internal index refers to the items ordered from newest to oldest. |
88 HEAD is the index of the oldest element in the ring. | |
89 RINGLEN is the number of elements currently in the ring. | |
90 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
|
91 (setq index (mod index ringlen)) |
95b9760d19e3
(ring-mod): Remove, since floor and mod
Paul Eggert <eggert@twinsun.com>
parents:
2582
diff
changeset
|
92 (mod (1- (+ head (- ringlen index))) veclen)) |
124 | 93 |
25467 | 94 (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
|
95 "Return t if RING is empty; nil otherwise." |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
96 (zerop (cadr ring))) |
25467 | 97 |
98 (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
|
99 "Return the size of RING, the maximum number of elements it can contain." |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
100 (length (cddr ring))) |
25467 | 101 |
102 (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
|
103 "Return a copy of RING." |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
104 (let ((vec (cddr ring)) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
105 (hd (car ring)) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
106 (ln (cadr ring))) |
25467 | 107 (cons hd (cons ln (copy-sequence vec))))) |
108 | |
124 | 109 (defun ring-insert (ring item) |
8031
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
110 "Insert onto ring RING the item ITEM, as the newest (last) item. |
25467 | 111 If the ring is full, dump the oldest item to make room." |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
112 (let* ((vec (cddr ring)) |
25467 | 113 (veclen (length vec)) |
114 (hd (car ring)) | |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
115 (ln (cadr 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
|
116 (prog1 |
25467 | 117 (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
|
118 (if (= ln veclen) |
25467 | 119 (setcar ring (ring-plus1 hd veclen)) |
120 (setcar (cdr ring) (1+ ln)))))) | |
124 | 121 |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
122 (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
|
123 "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
|
124 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
|
125 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
|
126 (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
|
127 (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
|
128 (let* ((hd (car ring)) |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
129 (ln (cadr ring)) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
130 (vec (cddr ring)) |
25467 | 131 (veclen (length vec)) |
132 (tl (mod (1- (+ hd ln)) veclen)) | |
133 oldelt) | |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
134 (when (null index) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
135 (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
|
136 (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
|
137 (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
|
138 (while (/= index tl) |
25467 | 139 (aset vec index (aref vec (ring-plus1 index veclen))) |
140 (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
|
141 (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
|
142 (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
|
143 oldelt))) |
124 | 144 |
145 (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
|
146 "Return RING's INDEX element. |
17212 | 147 INDEX = 0 is the most recently inserted; higher indices |
148 correspond to older elements. | |
25468 | 149 INDEX need not be <= the ring length; the appropriate modulo operation |
17212 | 150 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
|
151 (if (ring-empty-p ring) |
17212 | 152 (error "Accessing an empty ring") |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
153 (let ((hd (car ring)) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
154 (ln (cadr ring)) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
155 (vec (cddr 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
|
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 |
85305
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
167 (defun ring-member (ring item) |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
168 "Return index of ITEM if on RING, else nil. |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
169 Comparison is done via `equal'. The index is 0-based." |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
170 (catch 'found |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
171 (dotimes (ind (ring-length ring) nil) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
172 (when (equal item (ring-ref ring ind)) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
173 (throw 'found ind))))) |
85305
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
174 |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
175 (defun ring-next (ring item) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
176 "Return the next item in the RING, after ITEM. |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
177 Raise error if ITEM is not in the RING." |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
178 (let ((curr-index (ring-member ring item))) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
179 (unless curr-index (error "Item is not in the ring: `%s'" item)) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
180 (ring-ref ring (ring-plus1 curr-index (ring-length ring))))) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
181 |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
182 (defun ring-previous (ring item) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
183 "Return the previous item in the RING, before ITEM. |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
184 Raise error if ITEM is not in the RING." |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
185 (let ((curr-index (ring-member ring item))) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
186 (unless curr-index (error "Item is not in the ring: `%s'" item)) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
187 (ring-ref ring (ring-minus1 curr-index (ring-length ring))))) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
188 |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
189 (defun ring-insert+extend (ring item &optional grow-p) |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
190 "Like `ring-insert', but if GROW-P is non-nil, then enlarge ring. |
85305
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
191 Insert onto ring RING the item ITEM, as the newest (last) item. |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
192 If the ring is full, behavior depends on GROW-P: |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
193 If GROW-P is non-nil, enlarge the ring to accommodate the new item. |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
194 If GROW-P is nil, dump the oldest item to make room for the new." |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
195 (let* ((vec (cddr ring)) |
85305
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
196 (veclen (length vec)) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
197 (hd (car ring)) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
198 (ringlen (ring-length ring))) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
199 (prog1 |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
200 (cond ((and grow-p (= ringlen veclen)) ; Full ring. Enlarge it. |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
201 (setq veclen (1+ veclen)) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
202 (setcdr ring (cons (setq ringlen (1+ ringlen)) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
203 (setq vec (vconcat vec (vector item))))) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
204 (setcar ring hd)) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
205 (t (aset vec (mod (+ hd ringlen) veclen) item))) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
206 (if (= ringlen veclen) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
207 (setcar ring (ring-plus1 hd veclen)) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
208 (setcar (cdr ring) (1+ ringlen)))))) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
209 |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
210 (defun ring-remove+insert+extend (ring item &optional grow-p) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
211 "`ring-remove' ITEM from RING, then `ring-insert+extend' it. |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
212 This ensures that there is only one ITEM on RING. |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
213 |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
214 If the RING is full, behavior depends on GROW-P: |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
215 If GROW-P is non-nil, enlarge the ring to accommodate the new ITEM. |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
216 If GROW-P is nil, dump the oldest item to make room for the new." |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
217 (let (ind) |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
218 (while (setq ind (ring-member ring item)) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
219 (ring-remove ring ind))) |
85305
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
220 (ring-insert+extend ring item grow-p)) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
221 |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
222 (defun ring-convert-sequence-to-ring (seq) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
223 "Convert sequence SEQ to a ring. Return the ring. |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
224 If SEQ is already a ring, return it." |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
225 (if (ring-p seq) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
226 seq |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
227 (let* ((size (length seq)) |
86170
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
228 (ring (make-ring size))) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
229 (dotimes (count size) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
230 (when (or (ring-empty-p ring) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
231 (not (equal (ring-ref ring 0) (elt seq count)))) |
e6b555f6c76b
(ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
Juanma Barranquero <lekktu@gmail.com>
parents:
85305
diff
changeset
|
232 (ring-insert-at-beginning ring (elt seq count)))) |
85305
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
233 ring))) |
e1264e487a97
(ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents:
78217
diff
changeset
|
234 |
25467 | 235 ;;; provide ourself: |
236 | |
2574
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
237 (provide 'ring) |
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
238 |
93975
1e3a407766b9
Fix up comment convention on the arch-tag lines.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
87649
diff
changeset
|
239 ;; arch-tag: e707682b-ed69-47c9-b20f-cf2c68cc92d2 |
658
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
240 ;;; ring.el ends here |