code.delx.au - gnu-emacs-elpa/blob - packages/queue/queue.el

   1 ;;; queue.el --- Queue data structure
   2
   3 ;; Copyright (C) 1991-1995, 2008-2009, 2012  Free Software Foundation, Inc
   4
   5 ;; Author: Inge Wallin <inge@lysator.liu.se>
   6 ;;         Toby Cubitt <toby-predictive@dr-qubit.org>
   7 ;; Maintainer: Toby Cubitt <toby-predictive@dr-qubit.org>
   8 ;; Version: 0.1
   9 ;; Keywords: extensions, data structures, queue
  10 ;; URL: http://www.dr-qubit.org/emacs.php
  11 ;; Repository: http://www.dr-qubit.org/git/predictive.git
  12
  13 ;; This file is part of Emacs.
  14 ;;
  15 ;; GNU Emacs is free software: you can redistribute it and/or modify it under
  16 ;; the terms of the GNU General Public License as published by the Free
  17 ;; Software Foundation, either version 3 of the License, or (at your option)
  18 ;; any later version.
  19 ;;
  20 ;; GNU Emacs is distributed in the hope that it will be useful, but WITHOUT
  21 ;; ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  22 ;; FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  23 ;; more details.
  24 ;;
  25 ;; You should have received a copy of the GNU General Public License along
  26 ;; with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
  27
  28
  29 ;;; Commentary:
  30 ;;
  31 ;; These queues can be used both as a first-in last-out (FILO) and as a
  32 ;; first-in first-out (FIFO) stack, i.e. elements can be added to the front or
  33 ;; back of the queue, and can be removed from the front. (This type of data
  34 ;; structure is sometimes called an "output-restricted deque".)
  35 ;;
  36 ;; You create a queue using `make-queue', add an element to the end of the
  37 ;; queue using `queue-enqueue', and push an element onto the front of the
  38 ;; queue using `queue-prepend'. To remove the first element from a queue, use
  39 ;; `queue-dequeue'. A number of other queue convenience functions are also
  40 ;; provided, all starting with the prefix `queue-'.  Functions with prefix
  41 ;; `queue--' are for internal use only, and should never be used outside this
  42 ;; package.
  43
  44
  45 ;;; Change Log:
  46 ;;
  47 ;; Version 0.1
  48 ;; * the old Elib library of the same name, updated to use defstructs
  49
  50
  51
  52 ;;; Code:
  53
  54 (eval-when-compile (require 'cl))
  55
  56
  57 (defstruct (queue
  58             ;; A tagged list is the pre-defstruct representation.
  59             ;; (:type list)
  60             :named
  61             (:constructor nil)
  62             (:constructor queue-create ())
  63             (:copier nil))
  64   head tail)
  65
  66
  67 ;;;###autoload
  68 (defalias 'make-queue 'queue-create
  69   "Create an empty queue data structure.")
  70
  71
  72 (defun queue-enqueue (queue element)
  73   "Append an ELEMENT to the end of the QUEUE."
  74   (if (queue-head queue)
  75       (setcdr (queue-tail queue)
  76               (setf (queue-tail queue) (cons element nil)))
  77     (setf (queue-head queue)
  78           (setf (queue-tail queue) (cons element nil)))))
  79
  80 (defalias 'queue-append 'queue-enqueue)
  81
  82
  83 (defun queue-prepend (queue element)
  84   "Prepend an ELEMENT to the front of the QUEUE."
  85   (if (queue-head queue)
  86       (push element (queue-head queue))
  87     (setf (queue-head queue)
  88           (setf (queue-tail queue) (cons element nil)))))
  89
  90
  91 (defun queue-dequeue (queue)
  92   "Remove the first element of QUEUE and return it.
  93 Returns nil if the queue is empty."
  94   (unless (cdr (queue-head queue)) (setf (queue-tail queue) nil))
  95   (pop (queue-head queue)))
  96
  97
  98 (defmacro queue-empty (queue)
  99   "Return t if QUEUE is empty, otherwise return nil."
 100   (null (queue-head queue)))
 101
 102
 103 (defmacro queue-first (queue)
 104   "Return the first element of QUEUE or nil if it is empty,
 105 without removing it from the QUEUE."
 106   (car (queue-head queue)))
 107
 108
 109 (defun queue-nth (queue n)
 110   "Return the nth element of a queue, without removing it.
 111 If the length of the queue is less than N, return nil. The first
 112 element in the queue has index 0."
 113   (nth n (queue-head queue)))
 114
 115
 116 (defun queue-last (queue)
 117   "Return the last element of QUEUE, without removing it.
 118 Returns nil if the QUEUE is empty."
 119   (car (queue-tail queue)))
 120
 121
 122 (defun queue-all (queue)
 123   "Return a list of all elements of QUEUE or nil if it is empty.
 124 The oldest element in the queue is the first in the list."
 125   (queue-head queue))
 126
 127
 128 (defun queue-copy (queue)
 129   "Return a copy of QUEUE.
 130 The new queue contains the elements of QUEUE in the same
 131 order. The elements themselves are *not* copied."
 132   (let ((q (queue-create))
 133         (list (queue-head queue)))
 134     (when (queue-head queue)
 135       (setf (queue-head q) (cons (car (queue-head queue)) nil)
 136             (queue-tail q) (queue-head q))
 137       (while (setq list (cdr list))
 138         (setf (queue-tail q)
 139               (setcdr (queue-tail q) (cons (car list) nil)))))
 140     q))
 141
 142
 143 (defun queue-length (queue)
 144   "Return the number of elements in QUEUE."
 145   (length (queue-head queue)))
 146
 147
 148 (defun queue-clear (queue)
 149   "Remove all elements from QUEUE."
 150   (setf (queue-head queue) nil
 151         (queue-tail queue) nil))
 152
 153
 154 (provide 'queue)
 155
 156
 157 ;;; queue.el ends here