MultiSet.Int

IntMultiSet

data IntMultiSet

A multiset of integers. The same value can occur multiple times.

Instances

Eq IntMultiSet

Defined in Data.IntMultiSet

Methods

(==) :: IntMultiSet -> IntMultiSet -> Bool

(/=) :: IntMultiSet -> IntMultiSet -> Bool

Data IntMultiSet

Defined in Data.IntMultiSet

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> IntMultiSet -> c IntMultiSet

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c IntMultiSet

toConstr :: IntMultiSet -> Constr

dataTypeOf :: IntMultiSet -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c IntMultiSet)

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c IntMultiSet)

gmapT :: (forall b. Data b => b -> b) -> IntMultiSet -> IntMultiSet

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> IntMultiSet -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> IntMultiSet -> r

gmapQ :: (forall d. Data d => d -> u) -> IntMultiSet -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> IntMultiSet -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> IntMultiSet -> m IntMultiSet

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> IntMultiSet -> m IntMultiSet

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> IntMultiSet -> m IntMultiSet

Ord IntMultiSet

Defined in Data.IntMultiSet

Methods

compare :: IntMultiSet -> IntMultiSet -> Ordering

(<) :: IntMultiSet -> IntMultiSet -> Bool

(<=) :: IntMultiSet -> IntMultiSet -> Bool

(>) :: IntMultiSet -> IntMultiSet -> Bool

(>=) :: IntMultiSet -> IntMultiSet -> Bool

max :: IntMultiSet -> IntMultiSet -> IntMultiSet

min :: IntMultiSet -> IntMultiSet -> IntMultiSet

Read IntMultiSet

Defined in Data.IntMultiSet

Methods

readsPrec :: Int -> ReadS IntMultiSet

readList :: ReadS [IntMultiSet]

readPrec :: ReadPrec IntMultiSet

readListPrec :: ReadPrec [IntMultiSet]

Show IntMultiSet

Defined in Data.IntMultiSet

Methods

showsPrec :: Int -> IntMultiSet -> ShowS

show :: IntMultiSet -> String

showList :: [IntMultiSet] -> ShowS

Semigroup IntMultiSet

Defined in Data.IntMultiSet

Methods

(<>) :: IntMultiSet -> IntMultiSet -> IntMultiSet

sconcat :: NonEmpty IntMultiSet -> IntMultiSet

stimes :: Integral b => b -> IntMultiSet -> IntMultiSet

Monoid IntMultiSet

Defined in Data.IntMultiSet

Methods

mempty :: IntMultiSet

mappend :: IntMultiSet -> IntMultiSet -> IntMultiSet

mconcat :: [IntMultiSet] -> IntMultiSet

NFData IntMultiSet

Defined in Data.IntMultiSet

Methods

rnf :: IntMultiSet -> ()

type Key = Int

Key type for IntMultiSet

null :: IntMultiSet -> Bool

O(1). Is this the empty multiset?

size :: IntMultiSet -> Int

O(n). The number of elements in the multiset.

distinctSize :: IntMultiSet -> Int

O(1). The number of distinct elements in the multiset.

member :: Key -> IntMultiSet -> Bool

O(min(n,W)). Is the element in the multiset?

notMember :: Key -> IntMultiSet -> Bool

O(min(n,W)). Is the element not in the multiset?

occur :: Key -> IntMultiSet -> Int

O(min(n,W)). The number of occurrences of an element in a multiset.

isSubsetOf :: IntMultiSet -> IntMultiSet -> Bool

O(n+m). Is this a subset? (s1 `isSubsetOf` s2) tells whether s1 is a subset of s2.

isProperSubsetOf :: IntMultiSet -> IntMultiSet -> Bool

O(n+m). Is this a proper subset? (ie. a subset but not equal).

empty :: IntMultiSet

O(1). The empty mutli set.

singleton :: Key -> IntMultiSet

O(1). Create a singleton mutli set.

insert :: Key -> IntMultiSet -> IntMultiSet

O(min(n,W)). Insert an element in a multiset.

insertMany :: Key -> Occur -> 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.

delete :: Key -> IntMultiSet -> IntMultiSet

O(min(n,W)). Delete a single element from a multiset.

deleteMany :: Key -> Occur -> 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.

deleteAll :: Key -> IntMultiSet -> IntMultiSet

O(min(n,W)). Delete all occurrences of an element from a multiset.

union :: IntMultiSet -> 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).

unions :: [IntMultiSet] -> IntMultiSet

The union of a list of multisets: (unions == foldl union empty).

maxUnion :: IntMultiSet -> 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).

