-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | The Data.MultiSet container type
--
-- A variation of Data.Set. Multisets, sometimes also called bags, can
-- contain multiple copies of the same key.
@package multiset
@version 0.3.4
-- | An efficient implementation of multisets, also sometimes called bags.
--
-- 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 occurrence.
--
-- Since many function names (but not the type name) clash with
-- Prelude names, this module is usually imported
-- qualified, e.g.
--
--
-- import Data.MultiSet (MultiSet)
-- import qualified Data.MultiSet as MultiSet
--
--
-- The implementation of MultiSet is based on the Data.Map
-- module.
--
-- Note that the implementation is left-biased -- the elements of
-- a first argument are always preferred to the second, for example in
-- union or insert. Of course, left-biasing can only be
-- observed when equality is an equivalence relation instead of
-- structural equality.
--
-- In the complexity of functions n refers to the number of
-- distinct elements, t is the total number of elements.
module Data.MultiSet
-- | A multiset of values a. The same value can occur multiple
-- times.
data MultiSet a
-- | The number of occurrences of an element
type Occur = Int
-- | O(n+m). See difference.
(\\) :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
infixl 9 \\
-- | O(1). Is this the empty multiset?
null :: MultiSet a -> Bool
-- | O(n). The number of elements in the multiset.
size :: MultiSet a -> Occur
-- | O(1). The number of distinct elements in the multiset.
distinctSize :: MultiSet a -> Occur
-- | O(log n). Is the element in the multiset?
member :: Ord a => a -> MultiSet a -> Bool
-- | O(log n). Is the element not in the multiset?
notMember :: Ord a => a -> MultiSet a -> Bool
-- | O(log n). The number of occurrences of an element in a
-- multiset.
occur :: Ord a => a -> MultiSet a -> Occur
-- | O(n+m). Is this a subset? (s1 `isSubsetOf` s2) tells
-- whether s1 is a subset of s2.
isSubsetOf :: Ord a => MultiSet a -> MultiSet a -> Bool
-- | O(n+m). Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: Ord a => MultiSet a -> MultiSet a -> Bool
-- | O(1). The empty mutli set.
empty :: MultiSet a
-- | O(1). Create a singleton mutli set.
singleton :: a -> MultiSet a
-- | O(log n). Insert an element in a multiset.
insert :: Ord a => a -> MultiSet a -> MultiSet a
-- | O(log n). Insert an element in a multiset a given number of
-- times.
--
-- Negative numbers remove occurrences of the given element.
insertMany :: Ord a => a -> Occur -> MultiSet a -> MultiSet a
-- | O(log n). Delete a single element from a multiset.
delete :: Ord a => a -> MultiSet a -> MultiSet a
-- | O(log n). Delete an element from a multiset a given number of
-- times.
--
-- Negative numbers add occurrences of the given element.
deleteMany :: Ord a => a -> Occur -> MultiSet a -> MultiSet a
-- | O(log n). Delete all occurrences of an element from a multiset.
deleteAll :: Ord a => a -> MultiSet a -> MultiSet a
-- | 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).
union :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
-- | The union of a list of multisets: (unions == foldl
-- union empty).
unions :: Ord a => [MultiSet a] -> MultiSet a
-- | O(n+m). The union of two multisets. 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).
maxUnion :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
-- | O(n+m). Difference of two multisets. The implementation uses an
-- efficient hedge algorithm comparable with hedge-union.
difference :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
-- | 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 :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
-- | O(n). Filter all elements that satisfy the predicate.
filter :: (a -> Bool) -> MultiSet a -> MultiSet a
-- | 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 :: (a -> Bool) -> MultiSet a -> (MultiSet a, MultiSet a)
-- | O(log n). The expression (split x set) is a
-- pair (set1,set2) where all elements in set1 are
-- lower than x and all elements in set2 larger than
-- x. x is not found in neither set1 nor
-- set2.
split :: Ord a => a -> MultiSet a -> (MultiSet a, MultiSet a)
-- | O(log n). Performs a split but also returns the number
-- of occurrences of the pivot element in the original set.
splitOccur :: Ord a => a -> MultiSet a -> (MultiSet a, Occur, MultiSet a)
-- | O(n*log n). map f s is the multiset obtained by
-- applying f to each element of s.
map :: (Ord b) => (a -> b) -> MultiSet a -> MultiSet b
-- | O(n). The
--
-- mapMonotonic f s == map f s, but works only
-- when f is strictly monotonic. The precondition is not
-- checked. Semi-formally, we have:
--
--
-- and [x < y ==> f x < f y | x <- ls, y <- ls]
-- ==> mapMonotonic f s == map f s
-- where ls = toList s
--
mapMonotonic :: (a -> b) -> MultiSet a -> MultiSet b
-- | O(n). Map and collect the Just results.
mapMaybe :: (Ord b) => (a -> Maybe b) -> MultiSet a -> MultiSet b
-- | O(n). Map and separate the Left and Right
-- results.
mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MultiSet a -> (MultiSet b, MultiSet c)
-- | O(n). Apply a function to each element, and take the union of
-- the results
concatMap :: (Ord b) => (a -> [b]) -> MultiSet a -> MultiSet b
-- | O(n). Apply a function to each element, and take the union of
-- the results
unionsMap :: (Ord b) => (a -> MultiSet b) -> MultiSet a -> MultiSet b
-- | O(n). The monad bind operation, (>>=), for multisets.
bind :: (Ord b) => MultiSet a -> (a -> MultiSet b) -> MultiSet b
-- | O(n). The monad join operation for multisets.
join :: Ord a => MultiSet (MultiSet a) -> MultiSet a
-- | O(t). Fold over the elements of a multiset in an unspecified
-- order.
fold :: (a -> b -> b) -> b -> MultiSet a -> b
-- | O(n). Fold over the elements of a multiset with their
-- occurrences.
foldOccur :: (a -> Occur -> b -> b) -> b -> MultiSet a -> b
-- | O(log n). The minimal element of a multiset.
findMin :: MultiSet a -> a
-- | O(log n). The maximal element of a multiset.
findMax :: MultiSet a -> a
-- | O(log n). Delete the minimal element.
deleteMin :: MultiSet a -> MultiSet a
-- | O(log n). Delete the maximal element.
deleteMax :: MultiSet a -> MultiSet a
-- | O(log n). Delete all occurrences of the minimal element.
deleteMinAll :: MultiSet a -> MultiSet a
-- | O(log n). Delete all occurrences of the maximal element.
deleteMaxAll :: MultiSet a -> MultiSet a
-- | O(log n). Delete and find the minimal element.
--
--
-- deleteFindMin set = (findMin set, deleteMin set)
--
deleteFindMin :: MultiSet a -> (a, MultiSet a)
-- | O(log n). Delete and find the maximal element.
--
--
-- deleteFindMax set = (findMax set, deleteMax set)
--
deleteFindMax :: MultiSet a -> (a, MultiSet a)
-- | O(log n). Retrieves the maximal element of the multiset, and
-- the set with that element removed. 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)
-- | O(log n). Retrieves the minimal element of the multiset, and
-- the set with that element removed. 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)
-- | O(t). The elements of a multiset.
elems :: MultiSet a -> [a]
-- | O(n). The distinct elements of a multiset, each element occurs
-- only once in the list.
--
--
-- distinctElems = map fst . toOccurList
--
distinctElems :: MultiSet a -> [a]
-- | O(t). Convert the multiset to a list of elements.
toList :: MultiSet a -> [a]
-- | O(t*log t). Create a multiset from a list of elements.
fromList :: Ord a => [a] -> MultiSet a
-- | O(t). Convert the multiset to an ascending list of elements.
toAscList :: MultiSet a -> [a]
-- | O(t). Build a multiset from an ascending list in linear time.
-- The precondition (input list is ascending) is not checked.
fromAscList :: Eq a => [a] -> MultiSet a
-- | O(n). Build a multiset from an ascending list of distinct
-- elements in linear time. The precondition (input list is strictly
-- ascending) is not checked.
fromDistinctAscList :: [a] -> MultiSet a
-- | O(n). Convert the multiset to a list of element/occurrence
-- pairs.
toOccurList :: MultiSet a -> [(a, Occur)]
-- | O(n). Convert the multiset to an ascending list of
-- element/occurrence pairs.
toAscOccurList :: MultiSet a -> [(a, Occur)]
-- | 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
-- | 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
-- | 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
-- | O(1). Convert a multiset to a Map from elements to
-- number of occurrences.
toMap :: MultiSet a -> Map a Occur
-- | O(n). Convert a Map from elements to occurrences to a
-- multiset.
fromMap :: Map a Occur -> MultiSet a
-- | O(1). Convert a Map from elements to occurrences to a
-- multiset. Assumes that the Map contains only values larger than
-- zero. The precondition (all elements > 0) is not checked.
fromOccurMap :: Map a Occur -> MultiSet a
-- | O(n). Convert a multiset to a Set, removing duplicates.
toSet :: MultiSet a -> Set a
-- | O(n). Convert a Set to a multiset.
fromSet :: Set a -> MultiSet a
-- | O(n). Show the tree that implements the set. The tree is shown
-- in a compressed, hanging format.
showTree :: Show a => MultiSet a -> String
-- | O(n). The expression (showTreeWith hang wide map)
-- shows the tree that implements the set. If hang is
-- True, a hanging tree is shown otherwise a rotated tree
-- is shown. If wide is True, an extra wide version is
-- shown.
--
--
-- Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1,1,2,3,4,5]
-- (1*) 4
-- +--(1*) 2
-- | +--(2*) 1
-- | +--(1*) 3
-- +--(1*) 5
--
-- Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1,1,2,3,4,5]
-- (1*) 4
-- |
-- +--(1*) 2
-- | |
-- | +--(2*) 1
-- | |
-- | +--(1*) 3
-- |
-- +--(1*) 5
--
-- Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1,1,2,3,4,5]
-- +--(1*) 5
-- |
-- (1*) 4
-- |
-- | +--(1*) 3
-- | |
-- +--(1*) 2
-- |
-- +--(2*) 1
--
showTreeWith :: Show a => Bool -> Bool -> MultiSet a -> String
-- | O(n). Test if the internal multiset structure is valid.
valid :: Ord a => MultiSet a -> Bool
instance GHC.Classes.Ord a => GHC.Base.Monoid (Data.MultiSet.MultiSet a)
instance Data.Foldable.Foldable Data.MultiSet.MultiSet
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.MultiSet.MultiSet a)
instance (Data.Data.Data a, GHC.Classes.Ord a) => Data.Data.Data (Data.MultiSet.MultiSet a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.MultiSet.MultiSet a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.MultiSet.MultiSet a)
instance GHC.Show.Show a => GHC.Show.Show (Data.MultiSet.MultiSet a)
instance (GHC.Read.Read a, GHC.Classes.Ord a) => GHC.Read.Read (Data.MultiSet.MultiSet a)
-- | An efficient implementation of multisets of integers, also sometimes
-- called bags.
--
-- A multiset is like a set, but it can contain multiple copies of the
-- same element.
--
-- Since many function names (but not the type name) clash with
-- Prelude names, this module is usually imported
-- qualified, e.g.
--
--
-- import Data.IntMultiSet (IntMultiSet)
-- import qualified Data.IntMultiSet as IntMultiSet
--
--
-- The implementation of IntMultiSet is based on the
-- Data.IntMap module.
--
-- Many operations have a worst-case complexity of O(min(n,W)).
-- This means that the operation can become linear in the number of
-- elements with a maximum of W -- the number of bits in an
-- Int (32 or 64). Here n refers to the number of distinct
-- elements, t is the total number of elements.
module Data.IntMultiSet
-- | A multiset of integers. The same value can occur multiple times.
data IntMultiSet
-- | Key type for IntMultiSet
type Key = Int
-- | The number of occurrences of an element
type Occur = Int
-- | O(n+m). See difference.
(\\) :: IntMultiSet -> IntMultiSet -> IntMultiSet
infixl 9 \\
-- | O(1). Is this the empty multiset?
null :: IntMultiSet -> Bool
-- | O(n). The number of elements in the multiset.
size :: IntMultiSet -> Int
-- | O(1). The number of distinct elements in the multiset.
distinctSize :: IntMultiSet -> Int
-- | O(min(n,W)). Is the element in the multiset?
member :: Key -> IntMultiSet -> Bool
-- | O(min(n,W)). Is the element not in the multiset?
notMember :: Key -> IntMultiSet -> Bool
-- | O(min(n,W)). The number of occurrences of an element in a
-- multiset.
occur :: Key -> IntMultiSet -> Int
-- | O(n+m). Is this a subset? (s1 `isSubsetOf` s2) tells
-- whether s1 is a subset of s2.
isSubsetOf :: IntMultiSet -> IntMultiSet -> Bool
-- | O(n+m). Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: IntMultiSet -> IntMultiSet -> Bool
-- | O(1). The empty mutli set.
empty :: IntMultiSet
-- | O(1). Create a singleton mutli set.
singleton :: Key -> IntMultiSet
-- | O(min(n,W)). Insert an element in a multiset.
insert :: Key -> IntMultiSet -> IntMultiSet
-- | O(min(n,W)). Insert an element in a multiset a given number of
-- times.
--
-- Negative numbers remove occurrences of the given element.
insertMany :: Key -> Occur -> IntMultiSet -> IntMultiSet
-- | O(min(n,W)). Delete a single element from a multiset.
delete :: Key -> IntMultiSet -> IntMultiSet
-- | O(min(n,W)). Delete an element from a multiset a given number
-- of times.
--
-- Negative numbers add occurrences of the given element.
deleteMany :: Key -> Occur -> IntMultiSet -> IntMultiSet
-- | O(min(n,W)). Delete all occurrences of an element from a
-- multiset.
deleteAll :: Key -> IntMultiSet -> IntMultiSet
-- | 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).
union :: IntMultiSet -> IntMultiSet -> IntMultiSet
-- | The union of a list of multisets: (unions == foldl
-- union empty).
unions :: [IntMultiSet] -> IntMultiSet
-- | O(n+m). The union of two multisets. 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).
maxUnion :: IntMultiSet -> IntMultiSet -> IntMultiSet
-- | O(n+m). Difference of two multisets. The implementation uses an
-- efficient hedge algorithm comparable with hedge-union.
difference :: IntMultiSet -> IntMultiSet -> IntMultiSet
-- | O(n+m). The intersection of two multisets.
--
-- prints (fromList [A],fromList [B]).
intersection :: IntMultiSet -> IntMultiSet -> IntMultiSet
-- | O(n). Filter all elements that satisfy the predicate.
filter :: (Key -> Bool) -> IntMultiSet -> IntMultiSet
-- | 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 :: (Key -> Bool) -> IntMultiSet -> (IntMultiSet, IntMultiSet)
-- | O(log n). The expression (split x set) is a
-- pair (set1,set2) where all elements in set1 are
-- lower than x and all elements in set2 larger than
-- x. x is not found in neither set1 nor
-- set2.
split :: Int -> IntMultiSet -> (IntMultiSet, IntMultiSet)
-- | O(log n). Performs a split but also returns the number
-- of occurrences of the pivot element in the original set.
splitOccur :: Int -> IntMultiSet -> (IntMultiSet, Int, IntMultiSet)
-- | O(n*log n). map f s is the multiset obtained by
-- applying f to each element of s.
map :: (Key -> Key) -> IntMultiSet -> IntMultiSet
-- | O(n). The
--
-- mapMonotonic f s == map f s, but works only
-- when f is strictly monotonic. The precondition is not
-- checked. Semi-formally, we have:
--
--
-- and [x < y ==> f x < f y | x <- ls, y <- ls]
-- ==> mapMonotonic f s == map f s
-- where ls = toList s
--
mapMonotonic :: (Key -> Key) -> IntMultiSet -> IntMultiSet
-- | O(n). Map and collect the Just results.
mapMaybe :: (Key -> Maybe Key) -> IntMultiSet -> IntMultiSet
-- | O(n). Map and separate the Left and Right
-- results.
mapEither :: (Key -> Either Key Key) -> IntMultiSet -> (IntMultiSet, IntMultiSet)
-- | O(n). Apply a function to each element, and take the union of
-- the results
concatMap :: (Key -> [Key]) -> IntMultiSet -> IntMultiSet
-- | O(n). Apply a function to each element, and take the union of
-- the results
unionsMap :: (Key -> IntMultiSet) -> IntMultiSet -> IntMultiSet
-- | O(n). The monad bind operation, (>>=), for multisets.
bind :: IntMultiSet -> (Key -> IntMultiSet) -> IntMultiSet
-- | O(n). The monad join operation for multisets.
join :: MultiSet IntMultiSet -> IntMultiSet
-- | O(t). Fold over the elements of a multiset in an unspecified
-- order.
fold :: (Key -> b -> b) -> b -> IntMultiSet -> b
-- | O(n). Fold over the elements of a multiset with their
-- occurrences.
foldOccur :: (Key -> Occur -> b -> b) -> b -> IntMultiSet -> b
-- | O(log n). The minimal element of a multiset.
findMin :: IntMultiSet -> Key
-- | O(log n). The maximal element of a multiset.
findMax :: IntMultiSet -> Key
-- | O(log n). Delete the minimal element.
deleteMin :: IntMultiSet -> IntMultiSet
-- | O(log n). Delete the maximal element.
deleteMax :: IntMultiSet -> IntMultiSet
-- | O(log n). Delete all occurrences of the minimal element.
deleteMinAll :: IntMultiSet -> IntMultiSet
-- | O(log n). Delete all occurrences of the maximal element.
deleteMaxAll :: IntMultiSet -> IntMultiSet
-- | O(log n). Delete and find the minimal element.
--
--
-- deleteFindMin set = (findMin set, deleteMin set)
--
deleteFindMin :: IntMultiSet -> (Key, IntMultiSet)
-- | O(log n). Delete and find the maximal element.
--
--
-- deleteFindMax set = (findMax set, deleteMax set)
--
deleteFindMax :: IntMultiSet -> (Key, IntMultiSet)
-- | O(log n). Retrieves the maximal element of the multiset, and
-- the set stripped from that element fails (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)
-- | O(log n). Retrieves the minimal element of the multiset, and
-- the set stripped from that element 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)
-- | O(t). The elements of a multiset.
elems :: IntMultiSet -> [Key]
-- | O(n). The distinct elements of a multiset, each element occurs
-- only once in the list.
--
--
-- distinctElems = map fst . toOccurList
--
distinctElems :: IntMultiSet -> [Key]
-- | O(t). Convert the multiset to a list of elements.
toList :: IntMultiSet -> [Key]
-- | O(t*min(n,W)). Create a multiset from a list of elements.
fromList :: [Int] -> IntMultiSet
-- | O(t). Convert the multiset to an ascending list of elements.
toAscList :: IntMultiSet -> [Key]
-- | O(t). Build a multiset from an ascending list in linear time.
-- The precondition (input list is ascending) is not checked.
fromAscList :: [Int] -> IntMultiSet
-- | O(n). Build a multiset from an ascending list of distinct
-- elements in linear time. The precondition (input list is strictly
-- ascending) is not checked.
fromDistinctAscList :: [Int] -> IntMultiSet
-- | O(n). Convert the multiset to a list of element/occurrence
-- pairs.
toOccurList :: IntMultiSet -> [(Int, Int)]
-- | O(n). Convert the multiset to an ascending list of
-- element/occurrence pairs.
toAscOccurList :: IntMultiSet -> [(Int, Int)]
-- | 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
-- | 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
-- | 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
-- | O(1). Convert a multiset to an IntMap from elements to
-- number of occurrences.
toMap :: IntMultiSet -> IntMap Int
-- | O(n). Convert an IntMap from elements to occurrences to
-- a multiset.
fromMap :: IntMap Int -> IntMultiSet
-- | O(1). Convert an IntMap from elements to occurrences to
-- a multiset. Assumes that the IntMap contains only values larger
-- than zero. The precondition (all elements > 0) is not
-- checked.
fromOccurMap :: IntMap Int -> IntMultiSet
-- | O(n). Convert a multiset to an IntMap, removing
-- duplicates.
toSet :: IntMultiSet -> IntSet
-- | O(n). Convert an IntMap to a multiset.
fromSet :: IntSet -> IntMultiSet
-- | O(n). Show the tree that implements the set. The tree is shown
-- in a compressed, hanging format.
showTree :: IntMultiSet -> String
-- | O(n). The expression (showTreeWith hang wide map)
-- shows the tree that implements the set. If hang is
-- True, a hanging tree is shown otherwise a rotated tree
-- is shown. If wide is True, an extra wide version is
-- shown.
--
--
-- Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1,1,2,3,4,5]
-- (1*) 4
-- +--(1*) 2
-- | +--(2*) 1
-- | +--(1*) 3
-- +--(1*) 5
--
-- Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1,1,2,3,4,5]
-- (1*) 4
-- |
-- +--(1*) 2
-- | |
-- | +--(2*) 1
-- | |
-- | +--(1*) 3
-- |
-- +--(1*) 5
--
-- Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1,1,2,3,4,5]
-- +--(1*) 5
-- |
-- (1*) 4
-- |
-- | +--(1*) 3
-- | |
-- +--(1*) 2
-- |
-- +--(2*) 1
--
showTreeWith :: Bool -> Bool -> IntMultiSet -> String
instance GHC.Base.Monoid Data.IntMultiSet.IntMultiSet
instance Control.DeepSeq.NFData Data.IntMultiSet.IntMultiSet
instance Data.Data.Data Data.IntMultiSet.IntMultiSet
instance GHC.Classes.Eq Data.IntMultiSet.IntMultiSet
instance GHC.Classes.Ord Data.IntMultiSet.IntMultiSet
instance GHC.Show.Show Data.IntMultiSet.IntMultiSet
instance GHC.Read.Read Data.IntMultiSet.IntMultiSet