annotate lisp/emacs-lisp/ring.el @ 91569:4a3d0b905c9e

(--with-gcc): Give an error saying this option has been removed. (--with-gtk): Remove this option.
author Glenn Morris <rgm@gnu.org>
date Wed, 06 Feb 2008 07:57:24 +0000
parents 107ccd98fa12
children 606f2d163a64 1e3a407766b9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
1d4b1a32fd66 Update copyright years.
Glenn Morris <rgm@gnu.org>
parents: 68648
diff changeset
3 ;; Copyright (C) 1992, 2001, 2002, 2003, 2004, 2005,
79704
78ee6fae0e41 Add 2008 to copyright years.
Glenn Morris <rgm@gnu.org>
parents: 78217
diff changeset
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
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
78217
935157c0b596 Switch license to GPLv3 or later.
Glenn Morris <rgm@gnu.org>
parents: 75346
diff changeset
13 ;; the Free Software Foundation; either version 3, 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
83f275dcd93a Update FSF's address.
Erik Naggum <erik@naggum.no>
parents: 8031
diff changeset
22 ;; along with GNU Emacs; see the file COPYING. If not, write to the
64085
18a818a2ee7c Update FSF's address.
Lute Kamstra <lute@gnu.org>
parents: 63727
diff changeset
23 ;; Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18a818a2ee7c Update FSF's address.
Lute Kamstra <lute@gnu.org>
parents: 63727
diff changeset
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
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
29 ;; (hd-index length . vector)
17212
de55dc47bae6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 14169
diff changeset
30 ;; list. You can insert to, remove from, and rotate a ring. When the ring
14169
83f275dcd93a Update FSF's address.
Erik Naggum <erik@naggum.no>
parents: 8031
diff changeset
31 ;; fills up, insertions cause the oldest elts to be quietly dropped.
83f275dcd93a Update FSF's address.
Erik Naggum <erik@naggum.no>
parents: 8031
diff changeset
32 ;;
83f275dcd93a Update FSF's address.
Erik Naggum <erik@naggum.no>
parents: 8031
diff changeset
33 ;; In ring-ref, 0 is the index of the newest element. Higher indexes
17212
de55dc47bae6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 14169
diff changeset
34 ;; correspond to older elements; when the index equals the ring length,
de55dc47bae6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 14169
diff changeset
35 ;; it wraps to the newest element again.
14169
83f275dcd93a Update FSF's address.
Erik Naggum <erik@naggum.no>
parents: 8031
diff changeset
36 ;;
17212
de55dc47bae6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 14169
diff changeset
37 ;; hd-index = vector index of the oldest ring item.
de55dc47bae6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 14169
diff changeset
38 ;; Newer items follow this item; at the end of the vector,
25467
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
39 ;; they wrap around to the start of the vector.
17212
de55dc47bae6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 14169
diff changeset
40 ;; length = number of items currently in the ring.
25467
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
41 ;; This never exceeds the length of the vector itself.
14169
83f275dcd93a Update FSF's address.
Erik Naggum <erik@naggum.no>
parents: 8031
diff changeset
42 ;;
83f275dcd93a Update FSF's address.
Erik Naggum <erik@naggum.no>
parents: 8031
diff changeset
43 ;; These functions are used by the input history mechanism, but they can
83f275dcd93a Update FSF's address.
Erik Naggum <erik@naggum.no>
parents: 8031
diff changeset
44 ;; be used for other purposes as well.
124
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
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
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
48 ;;; User Functions:
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
49
905
48e4034a2176 entered into RCS
Richard M. Stallman <rms@gnu.org>
parents: 846
diff changeset
50 ;;;###autoload
25467
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
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
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
53 (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
54 (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
55 (vectorp (cddr x))))
124
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
56
905
48e4034a2176 entered into RCS
Richard M. Stallman <rms@gnu.org>
parents: 846
diff changeset
57 ;;;###autoload
124
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
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
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
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)
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
63 "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
64 (let* ((vec (cddr ring))
25467
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
65 (veclen (length vec))
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
66 (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
67 (ln (cadr 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
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
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
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
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."
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
76 (let ((new-index (1+ index)))
124
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
77 (if (= new-index veclen) 0 new-index)))
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
78
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
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."
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
81 (- (if (zerop index) veclen index) 1))
124
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
82
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
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."
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
85 (cadr ring))
124
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
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
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
89 The internal index refers to the items ordered from newest to oldest.
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
90 HEAD is the index of the oldest element in the ring.
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
91 RINGLEN is the number of elements currently in the ring.
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
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
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
95
25467
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
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."
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
98 (zerop (cadr ring)))
25467
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
99
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
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."
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
102 (length (cddr ring)))
25467
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
103
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
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."
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
106 (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
107 (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
108 (ln (cadr ring)))
25467
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
109 (cons hd (cons ln (copy-sequence vec)))))
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
110
124
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
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
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
113 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
114 (let* ((vec (cddr ring))
25467
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
115 (veclen (length vec))
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
116 (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
117 (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
118 (prog1
25467
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
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
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
121 (setcar ring (ring-plus1 hd veclen))
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
122 (setcar (cdr ring) (1+ ln))))))
124
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
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))
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
131 (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
132 (vec (cddr ring))
25467
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
133 (veclen (length vec))
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
134 (tl (mod (1- (+ hd ln)) veclen))
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
135 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
136 (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
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
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
141 (aset vec index (aref vec (ring-plus1 index veclen)))
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
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
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
146
27691d738b4f Initial revision
David Lawrence <tale@gnu.org>
parents:
diff changeset
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
de55dc47bae6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 14169
diff changeset
149 INDEX = 0 is the most recently inserted; higher indices
de55dc47bae6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 14169
diff changeset
150 correspond to older elements.
25468
637af9b4fdbb Fix previous change.
Richard M. Stallman <rms@gnu.org>
parents: 25467
diff changeset
151 INDEX need not be <= the ring length; the appropriate modulo operation
17212
de55dc47bae6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 14169
diff changeset
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
de55dc47bae6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 14169
diff changeset
154 (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
155 (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
156 (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
157 (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
158 (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
159
29055
661c97b907a8 (ring-elements): New function.
Dave Love <fx@gnu.org>
parents: 25468
diff changeset
160 (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
161 "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
162 (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
163 (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
164 (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
165 lst)
fe0423976eb0 (ring-elements): Make it return a list of the elements of RING in
Luc Teirlinck <teirllm@auburn.edu>
parents: 52401
diff changeset
166 (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
167 (push (aref vect (mod (+ start var) size)) lst))))
29055
661c97b907a8 (ring-elements): New function.
Dave Love <fx@gnu.org>
parents: 25468
diff changeset
168
85305
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
169 (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
170 "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
171 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
172 (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
173 (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
174 (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
175 (throw 'found ind)))))
85305
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
176
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
177 (defun ring-next (ring item)
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
178 "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
179 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
180 (let ((curr-index (ring-member ring item)))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
181 (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
182 (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
183
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
184 (defun ring-previous (ring item)
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
185 "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
186 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
187 (let ((curr-index (ring-member ring item)))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
188 (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
189 (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
190
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
191 (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
192 "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
193 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
194 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
195 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
196 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
197 (let* ((vec (cddr ring))
85305
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
198 (veclen (length vec))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
199 (hd (car ring))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
200 (ringlen (ring-length ring)))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
201 (prog1
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
202 (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
203 (setq veclen (1+ veclen))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
204 (setcdr ring (cons (setq ringlen (1+ ringlen))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
205 (setq vec (vconcat vec (vector item)))))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
206 (setcar ring hd))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
207 (t (aset vec (mod (+ hd ringlen) veclen) item)))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
208 (if (= ringlen veclen)
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
209 (setcar ring (ring-plus1 hd veclen))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
210 (setcar (cdr ring) (1+ ringlen))))))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
211
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
212 (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
213 "`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
214 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
215
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
216 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
217 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
218 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
219 (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
220 (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
221 (ring-remove ring ind)))
85305
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
222 (ring-insert+extend ring item grow-p))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
223
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
224 (defun ring-convert-sequence-to-ring (seq)
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
225 "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
226 If SEQ is already a ring, return it."
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
227 (if (ring-p seq)
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
228 seq
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
229 (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
230 (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
231 (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
232 (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
233 (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
234 (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
235 ring)))
e1264e487a97 (ring-convert-sequence-to-ring)
Richard M. Stallman <rms@gnu.org>
parents: 78217
diff changeset
236
25467
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
237 ;;; provide ourself:
cf992000b9c6 Many doc fixes.
Richard M. Stallman <rms@gnu.org>
parents: 17212
diff changeset
238
2574
c782b69b60a4 Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents: 2424
diff changeset
239 (provide 'ring)
c782b69b60a4 Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents: 2424
diff changeset
240
52401
695cf19ef79e Add arch taglines
Miles Bader <miles@gnu.org>
parents: 51873
diff changeset
241 ;;; arch-tag: e707682b-ed69-47c9-b20f-cf2c68cc92d2
658
7cbd4fcd8b0f *** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents: 245
diff changeset
242 ;;; ring.el ends here