difference :: IntMultiSet -> IntMultiSet -> IntMultiSet

O(n+m). Difference of two multisets. The implementation uses an efficient hedge algorithm comparable with hedge-union.

intersection :: IntMultiSet -> IntMultiSet -> IntMultiSet

O(n+m). The intersection of two multisets.

prints (fromList [A],fromList [B]).

filter :: (Key -> Bool) -> IntMultiSet -> IntMultiSet

O(n). Filter all elements that satisfy the predicate.

partition :: (Key -> Bool) -> IntMultiSet -> (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.

split :: Int -> 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.

splitOccur :: Int -> IntMultiSet -> (IntMultiSet, Int, IntMultiSet)

O(log n). Performs a split but also returns the number of occurrences of the pivot element in the original set.

map :: (Key -> Key) -> IntMultiSet -> IntMultiSet

O(n*log n). map f s is the multiset obtained by applying f to each element of s.

mapMonotonic :: (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

mapMaybe :: (Key -> Maybe Key) -> IntMultiSet -> IntMultiSet

O(n). Map and collect the Just results.

mapEither :: (Key -> Either Key Key) -> IntMultiSet -> (IntMultiSet, IntMultiSet)

O(n). Map and separate the Left and Right 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). Apply a function to each element, and take the union of the results

bind :: IntMultiSet -> (Key -> IntMultiSet) -> IntMultiSet

O(n). The monad bind operation, (>>=), for multisets.

join :: MultiSet IntMultiSet -> IntMultiSet

O(n). The monad join operation for multisets.

fold :: (Key -> b -> b) -> b -> IntMultiSet -> b

O(t). Fold over the elements of a multiset in an unspecified order.

foldOccur :: (Key -> Occur -> b -> b) -> b -> IntMultiSet -> b

O(n). Fold over the elements of a multiset with their occurrences.

findMin :: IntMultiSet -> Key

O(log n). The minimal element of a multiset.

findMax :: IntMultiSet -> Key

O(log n). The maximal element of a multiset.

deleteMin :: IntMultiSet -> IntMultiSet

O(log n). Delete the minimal element.

deleteMax :: IntMultiSet -> IntMultiSet

O(log n). Delete the maximal element.

deleteMinAll :: IntMultiSet -> IntMultiSet

O(log n). Delete all occurrences of the minimal element.

deleteMaxAll :: IntMultiSet -> IntMultiSet

O(log n). Delete all occurrences of the maximal element.

deleteFindMin :: IntMultiSet -> (Key, IntMultiSet)

O(log n). Delete and find the minimal element.

deleteFindMin set = (findMin set, deleteMin set)

deleteFindMax :: IntMultiSet -> (Key, IntMultiSet)

O(log n). Delete and find the maximal element.

deleteFindMax set = (findMax set, deleteMax set)

maxView :: IntMultiSet -> Maybe (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)])

minView :: 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)])

elems :: IntMultiSet -> [Key]

O(t). The elements of a multiset.

distinctElems :: IntMultiSet -> [Key]

O(n). The distinct elements of a multiset, each element occurs only once in the list.

distinctElems = map fst . toOccurList

toList :: IntMultiSet -> [Key]

O(t). Convert the multiset to a list of elements.

toAscList :: IntMultiSet -> [Key]

O(t). Convert the multiset to an ascending list of elements.

toOccurList :: IntMultiSet -> [(Int, Int)]

O(n). Convert the multiset to a list of element/occurrence pairs.

toAscOccurList :: IntMultiSet -> [(Int, Int)]

O(n). Convert the multiset to an ascending list of element/occurrence pairs.

fromList :: [Int] -> IntMultiSet

O(t*min(n,W)). Create a multiset from a list of elements.

fromAscList :: [Int] -> IntMultiSet

O(t). Build a multiset from an ascending list in linear time. The precondition (input list is ascending) is not checked.

fromDistinctAscList :: [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.

fromOccurList :: [(Int, Int)] -> IntMultiSet

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.

fromAscOccurList :: [(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.

fromDistinctAscOccurList :: [(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.

toMap :: IntMultiSet -> IntMap Int

O(1). Convert a multiset to an IntMap from elements to number of occurrences.

fromMap :: IntMap Int -> IntMultiSet

O(n). Convert an IntMap from elements to occurrences to a multiset.

fromOccurMap :: 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.

toSet :: IntMultiSet -> IntSet

O(n). Convert a multiset to an IntMap, removing duplicates.

fromSet :: IntSet -> IntMultiSet

O(n). Convert an IntMap to a multiset.