-- 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 <tt>deleteMin</tt> could be the same,
--   only with one less occurrence.
--   
--   Since many function names (but not the type name) clash with
--   <a>Prelude</a> names, this module is usually imported
--   <tt>qualified</tt>, e.g.
--   
--   <pre>
--   import Data.MultiSet (MultiSet)
--   import qualified Data.MultiSet as MultiSet
--   </pre>
--   
--   The implementation of <a>MultiSet</a> is based on the <a>Data.Map</a>
--   module.
--   
--   Note that the implementation is <i>left-biased</i> -- the elements of
--   a first argument are always preferred to the second, for example in
--   <a>union</a> or <a>insert</a>. Of course, left-biasing can only be
--   observed when equality is an equivalence relation instead of
--   structural equality.
--   
--   In the complexity of functions <i>n</i> refers to the number of
--   distinct elements, <i>t</i> is the total number of elements.
module Data.MultiSet

-- | A multiset of values <tt>a</tt>. The same value can occur multiple
--   times.
data MultiSet a

-- | The number of occurrences of an element
type Occur = Int

-- | <i>O(n+m)</i>. See <a>difference</a>.
(\\) :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
infixl 9 \\

-- | <i>O(1)</i>. Is this the empty multiset?
null :: MultiSet a -> Bool

-- | <i>O(n)</i>. The number of elements in the multiset.
size :: MultiSet a -> Occur

-- | <i>O(1)</i>. The number of distinct elements in the multiset.
distinctSize :: MultiSet a -> Occur

-- | <i>O(log n)</i>. Is the element in the multiset?
member :: Ord a => a -> MultiSet a -> Bool

-- | <i>O(log n)</i>. Is the element not in the multiset?
notMember :: Ord a => a -> MultiSet a -> Bool

-- | <i>O(log n)</i>. The number of occurrences of an element in a
--   multiset.
occur :: Ord a => a -> MultiSet a -> Occur

-- | <i>O(n+m)</i>. Is this a subset? <tt>(s1 `isSubsetOf` s2)</tt> tells
--   whether <tt>s1</tt> is a subset of <tt>s2</tt>.
isSubsetOf :: Ord a => MultiSet a -> MultiSet a -> Bool

-- | <i>O(n+m)</i>. Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: Ord a => MultiSet a -> MultiSet a -> Bool

-- | <i>O(1)</i>. The empty mutli set.
empty :: MultiSet a

-- | <i>O(1)</i>. Create a singleton mutli set.
singleton :: a -> MultiSet a

-- | <i>O(log n)</i>. Insert an element in a multiset.
insert :: Ord a => a -> MultiSet a -> MultiSet a

-- | <i>O(log n)</i>. 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

-- | <i>O(log n)</i>. Delete a single element from a multiset.
delete :: Ord a => a -> MultiSet a -> MultiSet a

-- | <i>O(log n)</i>. 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

-- | <i>O(log n)</i>. Delete all occurrences of an element from a multiset.
deleteAll :: Ord a => a -> MultiSet a -> MultiSet a

-- | <i>O(n+m)</i>. The union of two multisets. The union adds the
--   occurrences together.
--   
--   The implementation uses the efficient <i>hedge-union</i> algorithm.
--   Hedge-union is more efficient on (bigset <a>union</a> smallset).
union :: Ord a => MultiSet a -> MultiSet a -> MultiSet a

-- | The union of a list of multisets: (<tt><a>unions</a> == <a>foldl</a>
--   <a>union</a> <a>empty</a></tt>).
unions :: Ord a => [MultiSet a] -> MultiSet a

-- | <i>O(n+m)</i>. 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 <i>hedge-union</i> algorithm.
--   Hedge-union is more efficient on (bigset <a>union</a> smallset).
maxUnion :: Ord a => MultiSet a -> MultiSet a -> MultiSet a

-- | <i>O(n+m)</i>. Difference of two multisets. The implementation uses an
--   efficient <i>hedge</i> algorithm comparable with <i>hedge-union</i>.
difference :: Ord a => MultiSet a -> MultiSet a -> MultiSet a

