Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Extra.MultiSet

Contents

MultiSet
Construtors
Metadata
Lookups
Modifications
Conversions
- Safe conversions
- Unsafe conversions

Description

A fast, mutable multiset for Int keys backed by a HashMap. Most operations are performed in $O(1)$ time, but in average.

Capacity limitation

Access to each key creates a new entry. Note that entries cannot be invalidated due to the internal implementation (called open addressing). If the hash map is full, access to a new key causes infinite loop .

Invariant

The count for each key must be non-negative. An exception is thrown if this invariant is violated on add or sub.

Example

Expand

Create a MultiSet with capacity $4$ :

>>> import AtCoder.Extra.MultiSet qualified as MS
>>> ms <- MS.new 4

inc and dec are the primary API:

>>> MS.inc ms 10
>>> MS.inc ms 10
>>> MS.lookup ms 10
Just 2

>>> MS.dec ms 10
>>> MS.lookup ms 10
Just 1

Entries with zero count are considered to be non-existing:

>>> MS.dec ms 10
>>> MS.member ms 10
False

>>> MS.lookup ms 10
Nothing

>>> MS.size ms
0

Creating a negative count results in an exception:

>>> MS.inc ms 11
>>> MS.sub ms 11 2
*** Exception: AtCoder.Extra.Multiset.subST: the count of `11` is becoming a negative value: `-1`
...

Decrementing a non-existing key does nothing and does not throw an exception:

>>> MS.dec ms 12

Misc:

>>> MS.insert ms 12 112
>>> MS.assocs ms
[(11,1),(12,112)]

Since: 1.1.0.0

Synopsis

data MultiSet s
new :: PrimMonad m => Int -> m (MultiSet (PrimState m))
capacity :: MultiSet s -> Int
size :: PrimMonad m => MultiSet (PrimState m) -> m Int
lookup :: PrimMonad m => MultiSet (PrimState m) -> Int -> m (Maybe Int)
member :: PrimMonad m => MultiSet (PrimState m) -> Int -> m Bool
notMember :: PrimMonad m => MultiSet (PrimState m) -> Int -> m Bool
inc :: (HasCallStack, PrimMonad m) => MultiSet (PrimState m) -> Int -> m ()
dec :: (HasCallStack, PrimMonad m) => MultiSet (PrimState m) -> Int -> m ()
add :: (HasCallStack, PrimMonad m) => MultiSet (PrimState m) -> Int -> Int -> m ()
sub :: (HasCallStack, PrimMonad m) => MultiSet (PrimState m) -> Int -> Int -> m ()
insert :: (HasCallStack, PrimMonad m) => MultiSet (PrimState m) -> Int -> Int -> m ()
delete :: (HasCallStack, PrimMonad m) => MultiSet (PrimState m) -> Int -> m ()
keys :: PrimMonad m => MultiSet (PrimState m) -> m (Vector Int)
elems :: PrimMonad m => MultiSet (PrimState m) -> m (Vector Int)
assocs :: PrimMonad m => MultiSet (PrimState m) -> m (Vector (Int, Int))
unsafeKeys :: PrimMonad m => MultiSet (PrimState m) -> m (Vector Int)
unsafeElems :: PrimMonad m => MultiSet (PrimState m) -> m (Vector Int)
unsafeAssocs :: PrimMonad m => MultiSet (PrimState m) -> m (Vector (Int, Int))

MultiSet

data MultiSet s Source #

A fast, mutable multiset for Int keys backed by a HashMap.

Since: 1.1.0.0

Construtors

new :: PrimMonad m => Int -> m (MultiSet (PrimState m)) Source #

$O(n)$ Creates a MultiSet with capacity $n$ .

Since: 1.1.0.0

Metadata

capacity :: MultiSet s -> Int Source #

$O(1)$ Returns the maximum number of distinct keys that can be inserted into the internal hash map.

Since: 1.1.0.0

size :: PrimMonad m => MultiSet (PrimState m) -> m Int Source #

$O(1)$ Returns the number of distinct keys with positive counts.

Since: 1.1.0.0

Lookups

lookup :: PrimMonad m => MultiSet (PrimState m) -> Int -> m (Maybe Int) Source #

$O(1)$ Looks up the count for a key.

Since: 1.1.0.0

member :: PrimMonad m => MultiSet (PrimState m) -> Int -> m Bool Source #

$O(1)$ Tests whether $k$ is in the set.

Since: 1.1.0.0

notMember :: PrimMonad m => MultiSet (PrimState m) -> Int -> m Bool Source #

$O(1)$ Tests whether $k$ is not in the set.

Since: 1.1.0.0

Modifications

inc :: (HasCallStack, PrimMonad m) => MultiSet (PrimState m) -> Int -> m () Source #

$O(1)$ Increments the count of a key.

Since: 1.1.0.0

dec :: (HasCallStack, PrimMonad m) => MultiSet (PrimState m) -> Int -> m () Source #

$O(1)$ Decrements the count of a key.

Since: 1.1.0.0

add :: (HasCallStack, PrimMonad m) => MultiSet (PrimState m) -> Int -> Int -> m () Source #

$O(1)$ Increments the count of a key $k$ by $c$ . If the key does not exist in the set, the $(k, c)$ pair is inserted. If $v$ is negative, it falls back to sub.

Since: 1.1.0.0

sub :: (HasCallStack, PrimMonad m) => MultiSet (PrimState m) -> Int -> Int -> m () Source #

$O(1)$ Decrements the count of a key $k$ by $c$ . If $c$ is negative, it falls back to add.

Since: 1.1.0.0

insert :: (HasCallStack, PrimMonad m) => MultiSet (PrimState m) -> Int -> Int -> m () Source #

$O(1)$ Inserts a key-count pair into the set. MultiSet is actually a count map.

Since: 1.1.0.0

delete :: (HasCallStack, PrimMonad m) => MultiSet (PrimState m) -> Int -> m () Source #

$O(1)$ Deletes a key. Note that it does not undo its insertion and does not increase the number of distinct keys that can be inserted into the internal hash map.

Since: 1.1.0.0

Conversions

Safe conversions

keys :: PrimMonad m => MultiSet (PrimState m) -> m (Vector Int) Source #

$O(n)$ Enumerates the keys in the set.

Since: 1.1.0.0

elems :: PrimMonad m => MultiSet (PrimState m) -> m (Vector Int) Source #

$O(n)$ Enumerates the counts in the set.

Since: 1.1.0.0

assocs :: PrimMonad m => MultiSet (PrimState m) -> m (Vector (Int, Int)) Source #

$O(n)$ Enumerates the key-count pairs in the set.

Since: 1.1.0.0

Unsafe conversions

unsafeKeys :: PrimMonad m => MultiSet (PrimState m) -> m (Vector Int) Source #

$O(n)$ Enumerates the keys in the set.

Since: 1.1.0.0

unsafeElems :: PrimMonad m => MultiSet (PrimState m) -> m (Vector Int) Source #

$O(n)$ Enumerates the counts in the set.

Since: 1.1.0.0

unsafeAssocs :: PrimMonad m => MultiSet (PrimState m) -> m (Vector (Int, Int)) Source #

$O(n)$ Enumerates the key-count pairs in the set.

Since: 1.1.0.0

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result