multiset 0.1 → 0.2

raw patch · 4 files changed

+59/−26 lines, 4 filesdep ~base

Dependency ranges changed: base

Files

• Data/IntMultiSet.hs +33/−14
• Data/MultiSet.hs +14/−4
• LICENSE +1/−1
• multiset.cabal +11/−7

@@ -54,6 +54,7 @@              -- * Combine             , union, unions+            , maxUnion             , difference             , intersection @@ -143,10 +144,10 @@ import qualified List -} +import Data.Typeable #if __GLASGOW_HASKELL__ import Text.Read-import Data.Generics.Basics-import Data.Generics.Instances ()+import Data.Data (Data(..), mkNorepType) #endif  {--------------------------------------------------------------------@@ -292,14 +293,31 @@ findMin :: IntMultiSet -> Key -- TODO: IntMap has a different findMin than Map --findMin = fst . Map.findMin . unMS-findMin = Map.findMin . unMS+--findMin = Map.findMin . unMS  -- | /O(log n)/. The maximal element of a multiset. findMax :: IntMultiSet -> Key -- TODO: IntMap has a different findMin than Map --findMax = fst . Map.findMax . unMS-findMax = Map.findMax . unMS+--findMax = Map.findMax . unMS +-- Note: the documentation for IntMap.findMin/Max is incorrect+-- they return the VALUE at the minimal/maximal key++-- Here is a workarounds of IntMap's deficiencies/inconsistencies.++-- | /O(log n)/. The minimal key of an IntMap.+minKey :: IntMap a -> Int+minKey = maybe (error "IntMultiSet.findMin: empty multiset") (fst . fst) . Map.minViewWithKey++-- | /O(log n)/. The maximal key of an IntMap.+maxKey :: IntMap a -> Int+maxKey = maybe (error "IntMultiSet.findMax: empty multiset") (fst . fst) . Map.maxViewWithKey++findMin = minKey . unMS+findMax = maxKey . unMS++ -- | /O(log n)/. Delete the minimal element. deleteMin :: IntMultiSet -> IntMultiSet -- TODO: IntMap has a different updateMin@@ -369,27 +387,28 @@ unions ts   = foldlStrict union empty ts --- | /O(n+m)/. The union of two multisets, preferring the first multiset when--- equal elements are encountered.+-- | /O(n+m)/. The union of two multisets. The union adds the occurences together.+-- -- The implementation uses the efficient /hedge-union/ algorithm. -- Hedge-union is more efficient on (bigset `union` smallset). union :: IntMultiSet -> IntMultiSet -> IntMultiSet union (MS m1) (MS m2) = MS $ Map.unionWith (+) m1 m2 +-- | /O(n+m)/. The union of two multisets.+-- The number of occurences of each element in the union is+-- the maximum of the number of occurences in the arguments (instead of the sum).+--+-- The implementation uses the efficient /hedge-union/ algorithm.+-- Hedge-union is more efficient on (bigset `union` smallset).+maxUnion :: IntMultiSet -> IntMultiSet -> IntMultiSet+maxUnion (MS m1) (MS m2) = MS $ Map.unionWith max m1 m2+ -- | /O(n+m)/. Difference of two multisets.  -- The implementation uses an efficient /hedge/ algorithm comparable with /hedge-union/. difference :: IntMultiSet -> IntMultiSet -> IntMultiSet difference (MS m1) (MS m2) = MS $ Map.differenceWith (flip deleteN) m1 m2  -- | /O(n+m)/. The intersection of two multisets.--- Elements of the result come from the first multiset, so for example------ > import qualified Data.MultiSet as MS--- > data AB = A | B deriving Show--- > instance Ord AB where compare _ _ = EQ--- > instance Eq AB where _ == _ = True--- > main = print (MS.singleton A `MS.intersection` MS.singleton B,--- >               MS.singleton B `MS.intersection` MS.singleton A) -- -- prints @(fromList [A],fromList [B])@. intersection :: IntMultiSet -> IntMultiSet -> IntMultiSet

@@ -59,6 +59,7 @@              -- * Combine             , union, unions+            , maxUnion             , difference             , intersection @@ -148,10 +149,10 @@ import qualified List -} +import Data.Typeable #if __GLASGOW_HASKELL__ import Text.Read-import Data.Generics.Basics-import Data.Generics.Instances ()+import Data.Data (Data(..), mkNorepType) #endif  {--------------------------------------------------------------------@@ -360,12 +361,21 @@ unions ts   = foldlStrict union empty ts --- | /O(n+m)/. The union of two multisets, preferring the first multiset when--- equal elements are encountered.+-- | /O(n+m)/. The union of two multisets. The union adds the occurences together.+--  -- The implementation uses the efficient /hedge-union/ algorithm. -- Hedge-union is more efficient on (bigset `union` smallset). union :: Ord a => MultiSet a -> MultiSet a -> MultiSet a union (MS m1) (MS m2) = MS $ Map.unionWith (+) m1 m2++-- | /O(n+m)/. The union of two multisets.+-- The number of occurences of each element in the union is+-- the maximum of the number of occurences in the arguments (instead of the sum).+--+-- The implementation uses the efficient /hedge-union/ algorithm.+-- Hedge-union is more efficient on (bigset `union` smallset).+maxUnion :: Ord a => MultiSet a -> MultiSet a -> MultiSet a+maxUnion (MS m1) (MS m2) = MS $ Map.unionWith max m1 m2  -- | /O(n+m)/. Difference of two multisets.  -- The implementation uses an efficient /hedge/ algorithm comparable with /hedge-union/.

@@ -1,4 +1,4 @@-Copyright (c) Twan van Laarhoven 2007.+Copyright (c) Twan van Laarhoven 2007-2009.  All rights reserved. 

@@ -1,16 +1,20 @@ name:             multiset-version:          0.1+version:          0.2 author:           Twan van Laarhoven maintainer:       twanvl@gmail.com-category:         Data+category:         Data Structures synopsis:         The Data.MultiSet container type description:      A variation of Data.Set. Multisets, sometimes also called bags, can contain multiple copies of the same key. license:          BSD3 license-file:     LICENSE-build-depends:    base, containers build-type:       Simple-include-dirs:     include-extensions:       CPP-exposed-modules:  Data.MultiSet, Data.IntMultiSet+Cabal-version:    >= 1.2 extra-source-files: include/Typeable.h-ghc-options:      -Wall++Library+  exposed-modules:    Data.MultiSet, Data.IntMultiSet++  include-dirs:       include+  extensions:         CPP+  ghc-options:        -Wall+  build-depends:      containers, base >= 2 && < 5