-- | <i>O(n+m)</i>. The intersection of two multisets. Elements of the
--   result come from the first multiset, so for example
--   
--   <pre>
--   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)
--   </pre>
--   
--   prints <tt>(fromList [A],fromList [B])</tt>.
intersection :: Ord a => MultiSet a -> MultiSet a -> MultiSet a

-- | <i>O(n)</i>. Filter all elements that satisfy the predicate.
filter :: (a -> Bool) -> MultiSet a -> MultiSet a

-- | <i>O(n)</i>. 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 <a>split</a>.
partition :: (a -> Bool) -> MultiSet a -> (MultiSet a, MultiSet a)

-- | <i>O(log n)</i>. The expression (<tt><a>split</a> x set</tt>) is a
--   pair <tt>(set1,set2)</tt> where all elements in <tt>set1</tt> are
--   lower than <tt>x</tt> and all elements in <tt>set2</tt> larger than
--   <tt>x</tt>. <tt>x</tt> is not found in neither <tt>set1</tt> nor
--   <tt>set2</tt>.
split :: Ord a => a -> MultiSet a -> (MultiSet a, MultiSet a)

-- | <i>O(log n)</i>. Performs a <a>split</a> 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)

-- | <i>O(n*log n)</i>. <tt><a>map</a> f s</tt> is the multiset obtained by
--   applying <tt>f</tt> to each element of <tt>s</tt>.
map :: (Ord b) => (a -> b) -> MultiSet a -> MultiSet b

-- | <i>O(n)</i>. The
--   
--   <tt><a>mapMonotonic</a> f s == <a>map</a> f s</tt>, but works only
--   when <tt>f</tt> is strictly monotonic. <i>The precondition is not
--   checked.</i> Semi-formally, we have:
--   
--   <pre>
--   and [x &lt; y ==&gt; f x &lt; f y | x &lt;- ls, y &lt;- ls]
--                       ==&gt; mapMonotonic f s == map f s
--       where ls = toList s
--   </pre>
mapMonotonic :: (a -> b) -> MultiSet a -> MultiSet b

-- | <i>O(n)</i>. Map and collect the <a>Just</a> results.
mapMaybe :: (Ord b) => (a -> Maybe b) -> MultiSet a -> MultiSet b

-- | <i>O(n)</i>. Map and separate the <a>Left</a> and <a>Right</a>
--   results.
mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MultiSet a -> (MultiSet b, MultiSet c)

-- | <i>O(n)</i>. Apply a function to each element, and take the union of
--   the results
concatMap :: (Ord b) => (a -> [b]) -> MultiSet a -> MultiSet b

-- | <i>O(n)</i>. Apply a function to each element, and take the union of
--   the results
unionsMap :: (Ord b) => (a -> MultiSet b) -> MultiSet a -> MultiSet b

-- | <i>O(n)</i>. The monad bind operation, (&gt;&gt;=), for multisets.
bind :: (Ord b) => MultiSet a -> (a -> MultiSet b) -> MultiSet b

-- | <i>O(n)</i>. The monad join operation for multisets.
join :: Ord a => MultiSet (MultiSet a) -> MultiSet a

-- | <i>O(t)</i>. Fold over the elements of a multiset in an unspecified
--   order.
fold :: (a -> b -> b) -> b -> MultiSet a -> b

-- | <i>O(n)</i>. Fold over the elements of a multiset with their
--   occurrences.
foldOccur :: (a -> Occur -> b -> b) -> b -> MultiSet a -> b

-- | <i>O(log n)</i>. The minimal element of a multiset.
findMin :: MultiSet a -> a

-- | <i>O(log n)</i>. The maximal element of a multiset.
findMax :: MultiSet a -> a

-- | <i>O(log n)</i>. Delete the minimal element.
deleteMin :: MultiSet a -> MultiSet a

-- | <i>O(log n)</i>. Delete the maximal element.
deleteMax :: MultiSet a -> MultiSet a

-- | <i>O(log n)</i>. Delete all occurrences of the minimal element.
deleteMinAll :: MultiSet a -> MultiSet a

-- | <i>O(log n)</i>. Delete all occurrences of the maximal element.
deleteMaxAll :: MultiSet a -> MultiSet a

-- | <i>O(log n)</i>. Delete and find the minimal element.
--   
--   <pre>
--   deleteFindMin set = (findMin set, deleteMin set)
--   </pre>
deleteFindMin :: MultiSet a -> (a, MultiSet a)

