Safe Haskell	None
Language	GHC2021

AtCoder.Extra.Pool

Contents

Pool
Constructors
Metadata
Allocations
Read/write
Handle

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 :: (HasCallStack, 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
newtype Handle s = Handle {
- unHandle :: MVector s Index
}
newHandle :: PrimMonad m => Index -> m (Handle (PrimState m))
nullHandle :: PrimMonad m => Handle (PrimState m) -> m Bool
invalidateHandle :: PrimMonad m => Handle (PrimState m) -> m ()

Pool

data Pool s a Source #

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

Since: 1.2.0.0

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.

Since: 1.2.0.0

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 #	Since: 1.2.0.0
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 #	Since: 1.2.0.0
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 #	Since: 1.2.0.0
Instance details Defined in AtCoder.Extra.Pool
Vector Vector Index Source #	Since: 1.2.0.0
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 #	Since: 1.2.0.0
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 #	Since: 1.2.0.0
Instance details Defined in AtCoder.Extra.Pool newtype Vector Index = V_Index (Vector Index)
newtype MVector s Index Source #	Since: 1.2.0.0
Instance details Defined in AtCoder.Extra.Pool newtype MVector s Index = MV_Index (MVector s Index)

undefIndex :: Index Source #

Invalid, null Index.

Since: 1.2.0.0

nullIndex :: Index -> Bool Source #

Returns True for undefIndex.

Since: 1.2.0.0

Constructors

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

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

Since: 1.2.0.0

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

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

Since: 1.2.0.0

Metadata

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

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

Since: 1.2.0.0

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

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

Since: 1.2.0.0

Allocations

alloc :: (HasCallStack, 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.

Since: 1.2.0.0

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$

Since: 1.2.0.0

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$

Since: 1.2.0.0

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$

Since: 1.2.0.0

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

$O(1)$ Given a user function $f$ , modifies the $k$ -th value with it.

Constraints

$0 \le i \lt n$

Since: 1.2.0.0

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$

Since: 1.2.0.0

Handle

newtype Handle s Source #

Mutable Handle of an Index.

Since: 1.2.0.0

Constructors

Handle
Fields unHandle :: MVector s Index Since: 1.2.0.0

newHandle :: PrimMonad m => Index -> m (Handle (PrimState m)) Source #

$O(1)$ Creates a new Handle from a root node index.

Since: 1.2.0.0

nullHandle :: PrimMonad m => Handle (PrimState m) -> m Bool Source #

$O(1)$ Returns whether the handle represents null.

Since: 1.2.0.0

invalidateHandle :: PrimMonad m => Handle (PrimState m) -> m () Source #

$O(1)$ Invalidates a handle. Note that it does not change or free the pool item.

Since: 1.2.0.0

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