| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.DenseIntMap
Description
Dense int map or a 64-ary tree that covers [0, n).
https://github.com/maspypy/library/blob/main/ds/fastset.hpp
FIXME: too slow compared to the original implementation.
Synopsis
- data DenseIntMap s a = DenseIntMap {
- setDIM :: !(DenseIntSet s)
- valDIM :: !(MVector s a)
- newDIM :: (Unbox a, PrimMonad m) => Int -> m (DenseIntMap (PrimState m) a)
- sizeDIM :: PrimMonad m => DenseIntMap (PrimState m) a -> m Int
- memberDIM :: PrimMonad m => DenseIntMap (PrimState m) a -> Int -> m Bool
- notMemberDIM :: PrimMonad m => DenseIntMap (PrimState m) a -> Int -> m Bool
- insertDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> a -> m ()
- deleteDIM :: PrimMonad m => DenseIntMap (PrimState m) a -> Int -> m ()
- lookupGEDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Maybe (Int, a))
- findGEDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Int, a)
- lookupGTDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Maybe (Int, a))
- findGTDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Int, a)
- lookupLEDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Maybe (Int, a))
- findLEDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Int, a)
- lookupLTDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Maybe (Int, a))
- findLTDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Int, a)
- lookupMinDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Maybe (Int, a))
- findMinDIM :: (Unbox a, HasCallStack, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Int, a)
- deleteFindMinDIM :: (Unbox a, HasCallStack, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Int, a)
- lookupMaxDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Maybe (Int, a))
- findMaxDIM :: (Unbox a, HasCallStack, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Int, a)
- deleteFindMaxDIM :: (Unbox a, HasCallStack, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Int, a)
- unsafeKeysDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Vector (Int, a))
Documentation
data DenseIntMap s a #
Dense int map or a 64-ary tree that covers [0, n).
Constructors
| DenseIntMap | |
Fields
| |
newDIM :: (Unbox a, PrimMonad m) => Int -> m (DenseIntMap (PrimState m) a) #
\(O(N \log N)\) Creates a new DenseIntMap that covers [0, n).
sizeDIM :: PrimMonad m => DenseIntMap (PrimState m) a -> m Int #
\(O(1)\) Returns the number of elements in the map.
memberDIM :: PrimMonad m => DenseIntMap (PrimState m) a -> Int -> m Bool #
\(O(\log N)\) Tests if k is in the map.
notMemberDIM :: PrimMonad m => DenseIntMap (PrimState m) a -> Int -> m Bool #
\(O(\log N)\) Tests if k is not in the map.
insertDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> a -> m () #
\(O(\log N)\) Inserts k to the set.
deleteDIM :: PrimMonad m => DenseIntMap (PrimState m) a -> Int -> m () #
\(O(\log N)\) Deletes k from the set.
GT / GE
lookupGEDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Maybe (Int, a)) #
\(O(\log N)\) Finds the smallest k' s.t. k' >= k in the set.
findGEDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Int, a) #
\(O(\log N)\)
lookupGTDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Maybe (Int, a)) #
\(O(\log N)\)
findGTDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Int, a) #
\(O(\log N)\)
LT / LE
lookupLEDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Maybe (Int, a)) #
\(O(\log N)\) Finds the biggest k' s.t. k' <= k in the set.
findLEDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Int, a) #
\(O(\log N)\)
lookupLTDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Maybe (Int, a)) #
\(O(\log N)\)
findLTDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> Int -> m (Int, a) #
\(O(\log N)\)
Min / Max
lookupMinDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Maybe (Int, a)) #
\(O(\log N)\)
findMinDIM :: (Unbox a, HasCallStack, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Int, a) #
\(O(\log N)\)
deleteFindMinDIM :: (Unbox a, HasCallStack, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Int, a) #
\(O(\log N)\)
lookupMaxDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Maybe (Int, a)) #
\(O(\log N)\)
findMaxDIM :: (Unbox a, HasCallStack, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Int, a) #
\(O(\log N)\)
deleteFindMaxDIM :: (Unbox a, HasCallStack, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Int, a) #
\(O(\log N)\)
unsafeKeysDIM :: (Unbox a, PrimMonad m) => DenseIntMap (PrimState m) a -> m (Vector (Int, a)) #
\(O(N)\)