-- | <i>O(log n)</i>. Delete and find the maximal element.
--   
--   <pre>
--   deleteFindMax set = (findMax set, deleteMax set)
--   </pre>
deleteFindMax :: MultiSet a -> (a, MultiSet a)

-- | <i>O(log n)</i>. Retrieves the maximal element of the multiset, and
--   the set with that element removed. Returns <tt>Nothing</tt> when
--   passed an empty multiset.
--   
--   Examples:
--   
--   <pre>
--   &gt;&gt;&gt; maxView $ fromList ['a', 'a', 'b', 'c']
--   Just ('c',fromOccurList [('a',2),('b',1)])
--   </pre>
maxView :: MultiSet a -> Maybe (a, MultiSet a)

-- | <i>O(log n)</i>. Retrieves the minimal element of the multiset, and
--   the set with that element removed. Returns <tt>Nothing</tt> when
--   passed an empty multiset.
--   
--   Examples:
--   
--   <pre>
--   &gt;&gt;&gt; minView $ fromList ['a', 'a', 'b', 'c']
--   Just ('a',fromOccurList [('a',1),('b',1),('c',1)])
--   </pre>
minView :: MultiSet a -> Maybe (a, MultiSet a)

-- | <i>O(t)</i>. The elements of a multiset.
elems :: MultiSet a -> [a]

-- | <i>O(n)</i>. The distinct elements of a multiset, each element occurs
--   only once in the list.
--   
--   <pre>
--   distinctElems = map fst . toOccurList
--   </pre>
distinctElems :: MultiSet a -> [a]

-- | <i>O(t)</i>. Convert the multiset to a list of elements.
toList :: MultiSet a -> [a]

-- | <i>O(t*log t)</i>. Create a multiset from a list of elements.
fromList :: Ord a => [a] -> MultiSet a

-- | <i>O(t)</i>. Convert the multiset to an ascending list of elements.
toAscList :: MultiSet a -> [a]

-- | <i>O(t)</i>. Build a multiset from an ascending list in linear time.
--   <i>The precondition (input list is ascending) is not checked.</i>
fromAscList :: Eq a => [a] -> MultiSet a

-- | <i>O(n)</i>. Build a multiset from an ascending list of distinct
--   elements in linear time. <i>The precondition (input list is strictly
--   ascending) is not checked.</i>
fromDistinctAscList :: [a] -> MultiSet a

-- | <i>O(n)</i>. Convert the multiset to a list of element/occurrence
--   pairs.
toOccurList :: MultiSet a -> [(a, Occur)]

-- | <i>O(n)</i>. Convert the multiset to an ascending list of
--   element/occurrence pairs.
toAscOccurList :: MultiSet a -> [(a, Occur)]

-- | <i>O(n*log n)</i>. Create a multiset from a list of element/occurrence
--   pairs. Occurrences must be positive. <i>The precondition (all
--   occurrences &gt; 0) is not checked.</i>
fromOccurList :: Ord a => [(a, Occur)] -> MultiSet a

-- | <i>O(n)</i>. Build a multiset from an ascending list of
--   element/occurrence pairs in linear time. Occurrences must be positive.
--   <i>The precondition (input list is ascending, all occurrences &gt; 0)
--   is not checked.</i>
fromAscOccurList :: Eq a => [(a, Occur)] -> MultiSet a

-- | <i>O(n)</i>. Build a multiset from an ascending list of
--   elements/occurrence pairs where each elements appears only once.
--   Occurrences must be positive. <i>The precondition (input list is
--   strictly ascending, all occurrences &gt; 0) is not checked.</i>
fromDistinctAscOccurList :: [(a, Occur)] -> MultiSet a

-- | <i>O(1)</i>. Convert a multiset to a <a>Map</a> from elements to
--   number of occurrences.
toMap :: MultiSet a -> Map a Occur

-- | <i>O(n)</i>. Convert a <a>Map</a> from elements to occurrences to a
--   multiset.
fromMap :: Map a Occur -> MultiSet a

