depq 0.3.0.0 → 0.4.0.0

raw patch · 5 files changed

+417/−27 lines, 5 filesdep +QuickCheckdep +depqdep +hspecdep ~containersPVP ok

version bump matches the API change (PVP)

Dependencies added: QuickCheck, depq, hspec

Dependency ranges changed: containers

API changes (from Hackage documentation)

Files

• ChangeLog.md +3/−0
• README.md +2/−2
• depq.cabal +18/−13
• src/Data/DEPQ.hs +37/−12
• test/Spec.hs +357/−0

@@ -1,5 +1,8 @@ # Changelog for depq +## 0.4+* Add test suite ( @HirotoShioi )+ ## 0.3 * Add 'size' * Add dependency lower bounds

@@ -6,9 +6,9 @@  ## Usage -The 'Data.DEPQ' module exports the user interface, which is similar to that of most Haskell data container libraries.+The `Data.DEPQ` module exports the user interface, which is similar to that of most Haskell data container libraries. -The most common use case of this library is to populate a DEPQ (either from a 'Foldable' collection or by 'insert'ing incrementally) and query either or both of its extremes (with 'findMin', 'findMax', 'popMin', 'popMax', 'topK', 'bottomK').+Populate a DEPQ (either from a `Foldable` collection such as a list or array or by `insert`ing incrementally) and query either of its extremes (with `findMin`, `findMax`, `popMin`, `popMax`, `topK`, `bottomK`).  Have fun! 

@@ -1,5 +1,5 @@ name:           depq-version:        0.3.0.0+version:        0.4.0.0 synopsis:       Double-ended priority queues description:    Double-ended priority queues, for efficient retrieval of minimum and maximum elements in ordered collections of items. homepage:       https://github.com/ocramz/depq@@ -30,19 +30,24 @@     , containers >= 0.6.0.1     , deepseq >= 1.4.4     , psqueues >= 0.2.7.2+    , QuickCheck   default-language: Haskell2010+  ghc-options: -Wall   --- test-suite depq-test---   type: exitcode-stdio-1.0---   main-is: Spec.hs---   other-modules:---       Paths_depq---   hs-source-dirs:---       test---   ghc-options: -threaded -rtsopts -with-rtsopts=-N---   build-depends:---       base >=4.7 && <5---     , depq---   default-language: Haskell2010+test-suite depq-test+  type: exitcode-stdio-1.0+  main-is: Spec.hs+  other-modules:+      Paths_depq+  hs-source-dirs:+      test+  ghc-options: -threaded -rtsopts -with-rtsopts=-N -Wall+  build-depends:+      base >=4.7 && <5+    , depq+    , QuickCheck+    , hspec+    , containers+  default-language: Haskell2010

