toy-lib-0.1.0.0
Safe HaskellSafe-Inferred
LanguageHaskell2010

Data.DenseIntSet

Description

Dense int set 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

Documentation

wordDIS :: Int #

Dense int set or a W-ary tree where W = wordDIS.

data DenseIntSet s #

Dense int set or a 64-ary tree that covers [0, n). = (Internal) segments

The idea is very similar to hibitset, with top and bottom reversed.

[.][.][.][.][.][.][.][.] ..  Layer 0: dense bits
[..........][..........] ..  Layer 1: sparse (1/64)
[......................] ..  Layer 2: more sparse (1/64^2)

Constructors

DenseIntSet 

Fields

newDIS :: PrimMonad m => Int -> m (DenseIntSet (PrimState m)) #

\(O(N \log N)\) Creates a new DenseIntSet that covers [0, n).

validateKeyDIS :: HasCallStack => String -> DenseIntSet s -> Int -> () #

(Internal) Keys out of the range are reported as runtime error.

sizeDIS :: PrimMonad m => DenseIntSet (PrimState m) -> m Int #

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

memberDIS :: PrimMonad m => DenseIntSet (PrimState m) -> Int -> m Bool #

\(O(\log N)\) Tests if k is in the set.

notMemberDIS :: PrimMonad m => DenseIntSet (PrimState m) -> Int -> m Bool #

\(O(\log N)\) Tests if k is not in the set.

insertDIS :: PrimMonad m => DenseIntSet (PrimState m) -> Int -> m () #

\(O(\log N)\) Inserts k to the set.

deleteDIS :: PrimMonad m => DenseIntSet (PrimState m) -> Int -> m () #

\(O(\log N)\) Deletes k from the set.

GT / GE

lookupGEDIS :: PrimMonad m => DenseIntSet (PrimState m) -> Int -> m (Maybe Int) #

\(O(\log N)\) Finds the smallest k' s.t. k' >= k in the set.

findGEDIS :: PrimMonad m => DenseIntSet (PrimState m) -> Int -> m Int #

\(O(\log N)\)

lookupGTDIS :: PrimMonad m => DenseIntSet (PrimState m) -> Int -> m (Maybe Int) #

\(O(\log N)\)

findGTDIS :: PrimMonad m => DenseIntSet (PrimState m) -> Int -> m Int #

\(O(\log N)\)

LT / LE

lookupLEDIS :: PrimMonad m => DenseIntSet (PrimState m) -> Int -> m (Maybe Int) #

\(O(\log N)\) Finds the biggest k' s.t. k' <= k in the set.

findLEDIS :: PrimMonad m => DenseIntSet (PrimState m) -> Int -> m Int #

\(O(\log N)\)

lookupLTDIS :: PrimMonad m => DenseIntSet (PrimState m) -> Int -> m (Maybe Int) #

\(O(\log N)\)

findLTDIS :: PrimMonad m => DenseIntSet (PrimState m) -> Int -> m Int #

\(O(\log N)\)

Min / Max

lookupMinDIS :: PrimMonad m => DenseIntSet (PrimState m) -> m (Maybe Int) #

\(O(\log N)\) Not tested.

findMinDIS :: (HasCallStack, PrimMonad m) => DenseIntSet (PrimState m) -> m Int #

\(O(\log N)\) Not tested.

deleteFindMinMayDIS :: PrimMonad m => DenseIntSet (PrimState m) -> m (Maybe Int) #

\(O(\log N)\) Not tested.

deleteFindMinDIS :: (HasCallStack, PrimMonad m) => DenseIntSet (PrimState m) -> m Int #

\(O(\log N)\) Not tested.

lookupMaxDIS :: PrimMonad m => DenseIntSet (PrimState m) -> m (Maybe Int) #

\(O(\log N)\) Not tested.

findMaxDIS :: (HasCallStack, PrimMonad m) => DenseIntSet (PrimState m) -> m Int #

\(O(\log N)\) Not tested.

deleteFindMaxMayDIS :: PrimMonad m => DenseIntSet (PrimState m) -> m (Maybe Int) #

\(O(\log N)\) Not tested.

deleteFindMaxDIS :: (HasCallStack, PrimMonad m) => DenseIntSet (PrimState m) -> m Int #

\(O(\log N)\) Not tested.

unsafeKeysDIS :: PrimMonad m => DenseIntSet (PrimState m) -> m (Vector Int) #

\(O(N)\) Not tested.