AtCoder.Extra.IntSet

A dense, fast Int set implemented as a 64-ary tree that covers an interval \([0, n)\).

Example

Create an IntSet with capacity \(10\):

>>> import AtCoder.Extra.IntSet qualified as IS
>>> is <- IS.new @_ 10

insert, delete and other functions are available:

>>> IS.insert is 0
>>> IS.insert is 9
>>> IS.member is 9
True

>>> IS.delete is 0
True

>>> IS.size is
1

>>> IS.member is 1
False

>>> IS.lookupGT is 5
Just 9

Since: 1.1.0.0

IntSet

data IntSet s

A dense, fast Int set implemented as a 64-ary tree that covers an interval \([0, n)\).

Since: 1.1.0.0

Constructors

new :: PrimMonad m => Int -> m (IntSet (PrimState m))

\(O(n)\) Creates an IntSet for the interval \([0, n)\).

Since: 1.1.0.0

build :: PrimMonad m => Int -> Vector Int -> m (IntSet (PrimState m))

\(O(n + m \log n)\) Creates an IntSet for the interval \([0, n)\) with initial values.

Since: 1.1.0.0

Metadata

capacity :: IntSet s -> Int

\(O(1)\) Returns the capacity \(n\), where the interval \([0, n)\) is covered by the set.

Since: 1.1.0.0

size :: PrimMonad m => IntSet (PrimState m) -> m Int

\(O(1)\) Returns the number of elements in the set.

Since: 1.1.0.0

null :: PrimMonad m => IntSet (PrimState m) -> m Bool

\(O(1)\) Returns whether the set is empty.

Since: 1.1.0.0

Lookups

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

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

Since: 1.1.0.0

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

\(O(\log n)\) Tests whether \(k\) is not in the set.

Since: 1.1.0.0

Compartive lookups

lookupGE :: PrimMonad m => IntSet (PrimState m) -> Int -> m (Maybe Int)

\(O(\log n)\) Looks up the smallest key \(k\) such that \(k \ge k_0\).

Since: 1.1.0.0

lookupGT :: PrimMonad m => IntSet (PrimState m) -> Int -> m (Maybe Int)

\(O(\log n)\) Looks up the smallest key \(k\) such that \(k \gt k_0\).

Since: 1.1.0.0

lookupLE :: PrimMonad m => IntSet (PrimState m) -> Int -> m (Maybe Int)

\(O(\log n)\) Looks up the largest key \(k\) such that \(k \le k_0\).

Since: 1.1.0.0

lookupLT :: PrimMonad m => IntSet (PrimState m) -> Int -> m (Maybe Int)

\(O(\log n)\) Looks up the largest key \(k\) such that \(k \lt k_0\).

Since: 1.1.0.0

Max/Min lookups

lookupMin :: PrimMonad m => IntSet (PrimState m) -> m (Maybe Int)

\(O(\log n)\) Looks up the minimum key.

Since: 1.1.0.0

lookupMax :: PrimMonad m => IntSet (PrimState m) -> m (Maybe Int)

\(O(\log n)\) Looks up the maximum key.

Since: 1.1.0.0

Modifications

Insertions

insert :: (HasCallStack, PrimMonad m) => IntSet (PrimState m) -> Int -> m ()

\(O(\log n)\) Inserts a key \(k\) into the set. If an entry with the same key already exists, it is overwritten.

Since: 1.1.0.0

Deletions

delete :: PrimMonad m => IntSet (PrimState m) -> Int -> m Bool

\(O(\log n)\) Deletes a key \(k\) from the set. Does nothing if no such key exists. Returns whether the key existed.

Since: 1.1.0.0

delete_ :: PrimMonad m => IntSet (PrimState m) -> Int -> m ()

\(O(\log n)\) Deletes a key \(k\) from the set. Does nothing if no such key exists.

Since: 1.1.0.0

deleteMin :: PrimMonad m => IntSet (PrimState m) -> m (Maybe Int)

\(O(\log n)\) Deletes the minimum key from the set. Returns Nothing if the set is empty.

Since: 1.1.0.0

deleteMax :: PrimMonad m => IntSet (PrimState m) -> m (Maybe Int)

\(O(\log n)\) Deletes the maximum key from the set. Returns Nothing if the set is empty.

Since: 1.1.0.0

Conversions

keys :: PrimMonad m => IntSet (PrimState m) -> m (Vector Int)

\(O(n \log n)\) Enumerates the keys in the map.

Since: 1.1.0.0