(defun ring-p (x)
"Returns 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)
"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."
(- (if (= 0 index) veclen index) 1))
(defun ring-length (ring)
"Number of elements in the ring RING."
(car (cdr ring)))
(defun ring-empty-p (ring)
(= 0 (car (cdr ring))))
(defun ring-index (index head ringlen veclen)
(setq index (mod index ringlen))
(mod (1- (+ head (- ringlen index))) veclen))
(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)
"Returns 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))))))
(provide 'ring)