(ewoc-create, ewoc-map, ewoc-locate, ewoc-invalidate, ewoc-collect):

[gnu-emacs] / lisp / emacs-lisp / ring.el

diff --git a/lisp/emacs-lisp/ring.el b/lisp/emacs-lisp/ring.el
index 9951221c1d860cf885a3c93f1f16c35e5424c292..fce07953ba92c5f93bd9c5d28c9141c029048301 100644 (file)
--- a/lisp/emacs-lisp/ring.el
+++ b/lisp/emacs-lisp/ring.el
@@ -1,4 +1,4 @@
-;;; ring.el --- handle rings of marks
+;;; ring.el --- handle rings of items

 
 ;; Copyright (C) 1992 Free Software Foundation, Inc.
 
 
 ;; Copyright (C) 1992 Free Software Foundation, Inc.
 


@@ -18,111 +18,149 @@
 ;; GNU General Public License for more details.
 
 ;; You should have received a copy of the GNU General Public License
 ;; GNU General Public License for more details.
 
 ;; You should have received a copy of the GNU General Public License

-;; along with GNU Emacs; see the file COPYING.  If not, write to
-;; the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
+;; along with GNU Emacs; see the file COPYING.  If not, write to the
+;; Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+;; Boston, MA 02111-1307, USA.

 
 ;;; Commentary:
 
 
 ;;; Commentary:
 

-;;; This code defines a ring data structure. A ring is a 
-;;;     (hd-index tl-index . vector) 
-;;; list. You can insert to, remove from, and rotate a ring. When the ring
-;;; fills up, insertions cause the oldest elts to be quietly dropped.
-;;;
-;;; HEAD = index of the newest item on the ring.
-;;; TAIL = index of the oldest item on the ring.
-;;;
-;;; These functions are used by the input history mechanism, but they can
-;;; be used for other purposes as well.
+;; This code defines a ring data structure.  A ring is a
+;;     (hd-index length . vector)
+;; list.  You can insert to, remove from, and rotate a ring.  When the ring
+;; fills up, insertions cause the oldest elts to be quietly dropped.
+;;
+;; In ring-ref, 0 is the index of the newest element.  Higher indexes
+;; correspond to older elements; when the index equals the ring length,
+;; it wraps to the newest element again.
+;;
+;; hd-index = vector index of the oldest ring item.
+;;         Newer items follow this item; at the end of the vector,
+;;         they wrap around to the start of the vector.
+;; length = number of items currently in the ring.
+;;         This never exceeds the length of the vector itself.
+;;
+;; These functions are used by the input history mechanism, but they can
+;; be used for other purposes as well.

 
 ;;; Code:
 
 
 ;;; Code:
 

