ac-library-hs-1.2.2.0: Data structures and algorithms
Safe HaskellSafe-Inferred
LanguageGHC2021

AtCoder.Extra.Pool

Description

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

Synopsis

Pool

data Pool s a Source #

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

Constructors

Pool 

Fields

newtype Index Source #

Strongly typed index of pool items. User has to explicitly corece on raw index use.

Constructors

Index 

Fields

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 :: (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.

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\)

Handle

newtype Handle s Source #

Mutable Handle of an Index.

Since: 1.2.0.0

Constructors

Handle 

Fields

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

\(O(1)\) Creates a new sequence 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 sequence is empty.

Since: 1.2.0.0

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

\(O(1)\) Invalidates a sequence handle. Note that it does not change or free the sequence.

Since: 1.2.0.0