multiset 0.3.2 → 0.3.3
raw patch · 4 files changed
+89/−64 lines, 4 filesdep ~base
Dependency ranges changed: base
Files
- Data/IntMultiSet.hs +38/−28
- Data/MultiSet.hs +42/−33
- multiset.cabal +1/−1
- test/Main.hs +8/−2
Data/IntMultiSet.hs view
@@ -1,4 +1,7 @@ {-# LANGUAGE CPP #-}+#if __GLASGOW_HASKELL__ < 710+{-# OPTIONS_GHC -fno-warn-amp #-}+#endif #if __GLASGOW_HASKELL__ {-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-} #endif@@ -130,12 +133,10 @@ , showTreeWith ) where -import Prelude hiding (filter,foldr,null,map,concatMap-#if __GLASGOW_HASKELL__ >= 709- ,join-#endif- )+import Prelude hiding (filter,foldr,null,map,concatMap)+#if __GLASGOW_HASKELL__ < 710 import Data.Monoid (Monoid(..))+#endif import Data.Typeable () import Data.IntMap.Strict (IntMap) import Data.IntSet (IntSet)@@ -176,9 +177,10 @@ newtype IntMultiSet = MS { unMS :: IntMap Occur } -- invariant: all values in the map are >= 1 +-- | Key type for IntMultiSet type Key = Int --- | The number of occurences of an element+-- | The number of occurrences of an element type Occur = Int instance Monoid IntMultiSet where@@ -227,7 +229,7 @@ notMember :: Key -> IntMultiSet -> Bool notMember x = not . member x --- | /O(min(n,W))/. The number of occurences of an element in a multiset.+-- | /O(min(n,W))/. The number of occurrences of an element in a multiset. occur :: Key -> IntMultiSet -> Int occur x = Map.findWithDefault 0 x . unMS @@ -253,7 +255,7 @@ -- | /O(min(n,W))/. Insert an element in a multiset a given number of times. ----- Negative numbers remove occurences of the given element.+-- Negative numbers remove occurrences of the given element. insertMany :: Key -> Occur -> IntMultiSet -> IntMultiSet insertMany x n | n < 0 = MS . Map.update (deleteN (negate n)) x . unMS@@ -266,11 +268,11 @@ -- | /O(min(n,W))/. Delete an element from a multiset a given number of times. ----- Negative numbers add occurences of the given element.+-- Negative numbers add occurrences of the given element. deleteMany :: Key -> Occur -> IntMultiSet -> IntMultiSet deleteMany x n = insertMany x (negate n) --- | /O(min(n,W))/. Delete all occurences of an element from a multiset.+-- | /O(min(n,W))/. Delete all occurrences of an element from a multiset. deleteAll :: Key -> IntMultiSet -> IntMultiSet deleteAll x = MS . Map.delete x . unMS @@ -334,11 +336,11 @@ deleteMax :: IntMultiSet -> IntMultiSet deleteMax = MS . Map.updateMax (deleteN 1) . unMS --- | /O(log n)/. Delete all occurences of the minimal element.+-- | /O(log n)/. Delete all occurrences of the minimal element. deleteMinAll :: IntMultiSet -> IntMultiSet deleteMinAll m = MS . Map.deleteMin . unMS $ m --- | /O(log n)/. Delete all occurences of the maximal element.+-- | /O(log n)/. Delete all occurrences of the maximal element. deleteMaxAll :: IntMultiSet -> IntMultiSet deleteMaxAll m = MS . Map.deleteMax . unMS $ m @@ -363,6 +365,7 @@ -- Returns @Nothing@ when passed an empty multiset. -- -- Examples:+-- -- >>> minView $ fromList [100, 100, 200, 300] -- Just (100,fromOccurList [(100,1),(200,1),(300,1)]) minView :: IntMultiSet -> Maybe (Key, IntMultiSet)@@ -374,6 +377,7 @@ -- @fail@s (in the monad) when passed an empty multiset. -- -- Examples:+-- -- >>> maxView $ fromList [100, 100, 200, 300] -- Just (300,fromOccurList [(100,2),(200,1)]) maxView :: IntMultiSet -> Maybe (Key, IntMultiSet)@@ -390,7 +394,7 @@ unions ts = foldlStrict union empty ts --- | /O(n+m)/. The union of two multisets. The union adds the occurences together.+-- | /O(n+m)/. The union of two multisets. The union adds the occurrences together. -- -- The implementation uses the efficient /hedge-union/ algorithm. -- Hedge-union is more efficient on (bigset `union` smallset).@@ -398,8 +402,8 @@ 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 number of occurrences of each element in the union is+-- the maximum of the number of occurrences in the arguments (instead of the sum). -- -- The implementation uses the efficient /hedge-union/ algorithm. -- Hedge-union is more efficient on (bigset `union` smallset).@@ -505,7 +509,7 @@ where repF a 1 b = f a b repF a n b = repF a (n - 1) (f a b) --- | /O(n)/. Fold over the elements of a multiset with their occurences.+-- | /O(n)/. Fold over the elements of a multiset with their occurrences. foldOccur :: (Key -> Occur -> b -> b) -> b -> IntMultiSet -> b foldOccur f z = Map.foldrWithKey f z . unMS @@ -548,29 +552,33 @@ fromDistinctAscList xs = fromDistinctAscOccurList $ zip xs (repeat 1) {--------------------------------------------------------------------- Occurence lists + Occurrence lists --------------------------------------------------------------------} --- | /O(n)/. Convert the multiset to a list of element\/occurence pairs.+-- | /O(n)/. Convert the multiset to a list of element\/occurrence pairs. toOccurList :: IntMultiSet -> [(Int,Int)] toOccurList = toAscOccurList --- | /O(n)/. Convert the multiset to an ascending list of element\/occurence pairs.+-- | /O(n)/. Convert the multiset to an ascending list of element\/occurrence pairs. toAscOccurList :: IntMultiSet -> [(Int,Int)] toAscOccurList = Map.toAscList . unMS --- | /O(n*min(n,W))/. Create a multiset from a list of element\/occurence pairs.+-- | /O(n*min(n,W))/. Create a multiset from a list of element\/occurrence pairs.+-- Occurrences must be positive.+-- /The precondition (all occurrences > 0) is not checked./ fromOccurList :: [(Int,Int)] -> IntMultiSet fromOccurList = MS . Map.fromListWith (+) --- | /O(n)/. Build a multiset from an ascending list of element\/occurence pairs in linear time.--- /The precondition (input list is ascending) is not checked./+-- | /O(n)/. Build a multiset from an ascending list of element\/occurrence pairs in linear time.+-- Occurrences must be positive.+-- /The precondition (input list is ascending, all occurrences > 0) is not checked./ fromAscOccurList :: [(Int,Int)] -> IntMultiSet fromAscOccurList = MS . Map.fromAscListWith (+) --- | /O(n)/. Build a multiset from an ascending list of elements\/occurence pairs where each elements appears only once.--- /The precondition (input list is strictly ascending) is not checked./+-- | /O(n)/. Build a multiset from an ascending list of elements\/occurrence pairs where each elements appears only once.+-- Occurrences must be positive.+-- /The precondition (input list is strictly ascending, all occurrences > 0) is not checked./ fromDistinctAscOccurList :: [(Int,Int)] -> IntMultiSet fromDistinctAscOccurList = MS . Map.fromDistinctAscList @@ -587,8 +595,8 @@ fromMap = MS . Map.filter (>0) -- | /O(1)/. Convert an 'IntMap' from elements to occurrences to a multiset.--- Assumes that the 'IntMap' contains only values larger than one.--- /The precondition (all elements > 1) is not checked./+-- Assumes that the 'IntMap' contains only values larger than zero.+-- /The precondition (all elements > 0) is not checked./ fromOccurMap :: IntMap Int -> IntMultiSet fromOccurMap = MS @@ -616,7 +624,7 @@ {- -- compare s1 s2 = compare (toAscList s1) (toAscList s2) -- We want {x,x,y} < {x,y}- -- i.e. if the number of occurences differ, more occurences come first.+ -- i.e. if the number of occurrences differ, more occurrences come first. -- But also, {x,x} > {x} -- so this does not hold at the end of the list. --@@ -668,8 +676,10 @@ Typeable/Data --------------------------------------------------------------------} +#if __GLASGOW_HASKELL__ < 800 #include "Typeable.h" INSTANCE_TYPEABLE0(IntMultiSet,intMultiSetTc,"IntMultiSet")+#endif {-------------------------------------------------------------------- Split@@ -682,7 +692,7 @@ split a = (\(x,y) -> (MS x, MS y)) . Map.split a . unMS -- | /O(log n)/. Performs a 'split' but also returns the number of--- occurences of the pivot element in the original set.+-- occurrences of the pivot element in the original set. splitOccur :: Int -> IntMultiSet -> (IntMultiSet,Int,IntMultiSet) splitOccur a (MS t) = let (l,m,r) = Map.splitLookup a t in (MS l, maybe 0 id m, MS r)
Data/MultiSet.hs view
@@ -1,4 +1,7 @@ {-# LANGUAGE CPP #-}+#if __GLASGOW_HASKELL__ < 710+{-# OPTIONS_GHC -fno-warn-amp #-}+#endif #if __GLASGOW_HASKELL__ {-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-} #endif@@ -15,7 +18,7 @@ -- -- A multiset is like a set, but it can contain multiple copies of the same element. -- Unless otherwise specified all insert and remove opertions affect only a single copy of an element.--- For example the minimal element before and after @deleteMin@ could be the same, only with one less occurence.+-- For example the minimal element before and after @deleteMin@ could be the same, only with one less occurrence. -- -- Since many function names (but not the type name) clash with -- "Prelude" names, this module is usually imported @qualified@, e.g.@@ -136,14 +139,12 @@ , valid ) where -import Prelude hiding (filter,foldr,null,map,concatMap-#if __GLASGOW_HASKELL__ >= 709- ,join-#endif- )+import Prelude hiding (filter,foldr,null,map,concatMap)+#if __GLASGOW_HASKELL__ < 710 import Data.Monoid (Monoid(..))+#endif import Data.Typeable ()-import qualified Data.Foldable as Foldable (Foldable(foldr))+import qualified Data.Foldable as Foldable import Data.Map.Strict (Map) import Data.Set (Set) import qualified Data.Map.Strict as Map@@ -181,7 +182,7 @@ newtype MultiSet a = MS { unMS :: Map a Occur } -- invariant: all values in the map are >= 1 --- | The number of occurences of an element+-- | The number of occurrences of an element type Occur = Int instance Ord a => Monoid (MultiSet a) where@@ -234,7 +235,7 @@ notMember :: Ord a => a -> MultiSet a -> Bool notMember x = not . member x --- | /O(log n)/. The number of occurences of an element in a multiset.+-- | /O(log n)/. The number of occurrences of an element in a multiset. occur :: Ord a => a -> MultiSet a -> Occur occur x = Map.findWithDefault 0 x . unMS @@ -260,7 +261,7 @@ -- | /O(log n)/. Insert an element in a multiset a given number of times. ----- Negative numbers remove occurences of the given element.+-- Negative numbers remove occurrences of the given element. insertMany :: Ord a => a -> Occur -> MultiSet a -> MultiSet a insertMany x n | n < 0 = MS . Map.update (deleteN (negate n)) x . unMS@@ -273,11 +274,11 @@ -- | /O(log n)/. Delete an element from a multiset a given number of times. ----- Negative numbers add occurences of the given element.+-- Negative numbers add occurrences of the given element. deleteMany :: Ord a => a -> Occur -> MultiSet a -> MultiSet a deleteMany x n = insertMany x (negate n) --- | /O(log n)/. Delete all occurences of an element from a multiset.+-- | /O(log n)/. Delete all occurrences of an element from a multiset. deleteAll :: Ord a => a -> MultiSet a -> MultiSet a deleteAll x = MS . Map.delete x . unMS @@ -320,11 +321,11 @@ deleteMax :: MultiSet a -> MultiSet a deleteMax = MS . Map.updateMax (deleteN 1) . unMS --- | /O(log n)/. Delete all occurences of the minimal element.+-- | /O(log n)/. Delete all occurrences of the minimal element. deleteMinAll :: MultiSet a -> MultiSet a deleteMinAll = MS . Map.deleteMin . unMS --- | /O(log n)/. Delete all occurences of the maximal element.+-- | /O(log n)/. Delete all occurrences of the maximal element. deleteMaxAll :: MultiSet a -> MultiSet a deleteMaxAll = MS . Map.deleteMax . unMS @@ -349,6 +350,7 @@ -- Returns @Nothing@ when passed an empty multiset. -- -- Examples:+-- -- >>> minView $ fromList ['a', 'a', 'b', 'c'] -- Just ('a',fromOccurList [('a',1),('b',1),('c',1)]) minView :: MultiSet a -> Maybe (a, MultiSet a)@@ -361,6 +363,7 @@ -- Returns @Nothing@ when passed an empty multiset. -- -- Examples:+-- -- >>> maxView $ fromList ['a', 'a', 'b', 'c'] -- Just ('c',fromOccurList [('a',2),('b',1)]) maxView :: MultiSet a -> Maybe (a, MultiSet a)@@ -377,7 +380,7 @@ unions ts = foldlStrict union empty ts --- | /O(n+m)/. The union of two multisets. The union adds the occurences together.+-- | /O(n+m)/. The union of two multisets. The union adds the occurrences together. -- -- The implementation uses the efficient /hedge-union/ algorithm. -- Hedge-union is more efficient on (bigset `union` smallset).@@ -385,8 +388,8 @@ 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 number of occurrences of each element in the union is+-- the maximum of the number of occurrences in the arguments (instead of the sum). -- -- The implementation uses the efficient /hedge-union/ algorithm. -- Hedge-union is more efficient on (bigset `union` smallset).@@ -416,13 +419,13 @@ Filter and partition --------------------------------------------------------------------} -- | /O(n)/. Filter all elements that satisfy the predicate.-filter :: Ord a => (a -> Bool) -> MultiSet a -> MultiSet a+filter :: (a -> Bool) -> MultiSet a -> MultiSet a filter p = MS . Map.filterWithKey (\k _ -> p k) . unMS -- | /O(n)/. Partition the multiset into two multisets, one with all elements that satisfy -- the predicate and one with all elements that don't satisfy the predicate. -- See also 'split'.-partition :: Ord a => (a -> Bool) -> MultiSet a -> (MultiSet a,MultiSet a)+partition :: (a -> Bool) -> MultiSet a -> (MultiSet a,MultiSet a) partition p = (\(x,y) -> (MS x, MS y)) . Map.partitionWithKey (\k _ -> p k) . unMS {----------------------------------------------------------------------@@ -499,7 +502,7 @@ where repF a 1 b = f a b repF a n b = repF a (n - 1) (f a b) --- | /O(n)/. Fold over the elements of a multiset with their occurences.+-- | /O(n)/. Fold over the elements of a multiset with their occurrences. foldOccur :: (a -> Occur -> b -> b) -> b -> MultiSet a -> b foldOccur f z = Map.foldrWithKey f z . unMS @@ -542,29 +545,33 @@ fromDistinctAscList xs = fromDistinctAscOccurList $ zip xs (repeat 1) {--------------------------------------------------------------------- Occurence lists + Occurrence lists --------------------------------------------------------------------} --- | /O(n)/. Convert the multiset to a list of element\/occurence pairs.+-- | /O(n)/. Convert the multiset to a list of element\/occurrence pairs. toOccurList :: MultiSet a -> [(a,Occur)] toOccurList = toAscOccurList --- | /O(n)/. Convert the multiset to an ascending list of element\/occurence pairs.+-- | /O(n)/. Convert the multiset to an ascending list of element\/occurrence pairs. toAscOccurList :: MultiSet a -> [(a,Occur)] toAscOccurList = Map.toAscList . unMS --- | /O(n*log n)/. Create a multiset from a list of element\/occurence pairs.+-- | /O(n*log n)/. Create a multiset from a list of element\/occurrence pairs.+-- Occurrences must be positive.+-- /The precondition (all occurrences > 0) is not checked./ fromOccurList :: Ord a => [(a,Occur)] -> MultiSet a fromOccurList = MS . Map.fromListWith (+) --- | /O(n)/. Build a multiset from an ascending list of element\/occurence pairs in linear time.--- /The precondition (input list is ascending) is not checked./+-- | /O(n)/. Build a multiset from an ascending list of element\/occurrence pairs in linear time.+-- Occurrences must be positive.+-- /The precondition (input list is ascending, all occurrences > 0) is not checked./ fromAscOccurList :: Eq a => [(a,Occur)] -> MultiSet a fromAscOccurList = MS . Map.fromAscListWith (+) --- | /O(n)/. Build a multiset from an ascending list of elements\/occurence pairs where each elements appears only once.--- /The precondition (input list is strictly ascending) is not checked./+-- | /O(n)/. Build a multiset from an ascending list of elements\/occurrence pairs where each elements appears only once.+-- Occurrences must be positive.+-- /The precondition (input list is strictly ascending, all occurrences > 0) is not checked./ fromDistinctAscOccurList :: [(a,Occur)] -> MultiSet a fromDistinctAscOccurList = MS . Map.fromDistinctAscList @@ -577,12 +584,12 @@ toMap = unMS -- | /O(n)/. Convert a 'Map' from elements to occurrences to a multiset.-fromMap :: Ord a => Map a Occur -> MultiSet a+fromMap :: Map a Occur -> MultiSet a fromMap = MS . Map.filter (>0) -- | /O(1)/. Convert a 'Map' from elements to occurrences to a multiset.--- Assumes that the 'Map' contains only values larger than one.--- /The precondition (all elements > 1) is not checked./+-- Assumes that the 'Map' contains only values larger than zero.+-- /The precondition (all elements > 0) is not checked./ fromOccurMap :: Map a Occur -> MultiSet a fromOccurMap = MS @@ -610,7 +617,7 @@ {- -- compare s1 s2 = compare (toAscList s1) (toAscList s2) -- We want {x,x,y} < {x,y}- -- i.e. if the number of occurences differ, more occurences come first.+ -- i.e. if the number of occurrences differ, more occurrences come first. -- But also, {x,x} > {x} -- so this does not hold at the end of the list. --@@ -662,8 +669,10 @@ Typeable/Data --------------------------------------------------------------------} +#if __GLASGOW_HASKELL__ < 800 #include "Typeable.h" INSTANCE_TYPEABLE1(MultiSet,multiSetTc,"MultiSet")+#endif {-------------------------------------------------------------------- Split@@ -676,7 +685,7 @@ split a = (\(x,y) -> (MS x, MS y)) . Map.split a . unMS -- | /O(log n)/. Performs a 'split' but also returns the number of--- occurences of the pivot element in the original set.+-- occurrences of the pivot element in the original set. splitOccur :: Ord a => a -> MultiSet a -> (MultiSet a,Occur,MultiSet a) splitOccur a (MS t) = let (l,m,r) = Map.splitLookup a t in (MS l, maybe 0 id m, MS r)
multiset.cabal view
@@ -1,5 +1,5 @@ name: multiset-version: 0.3.2+version: 0.3.3 author: Twan van Laarhoven maintainer: twanvl@gmail.com bug-reports: https://github.com/twanvl/multiset/issues
test/Main.hs view
@@ -5,8 +5,14 @@ import "Glob" System.FilePath.Glob (glob) import "doctest" Test.DocTest (doctest) +includeDirs :: [String]+includeDirs = ["include"]++doctestWithIncludeDirs :: [String] -> IO ()+doctestWithIncludeDirs fs = doctest (map ((++) "-I") includeDirs ++ fs)+ main :: IO () main = do- glob "Data/**/*.hs" >>= doctest- glob "test/**/*.hs" >>= doctest+ glob "Data/**/*.hs" >>= doctestWithIncludeDirs+ glob "test/**/*.hs" >>= doctestWithIncludeDirs