dequeue 0.1.5 → 0.1.7

raw patch · 2 files changed

+18/−20 lines, 2 filesdep ~QuickCheckPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: QuickCheck

API changes (from Hackage documentation)

Files

• dequeue.cabal +2/−2
• src/Data/Dequeue.hs +16/−18

@@ -1,7 +1,7 @@ Build-Type: Simple Name: dequeue Category: Data Structures-Version: 0.1.5+Version: 0.1.7 Cabal-Version: >= 1.2 Synopsis: A typeclass and an implementation for double-ended queues. Description:@@ -17,7 +17,7 @@  Library     Exposed-Modules: Data.Dequeue, Data.Dequeue.Show-    Build-Depends: base < 5, safe, QuickCheck+    Build-Depends: base < 5, safe, QuickCheck >= 2     Hs-Source-Dirs: src     GHC-Options: -Wall 

@@ -62,13 +62,11 @@ import qualified Data.Dequeue.Show  -- | A typeclass for double-ended queues.-class Dequeue q where+class Foldable q => Dequeue q where     -- | Generates an empty queue.     empty :: q a     -- | Returns 'True' if this queue is empty.     null :: q a -> Bool-    -- | Returns the number of elements in this queue.-    length :: q a -> Int     -- | Returns the item on the front of the queue.     first :: q a -> Maybe a     -- | Returns the item on the end of the queue.@@ -82,11 +80,11 @@     -- | Pushes an item onto the front of the queue.     pushFront :: q a -> a -> q a     -- | Pops an item from the front of the queue.-    popFront :: q a -> (Maybe a, q a)+    popFront :: q a -> Maybe (a, q a)     -- | Pushes an item onto the back of the queue.     pushBack :: q a -> a -> q a     -- | Pops an item from the back of the queue.-    popBack :: q a -> (Maybe a, q a)+    popBack :: q a -> Maybe (a, q a)     -- | Converts a list into a queue.     fromList :: [a] -> q a @@ -125,15 +123,15 @@ --   you get the same queue. prop_pushpop_front :: (Dequeue q, Eq a, Eq (q a)) => q a -> a -> Bool prop_pushpop_front q a =-    let (a', q') = popFront (pushFront q a) in-    a' == Just a && q' == q+    let Just (a', q') = popFront (pushFront q a) in+    a' == a && q' == q  -- | 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 prop_pushpop_back q a =-    let (a', q') = popBack (pushBack q a) in-    a' == Just a && q' == q+    let Just (a', q') = popBack (pushBack q a) in+    a' == a && q' == q  -- | Validates that 'first' returns the last 'pushFront''d element. prop_push_front :: (Dequeue q, Eq a) => q a -> a -> Bool@@ -199,12 +197,12 @@     foldl f a (BankersDequeue _ front _ rear) = foldl f a (front ++ reverse rear)     foldr1 f (BankersDequeue _ front _ rear) = foldr1 f (front ++ reverse rear)     foldl1 f (BankersDequeue _ front _ rear) = foldl1 f (front ++ reverse rear)+    length (BankersDequeue sizeF _ sizeR _) = sizeF + sizeR  instance Dequeue BankersDequeue where     empty = BankersDequeue 0 [] 0 []     null (BankersDequeue 0 [] 0 []) = True     null _ = False-    length (BankersDequeue sizeF _ sizeR _) = sizeF + sizeR     first (BankersDequeue _ [] _ [x]) = Just x     first (BankersDequeue _ front _ _) =  headMay front     last (BankersDequeue _ [x] _ []) = Just x@@ -215,18 +213,18 @@         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)-    popFront (BankersDequeue _ [] _ [x]) = (Just x, empty)+    popFront (BankersDequeue _ [] _ []) = Nothing+    popFront (BankersDequeue _ [] _ [x]) = Just (x, empty)     popFront (BankersDequeue _ [] _ _) = error "Queue is too far unbalanced."     popFront (BankersDequeue sizeF (f : fs) sizeR rear) =-        (Just f, check $ BankersDequeue (sizeF - 1) fs sizeR rear)+        Just (f, check $ BankersDequeue (sizeF - 1) fs sizeR rear)     pushBack (BankersDequeue sizeF front sizeR rear) x =         check $ BankersDequeue sizeF front (sizeR + 1) (x : rear)-    popBack (BankersDequeue _ [] _ []) = (Nothing, empty)-    popBack (BankersDequeue _ [x] _ []) = (Just x, empty)+    popBack (BankersDequeue _ [] _ []) = Nothing+    popBack (BankersDequeue _ [x] _ []) = Just (x, empty)     popBack (BankersDequeue _ _ _ []) = error "Queue is too far unbalanced."     popBack (BankersDequeue sizeF front sizeR (r : rs)) =-        (Just r, check $ BankersDequeue sizeF front (sizeR - 1) rs)+        Just (r, check $ BankersDequeue sizeF front (sizeR - 1) rs)     fromList list = check $ BankersDequeue (List.length list) list 0 []  -- | The maximum number of times longer one half of a 'BankersDequeue' is@@ -336,7 +334,7 @@ --   pops from the front. prop_pop_front_bq_balance :: BankersDequeue Int -> Int -> Bool prop_pop_front_bq_balance q count =-    let pop _ queue = let (_, queue') = popFront queue in queue'+    let pop _ queue = (fromJustDef queue . liftM snd . popFront) queue         q' = foldr pop q [0 .. count] in     balanced q' @@ -344,7 +342,7 @@ --   pops from the back. prop_pop_back_bq_balance :: BankersDequeue Int -> Int -> Bool prop_pop_back_bq_balance q count =-    let pop _ queue = let (_, queue') = popBack queue in queue'+    let pop _ queue = (fromJustDef queue . liftM snd . popBack) queue         q' = foldr pop q [0 .. count] in     balanced q'