-(provide 'history)
+;;; User Functions:

 
 

-(defun ring-p (x) 
-  "T if X is a ring; NIL otherwise."
+;;;###autoload
+(defun ring-p (x)
+  "Return t if X is a ring; nil otherwise."

   (and (consp x) (integerp (car x))
        (consp (cdr x)) (integerp (car (cdr x)))
        (vectorp (cdr (cdr x)))))
 
   (and (consp x) (integerp (car x))
        (consp (cdr x)) (integerp (car (cdr x)))
        (vectorp (cdr (cdr x)))))
 

+;;;###autoload

 (defun make-ring (size)
 (defun make-ring (size)

-  "Make a ring that can contain SIZE elts"
-  (cons 1 (cons 0 (make-vector (+ size 1) nil))))
+  "Make a ring that can contain SIZE elements."
+  (cons 0 (cons 0 (make-vector size nil))))
+
+(defun ring-insert-at-beginning (ring item)
+  "Add to RING the item ITEM.  Add it at the front, as the oldest item."
+  (let* ((vec (cdr (cdr ring)))
+         (veclen (length vec))
+         (hd (car ring))
+         (ln (car (cdr ring))))
+    (setq ln (min veclen (1+ ln))
+          hd (ring-minus1 hd veclen))
+    (aset vec hd item)
+    (setcar ring hd)
+    (setcar (cdr ring) ln)))

 
 (defun ring-plus1 (index veclen)
 
 (defun ring-plus1 (index veclen)

-  "INDEX+1, with wraparound"
+  "Return INDEX+1, with wraparound."

   (let ((new-index (+ index 1)))
     (if (= new-index veclen) 0 new-index)))
 
 (defun ring-minus1 (index veclen)
   (let ((new-index (+ index 1)))
     (if (= new-index veclen) 0 new-index)))
 
 (defun ring-minus1 (index veclen)

-  "INDEX-1, with wraparound"
+  "Return INDEX-1, with wraparound."

   (- (if (= 0 index) veclen index) 1))
 
 (defun ring-length (ring)
   (- (if (= 0 index) veclen index) 1))
 
 (defun ring-length (ring)

-  "Number of elts in the ring."
-  (let ((hd (car ring)) (tl (car (cdr ring)))  (siz (length (cdr (cdr ring)))))
-    (let ((len (if (<= hd tl) (+ 1 (- tl hd)) (+ 1 tl (- siz hd)))))
-      (if (= len siz) 0 len))))
+  "Return the number of elements in the RING."
+  (car (cdr ring)))
+
+(defun ring-index (index head ringlen veclen)
+  "Convert nominal ring index INDEX to an internal index.
+The internal index refers to the items ordered from newest to oldest.
+HEAD is the index of the oldest element in the ring.
+RINGLEN is the number of elements currently in the ring.
+VECLEN is the size of the vector in the ring."
+  (setq index (mod index ringlen))
+  (mod (1- (+ head (- ringlen index))) veclen))

 
 (defun ring-empty-p (ring)
 
 (defun ring-empty-p (ring)

-  (= 0 (ring-length ring)))
+  "Return t if RING is empty; nil otherwise."
+  (zerop (car (cdr ring))))
+
+(defun ring-size (ring)
+  "Return the size of RING, the maximum number of elements it can contain."
+  (length (cdr (cdr ring))))
+
+(defun ring-copy (ring)
+  "Return a copy of RING."
+  (let* ((vec (cdr (cdr ring)))
+        (hd  (car ring))
+        (ln  (car (cdr ring))))
+    (cons hd (cons ln (copy-sequence vec)))))

 
 (defun ring-insert (ring item)
 
 (defun ring-insert (ring item)

-  "Insert a new item onto the ring. If the ring is full, dump the oldest
-item to make room."       
-  (let* ((vec (cdr (cdr ring)))  (len (length vec))
-        (new-hd (ring-minus1 (car ring) len)))
-      (setcar ring new-hd)
-      (aset vec new-hd item)
-      (if (ring-empty-p ring) ;overflow -- dump one off the tail.
-         (setcar (cdr ring) (ring-minus1 (car (cdr ring)) len)))))
-
-(defun ring-remove (ring)
-  "Remove the oldest item retained on the ring."
-  (if (ring-empty-p ring) (error "Ring empty")
-      (let ((tl (car (cdr ring)))  (vec (cdr (cdr ring))))
-       (set-car (cdr ring) (ring-minus1 tl (length vec)))
-       (aref vec tl))))
-
-;;; This isn't actually used in this package. I just threw it in in case
-;;; someone else wanted it. If you want rotating-ring behavior on your history
-;;; retrieval (analagous to kill ring behavior), this function is what you
-;;; need. I should write the yank-input and yank-pop-input-or-kill to go with
-;;; this, and not bind it to a key by default, so it would be available to
-;;; people who want to bind it to a key. But who would want it? Blech.
-(defun ring-rotate (ring n)
-  (if (not (= n 0))
-      (if (ring-empty-p ring) ;Is this the right error check?
-         (error "ring empty")
-         (let ((hd (car ring))  (tl (car (cdr ring)))  (vec (cdr (cdr ring))))
-           (let ((len (length vec)))
-             (while (> n 0)
-               (setq tl (ring-plus1 tl len))
-               (aset ring tl (aref ring hd))
-               (setq hd (ring-plus1 hd len))
-               (setq n (- n 1)))
-             (while (< n 0)
-               (setq hd (ring-minus1 hd len))
-               (aset vec hd (aref vec tl))
-               (setq tl (ring-minus1 tl len))
-               (setq n (- n 1))))
-           (set-car ring hd)
-           (set-car (cdr ring) tl)))))
-
-(defun comint-mod (n m)
-  "Returns N mod M.  M is positive.
-Answer is guaranteed to be non-negative, and less than m."
-  (let ((n (% n m)))
-    (if (>= n 0) n
-       (+ n
-          (if (>= m 0) m (- m)))))) ; (abs m)
+  "Insert onto ring RING the item ITEM, as the newest (last) item.
+If the ring is full, dump the oldest item to make room."
+  (let* ((vec (cdr (cdr ring)))
+         (veclen (length vec))
+         (hd (car ring))
+         (ln (car (cdr ring))))
+    (prog1
+        (aset vec (mod (+ hd ln) veclen) item)
+      (if (= ln veclen)
+          (setcar ring (ring-plus1 hd veclen))
+        (setcar (cdr ring) (1+ ln))))))
+
+(defun ring-remove (ring &optional index)
+  "Remove an item from the RING.  Return the removed item.
+If optional INDEX is nil, remove the oldest item.  If it's
+numeric, remove the element indexed."
+  (if (ring-empty-p ring)
+      (error "Ring empty")
+    (let* ((hd (car ring))
+           (ln (car (cdr ring)))
+           (vec (cdr (cdr ring)))
+           (veclen (length vec))
+           (tl (mod (1- (+ hd ln)) veclen))
+           oldelt)
+      (if (null index)
+          (setq index (1- ln)))
+      (setq index (ring-index index hd ln veclen))
+      (setq oldelt (aref vec index))
+      (while (/= index tl)
+        (aset vec index (aref vec (ring-plus1 index veclen)))
+        (setq index (ring-plus1 index veclen)))
+      (aset vec tl nil)
+      (setcar (cdr ring) (1- ln))
+      oldelt)))

 
 (defun ring-ref (ring index)
 
 (defun ring-ref (ring index)

-  (let ((numelts (ring-length ring)))
-    (if (= numelts 0) (error "indexed empty ring")
-       (let* ((hd (car ring))  (tl (car (cdr ring)))  (vec (cdr (cdr ring)))
-              (index (comint-mod index numelts))
-              (vec-index (comint-mod (+ index hd) 
-                                     (length vec))))
-         (aref vec vec-index)))))
+  "Return RING's INDEX element.
+INDEX = 0 is the most recently inserted; higher indices
+correspond to older elements.
+INDEX need not be <= the ring length; the appropriate modulo operation
+will be performed."
+  (if (ring-empty-p ring)
+      (error "Accessing an empty ring")
+    (let* ((hd (car ring))  (ln (car (cdr ring)))  (vec (cdr (cdr ring))))
+      (aref vec (ring-index index hd ln (length vec))))))
+
+(defun ring-elements (ring)
+  "Return a list of the elements of RING."
+  (mapcar #'identity (cddr ring)))
+
+;;; provide ourself:
+
+(provide 'ring)

 
 

+;;; arch-tag: e707682b-ed69-47c9-b20f-cf2c68cc92d2

 ;;; ring.el ends here
 ;;; ring.el ends here