[project @ 2005-10-21 10:26:57 by ross]
[packages/old-time.git] / 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