-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A typeclass and an implementation for double-ended queues.
--   
--   A typeclass for double-ended queues, and an implementation of Banker's
--   Dequeues, as described in Chris Okasaki's Purely Functional Data
--   Structures.
@package dequeue
@version 0.1.7


-- | A newtype used entirely for its derived <a>Read</a> and <a>Show</a>
--   instances. These are then used by <tt>showDequeue</tt> and
--   <tt>readDequeue</tt> to make writing <a>Read</a> and <a>Show</a>
--   instances for <a>Dequeue</a>s easier.
module Data.Dequeue.Show
newtype Dequeue a
Dequeue :: [a] -> Dequeue a
instance GHC.Show.Show a => GHC.Show.Show (Data.Dequeue.Show.Dequeue a)
instance GHC.Read.Read a => GHC.Read.Read (Data.Dequeue.Show.Dequeue a)


-- | A typeclass for double-ended queues, and an implementation of Banker's
--   Dequeues, as described in Chris Okasaki's Purely Functional Data
--   Structures.
module Data.Dequeue

-- | A typeclass for double-ended queues.
class Foldable q => Dequeue q

-- | Generates an empty queue.
empty :: Dequeue q => q a

-- | Returns <a>True</a> if this queue is empty.
null :: Dequeue q => q a -> Bool

-- | Returns the item on the front of the queue.
first :: Dequeue q => q a -> Maybe a

-- | Returns the item on the end of the queue.
last :: Dequeue q => q a -> Maybe a

-- | Returns the first n items from the front of the queue, in the order
--   they would be popped.
takeFront :: Dequeue q => Int -> q a -> [a]

-- | Returns the last n items from the end of the queue, in the order they
--   would be popped.
takeBack :: Dequeue q => Int -> q a -> [a]

-- | Pushes an item onto the front of the queue.
pushFront :: Dequeue q => q a -> a -> q a

-- | Pops an item from the front of the queue.
popFront :: Dequeue q => q a -> Maybe (a, q a)

-- | Pushes an item onto the back of the queue.
pushBack :: Dequeue q => q a -> a -> q a

-- | Pops an item from the back of the queue.
popBack :: Dequeue q => q a -> Maybe (a, q a)

-- | Converts a list into a queue.
fromList :: Dequeue q => [a] -> q a

-- | Support to make generating <a>Show</a> instances for <a>Dequeue</a>s
--   easier. Use as follows:
--   
--   <pre>
--   instance Show a =&gt; Show (MyDequeue a) where
--       show q = showDequeue q
--   
--   </pre>
--   
--   The resulting <a>Show</a> instance will be portable between
--   <tt>Deqeue</tt> instances, and will not expose the details of how your
--   <a>Dequeue</a> instance is constructed.
showDequeue :: (Foldable q, Dequeue q, Show a) => q a -> String

-- | Support to make generating <a>Read</a> instances for <a>Dequeue</a>s
--   easier. Use as follows:
--   
--   <pre>
--   instance Read a =&gt; Read (MyDequeue a) where
--       readsPrec i = readDequeue $ readsPrec i
--   
--   </pre>
--   
--   The resulting <a>Read</a> instance will be portable between
--   <tt>Deqeue</tt> instances, and will not expose the details of how your
--   <a>Dequeue</a> instance is constructed.
readDequeue :: (Dequeue q, Read a) => ReadS (Dequeue a) -> ReadS (q a)

-- | Validates that if you push, then pop, the front of the queue, you get
--   the same queue.
prop_pushpop_front :: (Dequeue q, Eq a, Eq (q a)) => q a -> a -> Bool

-- | Validates that if you push, then pop, the back of the queue, you get
--   the same queue.
prop_pushpop_back :: (Dequeue q, Eq a, Eq (q a)) => q a -> a -> Bool

-- | Validates that <a>first</a> returns the last <tt>pushFront'</tt>d
--   element.
prop_push_front :: (Dequeue q, Eq a) => q a -> a -> Bool

-- | Validates that <a>last</a> returns the last <tt>pushBack'</tt>d
--   element.
prop_push_back :: (Dequeue q, Eq a) => q a -> a -> Bool

-- | Validates that the last <tt>n</tt> pushed elements are returned by
--   takeFront.
prop_takeFront :: (Dequeue q, Eq a) => q a -> [a] -> Bool