-- | <i>O(1)</i>. Convert a <a>Map</a> from elements to occurrences to a
--   multiset. Assumes that the <a>Map</a> contains only values larger than
--   zero. <i>The precondition (all elements &gt; 0) is not checked.</i>
fromOccurMap :: Map a Occur -> MultiSet a

-- | <i>O(n)</i>. Convert a multiset to a <a>Set</a>, removing duplicates.
toSet :: MultiSet a -> Set a

-- | <i>O(n)</i>. Convert a <a>Set</a> to a multiset.
fromSet :: Set a -> MultiSet a

-- | <i>O(n)</i>. Show the tree that implements the set. The tree is shown
--   in a compressed, hanging format.
showTree :: Show a => MultiSet a -> String

-- | <i>O(n)</i>. The expression (<tt>showTreeWith hang wide map</tt>)
--   shows the tree that implements the set. If <tt>hang</tt> is
--   <tt>True</tt>, a <i>hanging</i> tree is shown otherwise a rotated tree
--   is shown. If <tt>wide</tt> is <a>True</a>, an extra wide version is
--   shown.
--   
--   <pre>
--   Set&gt; putStrLn $ showTreeWith True False $ fromDistinctAscList [1,1,2,3,4,5]
--   (1*) 4
--   +--(1*) 2
--   |  +--(2*) 1
--   |  +--(1*) 3
--   +--(1*) 5
--   
--   Set&gt; putStrLn $ showTreeWith True True $ fromDistinctAscList [1,1,2,3,4,5]
--   (1*) 4
--   |
--   +--(1*) 2
--   |  |
--   |  +--(2*) 1
--   |  |
--   |  +--(1*) 3
--   |
--   +--(1*) 5
--   
--   Set&gt; putStrLn $ showTreeWith False True $ fromDistinctAscList [1,1,2,3,4,5]
--   +--(1*) 5
--   |
--   (1*) 4
--   |
--   |  +--(1*) 3
--   |  |
--   +--(1*) 2
--      |
--      +--(2*) 1
--   </pre>
showTreeWith :: Show a => Bool -> Bool -> MultiSet a -> String

-- | <i>O(n)</i>. 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
--   <a>Prelude</a> names, this module is usually imported
--   <tt>qualified</tt>, e.g.
--   
--   <pre>
--   import Data.IntMultiSet (IntMultiSet)
--   import qualified Data.IntMultiSet as IntMultiSet
--   </pre>
--   
--   The implementation of <a>IntMultiSet</a> is based on the
--   <a>Data.IntMap</a> module.
--   
--   Many operations have a worst-case complexity of <i>O(min(n,W))</i>.
--   This means that the operation can become linear in the number of
--   elements with a maximum of <i>W</i> -- the number of bits in an
--   <a>Int</a> (32 or 64). Here <i>n</i> refers to the number of distinct
--   elements, <i>t</i> 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

-- | <i>O(n+m)</i>. See <a>difference</a>.
(\\) :: IntMultiSet -> IntMultiSet -> IntMultiSet
infixl 9 \\

-- | <i>O(1)</i>. Is this the empty multiset?
null :: IntMultiSet -> Bool

-- | <i>O(n)</i>. The number of elements in the multiset.
size :: IntMultiSet -> Int

-- | <i>O(1)</i>. The number of distinct elements in the multiset.
distinctSize :: IntMultiSet -> Int

-- | <i>O(min(n,W))</i>. Is the element in the multiset?
member :: Key -> IntMultiSet -> Bool

-- | <i>O(min(n,W))</i>. Is the element not in the multiset?
notMember :: Key -> IntMultiSet -> Bool

-- | <i>O(min(n,W))</i>. The number of occurrences of an element in a
--   multiset.
occur :: Key -> IntMultiSet -> Int

-- | <i>O(n+m)</i>. Is this a subset? <tt>(s1 `isSubsetOf` s2)</tt> tells
--   whether <tt>s1</tt> is a subset of <tt>s2</tt>.
isSubsetOf :: IntMultiSet -> IntMultiSet -> Bool

-- | <i>O(n+m)</i>. Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: IntMultiSet -> IntMultiSet -> Bool

-- | <i>O(1)</i>. The empty mutli set.
empty :: IntMultiSet

-- | <i>O(1)</i>. Create a singleton mutli set.
singleton :: Key -> IntMultiSet