@@ -1,19 +1,35 @@-{-| Double-ended priority queue (DEPQ)--Allows for efficiently finding and removing both the minimum and maximum priority elements, due to the min-heap invariant property of the underlying representation.--See https://en.wikipedia.org/wiki/Double-ended_priority_queue for definitions; the current implementation is based on the "dual structure" method outlined in the wikipedia page.--Based on `P.IntPSQ` : https://hackage.haskell.org/package/psqueues-0.2.7.2/docs/Data-IntPSQ.html--}+{-# LANGUAGE ScopedTypeVariables #-}+------------------------------------------------------------------------+-- |+-- Module      :  Data.DEPQ+-- Copyright   :  (c) Marco Zocca 2020+-- License     :  BSD3-style (see LICENSE)+--+-- Maintainer  :  @ocramz+-- Stability   :  experimental+-- Portability :  portable+--+-- Double-ended priority queue (DEPQ)+--+-- Allows for efficiently finding and removing both the minimum and maximum priority elements, due to the min-heap invariant property of the underlying representation.+--+-- See https://en.wikipedia.org/wiki/Double-ended_priority_queue for definitions; the current implementation is based on the "dual structure" method outlined in the wikipedia page.+--+-- Based on `P.IntPSQ` : https://hackage.haskell.org/package/psqueues-0.2.7.2/docs/Data-IntPSQ.html+--+-- = Usage+--+-- Populate a DEPQ (either from a `Foldable` collection such as a list or array or by `insert`ing incrementally) and query either of its extremes (with `findMin`, `findMax`, `popMin`, `popMax`, `topK`, `bottomK`).+------------------------------------------------------------------------ module Data.DEPQ (    DEPQ,     -- * Creation    empty, fromList,    -- * Predicates    null,+   valid,    -- * Properties-   size, +   size,    -- * Modification    insert, deleteMin, deleteMax, popMin, popMax,    -- * Lookup@@ -30,11 +46,11 @@ -- deepseq import Control.DeepSeq     (NFData (rnf)) -- psqueues-import qualified Data.IntPSQ as P (IntPSQ, empty, null, size, insert, delete, member, toList, fromList, findMin, delete, deleteMin)+import qualified Data.IntPSQ as P (IntPSQ, empty, null, size, insert, delete, toList, findMin, delete, deleteMin, valid)  import Prelude hiding (null) -+import Test.QuickCheck (Arbitrary(..), Gen)  -- | A double-ended priority queue data DEPQ p a = DEPQ {@@ -45,6 +61,13 @@ instance (NFData p, NFData a) => NFData (DEPQ p a) where   rnf (DEPQ mi ma) = rnf mi `seq` rnf ma +instance (Ord p, Arbitrary p, Arbitrary a) => Arbitrary (DEPQ p a) where+  arbitrary = fromList <$> (arbitrary :: Gen [(Int, p, a)])+  -- Convert given DEPQ into list, shrink it, then convert it back+  shrink depq = map fromList $ shrink $ toList depq+   where+     toList :: DEPQ p a -> [(Int, p, a)]+     toList (DEPQ p _) = P.toList p  -- | Insert an element insert :: (Ord p) =>@@ -58,7 +81,6 @@     ma' = P.insert k (Down p) v ma {-# INLINE insert #-} - -- | The empty DEPQ empty :: DEPQ p a empty = DEPQ P.empty P.empty@@ -79,6 +101,9 @@ null :: DEPQ p v -> Bool null (DEPQ mi ma) = P.null mi && P.null ma +-- | Is the DEPQ valid ?+valid :: (Ord p) => DEPQ p v -> Bool+valid (DEPQ mi ma) = P.valid mi && P.valid ma  -- | Delete the minimum-priority element in the DEPQ deleteMin :: Ord p => DEPQ p a -> DEPQ p a

@@ -0,0 +1,357 @@+{-# LANGUAGE OverloadedStrings #-}++module Main where++import qualified Data.DEPQ as D+import Data.DEPQ (DEPQ)+import Test.QuickCheck (Arbitrary(..), Property, elements, property, (===))+import Test.Hspec (Spec, describe, hspec, it)+import Test.Hspec.QuickCheck (prop, modifyMaxSuccess)+import Data.Map.Strict (Map)+import qualified Data.Map.Strict as M+import Data.Sequence (Seq)+import qualified Data.Sequence as Seq+import qualified Data.List as L+import Data.Maybe (fromJust)+import qualified Data.Foldable as F (Foldable(..))++main :: IO ()+main = hspec $ modifyMaxSuccess (const 1000) $ do+    validitySpec+    postConditionSpec+    metamorphicSpec+    modelBasedSpec++--------------------------------------------------------------------------------+-- Setting everything up+--------------------------------------------------------------------------------++-- We want our QuickCheck generators to generate edge cases which are:++-- 1. When we try to insert a new value into DEPQ+-- 2. When modification function tries to overwrite existing values+-- 3. When DEPQ contains multiple key-pair values in which the key is different +-- (e.g insert 4 A "Val" $ insert 5 A "Val2" empty)++-- To enable this, we use Priority type in which the range of values+-- are somewhat small and readable.+data Priority+  = A+  | B+  | C+  | D+  | E+  | F+  | G+  | H+  deriving (Eq, Enum, Ord, Show)++instance Arbitrary Priority where+    arbitrary = elements [A, B, C, D, E, F, G, H]++type Val = Int++type TestDEPQ = DEPQ Priority Val++--------------------------------------------------------------------------------+-- Validity testing+-- These sets of tests prove that given function will always return valid DEPQ+--------------------------------------------------------------------------------++validitySpec :: Spec+validitySpec = describe "Validity test" $ do+    it "null" empty_is_null+    prop "Generated DEPQ always valid" generator_valid+    prop "insert" insert_valid+    prop "fromList" fromList_valid+    prop "deleteMin" deleteMin_valid+    prop "deleteMax" deleteMax_valid+    prop "popMin" popMin_valid+    prop "popMax" popMax_valid++-- Test that DEPQ generated from QuickCheck are always valid+generator_valid :: TestDEPQ -> Property+generator_valid = property . D.valid++insert_valid :: Int -> Priority -> Val -> TestDEPQ -> Property+insert_valid key priority value  depq = +  property $ D.valid $ D.insert key priority value depq ++fromList_valid :: [(Int, Priority, Val)] -> Property+fromList_valid = property . D.valid . D.fromList++deleteMin_valid :: TestDEPQ -> Property+deleteMin_valid = property . D.valid . D.deleteMin++deleteMax_valid :: TestDEPQ -> Property+deleteMax_valid = property . D.valid . D.deleteMax++popMin_valid :: TestDEPQ -> Property+popMin_valid depq = +    property $ maybe True (\(_val, depq') -> D.valid depq') (D.popMin depq)++popMax_valid :: TestDEPQ -> Property+popMax_valid depq =+    property $ maybe True (\(_val, depq') -> D.valid depq') (D.popMin depq)++empty_is_null :: Bool+empty_is_null = D.null D.empty++--------------------------------------------------------------------------------+-- Post condition+-- Here, we test that given function returns expected value+--------------------------------------------------------------------------------++postConditionSpec :: Spec+postConditionSpec = describe "Post condition" $ do+    prop "findMin" findMin_post_condition+    prop "findMax" findMax_post_condition+    prop "size" size_post_condition+    prop "topK" topK_post_condition+    prop "bottomK" bottomK_post_condition++findMin_post_condition :: Int -> Priority -> Val -> Property+findMin_post_condition priority key val =+    let depq = D.insert priority key val D.empty+    in D.findMin depq === Just (priority, key, val)++findMax_post_condition :: Int -> Priority -> Val -> Property+findMax_post_condition priority key val =+    let depq = D.insert priority key val D.empty+    in D.findMax depq === Just (priority, key, val)++size_post_condition :: Int -> Priority -> Val -> TestDEPQ -> Property+size_post_condition key priority val depq =+    property $ D.size (D.insert key priority val depq) >= D.size depq++topK_post_condition :: Int -> TestDEPQ -> Property+topK_post_condition num depq =+    let s = D.topK num depq+    in if num <= (D.size depq) && num > 0+        then Seq.length s === num+        else Seq.length s === 0++bottomK_post_condition :: Int -> TestDEPQ -> Property+bottomK_post_condition num depq =+    let s = D.bottomK num depq+    in if num <= (D.size depq) && num > 0+        then Seq.length s === num+        else Seq.length s === 0++popMin_post_condition :: TestDEPQ -> Property+popMin_post_condition depq = +    let mPoped = D.popMin depq+    in if D.size depq == 0+        then mPoped === Nothing+        else property $ maybe+          False+          (\(_val, depq') -> D.size depq' < D.size depq)+          mPoped++popMax_post_condition :: TestDEPQ -> Property+popMax_post_condition depq = +    let mPoped = D.popMax depq+    in if D.size depq == 0+        then mPoped === Nothing+        else property $ maybe+          False+          (\(_val, depq') -> D.size depq' < D.size depq)+          mPoped++--------------------------------------------------------------------------------+-- Metamorphic+-- Instead of testing single function, we're now going to test multiple set of+-- functions+--------------------------------------------------------------------------------++metamorphicSpec :: Spec+metamorphicSpec = describe "Metamorphic" $ do+    prop "insert twice, findMax" insert_insert_findMax+    prop "insert twice, findMin" insert_insert_findMin++-- Insert 2 key value pairs, test that findMax return expected value+insert_insert_findMax :: (Int, Priority, Val) -> (Int, Priority, Val) -> Property+insert_insert_findMax t1@(k1, p1, v1) t2@(k2, p2, v2)+      | k1 == k2 = D.findMax depq === Just t2+      | p1 < p2 = D.findMax depq === Just t2+      | p1 > p2 = D.findMax depq === Just t1+      | k1 > k2 = D.findMax depq === Just t2+      | otherwise = D.findMax depq === Just t1+  where+    depq = D.insert k2 p2 v2 $ D.insert k1 p1 v1 D.empty++-- Insert 2 key value pairs, test that findMin return expected value+insert_insert_findMin :: (Int, Priority, Val) -> (Int, Priority, Val) -> Property+insert_insert_findMin t1@(k1, p1, v1) t2@(k2, p2, v2)+      | k1 == k2 = D.findMin depq === Just t2+      | p1 < p2 = D.findMin depq === Just t1+      | p1 > p2 = D.findMin depq === Just t2+      | k1 > k2 = D.findMin depq === Just t2+      | otherwise = D.findMin depq === Just t1+  where+    depq = D.insert k2 p2 v2 $ D.insert k1 p1 v1 D.empty++--------------------------------------------------------------------------------+-- Model based testing+-- Here, we test against a data structure that would act as an model+-- (i.e. Something that would behave similar to DEPQ and is well tested)+--------------------------------------------------------------------------------++{-|+     --------  fromDEPQ ---------+    |  DEPQ | ------ > |  Model |+    --------           ---------+        |                  |+       ｜　f(DEPQ)　  　　　 | g(Model)+       |　　　　　　　　　　　|+     -------------------------+    |   f(DEPQ) ==  g(Model) |+     ------------------------+-}++-- | Model of 'DEPQ'+type Model = Map Int (Priority, Val)++-- | /O(n)/ Convert a queue to a Sequence of (key, priority, value) tuples. +toList :: (Ord p, Ord a) => DEPQ p a -> [(Int, p, a)]+toList depq = L.sort $ F.toList $ D.topK (D.size depq) depq++fromDEPQ :: TestDEPQ -> Model+fromDEPQ depq = L.foldl' f mempty (toList depq)+  where+    f :: Model -> (Int, Priority, Val) -> Model+    f accum (key, priority, val) = M.insert key (priority, val) accum++modelToList :: Model -> [(Int, Priority, Val)]+modelToList model = L.sort $ map convert $ M.toList model++-- Helful functions++-- This is helpful when converting+convert :: (Int, (Priority, Val)) -> (Int, Priority, Val)+convert (key, (priority, val)) = (key, priority, val)++-- Get minimal value of an given 'Priority'+getVal :: Priority -> Model -> Maybe (Int, (Priority, Val))+getVal priority model = M.lookupMin $ M.filter (\(p, _) -> p == priority) model++getPriority :: (a, Priority, b) -> Priority+getPriority (_, p, _) = p++-- Set of functions which should behave the same way as the one that we're testing+-- against++size :: Model -> Int+size model = length $ map convert $ M.toList model++insert :: Int -> Priority -> Val -> Model -> Model+insert key priority val model = M.insert key (priority, val) model++lookupMax :: Model -> Maybe (Int, Priority, Val)+lookupMax model = +    if M.null model+        then Nothing+        else +          let (_, maxPriority, _) = L.maximumBy+                (\t1 t2 -> getPriority t1 `compare` getPriority t2) $ modelToList model+          in convert <$> getVal maxPriority model++lookupMin :: Model -> Maybe (Int, Priority, Val)+lookupMin model =+    if M.null model+        then Nothing+        else+          let (_, minPriority, _) = L.minimumBy+                (\t1 t2 -> getPriority t1 `compare` getPriority t2) (modelToList model)+          in convert <$> getVal minPriority model++takeTop :: Int -> Model -> Seq (Int, Priority, Val)+takeTop num model =+    let sortedList = L.sortBy +          (\t1 t2 -> getPriority t2 `compare` getPriority t1) $ modelToList model+    in Seq.fromList $ take num sortedList++takeBottom :: Int -> Model -> Seq (Int, Priority, Val)+takeBottom num model =+    let sortedList =+          L.sortBy (\t1 t2 -> getPriority t1 `compare` getPriority t2) $ modelToList model+    in Seq.fromList $ take num sortedList++deleteMax :: Model -> Model+deleteMax model =+    if M.null model+        then model+        -- It's safe to use partial functions since we know that the model has+        -- at least 1 element+        else+            let (_, maxPriority, _) = L.maximumBy+                  (\t1 t2 -> getPriority t1 `compare` getPriority t2)+                  (modelToList model)+                (k, _) = fromJust $ getVal maxPriority model+            in M.delete k model++deleteMin :: Model -> Model+deleteMin model =+    if M.null model+        then model+        else+            let (_, minPriority, _) = L.minimumBy+                  (\t1 t2 -> getPriority t1 `compare` getPriority t2) $ modelToList model+                (k, _) = fromJust $ getVal minPriority model+            in M.delete k model++-- Tests++modelBasedSpec :: Spec+modelBasedSpec = describe "Model based testing" $ do+    it "empty" nil_model+    prop "size" size_model+    prop "findMax" findMax_model+    prop "findMin" findMin_model+    prop "bottomK" bottomK_model+    prop "topK" topK_model+    prop "deleteMax" deleteMax_model+    prop "deleteMin" deleteMin_model++-- Tests++nil_model :: Property+nil_model = (fromDEPQ D.empty) === (mempty :: Model)++size_model :: TestDEPQ -> Property+size_model depq = D.size depq === size (fromDEPQ depq)++findMax_model :: TestDEPQ -> Property+findMax_model depq = D.findMax depq === lookupMax (fromDEPQ depq)++findMin_model :: TestDEPQ -> Property+findMin_model depq = D.findMin depq === lookupMin (fromDEPQ depq)++bottomK_model :: Int -> TestDEPQ -> Property+bottomK_model num depq = +    let s = D.bottomK num depq+    in if num <= D.size depq+        then s === takeBottom num (fromDEPQ depq)+        else s === mempty++topK_model :: Int -> TestDEPQ -> Property+topK_model num depq =+    let s = D.topK num depq+    in if num <= D.size depq+        then s === takeTop num (fromDEPQ depq)+        else s === mempty++-- Here, we check that the Model and DEPQ contains exact same content after+-- applying an function+hasContent :: TestDEPQ -> Model -> Property+hasContent depq model = toList depq === (modelToList model)++insert_model :: Int -> Priority -> Val -> TestDEPQ -> Property+insert_model key priority val depq = +    D.insert key priority val depq `hasContent` insert key priority val (fromDEPQ depq)++deleteMax_model :: TestDEPQ -> Property+deleteMax_model depq = D.deleteMax depq `hasContent` (deleteMax $ fromDEPQ depq)++deleteMin_model :: TestDEPQ -> Property+deleteMin_model depq = D.deleteMin depq `hasContent` (deleteMin $ fromDEPQ depq)