X-Git-Url: https://code.delx.au/gnu-emacs/blobdiff_plain/41dc743ded9ab4a149804d2f0ce3c6758c121cdb..0111ab41ec5239b1d7d0aed44dac798ebaa963e5:/lisp/emacs-lisp/ring.el

diff --git a/lisp/emacs-lisp/ring.el b/lisp/emacs-lisp/ring.el
index eedc801e16..fce07953ba 100644
--- a/lisp/emacs-lisp/ring.el
+++ b/lisp/emacs-lisp/ring.el
@@ -18,30 +18,37 @@
 ;; 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:
 
-;;; 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.
-;;;
-;;; In ring-ref, 0 is the index of the newest element.  Higher indexes
-;;; correspond to older elements until they wrap.
-;;;
-;;; 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:
 
+;;; User Functions:
+
 ;;;###autoload
-(defun ring-p (x) 
-  "Returns t if X is a ring; nil otherwise."
+(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)))))
@@ -49,63 +56,111 @@
 ;;;###autoload
 (defun make-ring (size)
   "Make a ring that can contain SIZE elements."
-  (cons 1 (cons 0 (make-vector (+ size 1) nil))))
+  (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)
-  "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)
-  "INDEX-1, with wraparound"
+  "Return INDEX-1, with wraparound."
   (- (if (= 0 index) veclen index) 1))
 
 (defun ring-length (ring)
-  "Number of elements 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)
-  (= 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)
-  "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))))
-	(setcar (cdr ring) (ring-minus1 tl (length vec)))
-	(aref vec tl))))
-
-(defun ring-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)
-  "Returns RING's INDEX element.
-INDEX need not be <= the ring length, the appropriate modulo operation
-will be performed.  Element 0 is the most recently inserted; higher indices
-correspond to older elements until they wrap."
-  (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 (ring-mod index numelts))
-	       (vec-index (ring-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