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


-- | 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 Dequeue q
empty :: (Dequeue q) => q a
null :: (Dequeue q) => q a -> Bool
length :: (Dequeue q) => q a -> Int
first :: (Dequeue q) => q a -> Maybe a
last :: (Dequeue q) => q a -> Maybe a
takeFront :: (Dequeue q) => Int -> q a -> [a]
takeBack :: (Dequeue q) => Int -> q a -> [a]
pushFront :: (Dequeue q) => q a -> a -> q a
popFront :: (Dequeue q) => q a -> (Maybe a, q a)
pushBack :: (Dequeue q) => q a -> a -> q a
popBack :: (Dequeue q) => q a -> (Maybe a, q a)
fromList :: (Dequeue q) => [a] -> 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
instance (Show a) => Show (BankersDequeue a)
instance (Eq a) => Eq (BankersDequeue a)
instance (Arbitrary a) => Arbitrary (BankersDequeue a)
instance Dequeue BankersDequeue
instance Foldable BankersDequeue
instance Functor BankersDequeue