-- | <i>O(min(n,W))</i>. Insert an element in a multiset.
insert :: Key -> IntMultiSet -> IntMultiSet

-- | <i>O(min(n,W))</i>. Insert an element in a multiset a given number of
--   times.
--   
--   Negative numbers remove occurrences of the given element.
insertMany :: Key -> Occur -> IntMultiSet -> IntMultiSet

-- | <i>O(min(n,W))</i>. Delete a single element from a multiset.
delete :: Key -> IntMultiSet -> IntMultiSet

-- | <i>O(min(n,W))</i>. Delete an element from a multiset a given number
--   of times.
--   
--   Negative numbers add occurrences of the given element.
deleteMany :: Key -> Occur -> IntMultiSet -> IntMultiSet

-- | <i>O(min(n,W))</i>. Delete all occurrences of an element from a
--   multiset.
deleteAll :: Key -> IntMultiSet -> IntMultiSet

-- | <i>O(n+m)</i>. The union of two multisets. The union adds the
--   occurrences together.
--   
--   The implementation uses the efficient <i>hedge-union</i> algorithm.
--   Hedge-union is more efficient on (bigset <a>union</a> smallset).
union :: IntMultiSet -> IntMultiSet -> IntMultiSet

-- | The union of a list of multisets: (<tt><a>unions</a> == <a>foldl</a>
--   <a>union</a> <a>empty</a></tt>).
unions :: [IntMultiSet] -> IntMultiSet

-- | <i>O(n+m)</i>. 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 <i>hedge-union</i> algorithm.
--   Hedge-union is more efficient on (bigset <a>union</a> smallset).
maxUnion :: IntMultiSet -> IntMultiSet -> IntMultiSet

-- | <i>O(n+m)</i>. Difference of two multisets. The implementation uses an
--   efficient <i>hedge</i> algorithm comparable with <i>hedge-union</i>.
difference :: IntMultiSet -> IntMultiSet -> IntMultiSet

-- | <i>O(n+m)</i>. The intersection of two multisets.
--   
--   prints <tt>(fromList [A],fromList [B])</tt>.
intersection :: IntMultiSet -> IntMultiSet -> IntMultiSet

-- | <i>O(n)</i>. Filter all elements that satisfy the predicate.
filter :: (Key -> Bool) -> IntMultiSet -> IntMultiSet

-- | <i>O(n)</i>. 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 <a>split</a>.
partition :: (Key -> Bool) -> IntMultiSet -> (IntMultiSet, IntMultiSet)

-- | <i>O(log n)</i>. The expression (<tt><a>split</a> x set</tt>) is a
--   pair <tt>(set1,set2)</tt> where all elements in <tt>set1</tt> are
--   lower than <tt>x</tt> and all elements in <tt>set2</tt> larger than
--   <tt>x</tt>. <tt>x</tt> is not found in neither <tt>set1</tt> nor
--   <tt>set2</tt>.
split :: Int -> IntMultiSet -> (IntMultiSet, IntMultiSet)

-- | <i>O(log n)</i>. Performs a <a>split</a> but also returns the number
--   of occurrences of the pivot element in the original set.
splitOccur :: Int -> IntMultiSet -> (IntMultiSet, Int, IntMultiSet)

-- | <i>O(n*log n)</i>. <tt><a>map</a> f s</tt> is the multiset obtained by
--   applying <tt>f</tt> to each element of <tt>s</tt>.
map :: (Key -> Key) -> IntMultiSet -> IntMultiSet

-- | <i>O(n)</i>. The
--   
--   <tt><a>mapMonotonic</a> f s == <a>map</a> f s</tt>, but works only
--   when <tt>f</tt> is strictly monotonic. <i>The precondition is not
--   checked.</i> Semi-formally, we have:
--   
--   <pre>
--   and [x &lt; y ==&gt; f x &lt; f y | x &lt;- ls, y &lt;- ls]
--                       ==&gt; mapMonotonic f s == map f s
--       where ls = toList s
--   </pre>
mapMonotonic :: (Key -> Key) -> IntMultiSet -> IntMultiSet

-- | <i>O(n)</i>. Map and collect the <a>Just</a> results.
mapMaybe :: (Key -> Maybe Key) -> IntMultiSet -> IntMultiSet

