Mercurial > emacs
annotate lisp/emacs-lisp/ring.el @ 11763:fc2a3a312e98
[MULTI_KBOARD] (read_char): If the character was for
the wrong kboard, don't let it get processed twice.
author | Karl Heuer <kwzh@gnu.org> |
---|---|
date | Tue, 09 May 1995 01:32:05 +0000 |
parents | 4b45aa6d5d76 |
children | 83f275dcd93a |
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 |
846
20674ae6bf52
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
811
diff
changeset
|
3 ;; Copyright (C) 1992 Free Software Foundation, Inc. |
20674ae6bf52
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
811
diff
changeset
|
4 |
811
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
5 ;; Maintainer: FSF |
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
6 ;; Keywords: extensions |
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
7 |
658
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
8 ;; This file is part of GNU Emacs. |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
9 |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
10 ;; 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
|
11 ;; 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
|
12 ;; 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
|
13 ;; any later version. |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
14 |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
15 ;; 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
|
16 ;; 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
|
17 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
18 ;; GNU General Public License for more details. |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
19 |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
20 ;; You should have received a copy of the GNU General Public License |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
21 ;; along with GNU Emacs; see the file COPYING. If not, write to |
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
22 ;; the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. |
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 |
124 | 26 ;;; This code defines a ring data structure. A ring is a |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
27 ;;; (hd-index length . vector) |
124 | 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 ;;; | |
2574
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
31 ;;; In ring-ref, 0 is the index of the newest element. Higher indexes |
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
32 ;;; correspond to older elements until they wrap. |
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
33 ;;; |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
34 ;;; hd-index = index of the newest item on the ring. |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
35 ;;; length = number of ring items. |
124 | 36 ;;; |
37 ;;; These functions are used by the input history mechanism, but they can | |
38 ;;; be used for other purposes as well. | |
39 | |
811
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
40 ;;; Code: |
e694e0879463
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
658
diff
changeset
|
41 |
905 | 42 ;;;###autoload |
124 | 43 (defun ring-p (x) |
2574
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
44 "Returns t if X is a ring; nil otherwise." |
124 | 45 (and (consp x) (integerp (car x)) |
46 (consp (cdr x)) (integerp (car (cdr x))) | |
47 (vectorp (cdr (cdr x))))) | |
48 | |
905 | 49 ;;;###autoload |
124 | 50 (defun make-ring (size) |
2574
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
51 "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
|
52 (cons 0 (cons 0 (make-vector size nil)))) |
124 | 53 |
8031
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
54 (defun ring-insert-at-beginning (ring item) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
55 "Add to RING the item ITEM. Add it at the front (the early end)." |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
56 (let* ((vec (cdr (cdr ring))) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
57 (veclen (length vec)) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
58 (hd (car ring)) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
59 (ln (car (cdr ring)))) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
60 (setq ln (min veclen (1+ ln)) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
61 hd (ring-minus1 hd veclen)) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
62 (aset vec hd item) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
63 (setcar ring hd) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
64 (setcar (cdr ring) ln))) |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
65 |
124 | 66 (defun ring-plus1 (index veclen) |
67 "INDEX+1, with wraparound" | |
68 (let ((new-index (+ index 1))) | |
69 (if (= new-index veclen) 0 new-index))) | |
70 | |
71 (defun ring-minus1 (index veclen) | |
72 "INDEX-1, with wraparound" | |
73 (- (if (= 0 index) veclen index) 1)) | |
74 | |
75 (defun ring-length (ring) | |
2574
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
76 "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
|
77 (car (cdr ring))) |
124 | 78 |
79 (defun ring-empty-p (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
|
80 (= 0 (car (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
|
81 |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
82 (defun ring-index (index head ringlen veclen) |
4516
95b9760d19e3
(ring-mod): Remove, since floor and mod
Paul Eggert <eggert@twinsun.com>
parents:
2582
diff
changeset
|
83 (setq index (mod index ringlen)) |
95b9760d19e3
(ring-mod): Remove, since floor and mod
Paul Eggert <eggert@twinsun.com>
parents:
2582
diff
changeset
|
84 (mod (1- (+ head (- ringlen index))) veclen)) |
124 | 85 |
86 (defun ring-insert (ring item) | |
8031
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
87 "Insert onto ring RING the item ITEM, as the newest (last) item. |
4b45aa6d5d76
(ring-insert-at-beginning): New function.
Richard M. Stallman <rms@gnu.org>
parents:
4516
diff
changeset
|
88 If the ring is full, dump the oldest item to make room." |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
89 (let* ((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
|
90 (veclen (length vec)) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
91 (hd (car ring)) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
92 (ln (car (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
|
93 (prog1 |
4516
95b9760d19e3
(ring-mod): Remove, since floor and mod
Paul Eggert <eggert@twinsun.com>
parents:
2582
diff
changeset
|
94 (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
|
95 (if (= 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
|
96 (setcar ring (ring-plus1 hd veclen)) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
97 (setcar (cdr ring) (1+ ln)))))) |
124 | 98 |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
99 (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
|
100 "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
|
101 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
|
102 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
|
103 (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
|
104 (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
|
105 (let* ((hd (car ring)) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
106 (ln (car (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
|
107 (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
|
108 (veclen (length vec)) |
4516
95b9760d19e3
(ring-mod): Remove, since floor and mod
Paul Eggert <eggert@twinsun.com>
parents:
2582
diff
changeset
|
109 (tl (mod (1- (+ hd ln)) 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
|
110 oldelt) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
111 (if (null index) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
112 (setq index (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
|
113 (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
|
114 (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
|
115 (while (/= index tl) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
116 (aset vec index (aref vec (ring-plus1 index veclen))) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
117 (setq index (ring-plus1 index veclen))) |
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
118 (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
|
119 (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
|
120 oldelt))) |
124 | 121 |
122 (defun ring-ref (ring index) | |
2574
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
123 "Returns RING's INDEX element. |
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
124 INDEX need not be <= the ring length, the appropriate modulo operation |
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
125 will be performed. Element 0 is the most recently inserted; higher indices |
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
126 correspond to older elements until they wrap." |
2582
e01048f32511
Rewritten. A poor choice of representation made the old code excessively
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2574
diff
changeset
|
127 (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
|
128 (error "indexed empty 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 (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
|
130 (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
|
131 |
2574
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
132 (provide 'ring) |
c782b69b60a4
Added and fixed documentation.
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
2424
diff
changeset
|
133 |
658
7cbd4fcd8b0f
*** empty log message ***
Eric S. Raymond <esr@snark.thyrsus.com>
parents:
245
diff
changeset
|
134 ;;; ring.el ends here |