-- |
-- Utility for construction of vectors when the size is not known ahead.
module VectorExtras.Accumulator
  ( Accumulator,
    add,

    -- * Execution
    toVector,
  )
where

import Data.Vector.Generic
import qualified VectorExtras.Generic as GenericExtras
import VectorExtras.Prelude hiding (length)

-- |
-- Finalise the accumulator as vector.
{-# INLINE toVector #-}
toVector :: Vector v a => Accumulator a -> v a
toVector :: Accumulator a -> v a
toVector (Accumulator Int
size [a]
list) =
  Int -> [a] -> v a
forall (v :: * -> *) a. Vector v a => Int -> [a] -> v a
GenericExtras.fromReverseListN Int
size [a]
list

-- |
-- Constructor of vectors optimised for appending elements one by one,
-- providing for \(\mathcal{O}(n)\) complexity of the whole construction process.
--
-- Very useful as accumulator in folds.
--
-- Under the hood it is the size counter and a reverse list of elements.
-- When executed, a vector of the according size gets allocated and
-- gets populated with the elements in reverse order
-- (starting from the last element).
data Accumulator a
  = Accumulator !Int ![a]

-- |
-- Add an element to the accumulator.
{-# INLINE add #-}
add :: a -> Accumulator a -> Accumulator a
add :: a -> Accumulator a -> Accumulator a
add a
head (Accumulator Int
size [a]
tail) =
  Int -> [a] -> Accumulator a
forall a. Int -> [a] -> Accumulator a
Accumulator (Int -> Int
forall a. Enum a => a -> a
succ Int
size) (a
head a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
tail)