(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)))))
(defun make-ring (size)
"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)
"Return INDEX+1, with wraparound."
(let ((new-index (+ index 1)))
(if (= new-index veclen) 0 new-index)))
(defun ring-minus1 (index veclen)
"Return INDEX-1, with wraparound."
(- (if (= 0 index) veclen index) 1))
(defun ring-length (ring)
"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)
"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 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)
"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, in order, newest first."
(let ((start (car ring))
(size (ring-size ring))
(vect (cddr ring))
lst)
(dotimes (var (cadr ring) lst)
(push (aref vect (mod (+ start var) size)) lst))))
(provide 'ring)