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 -----------------------------------------------------------------------------

22 {-# DEPRECATED "Use Data.Sequence instead: it's faster and has more operations" #-}

24 -- * Primitive operations

25 -- | Each of these requires /O(1)/ time in the worst case.

27 -- * Queues and lists

28 listToQueue, queueToList

34 -- | The type of FIFO queues.

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

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.

51 -- | The empty queue.

52 emptyQueue :: Queue a

55 -- | Add an element to the back of a queue.

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.

66 -- Assuming

67 -- length ys <= length xs + 1

68 -- xs' = drop (length ys - 1) xs

69 -- construct a queue respecting the invariant.

74 -- Assuming length ys = length xs + 1,

75 -- rotate xs ys zs = xs ++ reverse ys ++ zs

80 -- | A queue with the same elements as the list.

84 -- | The elements of a queue, front first.