Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Extra.Pool

Contents

Pool
Constructors
Metadata
Allocations
Read/write

Description

Fixed-sized array for $O(1)$ allocation and $O(1)$ clearing after $O(n)$ construction.

Synopsis

data Pool s a = Pool {
- dataPool :: !(MVector s a)
- freePool :: !(Buffer s Index)
- nextPool :: !(MVector s Index)
}
newtype Index = Index {
- unIndex :: Int
}
undefIndex :: Index
nullIndex :: Index -> Bool
new :: (Unbox a, PrimMonad m) => Int -> m (Pool (PrimState m) a)
clear :: PrimMonad m => Pool (PrimState m) a -> m ()
capacity :: Unbox a => Pool s a -> Int
size :: (PrimMonad m, Unbox a) => Pool (PrimState m) a -> m Int
alloc :: (PrimMonad m, Unbox a) => Pool (PrimState m) a -> a -> m Index
free :: PrimMonad m => Pool (PrimState m) a -> Index -> m ()
read :: (PrimMonad m, Unbox a) => Pool (PrimState m) a -> Index -> m a
write :: (PrimMonad m, Unbox a) => Pool (PrimState m) a -> Index -> a -> m ()
modify :: (PrimMonad m, Unbox a) => Pool (PrimState m) a -> (a -> a) -> Index -> m ()
exchange :: (PrimMonad m, Unbox a) => Pool (PrimState m) a -> Index -> a -> m a

Pool

data Pool s a Source #

Fixed-sized array for $O(1)$ allocation and $O(1)$ clearing after $O(n)$ construction.

Constructors

Pool
Fields dataPool :: !(MVector s a) Data array. freePool :: !(Buffer s Index) Free slot indices pushed on free. nextPool :: !(MVector s Index) Next index when `freePool` is empty.

newtype Index Source #

Strongly typed index of pool items. User has to explicitly corece on raw index use, but it's ok as far as the end user don't see it.

Constructors

Index
Fields unIndex :: Int

Instances

Instances details

Show Index Source #
Instance details Defined in AtCoder.Extra.Pool Methods showsPrec :: Int -> Index -> ShowS # show :: Index -> String # showList :: [Index] -> ShowS #
Eq Index Source #
Instance details Defined in AtCoder.Extra.Pool Methods (==) :: Index -> Index -> Bool # (/=) :: Index -> Index -> Bool #
Ord Index Source #
Instance details Defined in AtCoder.Extra.Pool Methods compare :: Index -> Index -> Ordering # (<) :: Index -> Index -> Bool # (<=) :: Index -> Index -> Bool # (>) :: Index -> Index -> Bool # (>=) :: Index -> Index -> Bool # max :: Index -> Index -> Index # min :: Index -> Index -> Index #
Prim Index Source #
Instance details Defined in AtCoder.Extra.Pool Methods sizeOfType# :: Proxy Index -> Int# # sizeOf# :: Index -> Int# # alignmentOfType# :: Proxy Index -> Int# # alignment# :: Index -> Int# # indexByteArray# :: ByteArray# -> Int# -> Index # readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Index #) # writeByteArray# :: MutableByteArray# s -> Int# -> Index -> State# s -> State# s # setByteArray# :: MutableByteArray# s -> Int# -> Int# -> Index -> State# s -> State# s # indexOffAddr# :: Addr# -> Int# -> Index # readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, Index #) # writeOffAddr# :: Addr# -> Int# -> Index -> State# s -> State# s # setOffAddr# :: Addr# -> Int# -> Int# -> Index -> State# s -> State# s #
Unbox Index Source #
Instance details Defined in AtCoder.Extra.Pool
Vector Vector Index Source #
Instance details Defined in AtCoder.Extra.Pool Methods basicUnsafeFreeze :: Mutable Vector s Index -> ST s (Vector Index) basicUnsafeThaw :: Vector Index -> ST s (Mutable Vector s Index) basicLength :: Vector Index -> Int basicUnsafeSlice :: Int -> Int -> Vector Index -> Vector Index basicUnsafeIndexM :: Vector Index -> Int -> Box Index basicUnsafeCopy :: Mutable Vector s Index -> Vector Index -> ST s () elemseq :: Vector Index -> Index -> b -> b
MVector MVector Index Source #
Instance details Defined in AtCoder.Extra.Pool Methods basicLength :: MVector s Index -> Int basicUnsafeSlice :: Int -> Int -> MVector s Index -> MVector s Index basicOverlaps :: MVector s Index -> MVector s Index -> Bool basicUnsafeNew :: Int -> ST s (MVector s Index) basicInitialize :: MVector s Index -> ST s () basicUnsafeReplicate :: Int -> Index -> ST s (MVector s Index) basicUnsafeRead :: MVector s Index -> Int -> ST s Index basicUnsafeWrite :: MVector s Index -> Int -> Index -> ST s () basicClear :: MVector s Index -> ST s () basicSet :: MVector s Index -> Index -> ST s () basicUnsafeCopy :: MVector s Index -> MVector s Index -> ST s () basicUnsafeMove :: MVector s Index -> MVector s Index -> ST s () basicUnsafeGrow :: MVector s Index -> Int -> ST s (MVector s Index)
newtype Vector Index Source #
Instance details Defined in AtCoder.Extra.Pool newtype Vector Index = V_Index (Vector Index)
newtype MVector s Index Source #
Instance details Defined in AtCoder.Extra.Pool newtype MVector s Index = MV_Index (MVector s Index)

undefIndex :: Index Source #

Invalid, null Index.

nullIndex :: Index -> Bool Source #

Returns True for undefIndex.

Constructors

new :: (Unbox a, PrimMonad m) => Int -> m (Pool (PrimState m) a) Source #

$O(n)$ Creates a pool with the specified capacity.

clear :: PrimMonad m => Pool (PrimState m) a -> m () Source #

$O(1)$ Resets the pool to the initial state.

Metadata

capacity :: Unbox a => Pool s a -> Int Source #

$O(1)$ Returns the maximum number of elements the pool can store.

size :: (PrimMonad m, Unbox a) => Pool (PrimState m) a -> m Int Source #

$O(1)$ Returns the number of elements in the pool.

Allocations

alloc :: (PrimMonad m, Unbox a) => Pool (PrimState m) a -> a -> m Index Source #

$O(1)$ Allocates a new element.

Constraints

The number of elements must not exceed the capacity.

free :: PrimMonad m => Pool (PrimState m) a -> Index -> m () Source #

$O(1)$ Frees an element. Be sure to not free a deleted element.

Constraints

$0 \le i \lt n$

Read/write

read :: (PrimMonad m, Unbox a) => Pool (PrimState m) a -> Index -> m a Source #

$O(1)$ Reads the $k$ -th value.

Constraints

$0 \le i \lt n$

write :: (PrimMonad m, Unbox a) => Pool (PrimState m) a -> Index -> a -> m () Source #

$O(1)$ Writes to the $k$ -th value.

Constraints

$0 \le i \lt n$

modify :: (PrimMonad m, Unbox a) => Pool (PrimState m) a -> (a -> a) -> Index -> m () Source #

$O(1)$ Modifies the $k$ -th value.

Constraints

$0 \le i \lt n$

exchange :: (PrimMonad m, Unbox a) => Pool (PrimState m) a -> Index -> a -> m a Source #

$O(1)$ Exchanges the $k$ -th value.

Constraints

$0 \le i \lt n$

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result