-- | <i>O(n)</i>. Map and separate the <a>Left</a> and <a>Right</a>
--   results.
mapEither :: (Key -> Either Key Key) -> IntMultiSet -> (IntMultiSet, IntMultiSet)

-- | <i>O(n)</i>. Apply a function to each element, and take the union of
--   the results
concatMap :: (Key -> [Key]) -> IntMultiSet -> IntMultiSet

-- | <i>O(n)</i>. Apply a function to each element, and take the union of
--   the results
unionsMap :: (Key -> IntMultiSet) -> IntMultiSet -> IntMultiSet

-- | <i>O(n)</i>. The monad bind operation, (&gt;&gt;=), for multisets.
bind :: IntMultiSet -> (Key -> IntMultiSet) -> IntMultiSet

-- | <i>O(n)</i>. The monad join operation for multisets.
join :: MultiSet IntMultiSet -> IntMultiSet

-- | <i>O(t)</i>. Fold over the elements of a multiset in an unspecified
--   order.
fold :: (Key -> b -> b) -> b -> IntMultiSet -> b

-- | <i>O(n)</i>. Fold over the elements of a multiset with their
--   occurrences.
foldOccur :: (Key -> Occur -> b -> b) -> b -> IntMultiSet -> b

-- | <i>O(log n)</i>. The minimal element of a multiset.
findMin :: IntMultiSet -> Key

-- | <i>O(log n)</i>. The maximal element of a multiset.
findMax :: IntMultiSet -> Key

-- | <i>O(log n)</i>. Delete the minimal element.
deleteMin :: IntMultiSet -> IntMultiSet

-- | <i>O(log n)</i>. Delete the maximal element.
deleteMax :: IntMultiSet -> IntMultiSet

-- | <i>O(log n)</i>. Delete all occurrences of the minimal element.
deleteMinAll :: IntMultiSet -> IntMultiSet

-- | <i>O(log n)</i>. Delete all occurrences of the maximal element.
deleteMaxAll :: IntMultiSet -> IntMultiSet

-- | <i>O(log n)</i>. Delete and find the minimal element.
--   
--   <pre>
--   deleteFindMin set = (findMin set, deleteMin set)
--   </pre>
deleteFindMin :: IntMultiSet -> (Key, IntMultiSet)

-- | <i>O(log n)</i>. Delete and find the maximal element.
--   
--   <pre>
--   deleteFindMax set = (findMax set, deleteMax set)
--   </pre>
deleteFindMax :: IntMultiSet -> (Key, IntMultiSet)

-- | <i>O(log n)</i>. Retrieves the maximal element of the multiset, and
--   the set stripped from that element <tt>fail</tt>s (in the monad) when
--   passed an empty multiset.
--   
--   Examples:
--   
--   <pre>
--   &gt;&gt;&gt; maxView $ fromList [100, 100, 200, 300]
--   Just (300,fromOccurList [(100,2),(200,1)])
--   </pre>
maxView :: IntMultiSet -> Maybe (Key, IntMultiSet)

-- | <i>O(log n)</i>. Retrieves the minimal element of the multiset, and
--   the set stripped from that element Returns <tt>Nothing</tt> when
--   passed an empty multiset.
--   
--   Examples:
--   
--   <pre>
--   &gt;&gt;&gt; minView $ fromList [100, 100, 200, 300]
--   Just (100,fromOccurList [(100,1),(200,1),(300,1)])
--   </pre>
minView :: IntMultiSet -> Maybe (Key, IntMultiSet)

-- | <i>O(t)</i>. The elements of a multiset.
elems :: IntMultiSet -> [Key]

-- | <i>O(n)</i>. The distinct elements of a multiset, each element occurs
--   only once in the list.
--   
--   <pre>
--   distinctElems = map fst . toOccurList
--   </pre>
distinctElems :: IntMultiSet -> [Key]

-- | <i>O(t)</i>. Convert the multiset to a list of elements.
toList :: IntMultiSet -> [Key]

-- | <i>O(t*min(n,W))</i>. Create a multiset from a list of elements.
fromList :: [Int] -> IntMultiSet

-- | <i>O(t)</i>. Convert the multiset to an ascending list of elements.
toAscList :: IntMultiSet -> [Key]

