bimap 0.2.3 → 0.2.4

raw patch · 4 files changed

+124/−5 lines, 4 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Data/Bimap.hs +37/−1
• HISTORY +4/−0
• Test/Tests.hs +82/−3
• bimap.cabal +1/−1

@@ -51,6 +51,9 @@     deleteFindMinR,     deleteFindMax,     deleteFindMaxR,+    -- * Filter+    filter,+    partition,     -- * Conversion\/traversal     fromList,     fromAList,@@ -74,7 +77,8 @@  import Data.List (foldl', sort) import qualified Data.Map as M-import Prelude hiding (lookup, null)+import Prelude hiding (lookup, null, filter, pred)+import qualified Prelude as P   infixr 9 .:@@ -379,6 +383,38 @@ /Version: 0.2.1/-} toMapR :: Bimap a b -> M.Map b a toMapR (MkBimap _ right) = right++{-| /O(n)/.+Filter all association pairs that satisfy the predicate.++Note that the predicate will be applied /twice/ for each association+in the bimap.++/Version: 0.2.4/-}+filter :: (Ord a, Ord b)+              => (a -> b -> Bool) -> Bimap a b -> Bimap a b+filter pred (MkBimap left right) =+    MkBimap+        (M.filterWithKey pred left)+        (M.filterWithKey (flip pred) right)++{-| /O(n)/.+Partition the bimap according to a predicate.+The first bimap contains all associations that satisfy the predicate;+the second contains all associations that fail the predicate.++Note that the predicate will be applied /twice/ for each association+in the bimap.++/Version: 0.2.4/-}+partition :: (Ord a, Ord b)+          => (a -> b -> Bool) -> Bimap a b -> (Bimap a b, Bimap a b)+partition pred (MkBimap left right) =+    (,) (MkBimap leftA rightA) (MkBimap leftB rightB)+    where+    (leftA, leftB) = M.partitionWithKey pred left+    (rightA, rightB) = M.partitionWithKey (flip pred) right+  {-| /O(n*log n)/. Test if the internal bimap structure is valid. This should be true

@@ -1,3 +1,7 @@+Version 0.2.4 (25 Aug 2008)++  * added filter and partition+ Version 0.2.3 (1 Jul 2008)    * added fromAscPairList and fromAscPairListUnchecked

@@ -1,19 +1,38 @@ module Test.Tests where  import Data.List (sort)-import Prelude hiding (null, lookup)+import qualified Data.Set as S+import Prelude hiding (null, lookup, filter)+import qualified Prelude as P import Test.QuickCheck import Test.QuickCheck.Batch  import Data.Bimap  +(.:) = (.).(.)+ instance (Ord a, Arbitrary a, Ord b, Arbitrary b)     => Arbitrary (Bimap a b) where     arbitrary = fromList `fmap` arbitrary     coarbitrary = coarbitrary . toList +-- generator for filter/partition classification functions+data FilterFunc a b = FilterFunc String (a -> b -> Bool)+instance Show (FilterFunc a b) where+    show (FilterFunc desc _) = desc+instance (Integral a, Arbitrary a, Integral b, Arbitrary b)+    => Arbitrary (FilterFunc a b) where+    arbitrary = do+        pivot <- (arbitrary :: Gen Integer)+        return $ FilterFunc+            ("(\\x y -> x - y < " ++ show pivot ++ ")")+            (\x y -> fromIntegral x - fromIntegral y < pivot)+    coarbitrary _ gen = do+        x <- arbitrary+        coarbitrary (x :: Int) gen + -- empty bimap has zero size prop_size_empty = size empty == 0 @@ -37,8 +56,8 @@     bi = fromList xs     isMember x = x `pairMember` bi     notUnique (x, y) = -        ((>1) . length . filter (== x) . map fst $ xs) ||-        ((>1) . length . filter (== y) . map snd $ xs)+        ((>1) . length . P.filter (== x) . map fst $ xs) ||+        ((>1) . length . P.filter (== y) . map snd $ xs)  -- a bimap created from a list is no larger than the list prop_fromList_size xs = (size $ fromList xs) <= length xs@@ -153,6 +172,66 @@     ]     where     _ = (x, y) :: (Int, Integer)++-- an always-true filter makes no changes+prop_filter_true bi =+    bi == filter (curry $ const True) bi+    where+    _ = bi :: Bimap Int Integer++-- an always-false filter gives an empty result+prop_filter_false bi =+    null $ filter (curry $ const False) bi+    where+    _ = bi :: Bimap Int Integer++-- all elements of the projection satisfy the predicate, and all+-- elements of the rejection do not+prop_partition_agree bi (FilterFunc _ ff) = and+    [ all (      uncurry ff) (toList projection)+    , all (not . uncurry ff) (toList rejection)+    ]+    where+    _ = bi :: Bimap Int Integer+    (projection, rejection) = partition ff bi++-- the two halves of a partition are disjoint+prop_partition_disjoint bi (FilterFunc _ ff) =+    S.null $ S.intersection (asSet projection) (asSet rejection)+    where+    _ = bi :: Bimap Int Integer+    (projection, rejection) = partition ff bi+    asSet = S.fromList . toList++-- the two halves of a partition contain the elements of the original+-- bimap+prop_partition_union bi (FilterFunc _ ff) =+    (==) (asSet bi) $+        S.union (asSet projection) (asSet rejection)+    where+    _ = bi :: Bimap Int Integer+    (projection, rejection) = partition ff bi+    asSet = S.fromList . toList++-- the two halves of a partition agree with individual filters+prop_partition_filter bi (FilterFunc _ ff) = and+    [ projection == filter (       ff) bi+    , rejection  == filter (not .: ff) bi+    ]+    where+    _ = bi :: Bimap Int Integer+    (projection, rejection) = partition ff bi++-- partition and filter produce valid results+prop_partition_filter_valid bi (FilterFunc _ ff) = all valid+    [ projection+    , rejection+    , filter (       ff) bi+    , filter (not .: ff) bi+    ]+    where+    _ = bi :: Bimap Int Integer+    (projection, rejection) = partition ff bi  -- twist is its own inverse prop_twist_twist bi =

@@ -1,6 +1,6 @@ cabal-version:       >= 1.2.3.0 name:                bimap-version:             0.2.3+version:             0.2.4 synopsis:            Bidirectional mapping between two key types description:   A data structure representing a bidirectional mapping between two