Data/Queue.hs

   1 -----------------------------------------------------------------------------
   2 -- |
   3 -- Module      :  Data.Queue
   4 -- Copyright   :  (c) The University of Glasgow 2002
   5 -- License     :  BSD-style (see the file libraries/base/LICENSE)
   6 --
   7 -- Maintainer  :  libraries@haskell.org
   8 -- Stability   :  experimental
   9 -- Portability :  portable
  10 --
  11 -- NOTE: This module is DEPRECATED.
  12 -- The data structure in "Data.Sequence" is a faster queue and also
  13 -- supports a wider variety of operations.
  14 --
  15 -- Queues with constant time operations, from
  16 -- /Simple and efficient purely functional queues and deques/,
  17 -- by Chris Okasaki, /JFP/ 5(4):583-592, October 1995.
  18 --
  19 -----------------------------------------------------------------------------
  20
  21 module Data.Queue
  22 {-# DEPRECATED "Use Data.Sequence instead: it's faster and has more operations" #-}
  23         (Queue,
  24         -- * Primitive operations
  25         -- | Each of these requires /O(1)/ time in the worst case.
  26         emptyQueue, addToQueue, deQueue,
  27         -- * Queues and lists
  28         listToQueue, queueToList
  29     ) where
  30
  31 import Prelude -- necessary to get dependencies right
  32 import Data.Typeable
  33
  34 -- | The type of FIFO queues.
  35 data Queue a = Q [a] [a] [a]
  36
  37 #include "Typeable.h"
  38 INSTANCE_TYPEABLE1(Queue,queueTc,"Queue")
  39
  40 -- Invariants for Q xs ys xs':
  41 --      length xs = length ys + length xs'
  42 --      xs' = drop (length ys) xs       -- in fact, shared (except after fmap)
  43 -- The queue then represents the list xs ++ reverse ys
  44
  45 instance Functor Queue where
  46         fmap f (Q xs ys xs') = Q (map f xs) (map f ys) (map f xs')
  47         -- The new xs' does not share the tail of the new xs, but it does
  48         -- share the tail of the old xs, so it still forces the rotations.
  49         -- Note that elements of xs' are ignored.
  50
  51 -- | The empty queue.
  52 emptyQueue :: Queue a
  53 emptyQueue = Q [] [] []
  54
  55 -- | Add an element to the back of a queue.
  56 addToQueue :: Queue a -> a -> Queue a
  57 addToQueue (Q xs ys xs') y = makeQ xs (y:ys) xs'
  58
  59 -- | Attempt to extract the front element from a queue.
  60 -- If the queue is empty, 'Nothing',
  61 -- otherwise the first element paired with the remainder of the queue.
  62 deQueue :: Queue a -> Maybe (a, Queue a)
  63 deQueue (Q [] _ _) = Nothing
  64 deQueue (Q (x:xs) ys xs') = Just (x, makeQ xs ys xs')
  65
  66 -- Assuming
  67 --      length ys <= length xs + 1
  68 --      xs' = drop (length ys - 1) xs
  69 -- construct a queue respecting the invariant.
  70 makeQ :: [a] -> [a] -> [a] -> Queue a
  71 makeQ xs ys [] = listToQueue (rotate xs ys [])
  72 makeQ xs ys (_:xs') = Q xs ys xs'
  73
  74 -- Assuming length ys = length xs + 1,
  75 --      rotate xs ys zs = xs ++ reverse ys ++ zs
  76 rotate :: [a] -> [a] -> [a] -> [a]
  77 rotate [] (y:_) zs = y : zs             -- the _ here must be []
  78 rotate (x:xs) (y:ys) zs = x : rotate xs ys (y:zs)
  79
  80 -- | A queue with the same elements as the list.
  81 listToQueue :: [a] -> Queue a
  82 listToQueue xs = Q xs [] xs
  83
  84 -- | The elements of a queue, front first.
  85 queueToList :: Queue a -> [a]
  86 queueToList (Q xs ys _) = xs ++ reverse ys