-- | <i>O(t)</i>. Build a multiset from an ascending list in linear time.
--   <i>The precondition (input list is ascending) is not checked.</i>
fromAscList :: [Int] -> IntMultiSet

-- | <i>O(n)</i>. Build a multiset from an ascending list of distinct
--   elements in linear time. <i>The precondition (input list is strictly
--   ascending) is not checked.</i>
fromDistinctAscList :: [Int] -> IntMultiSet

-- | <i>O(n)</i>. Convert the multiset to a list of element/occurrence
--   pairs.
toOccurList :: IntMultiSet -> [(Int, Int)]

-- | <i>O(n)</i>. Convert the multiset to an ascending list of
--   element/occurrence pairs.
toAscOccurList :: IntMultiSet -> [(Int, Int)]

-- | <i>O(n*min(n,W))</i>. Create a multiset from a list of
--   element/occurrence pairs. Occurrences must be positive. <i>The
--   precondition (all occurrences &gt; 0) is not checked.</i>
fromOccurList :: [(Int, Int)] -> IntMultiSet

-- | <i>O(n)</i>. Build a multiset from an ascending list of
--   element/occurrence pairs in linear time. Occurrences must be positive.
--   <i>The precondition (input list is ascending, all occurrences &gt; 0)
--   is not checked.</i>
fromAscOccurList :: [(Int, Int)] -> IntMultiSet

-- | <i>O(n)</i>. Build a multiset from an ascending list of
--   elements/occurrence pairs where each elements appears only once.
--   Occurrences must be positive. <i>The precondition (input list is
--   strictly ascending, all occurrences &gt; 0) is not checked.</i>
fromDistinctAscOccurList :: [(Int, Int)] -> IntMultiSet

-- | <i>O(1)</i>. Convert a multiset to an <a>IntMap</a> from elements to
--   number of occurrences.
toMap :: IntMultiSet -> IntMap Int

-- | <i>O(n)</i>. Convert an <a>IntMap</a> from elements to occurrences to
--   a multiset.
fromMap :: IntMap Int -> IntMultiSet

-- | <i>O(1)</i>. Convert an <a>IntMap</a> from elements to occurrences to
--   a multiset. Assumes that the <a>IntMap</a> contains only values larger
--   than zero. <i>The precondition (all elements &gt; 0) is not
--   checked.</i>
fromOccurMap :: IntMap Int -> IntMultiSet

-- | <i>O(n)</i>. Convert a multiset to an <a>IntMap</a>, removing
--   duplicates.
toSet :: IntMultiSet -> IntSet

-- | <i>O(n)</i>. Convert an <a>IntMap</a> to a multiset.
fromSet :: IntSet -> IntMultiSet

-- | <i>O(n)</i>. Show the tree that implements the set. The tree is shown
--   in a compressed, hanging format.
showTree :: IntMultiSet -> String

-- | <i>O(n)</i>. The expression (<tt>showTreeWith hang wide map</tt>)
--   shows the tree that implements the set. If <tt>hang</tt> is
--   <tt>True</tt>, a <i>hanging</i> tree is shown otherwise a rotated tree
--   is shown. If <tt>wide</tt> is <a>True</a>, an extra wide version is
--   shown.
--   
--   <pre>
--   Set&gt; putStrLn $ showTreeWith True False $ fromDistinctAscList [1,1,2,3,4,5]
--   (1*) 4
--   +--(1*) 2
--   |  +--(2*) 1
--   |  +--(1*) 3
--   +--(1*) 5
--   
--   Set&gt; putStrLn $ showTreeWith True True $ fromDistinctAscList [1,1,2,3,4,5]
--   (1*) 4
--   |
--   +--(1*) 2
--   |  |
--   |  +--(2*) 1
--   |  |
--   |  +--(1*) 3
--   |
--   +--(1*) 5
--   
--   Set&gt; putStrLn $ showTreeWith False True $ fromDistinctAscList [1,1,2,3,4,5]
--   +--(1*) 5
--   |
--   (1*) 4
--   |
--   |  +--(1*) 3
--   |  |
--   +--(1*) 2
--      |
--      +--(2*) 1
--   </pre>
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
