bimap 0.2.1 → 0.2.2

raw patch · 6 files changed

+358/−36 lines, 6 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/Bimap.hs +136/−27
• HISTORY +7/−0
• LICENSE +1/−1
• Test/Tests.hs +204/−1
• bimap.cabal +3/−3
• tests.sh +7/−4

@@ -35,10 +35,25 @@     singleton,     -- * Update     insert,+    tryInsert,     delete,     deleteR,+    -- * Min\/Max+    findMin,+    findMinR,+    findMax,+    findMaxR,+    deleteMin,+    deleteMinR,+    deleteMax,+    deleteMaxR,+    deleteFindMin,+    deleteFindMinR,+    deleteFindMax,+    deleteFindMaxR,     -- * Conversion\/traversal     fromList,+    fromAList,     toList,     toAscList,     toAscListR,@@ -76,47 +91,39 @@     (==) bx by = toAscList bx == toAscList by  {-| /O(1)/. The empty bimap.- /Version: 0.2/-} empty :: Bimap a b empty = MkBimap M.empty M.empty  {-| /O(1)/. A bimap with a single element.- /Version: 0.2/-} singleton :: a -> b -> Bimap a b singleton x y = MkBimap (M.singleton x y) (M.singleton y x)  {-| /O(1)/. Is the bimap empty?- /Version: 0.2/-} null :: Bimap a b -> Bool null (MkBimap left _) = M.null left  {-| /O(1)/. The number of elements in the bimap.- /Version: 0.2/-} size :: Bimap a b -> Int size (MkBimap left _) = M.size left  {-| /O(log n)/. Is the specified value a member of the bimap?- /Version: 0.2/-} member :: (Ord a, Ord b) => a -> Bimap a b -> Bool member x (MkBimap left _) = M.member x left {-| /O(log n)/. A version of 'member' specialized to the right key.- /Version: 0.2/-} memberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool memberR y (MkBimap _ right) = M.member y right  {-| /O(log n)/. Is the specified value not a member of the bimap?- /Version: 0.2/-} notMember :: (Ord a, Ord b) => a -> Bimap a b -> Bool notMember = not .: member {-| /O(log n)/. A version of 'notMember' specialized to the right key.- /Version: 0.2/-} notMemberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool notMemberR = not .: memberR@@ -136,7 +143,6 @@ {-| /O(log n)/. Are the two values not in the bimap, or not associated with each other? (Complement of 'pairMember'.)- /Version: 0.2/-} pairNotMember :: (Ord a, Ord b)               => (a, b) -> Bimap a b -> Bool@@ -150,12 +156,22 @@  /Version: 0.2/-} insert :: (Ord a, Ord b)-        => a -> b -> Bimap a b -> Bimap a b+       => a -> b -> Bimap a b -> Bimap a b insert x y = delete x >>> deleteR y >>> unsafeInsert x y     where     (>>>) = flip (.)  {-| /O(log n)/.+Insert a pair of values into the bimap, but only if neither is+already in the bimap.+/Version: 0.2.2/-}+tryInsert :: (Ord a, Ord b)+          => a -> b -> Bimap a b -> Bimap a b+tryInsert x y bi+    | (x `notMember` bi && y `notMemberR` bi) = unsafeInsert x y bi+    | otherwise                               = bi++{-| /O(log n)/. Insert a pair of values into the bimap, without checking for overlapping bindings. @@ -190,7 +206,6 @@ delete = deleteE . Left  {-| /O(log n)/ A version of 'delete' specialized to the right key.- /Version: 0.2/-} deleteR :: (Ord a, Ord b) => b -> Bimap a b -> Bimap a b deleteR = deleteE . Right@@ -212,7 +227,6 @@ {-| /O(log n)/. A version of 'lookup' that is specialized to the right key, and returns the corresponding left key.- /Version: 0.2/-} lookupR :: (Ord a, Ord b, Monad m)         => b -> Bimap a b -> m a@@ -224,7 +238,6 @@ {-| /O(log n)/. Find the right key corresponding to a given left key. Calls @'error'@ when the key is not in the bimap.- /Version: 0.2/-} (!) :: (Ord a, Ord b) => Bimap a b -> a -> b (!) bi x = case lookup x bi of@@ -234,7 +247,6 @@ {-| /O(log n)/. A version of @(!)@ that is specialized to the right key, and returns the corresponding left key.- /Version: 0.2/-} (!>) :: (Ord a, Ord b) => Bimap a b -> b -> a (!>) bi y = case lookupR y bi of@@ -244,14 +256,28 @@ {-| /O(n*log n)/. Build a map from a list of pairs. If there are any overlapping pairs in the list, the later ones will override the earlier ones.- /Version: 0.2/-} fromList :: (Ord a, Ord b)          => [(a, b)] -> Bimap a b fromList xs = foldl' (flip . uncurry $ insert) empty xs -{-| /O(n)/. Convert to a list of associated pairs.+{-| /O(n*log n)/.+Build a map from a list of pairs. Unlike 'fromList', earlier pairs+will take precedence over later ones. +The name @fromAList@ is a reference to Lisp-style association+lists, where associations can be overridden by prepending new ones.++Note that when duplicates occur in both the keys and in the values,+@fromList xs /= fromAList (reverse xs)@. However, if either+contains no duplicates, then the equality holds.++/Version: 0.2.2/-}+fromAList :: (Ord a, Ord b)+          => [(a, b)] -> Bimap a b+fromAList xs = foldl' (flip . uncurry $ tryInsert) empty xs++{-| /O(n)/. Convert to a list of associated pairs. /Version: 0.2/-} toList :: Bimap a b -> [(a, b)] toList = toAscList@@ -281,46 +307,40 @@ {-| /O(n)/. Return all associated pairs in the bimap, with the left-hand values in ascending order.- /Version: 0.2/-} assocs :: Bimap a b -> [(a, b)] assocs = toList  {-| /O(n)/. Return all left-hand keys in the bimap in ascending order.- /Version: 0.2/-} keys :: Bimap a b -> [a] keys (MkBimap left _) = M.keys left  {-| /O(n)/. Return all right-hand keys in the bimap in ascending order.- /Version: 0.2/-} keysR :: Bimap a b -> [b] keysR (MkBimap _ right) = M.keys right  {-| /O(n)/. An alias for 'keysR'.- /Version: 0.2/-} elems :: Bimap a b -> [b] elems = keysR  {-| /O(1)/. Extract only the left-to-right component of a bimap.- /Version: 0.2.1/-} toMap :: Bimap a b -> M.Map a b toMap (MkBimap left _) = left  {-| /O(1)/. Extract only the right-to-left component of a bimap.- /Version: 0.2.1/-} toMapR :: Bimap a b -> M.Map b a toMapR (MkBimap _ right) = right  {-| /O(n*log n)/.-Test if the internal bimap structure is valid.-+Test if the internal bimap structure is valid. This should be true+for any bimap created using the public interface. /Version: 0.2/-} valid :: (Ord a, Ord b)       => Bimap a b -> Bool@@ -335,7 +355,6 @@  {-| /O(1)/. Reverse the positions of the two element types in the bimap.- /Version: 0.2/-} twist ::  Bimap a b -> Bimap b a twist (MkBimap left right) = MkBimap right left@@ -343,7 +362,6 @@ {-| /O(1)/. Reverse the positions of the two element types in a bimap transformation.- /Version: 0.2/-} twisted :: (Bimap a b -> Bimap a b) -> (Bimap b a -> Bimap b a) twisted f = twist . f . twist@@ -351,8 +369,99 @@ {-| /O(n)/. Fold the association pairs in the map, such that @'fold' f z == 'foldr' f z . 'assocs'@.- /Version: 0.2/-} fold :: (a -> b -> c -> c) -> c -> Bimap a b -> c fold f z = foldr (uncurry f) z . assocs++{-| /O(log n)/.+Delete and find the element with maximal left key.+Calls @'error'@ if the bimap is empty.+/Version: 0.2.2/-}+deleteFindMax :: (Ord b) => Bimap a b -> ((a, b), Bimap a b)+deleteFindMax (MkBimap left right) = ((a, b), MkBimap left' right') where+    ((a, b), left') = M.deleteFindMax left+    right' = b `M.delete` right++{-| /O(log n)/.+Delete and find the element with maximal right key.+Calls @'error'@ if the bimap is empty.+/Version: 0.2.2/-}+deleteFindMaxR :: (Ord a) => Bimap a b ->  ((b, a), Bimap a b)+deleteFindMaxR = second twist . deleteFindMax . twist where+    second f (x, y) = (x, f y)++{-| /O(log n)/.+Delete the element with maximal left key.+Calls @'error'@ if the bimap is empty.+/Version: 0.2.2/-}+deleteMax :: (Ord b) => Bimap a b -> Bimap a b+deleteMax = snd . deleteFindMax+ +{-| /O(log n)/.+Delete the element with maximal right key.+Calls @'error'@ if the bimap is empty.+/Version: 0.2.2/-}+deleteMaxR :: (Ord a) => Bimap a b -> Bimap a b+deleteMaxR = snd . deleteFindMaxR++{-| /O(log n)/.+Find the element with maximal left key.+Calls @'error'@ if the bimap is empty.+/Version: 0.2.2/-}+findMax :: Bimap a b -> (a, b)+findMax = M.findMax . toMap++{-| /O(log n)/.+Find the element with maximal right key. The +right-hand key is the first entry in the pair.+Calls @'error'@ if the bimap is empty.+/Version: 0.2.2/-}+findMaxR :: Bimap a b -> (b, a)+findMaxR = M.findMax . toMapR++{-| /O(log n)/.+Delete and find the element with minimal left key.+Calls @'error'@ if the bimap is empty.+/Version: 0.2.2/-}+deleteFindMin :: (Ord b) => Bimap a b -> ((a, b), Bimap a b)+deleteFindMin (MkBimap left right) = ((a, b), MkBimap left' right') where+    ((a, b), left') = M.deleteFindMin left+    right' = b `M.delete` right++{-| /O(log n)/.+Delete and find the element with minimal right key.+Calls @'error'@ if the bimap is empty.+/Version: 0.2.2/-}+deleteFindMinR :: (Ord a) => Bimap a b ->  ((b, a), Bimap a b)+deleteFindMinR = second twist . deleteFindMin . twist where+    second f (x, y) = (x, f y)++{-| /O(log n)/.+Delete the element with minimal left key.+Calls @'error'@ if the bimap is empty.+/Version: 0.2.2/-}+deleteMin :: (Ord b) => Bimap a b -> Bimap a b+deleteMin = snd . deleteFindMin+ +{-| /O(log n)/.+Delete the element with minimal right key.+Calls @'error'@ if the bimap is empty.+/Version: 0.2.2/-}+deleteMinR :: (Ord a) => Bimap a b -> Bimap a b+deleteMinR = snd . deleteFindMinR++{-| /O(log n)/.+Find the element with minimal left key.+Calls @'error'@ if the bimap is empty.+/Version: 0.2.2/-}+findMin :: Bimap a b -> (a, b)+findMin = M.findMin . toMap++{-| /O(log n)/.+Find the element with minimal right key. The +right-hand key is the first entry in the pair.+Calls @'error'@ if the bimap is empty.+/Version: 0.2.2/-}+findMinR :: Bimap a b -> (b, a)+findMinR = M.findMin . toMapR 

@@ -1,3 +1,10 @@+Version 0.2.2 (18 Jun 2008)++  * added min/max functions (thanks to Jochem Berndsen)+  * added tryInsert+  * added fromAList+  * more tests for existing functionality+ Version 0.2.1 (6 Feb 2008)    * removed MTL dependency

@@ -1,4 +1,4 @@-Copyright Stuart Cook 2008+Copyright Stuart Cook and contributors 2008  All rights reserved. 

@@ -1,6 +1,6 @@ module Test.Tests where -import Prelude hiding (null)+import Prelude hiding (null, lookup) import Test.QuickCheck  import Data.Bimap@@ -12,10 +12,14 @@     coarbitrary = coarbitrary . toList  +-- empty bimap has zero size prop_size_empty = size empty == 0 +-- empty bimap is null prop_null_empty = null empty +-- when converting from a list and back, each pair in the latter+-- list was originally in the former list -- (heh, this is probably made redundant by polymorphism) prop_fromList_toList xs =     let xs' = toList . fromList $ xs@@ -34,10 +38,28 @@         ((>1) . length . filter (== x) . map fst $ xs) ||         ((>1) . length . 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     where     _ = xs :: [(Int, Integer)] +-- if a pair is a member of the bimap, then both elements are present+-- and associated with each other+prop_pairMember bi k v =+    ((k, v) `pairMember` bi) == and+        [ k `member`  bi+        , v `memberR` bi+        , lookup  k bi == Just v+        , lookupR v bi == Just k+        ]+    where+    _ = bi :: Bimap Int Integer++-- an inserted pair ends up in the bimap+prop_insert_member bi k v = (k, v) `pairMember` (insert k v bi)+    where+    _ = bi :: Bimap Int Integer+ -- if we insert a pair with an existing value, the old value's twin -- is no longer in the bimap prop_clobberL bi b' =@@ -54,11 +76,26 @@     where     (a, b) = head . toList $ bi :: (Int, Integer) +-- if we politely insert two members, neither of which is present,+-- then the two are successfully associated+prop_tryInsert_member bi k v = (k, v) `neitherMember` bi ==>+    pairMember (k, v) (tryInsert k v bi)+    where+    _ = bi :: Bimap Int Integer+    neitherMember (k, v) bi = k `notMember` bi && v `notMemberR` bi++-- polite insertion will never remove existing associations+prop_tryInsert_not_clobber bi k v =+    all (flip pairMember $ tryInsert k v bi) (toList bi)+    where+    _ = bi :: Bimap Int Integer+ -- an arbitrary bimap is valid prop_valid bi = valid bi     where     _ = bi :: Bimap Int Integer +-- if x maps to y, then y maps to x prop_member_twin bi = flip all (toList bi) $ \(x, y) -> and     [ (bi !  x) `memberR` bi     , (bi !> y) `member`  bi@@ -66,6 +103,7 @@     where     _ = bi :: Bimap Int Integer +-- deleting an element removes it from the map prop_delete bi = flip all (toList bi) $ \(x, y) -> and     [ x `notMember`  delete  x bi     , y `notMemberR` deleteR y bi@@ -73,6 +111,7 @@     where     _ = bi :: Bimap Int Integer +-- deleting an element removes its twin from the map prop_delete_twin bi = flip all (toList bi) $ \(x, y) -> and     [ (bi !  x) `notMemberR` delete  x bi     , (bi !> y) `notMember`  deleteR y bi@@ -80,6 +119,8 @@     where     _ = bi :: Bimap Int Integer +-- a singleton bimap is valid, has one association, and the two+-- given values map to each other prop_singleton x y = let bi = singleton x y in and     [ valid bi     , (x, y) `pairMember` bi@@ -90,7 +131,169 @@     where     _ = (x, y) :: (Int, Integer) +-- twist is its own inverse prop_twist_twist bi =     bi == (twist . twist $ bi)     where     _ = bi :: Bimap Int Integer++-- the property (fromList == fromAList . reverse) only holds+-- if either the left or right values are all distinct+prop_fromList_fromAList xs = and+    [ fromList  ys == fromAList rys+    , fromList rys == fromAList  ys+    ]+    where+    ys = xs `zip` [1..] :: [(Int, Integer)]+    rys = reverse ys++swap (x, y) = (y, x)++prop_deleteMin_is_delete bi = not (null bi) ==>+    snd (deleteFindMin bi) `equals` deleteMin bi+    where+    _ = bi :: Bimap Int Integer+    x `equals` y = toList x == toList y++prop_deleteMin_is_find bi = not (null bi) ==>+    fst (deleteFindMin bi) == findMin bi+    where+    _ = bi :: Bimap Int Integer++prop_deleteMin_deletes bi = not (null bi) ==>+    fst (deleteFindMin bi) `pairNotMember` snd (deleteFindMin bi)+    where+    _ = bi :: Bimap Int Integer++prop_findMin_member bi = not (null bi) ==>+    findMin bi `pairMember` bi+    where+    _ = bi :: Bimap Int Integer+        +prop_singleton_is_findMin x y = findMin bi == (x, y)+    where+    bi :: Bimap Int Integer+    bi = singleton x y++prop_singleton_deleteMin_empty x y = null (deleteMin bi)+    where+    bi :: Bimap Int Integer+    bi = singleton x y++prop_findMin_is_minimal bi = all (\ (a, _) -> a >= x) lst+    where+    lst = toList bi+    _ = bi :: Bimap Int Integer+    x = fst . findMin $ bi++prop_deleteMinR_is_delete bi = not (null bi) ==>+    snd (deleteFindMinR bi) == deleteMinR bi +    where+    _ = bi :: Bimap Int Integer++prop_deleteMinR_is_find bi = not (null bi) ==>+    fst (deleteFindMinR bi) == findMinR bi +    where+    _ = bi :: Bimap Int Integer++prop_deleteMinR_deletes bi = not (null bi) ==>+    (swap . fst) (deleteFindMinR bi) `pairNotMember` snd (deleteFindMinR bi)+    where+    _ = bi :: Bimap Int Integer++prop_findMinR_member bi = not (null bi) ==>+    swap (findMinR bi) `pairMember` bi+    where+    _ = bi :: Bimap Int Integer+        +prop_singleton_is_findMinR x y = findMinR bi == (y, x)+    where+    bi :: Bimap Int Integer+    bi = singleton x y++prop_singleton_deleteMinR_empty x y = null (deleteMinR bi)+    where+    bi :: Bimap Int Integer+    bi = singleton x y++prop_findMinR_is_minimal bi = all (\ (_, b) -> b >= y) lst+    where+    lst = toList bi+    _ = bi :: Bimap Int Integer+    y = fst . findMinR $ bi++++prop_deleteMax_is_delete bi = not (null bi) ==>+    snd (deleteFindMax bi) `equals` deleteMax bi+    where+    _ = bi :: Bimap Int Integer+    x `equals` y = toList x == toList y++prop_deleteMax_is_find bi = not (null bi) ==>+    fst (deleteFindMax bi) == findMax bi+    where+    _ = bi :: Bimap Int Integer++prop_deleteMax_deletes bi = not (null bi) ==>+    fst (deleteFindMax bi) `pairNotMember` snd (deleteFindMax bi)+    where+    _ = bi :: Bimap Int Integer++prop_findMax_member bi = not (null bi) ==>+    findMax bi `pairMember` bi+    where+    _ = bi :: Bimap Int Integer+        +prop_singleton_is_findMax x y = findMax bi == (x, y)+    where+    bi :: Bimap Int Integer+    bi = singleton x y++prop_singleton_deleteMax_empty x y = null (deleteMax bi)+    where+    bi :: Bimap Int Integer+    bi = singleton x y++prop_findMax_is_maximal bi = all (\ (a, _) -> a <= x) lst+    where+    lst = toList bi+    _ = bi :: Bimap Int Integer+    x = fst . findMax $ bi++prop_deleteMaxR_is_delete bi = not (null bi) ==>+    snd (deleteFindMaxR bi) == deleteMaxR bi +    where+    _ = bi :: Bimap Int Integer++prop_deleteMaxR_is_find bi = not (null bi) ==>+    fst (deleteFindMaxR bi) == findMaxR bi+    where+    _ = bi :: Bimap Int Integer++prop_deleteMaxR_deletes bi = not (null bi) ==>+    (swap . fst) (deleteFindMaxR bi) `pairNotMember` snd (deleteFindMaxR bi)+    where+    _ = bi :: Bimap Int Integer++prop_findMaxR_member bi = not (null bi) ==>+    swap (findMaxR bi) `pairMember` bi+    where+    _ = bi :: Bimap Int Integer+        +prop_singleton_is_findMaxR x y = findMaxR bi == (y, x)+    where+    bi :: Bimap Int Integer+    bi = singleton x y++prop_singleton_deleteMaxR_empty x y = null (deleteMaxR bi)+    where+    bi :: Bimap Int Integer+    bi = singleton x y++prop_findMaxR_is_maximal bi = all (\ (_, b) -> b <= y) lst+    where+    lst = toList bi+    _ = bi :: Bimap Int Integer+    y = fst . findMaxR $ bi+

@@ -1,6 +1,6 @@ cabal-version:       >= 1.2.3.0 name:                bimap-version:             0.2.1+version:             0.2.2 synopsis:            Bidirectional mapping between two key types description:   A data structure representing a bidirectional mapping between two@@ -9,7 +9,7 @@ category:            Data license:             BSD3 license-file:        LICENSE-copyright:           Stuart Cook 2008+copyright:           Stuart Cook and contributors 2008 author:              Stuart Cook maintainer:          scook0@gmail.com homepage:            http://code.haskell.org/bimap@@ -31,7 +31,7 @@     build-depends:       base >= 3, containers   else     build-depends:       base < 3-  ghc-options:         -Wall -O2+  ghc-options:         -Wall   exposed-modules:       Data.Bimap 

@@ -1,5 +1,8 @@ #!/bin/bash-# ensure that an error in the test program doesn't accidentally-# produce success-set -o pipefail-(runhaskell Test/RunTests.hs | tee .test.log) && if grep Falsifiable .test.log >/dev/null; then exit 1; fi++rm .test.log 2>/dev/null+runhaskell Test/RunTests.hs > .test.log || exit 1+cat .test.log || exit 2+grep Falsifiable .test.log >/dev/null && exit 3+echo "~~ all tests passed ~~"+exit 0