- data MultiSet a
- (\\) :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
- isEmpty :: MultiSet a -> Bool
- size :: MultiSet a -> Int
- distinctSize :: MultiSet a -> Int
- member :: Ord a => a -> MultiSet a -> Bool
- occur :: Ord a => a -> MultiSet a -> Int
- subset :: Ord a => MultiSet a -> MultiSet a -> Bool
- properSubset :: Ord a => MultiSet a -> MultiSet a -> Bool
- empty :: MultiSet a
- single :: a -> MultiSet a
- insert :: Ord a => a -> MultiSet a -> MultiSet a
- insertMany :: Ord a => a -> Int -> MultiSet a -> MultiSet a
- delete :: Ord a => a -> MultiSet a -> MultiSet a
- deleteAll :: Ord a => a -> MultiSet a -> MultiSet a
- union :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
- difference :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
- intersection :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
- unions :: Ord a => [MultiSet a] -> MultiSet a
- filter :: Ord a => (a -> Bool) -> MultiSet a -> MultiSet a
- partition :: Ord a => (a -> Bool) -> MultiSet a -> (MultiSet a, MultiSet a)
- fold :: (a -> b -> b) -> b -> MultiSet a -> b
- foldOccur :: (a -> Int -> b -> b) -> b -> MultiSet a -> b
- findMin :: MultiSet a -> a
- findMax :: MultiSet a -> a
- deleteMin :: MultiSet a -> MultiSet a
- deleteMax :: MultiSet a -> MultiSet a
- deleteMinAll :: MultiSet a -> MultiSet a
- deleteMaxAll :: MultiSet a -> MultiSet a
- elems :: MultiSet a -> [a]
- toList :: MultiSet a -> [a]
- fromList :: Ord a => [a] -> MultiSet a
- toAscList :: MultiSet a -> [a]
- fromAscList :: Eq a => [a] -> MultiSet a
- fromDistinctAscList :: [a] -> MultiSet a
- toOccurList :: MultiSet a -> [(a, Int)]
- toAscOccurList :: MultiSet a -> [(a, Int)]
- fromOccurList :: Ord a => [(a, Int)] -> MultiSet a
- fromAscOccurList :: Ord a => [(a, Int)] -> MultiSet a
- toMap :: MultiSet a -> Map a Int
- fromMap :: Ord a => Map a Int -> MultiSet a
- fromOccurMap :: Map a Int -> MultiSet a
- showTree :: Show a => MultiSet a -> String
- showTreeWith :: Show a => Bool -> Bool -> MultiSet a -> String
- valid :: Ord a => MultiSet a -> Bool
MultiSet type
Operators
Query
distinctSize :: MultiSet a -> IntSource
O(1). Returns the number of distinct elements in the multi set, ie. (distinctSize mset == Set.size (
).
toSet
mset)
occur :: Ord a => a -> MultiSet a -> IntSource
O(log n). The number of occurrences of an element in the multi set.
properSubset :: Ord a => MultiSet a -> MultiSet a -> BoolSource
O(n+m). Is this a proper subset? (ie. a subset and not equal)
Construction
insertMany :: Ord a => a -> Int -> MultiSet a -> MultiSet aSource
O(min(n,W)). The expression (insertMany x count mset
)
inserts count
instances of x
in the multi set mset
.
deleteAll :: Ord a => a -> MultiSet a -> MultiSet aSource
O(log n). Delete all occurrences of an element.
Combine
union :: Ord a => MultiSet a -> MultiSet a -> MultiSet aSource
O(n+m). Union of two multisets. The union adds the elements together.
MultiSet\> union (fromList [1,1,2]) (fromList [1,2,2,3]) {1,1,1,2,2,2,3}
difference :: Ord a => MultiSet a -> MultiSet a -> MultiSet aSource
O(n+m). Difference between two multisets.
MultiSet\> difference (fromList [1,1,2]) (fromList [1,2,2,3]) {1}
intersection :: Ord a => MultiSet a -> MultiSet a -> MultiSet aSource
O(n+m). Intersection of two multisets.
MultiSet\> intersection (fromList [1,1,2]) (fromList [1,2,2,3]) {1,2}
Filter
filter :: Ord a => (a -> Bool) -> MultiSet a -> MultiSet aSource
O(n). Filter all elements that satisfy some predicate.
partition :: Ord a => (a -> Bool) -> MultiSet a -> (MultiSet a, MultiSet a)Source
O(n). Partition the multi set according to some predicate.
Fold
foldOccur :: (a -> Int -> b -> b) -> b -> MultiSet a -> bSource
O(n). Fold over all occurrences of an element at once.
Min/Max
deleteMinAll :: MultiSet a -> MultiSet aSource
O(log n). Delete all occurrences of the minimal element.
deleteMaxAll :: MultiSet a -> MultiSet aSource
O(log n). Delete all occurrences of the maximal element.
Conversion
List
Ordered list
fromAscList :: Eq a => [a] -> MultiSet aSource
O(n). Create a multi set from an ascending list in linear time.
fromDistinctAscList :: [a] -> MultiSet aSource
O(n). Create a multi set from an ascending list of distinct elements in linear time.
Occurrence lists
toOccurList :: MultiSet a -> [(a, Int)]Source
O(n). Create a list of element/occurrence pairs.
toAscOccurList :: MultiSet a -> [(a, Int)]Source
O(n). Create an ascending list of element/occurrence pairs.
fromOccurList :: Ord a => [(a, Int)] -> MultiSet aSource
O(n*log n). Create a multi set from a list of element/occurrence pairs.
fromAscOccurList :: Ord a => [(a, Int)] -> MultiSet aSource
O(n). Create a multi set from an ascending list of element/occurrence pairs.
Map
toMap :: MultiSet a -> Map a IntSource
O(1). Convert to a Map.Map
from elements to number of occurrences.
fromMap :: Ord a => Map a Int -> MultiSet aSource
O(n). Convert a Map.Map
from elements to occurrences into a multi set.
fromOccurMap :: Map a Int -> MultiSet aSource
O(1). Convert a Map.Map
from elements to occurrences into a multi set.
Assumes that the Map.Map
contains only elements that occur at least once.
Debugging
showTree :: Show a => MultiSet a -> StringSource
O(n). Show the tree structure that implements the MultiSet
. The tree
is shown as a compressed and hanging.