UU.DData.MultiSet

MultiSet type

data MultiSet a

A multi set of values a.

Instances

Eq a => Eq (MultiSet a)

Show a => Show (MultiSet a)

Operators

(\\) :: Ord a => MultiSet a -> MultiSet a -> MultiSet a

O(n+m). See difference.

Query

isEmpty :: MultiSet a -> Bool

O(1). Is the multi set empty?

size :: MultiSet a -> Int

O(n). The number of elements in the multi set.

distinctSize :: MultiSet a -> Int

O(1). Returns the number of distinct elements in the multi set, ie. (distinctSize mset == Set.size (toSet mset)).

member :: Ord a => a -> MultiSet a -> Bool

O(log n). Is the element in the multi set?

occur :: Ord a => a -> MultiSet a -> Int

O(log n). The number of occurrences of an element in the multi set.

subset :: Ord a => MultiSet a -> MultiSet a -> Bool

O(n+m). Is this a subset of the multi set?

properSubset :: Ord a => MultiSet a -> MultiSet a -> Bool

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

Construction

empty :: MultiSet a

O(1). Create an empty multi set.

single :: a -> MultiSet a

O(1). Create a singleton multi set.

insert :: Ord a => a -> MultiSet a -> MultiSet a

O(log n). Insert an element in the multi set.

insertMany :: Ord a => a -> Int -> MultiSet a -> MultiSet a

O(min(n,W)). The expression (insertMany x count mset) inserts count instances of x in the multi set mset.

delete :: Ord a => a -> MultiSet a -> MultiSet a

O(log n). Delete a single element.

deleteAll :: Ord a => a -> MultiSet a -> MultiSet a

O(log n). Delete all occurrences of an element.

Combine

union :: Ord a => MultiSet a -> MultiSet a -> MultiSet a

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 a

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 a

O(n+m). Intersection of two multisets.

 MultiSet\> intersection (fromList [1,1,2]) (fromList [1,2,2,3])
 {1,2}

unions :: Ord a => [MultiSet a] -> MultiSet a

The union of a list of multisets.

Filter

filter :: Ord a => (a -> Bool) -> MultiSet a -> MultiSet a

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

partition :: Ord a => (a -> Bool) -> MultiSet a -> (MultiSet a, MultiSet a)

O(n). Partition the multi set according to some predicate.

Fold

fold :: (a -> b -> b) -> b -> MultiSet a -> b

O(n). Fold over each element in the multi set.

foldOccur :: (a -> Int -> b -> b) -> b -> MultiSet a -> b

O(n). Fold over all occurrences of an element at once.

Min/Max

findMin :: MultiSet a -> a

O(log n). The minimal element of a multi set.

findMax :: MultiSet a -> a

O(log n). The maximal element of a multi set.

deleteMin :: MultiSet a -> MultiSet a

O(log n). Delete the minimal element.

deleteMax :: MultiSet a -> MultiSet a

O(log n). Delete the maximal element.

deleteMinAll :: MultiSet a -> MultiSet a

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

deleteMaxAll :: MultiSet a -> MultiSet a

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

Conversion

elems :: MultiSet a -> [a]

O(n). The list of elements.

List

toList :: MultiSet a -> [a]

O(n). Create a list with all elements.

fromList :: Ord a => [a] -> MultiSet a

O(n*log n). Create a multi set from a list of elements.

Ordered list

toAscList :: MultiSet a -> [a]

O(n). Create an ascending list of all elements.

fromAscList :: Eq a => [a] -> MultiSet a

O(n). Create a multi set from an ascending list in linear time.

fromDistinctAscList :: [a] -> MultiSet a

O(n). Create a multi set from an ascending list of distinct elements in linear time.

Occurrence lists

toOccurList :: MultiSet a -> [(a, Int)]

O(n). Create a list of element/occurrence pairs.

toAscOccurList :: MultiSet a -> [(a, Int)]

O(n). Create an ascending list of element/occurrence pairs.

fromOccurList :: Ord a => [(a, Int)] -> MultiSet a

O(n*log n). Create a multi set from a list of element/occurrence pairs.

fromAscOccurList :: Ord a => [(a, Int)] -> MultiSet a

O(n). Create a multi set from an ascending list of element/occurrence pairs.

Map

toMap :: MultiSet a -> Map a Int

O(1). Convert to a Map.Map from elements to number of occurrences.

fromMap :: Ord a => Map a Int -> MultiSet a

O(n). Convert a Map.Map from elements to occurrences into a multi set.

fromOccurMap :: Map a Int -> MultiSet a

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 -> String

O(n). Show the tree structure that implements the MultiSet. The tree is shown as a compressed and hanging.

showTreeWith :: Show a => Bool -> Bool -> MultiSet a -> String

O(n). The expression (showTreeWith hang wide map) shows the tree that implements the multi set. The tree is shown hanging when hang is True and otherwise as a rotated tree. When wide is True an extra wide version is shown.

valid :: Ord a => MultiSet a -> Bool

O(n). Is this a valid multi set?