Mercurial > hg > xemacs-beta

comparison lisp/utils/ring.el @ 0:376386a54a3c r19-14

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r19-14
author cvs
date Mon, 13 Aug 2007 08:45:50 +0200
parents
children ac2d302a0011
comparison
equal deleted inserted replaced
-1:000000000000 0:376386a54a3c
1 ;;; ring.el --- handle rings of items
2
3 ;; Copyright (C) 1992 Free Software Foundation, Inc.
4
5 ;; Maintainer: FSF
6 ;; Keywords: extensions
7
8 ;; This file is part of GNU Emacs.
9
10 ;; GNU Emacs is free software; you can redistribute it and/or modify
11 ;; it under the terms of the GNU General Public License as published by
12 ;; the Free Software Foundation; either version 2, or (at your option)
13 ;; any later version.
14
15 ;; GNU Emacs is distributed in the hope that it will be useful,
16 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
17 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 ;; GNU General Public License for more details.
19
20 ;; You should have received a copy of the GNU General Public License
21 ;; along with GNU Emacs; see the file COPYING. If not, write to
22 ;; the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
23
24 ;;; Synched up with: FSF 19.30.
25
26 ;;; Commentary:
27
28 ;;; This code defines a ring data structure. A ring is a
29 ;;; (hd-index length . vector)
30 ;;; list. You can insert to, remove from, and rotate a ring. When the ring
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
34 ;;; correspond to older elements until they wrap.
35 ;;;
36 ;;; hd-index = index of the newest item on the ring.
37 ;;; length = number of ring items.
38 ;;;
39 ;;; These functions are used by the input history mechanism, but they can
40 ;;; be used for other purposes as well.
41
42 ;;; Code:
43
44 ;;;###autoload
45 (defun ringp (x)
46 "Returns t if X is a ring; nil otherwise."
47 (and (consp x) (integerp (car x))
48 (consp (cdr x)) (integerp (car (cdr x)))
49 (vectorp (cdr (cdr x)))))
50
51 ;;;###autoload
52 (define-obsolete-function-alias 'ring-p 'ringp)
53
54 ;;;###autoload
55 (defun make-ring (size)
56 "Make a ring that can contain SIZE elements."
57 (cons 0 (cons 0 (make-vector size nil))))
58
59 (defun ring-insert-at-beginning (ring item)
60 "Add to RING the item ITEM. Add it at the front (the early end)."
61 (let* ((vec (cdr (cdr ring)))
62 (veclen (length vec))
63 (hd (car ring))
64 (ln (car (cdr ring))))
65 (setq ln (min veclen (1+ ln))
66 hd (ring-minus1 hd veclen))
67 (aset vec hd item)
68 (setcar ring hd)
69 (setcar (cdr ring) ln)))
70
71 (defun ring-plus1 (index veclen)
72 "INDEX+1, with wraparound"
73 (let ((new-index (+ index 1)))
74 (if (= new-index veclen) 0 new-index)))
75
76 (defun ring-minus1 (index veclen)
77 "INDEX-1, with wraparound"
78 (- (if (= 0 index) veclen index) 1))
79
80 (defun ring-length (ring)
81 "Number of elements in the ring."
82 (car (cdr ring)))
83
84 (defun ring-empty-p (ring)
85 (= 0 (car (cdr ring))))
86
87 (defun ring-index (index head ringlen veclen)
88 (setq index (mod index ringlen))
89 (mod (1- (+ head (- ringlen index))) veclen))
90
91 (defun ring-insert (ring item)
92 "Insert onto ring RING the item ITEM, as the newest (last) item.
93 If the ring is full, dump the oldest item to make room."
94 (let* ((vec (cdr (cdr ring)))
95 (veclen (length vec))
96 (hd (car ring))
97 (ln (car (cdr ring))))
98 (prog1
99 (aset vec (mod (+ hd ln) veclen) item)
100 (if (= ln veclen)
101 (setcar ring (ring-plus1 hd veclen))
102 (setcar (cdr ring) (1+ ln))))))
103
104 (defun ring-remove (ring &optional index)
105 "Remove an item from the RING. Return the removed item.
106 If optional INDEX is nil, remove the oldest item. If it's
107 numeric, remove the element indexed."
108 (if (ring-empty-p ring)
109 (error "Ring empty")
110 (let* ((hd (car ring))
111 (ln (car (cdr ring)))
112 (vec (cdr (cdr ring)))
113 (veclen (length vec))
114 (tl (mod (1- (+ hd ln)) veclen))
115 oldelt)
116 (if (null index)
117 (setq index (1- ln)))
118 (setq index (ring-index index hd ln veclen))
119 (setq oldelt (aref vec index))
120 (while (/= index tl)
121 (aset vec index (aref vec (ring-plus1 index veclen)))
122 (setq index (ring-plus1 index veclen)))
123 (aset vec tl nil)
124 (setcar (cdr ring) (1- ln))
125 oldelt)))
126
127 (defun ring-ref (ring index)
128 "Returns RING's INDEX element.
129 INDEX need not be <= the ring length, the appropriate modulo operation
130 will be performed. Element 0 is the most recently inserted; higher indices
131 correspond to older elements until they wrap."
132 (if (ring-empty-p ring)
133 (error "indexed empty ring")
134 (let* ((hd (car ring)) (ln (car (cdr ring))) (vec (cdr (cdr ring))))
135 (aref vec (ring-index index hd ln (length vec))))))
136
137 (provide 'ring)
138
139 ;;; ring.el ends here