AtCoder.Extra.IntMap

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

Example

Create an IntMap with capacity \(10\):

>>> import AtCoder.Extra.IntMap qualified as IM
>>> im <- IM.new @_ @Int 10

insert, delete, lookup and other functions are available:

>>> IM.insert im 0 100
>>> IM.insert im 9 101
>>> IM.delete im 0
True

>>> IM.size im
1

>>> IM.lookup im 9
Just 101

>>> IM.lookup im 1
Nothing

>>> IM.lookupGT im 5
Just (9,101)

Since: 1.1.0.0

IntMap

data IntMap s a

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

Since: 1.1.0.0

Constructors

new :: (PrimMonad m, Unbox a) => Int -> m (IntMap (PrimState m) a)

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

Since: 1.1.0.0

build :: (PrimMonad m, Unbox a) => Int -> Vector (Int, a) -> m (IntMap (PrimState m) a)

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

Since: 1.1.0.0

Metadata

capacity :: IntMap s a -> Int

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

Since: 1.1.0.0

size :: PrimMonad m => IntMap (PrimState m) a -> m Int

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

Since: 1.1.0.0

null :: PrimMonad m => IntMap (PrimState m) a -> m Bool

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

Since: 1.1.0.0

Lookups

lookup :: (PrimMonad m, Unbox a) => IntMap (PrimState m) a -> Int -> m (Maybe a)

\(O(\log n)\) Looks up the value for a key.

Since: 1.1.0.0

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

\(O(\log n)\) Tests whether a key \(k\) is in the map.

Since: 1.1.0.0

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

\(O(\log n)\) Tests whether a key \(k\) is not in the map.

Since: 1.1.0.0

Compartive lookups

lookupGE :: (PrimMonad m, Unbox a) => IntMap (PrimState m) a -> Int -> m (Maybe (Int, a))

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

Since: 1.1.0.0

lookupGT :: (PrimMonad m, Unbox a) => IntMap (PrimState m) a -> Int -> m (Maybe (Int, a))

\(O(\log n)\) Looks up the \((k, v)\) pair with the smallest \(k\) such that \(k \gt k_0\).

Since: 1.1.0.0

lookupLE :: (HasCallStack, PrimMonad m, Unbox a) => IntMap (PrimState m) a -> Int -> m (Maybe (Int, a))

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

Since: 1.1.0.0

lookupLT :: (PrimMonad m, Unbox a) => IntMap (PrimState m) a -> Int -> m (Maybe (Int, a))

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

Since: 1.1.0.0

Max/Min lookups

lookupMin :: (PrimMonad m, Unbox a) => IntMap (PrimState m) a -> m (Maybe (Int, a))

\(O(\log n)\) Looks up the \((k, v)\) pair with the minimum key \(k\).

Since: 1.1.0.0

lookupMax :: (PrimMonad m, Unbox a) => IntMap (PrimState m) a -> m (Maybe (Int, a))

\(O(\log n)\) Looks up the \((k, v)\) pair with the maximum key \(k\).

Since: 1.1.0.0

Modifications

Insertions

insert :: (HasCallStack, PrimMonad m, Unbox a) => IntMap (PrimState m) a -> Int -> a -> m ()

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

Since: 1.1.0.0

insertWith :: (HasCallStack, PrimMonad m, Unbox a) => IntMap (PrimState m) a -> (a -> a -> a) -> Int -> a -> m ()

\(O(\log n)\) Inserts a \((k, v)\) pair into the map. If an entry with the same key already exists, it overwritten with \(f(v_{\mathrm{new}}, v_{\mathrm{old}})\).

Since: 1.1.0.0

Updates

modify :: (HasCallStack, PrimMonad m, Unbox a) => IntMap (PrimState m) a -> (a -> a) -> Int -> m ()

\(O(\log n)\) Modifies the value associated with a key. If an entry with the same key already does not exist, nothing is performed.

Since: 1.1.0.0

modifyM :: (HasCallStack, PrimMonad m, Unbox a) => IntMap (PrimState m) a -> (a -> m a) -> Int -> m ()

\(O(\log n)\) Modifies the value associated with a key. If an entry with the same key already does not exist, nothing is performed.

Since: 1.1.0.0

Deletions

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

\(O(\log n)\) Deletes the \((k, v)\) pair with the key \(k\) from the map. Does nothing if no such key exists. Returns whether the key existed.

Since: 1.1.0.0

delete_ :: PrimMonad m => IntMap (PrimState m) a -> Int -> m ()

\(O(\log n)\) Deletes the \((k, v)\) pair with the key \(k\) from the map. Does nothing if no such key exists.

Since: 1.1.0.0

deleteMin :: (HasCallStack, PrimMonad m, Unbox a) => IntMap (PrimState m) a -> m (Maybe (Int, a))

\(O(\log n)\) Deletes the \((k, v)\) pair with the minimum key \(k\) in the map.

Since: 1.1.0.0

deleteMax :: (HasCallStack, PrimMonad m, Unbox a) => IntMap (PrimState m) a -> m (Maybe (Int, a))

\(O(\log n)\) Deletes the \((k, v)\) pair with maximum key \(k\) in the map.

Since: 1.1.0.0

Conversions

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

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

Since: 1.1.0.0

elems :: (PrimMonad m, Unbox a) => IntMap (PrimState m) a -> m (Vector a)

\(O(n \log n)\) Enumerates the elements (values) in the map.

Since: 1.1.0.0

assocs :: (PrimMonad m, Unbox a) => IntMap (PrimState m) a -> m (Vector (Int, a))

\(O(n \log n)\) Enumerates the key-value pairs in the map.

Since: 1.1.0.0