lisp/emacs-lisp/ring.el

   1 ;;; ring.el --- handle rings of items
   2
   3 ;; Copyright (C) 1992, 2001, 2002, 2003, 2004, 2005,
   4 ;;   2006, 2007 Free Software Foundation, Inc.
   5
   6 ;; Maintainer: FSF
   7 ;; Keywords: extensions
   8
   9 ;; This file is part of GNU Emacs.
  10
  11 ;; GNU Emacs is free software; you can redistribute it and/or modify
  12 ;; it under the terms of the GNU General Public License as published by
  13 ;; the Free Software Foundation; either version 2, or (at your option)
  14 ;; any later version.
  15
  16 ;; GNU Emacs is distributed in the hope that it will be useful,
  17 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19 ;; GNU General Public License for more details.
  20
  21 ;; You should have received a copy of the GNU General Public License
  22 ;; along with GNU Emacs; see the file COPYING.  If not, write to the
  23 ;; Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  24 ;; Boston, MA 02110-1301, USA.
  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; when the index equals the ring length,
  35 ;; it wraps to the newest element again.
  36 ;;
  37 ;; hd-index = vector index of the oldest ring item.
  38 ;;         Newer items follow this item; at the end of the vector,
  39 ;;         they wrap around to the start of the vector.
  40 ;; length = number of items currently in the ring.
  41 ;;         This never exceeds the length of the vector itself.
  42 ;;
  43 ;; These functions are used by the input history mechanism, but they can
  44 ;; be used for other purposes as well.
  45
  46 ;;; Code:
  47
  48 ;;; User Functions:
  49
  50 ;;;###autoload
  51 (defun ring-p (x)
  52   "Return t if X is a ring; nil otherwise."
  53   (and (consp x) (integerp (car x))
  54        (consp (cdr x)) (integerp (car (cdr x)))
  55        (vectorp (cdr (cdr x)))))
  56
  57 ;;;###autoload
  58 (defun make-ring (size)
  59   "Make a ring that can contain SIZE elements."
  60   (cons 0 (cons 0 (make-vector size nil))))
  61
  62 (defun ring-insert-at-beginning (ring item)
  63   "Add to RING the item ITEM.  Add it at the front, as the oldest item."
  64   (let* ((vec (cdr (cdr ring)))
  65          (veclen (length vec))
  66          (hd (car ring))
  67          (ln (car (cdr ring))))
  68     (setq ln (min veclen (1+ ln))
  69           hd (ring-minus1 hd veclen))
  70     (aset vec hd item)
  71     (setcar ring hd)
  72     (setcar (cdr ring) ln)))
  73
  74 (defun ring-plus1 (index veclen)
  75   "Return INDEX+1, with wraparound."
  76   (let ((new-index (+ index 1)))
  77     (if (= new-index veclen) 0 new-index)))
  78
  79 (defun ring-minus1 (index veclen)
  80   "Return INDEX-1, with wraparound."
  81   (- (if (= 0 index) veclen index) 1))
  82
  83 (defun ring-length (ring)
  84   "Return the number of elements in the RING."
  85   (car (cdr ring)))
  86
  87 (defun ring-index (index head ringlen veclen)
  88   "Convert nominal ring index INDEX to an internal index.
  89 The internal index refers to the items ordered from newest to oldest.
  90 HEAD is the index of the oldest element in the ring.
  91 RINGLEN is the number of elements currently in the ring.
  92 VECLEN is the size of the vector in the ring."
  93   (setq index (mod index ringlen))
  94   (mod (1- (+ head (- ringlen index))) veclen))
  95
  96 (defun ring-empty-p (ring)
  97   "Return t if RING is empty; nil otherwise."
  98   (zerop (car (cdr ring))))
  99
 100 (defun ring-size (ring)
 101   "Return the size of RING, the maximum number of elements it can contain."
 102   (length (cdr (cdr ring))))
 103
 104 (defun ring-copy (ring)
 105   "Return a copy of RING."
 106   (let* ((vec (cdr (cdr ring)))
 107          (hd  (car ring))
 108          (ln  (car (cdr ring))))
 109     (cons hd (cons ln (copy-sequence vec)))))
 110
 111 (defun ring-insert (ring item)
 112   "Insert onto ring RING the item ITEM, as the newest (last) item.
 113 If the ring is full, dump the oldest item to make room."
 114   (let* ((vec (cdr (cdr ring)))
 115          (veclen (length vec))
 116          (hd (car ring))
 117          (ln (car (cdr ring))))
 118     (prog1
 119         (aset vec (mod (+ hd ln) veclen) item)
 120       (if (= ln veclen)
 121           (setcar ring (ring-plus1 hd veclen))
 122         (setcar (cdr ring) (1+ ln))))))
 123
 124 (defun ring-remove (ring &optional index)
 125   "Remove an item from the RING.  Return the removed item.
 126 If optional INDEX is nil, remove the oldest item.  If it's
 127 numeric, remove the element indexed."
 128   (if (ring-empty-p ring)
 129       (error "Ring empty")
 130     (let* ((hd (car ring))
 131            (ln (car (cdr ring)))
 132            (vec (cdr (cdr ring)))
 133            (veclen (length vec))
 134            (tl (mod (1- (+ hd ln)) veclen))
 135            oldelt)
 136       (if (null index)
 137           (setq index (1- ln)))
 138       (setq index (ring-index index hd ln veclen))
 139       (setq oldelt (aref vec index))
 140       (while (/= index tl)
 141         (aset vec index (aref vec (ring-plus1 index veclen)))
 142         (setq index (ring-plus1 index veclen)))
 143       (aset vec tl nil)
 144       (setcar (cdr ring) (1- ln))
 145       oldelt)))
 146
 147 (defun ring-ref (ring index)
 148   "Return RING's INDEX element.
 149 INDEX = 0 is the most recently inserted; higher indices
 150 correspond to older elements.
 151 INDEX need not be <= the ring length; the appropriate modulo operation
 152 will be performed."
 153   (if (ring-empty-p ring)
 154       (error "Accessing an empty ring")
 155     (let* ((hd (car ring))  (ln (car (cdr ring)))  (vec (cdr (cdr ring))))
 156       (aref vec (ring-index index hd ln (length vec))))))
 157
 158 (defun ring-elements (ring)
 159   "Return a list of the elements of RING, in order, newest first."
 160   (let ((start (car ring))
 161         (size (ring-size ring))
 162         (vect (cddr ring))
 163         lst)
 164     (dotimes (var (cadr ring) lst)
 165       (push (aref vect (mod (+ start var) size)) lst))))
 166
 167 ;;; provide ourself:
 168
 169 (provide 'ring)
 170
 171 ;;; arch-tag: e707682b-ed69-47c9-b20f-cf2c68cc92d2
 172 ;;; ring.el ends here