AtCoder.Extra.MultiSet

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

Invariant

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

Capacity limitation

The maximum number of distinct keys that can be inserted is fixed at \(n\), even if some keys are deleted. This is due to the limitation of the internal HashMap.

Example

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

MultiSet

data MultiSet s

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

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

Since: 1.1.0.0

Metadata

capacity :: MultiSet s -> Int

\(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

\(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)

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

Since: 1.1.0.0

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

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

Since: 1.1.0.0

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

\(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 ()

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

Since: 1.1.0.0

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

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

Since: 1.1.0.0

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

\(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 ()

\(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 ()

\(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 ()

\(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)

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

Since: 1.1.0.0

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

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

Since: 1.1.0.0

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

\(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)

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

Since: 1.1.0.0

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

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

Since: 1.1.0.0

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

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

Since: 1.1.0.0