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

   1 ;;; queue.el --- Queue data structure  -*- lexical-binding: t; -*-
   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.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 ;;; Code:
  46
  47 (eval-when-compile (require 'cl))
  48
  49
  50 (defstruct (queue
  51             ;; A tagged list is the pre-defstruct representation.
  52             ;; (:type list)
  53             :named
  54             (:constructor nil)
  55             (:constructor queue-create ())
  56             (:copier nil))
  57   head tail)
  58
  59
  60 ;;;###autoload
  61 (defalias 'make-queue 'queue-create
  62   "Create an empty queue data structure.")
  63
  64
  65 (defun queue-enqueue (queue element)
  66   "Append an ELEMENT to the end of the QUEUE."
  67   (if (queue-head queue)
  68       (setcdr (queue-tail queue)
  69               (setf (queue-tail queue) (cons element nil)))
  70     (setf (queue-head queue)
  71           (setf (queue-tail queue) (cons element nil)))))
  72
  73 (defalias 'queue-append 'queue-enqueue)
  74
  75
  76 (defun queue-prepend (queue element)
  77   "Prepend an ELEMENT to the front of the QUEUE."
  78   (if (queue-head queue)
  79       (push element (queue-head queue))
  80     (setf (queue-head queue)
  81           (setf (queue-tail queue) (cons element nil)))))
  82
  83
  84 (defun queue-dequeue (queue)
  85   "Remove the first element of QUEUE and return it.
  86 Returns nil if the queue is empty."
  87   (unless (cdr (queue-head queue)) (setf (queue-tail queue) nil))
  88   (pop (queue-head queue)))
  89
  90
  91 (defun queue-empty (queue)
  92   "Return t if QUEUE is empty, otherwise return nil."
  93   (null (queue-head queue)))
  94
  95
  96 (defun queue-first (queue)
  97   "Return the first element of QUEUE or nil if it is empty,
  98 without removing it from the QUEUE."
  99   (car (queue-head queue)))
 100
 101
 102 (defun queue-nth (queue n)
 103   "Return the nth element of a queue, without removing it.
 104 If the length of the queue is less than N, return nil. The first
 105 element in the queue has index 0."
 106   (nth n (queue-head queue)))
 107
 108
 109 (defun queue-last (queue)
 110   "Return the last element of QUEUE, without removing it.
 111 Returns nil if the QUEUE is empty."
 112   (car (queue-tail queue)))
 113
 114
 115 (defun queue-all (queue)
 116   "Return a list of all elements of QUEUE or nil if it is empty.
 117 The oldest element in the queue is the first in the list."
 118   (queue-head queue))
 119
 120
 121 (defun queue-copy (queue)
 122   "Return a copy of QUEUE.
 123 The new queue contains the elements of QUEUE in the same
 124 order. The elements themselves are *not* copied."
 125   (let ((q (queue-create))
 126         (list (queue-head queue)))
 127     (when (queue-head queue)
 128       (setf (queue-head q) (cons (car (queue-head queue)) nil)
 129             (queue-tail q) (queue-head q))
 130       (while (setq list (cdr list))
 131         (setf (queue-tail q)
 132               (setcdr (queue-tail q) (cons (car list) nil)))))
 133     q))
 134
 135
 136 (defun queue-length (queue)
 137   "Return the number of elements in QUEUE."
 138   (length (queue-head queue)))
 139
 140
 141 (defun queue-clear (queue)
 142   "Remove all elements from QUEUE."
 143   (setf (queue-head queue) nil
 144         (queue-tail queue) nil))
 145
 146
 147 (provide 'queue)
 148
 149
 150 ;;; queue.el ends here