-- | Validates that the last <tt>n</tt> pushed elements are returned by
--   takeBack.
prop_takeBack :: (Dequeue q, Eq a) => q a -> [a] -> Bool

-- | Validates that the length of a queue is the same as the length of the
--   list generated from the queue.
prop_length_toList :: (Dequeue q, Foldable q) => q a -> Bool

-- | Validates that fromList . toList is the identity.
prop_fromList_toList :: (Dequeue q, Foldable q, Eq (q a)) => q a -> Bool

-- | An implementation of Banker's Dequeues, as described in Chris
--   Okasaki's Purely Functional Data Structures. The functions for the
--   <a>Dequeue</a> instance have the following complexities (where n is
--   the <a>length</a> of the queue):
--   
--   <ul>
--   <li><a>length</a>: O(1)</li>
--   <li><a>first</a>: O(1)</li>
--   <li><a>last</a>: O(1)</li>
--   <li><a>takeFront</a>: O(n)</li>
--   <li><a>takeBack</a>: O(n)</li>
--   <li><a>pushFront</a>: O(1) amortised</li>
--   <li><a>popFront</a>: O(1) amortised</li>
--   <li><a>pushBack</a>: O(1) amortised</li>
--   <li><a>popBack</a>: O(1) amortised</li>
--   <li><a>fromList</a>: O(n)</li>
--   </ul>
data BankersDequeue a

-- | Validates that if you push, then pop, the front of a
--   <tt>BankersQueue</tt>, you get the same queue.
prop_pushpop_front_bq :: BankersDequeue Int -> Int -> Bool

-- | Validates that if you push, then pop, the back of a
--   <a>BankersDequeue</a>, you get the same queue.
prop_pushpop_back_bq :: BankersDequeue Int -> Int -> Bool

-- | Validates that <a>first</a> returns the last <tt>pushFront'</tt>d
--   element.
prop_push_front_bq :: BankersDequeue Int -> Int -> Bool

-- | Validates that <a>last</a> returns the last <tt>pushBack'</tt>d
--   element.
prop_push_back_bq :: BankersDequeue Int -> Int -> Bool

-- | Validates that the last <tt>n</tt> pushed elements are returned by
--   takeFront.
prop_takeFront_bq :: BankersDequeue Int -> [Int] -> Bool

-- | Validates that the last <tt>n</tt> pushed elements are returned by
--   takeBack.
prop_takeBack_bq :: BankersDequeue Int -> [Int] -> Bool

-- | Validates that the length of a <a>BankersDequeue</a> is the same as
--   the length of the list generated from the queue.
prop_length_toList_bq :: BankersDequeue Int -> Bool

-- | Validates that fromList . toList is the identity for a
--   <a>BankersDequeue</a>.
prop_fromList_toList_bq :: BankersDequeue Int -> Bool

-- | Validates that a <a>BankersDequeue</a> remains balanced despite
--   repeated pushes to the front.
prop_push_front_bq_balance :: BankersDequeue Int -> Int -> Bool

-- | Validates that a <a>BankersDequeue</a> remains balanced despite
--   repeated pushes to the back.
prop_push_back_bq_balance :: BankersDequeue Int -> Int -> Bool

-- | Validates that a <a>BankersDequeue</a> remains balanced despite
--   repeated pops from the front.
prop_pop_front_bq_balance :: BankersDequeue Int -> Int -> Bool

-- | Validates that a <a>BankersDequeue</a> remains balanced despite
--   repeated pops from the back.
prop_pop_back_bq_balance :: BankersDequeue Int -> Int -> Bool

-- | Validates that a <a>BankersDequeue</a> has read and show instances
--   that are the inverse of each other.
prop_read_show_bq :: BankersDequeue Int -> Bool
instance GHC.Base.Functor Data.Dequeue.BankersDequeue
instance Data.Foldable.Foldable Data.Dequeue.BankersDequeue
instance Data.Dequeue.Dequeue Data.Dequeue.BankersDequeue
instance Test.QuickCheck.Arbitrary.Arbitrary a => Test.QuickCheck.Arbitrary.Arbitrary (Data.Dequeue.BankersDequeue a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Dequeue.BankersDequeue a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Dequeue.BankersDequeue a)
instance GHC.Read.Read a => GHC.Read.Read (Data.Dequeue.BankersDequeue a)