Safe Haskell	None
Language	GHC2021

Algorithm.Mo

Description

Mo's Algotrithm

Synopsis

moAlgorithm :: (Unbox a, PrimMonad m) => Int -> Int -> (a -> Int -> m a) -> (a -> Int -> m a) -> a -> Vector MoQuery -> m (Vector a)
moBlockSize :: Int -> Int -> Int
data MoState a = MoState !Int !Int !a
data MoQuery = MoQuery !Int !Int !Int
moSort :: Int -> Vector MoQuery -> Vector MoQuery
moEncode :: Int -> MoQuery -> Word64
moDecodeQueryIndex :: Word64 -> Int
encodeMoQuery :: MoQuery -> Word64
decodeMoQuery :: Word64 -> MoQuery

Documentation

moAlgorithm Source #

Arguments

:: (Unbox a, PrimMonad m)
=> Int	index size (N)
-> Int	query size (Q)
-> (a -> Int -> m a)	add
-> (a -> Int -> m a)	delete
-> a	initial value
-> Vector MoQuery	query [l, r)
-> m (Vector a)

O(N * sqrt Q)

moBlockSize :: Int -> Int -> Int Source #

N/sqrt Q

data MoState a Source #

Constructors

MoState
Fields !Int left !Int right !a

data MoQuery Source #

query for [l,r)

Constructors

MoQuery
Fields !Int left index (inclusive) !Int right index (exclusive) !Int query index

Instances

Instances details

Unbox MoQuery Source #
Instance details Defined in Algorithm.Mo
Vector Vector MoQuery Source #
Instance details Defined in Algorithm.Mo Methods basicUnsafeFreeze :: Mutable Vector s MoQuery -> ST s (Vector MoQuery) basicUnsafeThaw :: Vector MoQuery -> ST s (Mutable Vector s MoQuery) basicLength :: Vector MoQuery -> Int basicUnsafeSlice :: Int -> Int -> Vector MoQuery -> Vector MoQuery basicUnsafeIndexM :: Vector MoQuery -> Int -> Box MoQuery basicUnsafeCopy :: Mutable Vector s MoQuery -> Vector MoQuery -> ST s () elemseq :: Vector MoQuery -> MoQuery -> b -> b
MVector MVector MoQuery Source #
Instance details Defined in Algorithm.Mo Methods basicLength :: MVector s MoQuery -> Int basicUnsafeSlice :: Int -> Int -> MVector s MoQuery -> MVector s MoQuery basicOverlaps :: MVector s MoQuery -> MVector s MoQuery -> Bool basicUnsafeNew :: Int -> ST s (MVector s MoQuery) basicInitialize :: MVector s MoQuery -> ST s () basicUnsafeReplicate :: Int -> MoQuery -> ST s (MVector s MoQuery) basicUnsafeRead :: MVector s MoQuery -> Int -> ST s MoQuery basicUnsafeWrite :: MVector s MoQuery -> Int -> MoQuery -> ST s () basicClear :: MVector s MoQuery -> ST s () basicSet :: MVector s MoQuery -> MoQuery -> ST s () basicUnsafeCopy :: MVector s MoQuery -> MVector s MoQuery -> ST s () basicUnsafeMove :: MVector s MoQuery -> MVector s MoQuery -> ST s () basicUnsafeGrow :: MVector s MoQuery -> Int -> ST s (MVector s MoQuery)
IsoUnbox MoQuery Word64 Source #
Instance details Defined in Algorithm.Mo Methods toURepr :: MoQuery -> Word64 fromURepr :: Word64 -> MoQuery
newtype Vector MoQuery Source #
Instance details Defined in Algorithm.Mo newtype Vector MoQuery = V_MoQuery (Vector Word64)
newtype MVector s MoQuery Source #
Instance details Defined in Algorithm.Mo newtype MVector s MoQuery = MV_MoQuery (MVector s Word64)

moSort Source #

Arguments

:: Int	block size
-> Vector MoQuery
-> Vector MoQuery

radix sort

moEncode Source #

Arguments

:: Int	block size
-> MoQuery
-> Word64

query priority

moDecodeQueryIndex :: Word64 -> Int Source #

encodeMoQuery :: MoQuery -> Word64 Source #

decodeMoQuery :: Word64 -> MoQuery Source #