dequeue 0.1.1 → 0.1.2

raw patch · 3 files changed

+42/−5 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• dequeue.cabal +1/−1
• src/Data/Dequeue.hs +38/−4
• src/Tests.hs +3/−0

@@ -1,7 +1,7 @@ Build-Type: Custom Name: dequeue Category: Data Structures-Version: 0.1.1+Version: 0.1.2 Cabal-Version: >= 1.2 Synopsis: A typeclass and an implementation for double-ended queues. Description:

@@ -19,7 +19,10 @@     prop_pushpop_back,     prop_push_front,     prop_push_back,+    prop_takeFront,+    prop_takeBack,     prop_length_toList,+    prop_fromList_toList,     -- * Banker's Dequeues     BankersDequeue,     -- * QuickCheck properties for 'BankersDequeue'@@ -27,7 +30,10 @@     prop_pushpop_back_bq,     prop_push_front_bq,     prop_push_back_bq,+    prop_takeFront_bq,+    prop_takeBack_bq,     prop_length_toList_bq,+    prop_fromList_toList_bq,     prop_push_front_bq_balance,     prop_push_back_bq_balance,     prop_pop_front_bq_balance,@@ -55,9 +61,11 @@     first :: q a -> Maybe a     -- | Returns the item on the end of the queue.     last :: q a -> Maybe a-    -- | Returns the first n items from the front of the queue.+    -- | Returns the first n items from the front of the queue, in the order+    --   they would be popped.     takeFront :: Int -> q a -> [a]-    -- | Returns the last n items from the end of the queue.+    -- | Returns the last n items from the end of the queue, in the order they+    --  would be popped.     takeBack :: Int -> q a -> [a]     -- | Pushes an item onto the front of the queue.     pushFront :: q a -> a -> q a@@ -94,11 +102,25 @@ prop_push_back :: (Dequeue q, Eq a) => q a -> a -> Bool prop_push_back q a = last (pushBack q a) == Just a +-- | Validates that the last 'n' pushed elements are returned by takeFront.+prop_takeFront :: (Dequeue q, Eq a) => q a -> [a] -> Bool+prop_takeFront q as =+    takeFront (List.length as) (foldr (flip pushFront) q as) == as++-- | Validates that the last 'n' pushed elements are returned by takeBack.+prop_takeBack :: (Dequeue q, Eq a) => q a -> [a] -> Bool+prop_takeBack q as =+    takeBack (List.length as) (foldr (flip pushBack) q as) == as+ -- | 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 prop_length_toList q = List.length (toList q) == length q +-- | Validates that fromList . toList is the identity.+prop_fromList_toList :: (Dequeue q, Foldable q, Eq (q a)) => q a -> Bool+prop_fromList_toList q = (fromList . toList) q == q+ -- | An implementation of Banker's Dequeues, as described in Chris Okasaki's --   Purely Functional Data Structures. The functions for the 'Dequeue' --   instance have the following complexities (where n is the 'length' of the@@ -149,7 +171,7 @@     takeFront i (BankersDequeue sizeF front _ rear) =         take i front ++ take (i - sizeF) (reverse rear)     takeBack i (BankersDequeue _ front sizeR rear) =-        reverse $ take i rear ++ take (i - sizeR) (reverse front)+        take i rear ++ take (i - sizeR) (reverse front)     pushFront (BankersDequeue sizeF front sizeR rear) x =         check $ BankersDequeue (sizeF + 1) (x : front) sizeR rear     popFront (BankersDequeue _ [] _ []) = (Nothing, empty)@@ -177,7 +199,7 @@ check q@(BankersDequeue sizeF front sizeR rear)     | sizeF > c * sizeR + 1 =         let front' = take size1 front-            rear' = rear ++ drop size1 front+            rear' = rear ++ reverse (drop size1 front)         in         BankersDequeue size1 front' size2 rear'     | sizeR > c * sizeF + 1 =@@ -222,10 +244,22 @@ prop_push_back_bq :: BankersDequeue Int -> Int -> Bool prop_push_back_bq = prop_push_back +-- | Validates that the last 'n' pushed elements are returned by takeFront.+prop_takeFront_bq :: BankersDequeue Int -> [Int] -> Bool+prop_takeFront_bq = prop_takeFront++-- | Validates that the last 'n' pushed elements are returned by takeBack.+prop_takeBack_bq :: BankersDequeue Int -> [Int] -> Bool+prop_takeBack_bq = prop_takeBack+ -- | Validates that the length of a 'BankersDequeue' is the same as the length --   of the list generated from the queue. prop_length_toList_bq :: BankersDequeue Int -> Bool prop_length_toList_bq = prop_length_toList++-- | Validates that fromList . toList is the identity for a 'BankersDequeue'.+prop_fromList_toList_bq :: BankersDequeue Int -> Bool+prop_fromList_toList_bq = prop_fromList_toList  balanced :: BankersDequeue a -> Bool balanced (BankersDequeue 0 _ 0 _) = True

@@ -10,7 +10,10 @@     ("pushpop_back_bq", quickCheck prop_pushpop_back_bq),     ("push_front_bq", quickCheck prop_push_front_bq),     ("push_back_bq", quickCheck prop_push_back_bq),+    ("takeFront_bq", quickCheck prop_takeFront_bq),+    ("takeBack_bq", quickCheck prop_takeBack_bq),     ("length_toList_bq", quickCheck prop_length_toList_bq),+    ("fromList_toList_bq", quickCheck prop_fromList_toList_bq),     ("push_back_bq_balance", quickCheck prop_push_back_bq_balance),     ("push_front_bq_balance", quickCheck prop_push_front_bq_balance),     ("pop_front_bq_balance", quickCheck prop_pop_front_bq_balance),