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

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