{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE LinearTypes #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StrictData #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# OPTIONS_GHC -Wno-unbanged-strict-patterns #-}
{-# OPTIONS_HADDOCK hide #-}

module Data.Vector.Mutable.Linear.Internal where

import Data.Array.Mutable.Linear (Array)
import qualified Data.Array.Mutable.Linear as Array
import qualified Data.Functor.Linear as Data
import Data.Monoid.Linear
import qualified Data.Vector as Vector
import GHC.Stack
import Prelude.Linear hiding (filter, mapMaybe, read)
import qualified Unsafe.Linear as Unsafe
import qualified Prelude

-- # Constants
-------------------------------------------------------------------------------

-- | When growing the vector, capacity will be multiplied by this number.
--
-- This is usually chosen between 1.5 and 2; 2 being the most common.
constGrowthFactor :: Int
constGrowthFactor :: Int
constGrowthFactor = Int
2

-- # Core data types
-------------------------------------------------------------------------------

-- | A dynamic mutable vector.
data Vector a where
  -- | Current size
  Vec ::
    -- | Underlying array (has size equal to or larger than the vectors)
    Int ->
    Array a %1 ->
    Vector a

-- # API: Construction, Mutation, Queries
-------------------------------------------------------------------------------

-- | Create a 'Vector' from an 'Array'. Result will have the size and capacity
-- equal to the size of the given array.
--
-- This is a constant time operation.
fromArray :: (HasCallStack) => Array a %1 -> Vector a
fromArray :: forall a. HasCallStack => Array a %1 -> Vector a
fromArray Array a
arr =
  forall a. Array a %1 -> (Ur Int, Array a)
Array.size Array a
arr
    forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur Int
size', Array a
arr') -> forall a. Int -> Array a -> Vector a
Vec Int
size' Array a
arr'

-- Allocate an empty vector
empty :: (Vector a %1 -> Ur b) %1 -> Ur b
empty :: forall a b. (Vector a %1 -> Ur b) %1 -> Ur b
empty Vector a %1 -> Ur b
f = forall a b. HasCallStack => [a] -> (Array a %1 -> Ur b) %1 -> Ur b
Array.fromList [] (Vector a %1 -> Ur b
f forall b c a (q :: Multiplicity) (m :: Multiplicity)
       (n :: Multiplicity).
(b %1 -> c) %q -> (a %1 -> b) %m -> a %n -> c
. forall a. HasCallStack => Array a %1 -> Vector a
fromArray)

-- | Allocate a constant vector of a given non-negative size (and error on a
-- bad size)
constant ::
  (HasCallStack) =>
  Int ->
  a ->
  (Vector a %1 -> Ur b) %1 ->
  Ur b
constant :: forall a b.
HasCallStack =>
Int -> a -> (Vector a %1 -> Ur b) %1 -> Ur b
constant Int
size' a
x Vector a %1 -> Ur b
f
  | Int
size' forall a. Ord a => a %1 -> a %1 -> Bool
< Int
0 =
      (forall a. HasCallStack => [Char] -> a
error ([Char]
"Trying to construct a vector of size " forall a. [a] %1 -> [a] %1 -> [a]
++ forall a. Show a => a -> [Char]
show Int
size') :: x %1 -> x)
        (Vector a %1 -> Ur b
f forall a. HasCallStack => a
undefined)
  | Bool
otherwise = forall a b.
HasCallStack =>
Int -> a -> (Array a %1 -> Ur b) %1 -> Ur b
Array.alloc Int
size' a
x (Vector a %1 -> Ur b
f forall b c a (q :: Multiplicity) (m :: Multiplicity)
       (n :: Multiplicity).
(b %1 -> c) %q -> (a %1 -> b) %m -> a %n -> c
. forall a. HasCallStack => Array a %1 -> Vector a
fromArray)

-- | Allocator from a list
fromList :: (HasCallStack) => [a] -> (Vector a %1 -> Ur b) %1 -> Ur b
fromList :: forall a b. HasCallStack => [a] -> (Vector a %1 -> Ur b) %1 -> Ur b
fromList [a]
xs Vector a %1 -> Ur b
f = forall a b. HasCallStack => [a] -> (Array a %1 -> Ur b) %1 -> Ur b
Array.fromList [a]
xs (Vector a %1 -> Ur b
f forall b c a (q :: Multiplicity) (m :: Multiplicity)
       (n :: Multiplicity).
(b %1 -> c) %q -> (a %1 -> b) %m -> a %n -> c
. forall a. HasCallStack => Array a %1 -> Vector a
fromArray)

-- | Number of elements inside the vector.
--
-- This might be different than how much actual memory the vector is using.
-- For that, see: 'capacity'.
size :: Vector a %1 -> (Ur Int, Vector a)
size :: forall a. Vector a %1 -> (Ur Int, Vector a)
size (Vec Int
size' Array a
arr) = (forall a. a -> Ur a
Ur Int
size', forall a. Int -> Array a -> Vector a
Vec Int
size' Array a
arr)

-- | Capacity of a vector. In other words, the number of elements
-- the vector can contain before it is copied to a bigger array.
capacity :: Vector a %1 -> (Ur Int, Vector a)
capacity :: forall a. Vector a %1 -> (Ur Int, Vector a)
capacity (Vec Int
s Array a
arr) =
  forall a. Array a %1 -> (Ur Int, Array a)
Array.size Array a
arr forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur Int
cap, Array a
arr') -> (Ur Int
cap, forall a. Int -> Array a -> Vector a
Vec Int
s Array a
arr')

-- | Insert at the end of the vector. This will grow the vector if there
-- is no empty space.
push :: a -> Vector a %1 -> Vector a
push :: forall a. a -> Vector a %1 -> Vector a
push a
x Vector a
vec =
  forall a. HasCallStack => Int -> Vector a %1 -> Vector a
growToFit Int
1 Vector a
vec forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Vec Int
s Array a
arr) ->
    forall a. HasCallStack => Int -> a -> Vector a %1 -> Vector a
unsafeSet Int
s a
x (forall a. Int -> Array a -> Vector a
Vec (Int
s forall a. Additive a => a %1 -> a %1 -> a
+ Int
1) Array a
arr)

-- | Pop from the end of the vector. This will never shrink the vector, use
-- 'shrinkToFit' to remove the wasted space.
pop :: Vector a %1 -> (Ur (Maybe a), Vector a)
pop :: forall a. Vector a %1 -> (Ur (Maybe a), Vector a)
pop Vector a
vec =
  forall a. Vector a %1 -> (Ur Int, Vector a)
size Vector a
vec forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \case
    (Ur Int
0, Vector a
vec') ->
      (forall a. a -> Ur a
Ur forall a. Maybe a
Nothing, Vector a
vec')
    (Ur Int
s, Vector a
vec') ->
      forall a. HasCallStack => Int -> Vector a %1 -> (Ur a, Vector a)
get (Int
s forall a. AdditiveGroup a => a %1 -> a %1 -> a
- Int
1) Vector a
vec' forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur a
a, Vec Int
_ Array a
arr) ->
        ( forall a. a -> Ur a
Ur (forall a. a -> Maybe a
Just a
a),
          forall a. Int -> Array a -> Vector a
Vec (Int
s forall a. AdditiveGroup a => a %1 -> a %1 -> a
- Int
1) Array a
arr
        )

-- | Write to an element . Note: this will not write to elements beyond the
-- current size of the vector and will error instead.
set :: (HasCallStack) => Int -> a -> Vector a %1 -> Vector a
set :: forall a. HasCallStack => Int -> a -> Vector a %1 -> Vector a
set Int
ix a
val Vector a
vec =
  forall a. HasCallStack => Int -> a -> Vector a %1 -> Vector a
unsafeSet Int
ix a
val (forall a. HasCallStack => Int -> Vector a %1 -> Vector a
assertIndexInRange Int
ix Vector a
vec)

-- | Same as 'write', but does not do bounds-checking. The behaviour is undefined
-- when passed an invalid index.
unsafeSet :: (HasCallStack) => Int -> a -> Vector a %1 -> Vector a
unsafeSet :: forall a. HasCallStack => Int -> a -> Vector a %1 -> Vector a
unsafeSet Int
ix a
val (Vec Int
size' Array a
arr) =
  forall a. Int -> Array a -> Vector a
Vec Int
size' (forall a. Int -> a -> Array a %1 -> Array a
Array.unsafeSet Int
ix a
val Array a
arr)

-- | Read from a vector, with an in-range index and error for an index that is
-- out of range (with the usual range @0..size-1@).
get :: (HasCallStack) => Int -> Vector a %1 -> (Ur a, Vector a)
get :: forall a. HasCallStack => Int -> Vector a %1 -> (Ur a, Vector a)
get Int
ix Vector a
vec =
  forall a. HasCallStack => Int -> Vector a %1 -> (Ur a, Vector a)
unsafeGet Int
ix (forall a. HasCallStack => Int -> Vector a %1 -> Vector a
assertIndexInRange Int
ix Vector a
vec)

-- | Same as 'read', but does not do bounds-checking. The behaviour is undefined
-- when passed an invalid index.
unsafeGet :: (HasCallStack) => Int -> Vector a %1 -> (Ur a, Vector a)
unsafeGet :: forall a. HasCallStack => Int -> Vector a %1 -> (Ur a, Vector a)
unsafeGet Int
ix (Vec Int
size' Array a
arr) =
  forall a. Int -> Array a %1 -> (Ur a, Array a)
Array.unsafeGet Int
ix Array a
arr
    forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur a
val, Array a
arr') -> (Ur a
val, forall a. Int -> Array a -> Vector a
Vec Int
size' Array a
arr')

-- | Same as 'modify', but does not do bounds-checking.
unsafeModify ::
  (HasCallStack) =>
  (a -> (a, b)) ->
  Int ->
  Vector a %1 ->
  (Ur b, Vector a)
unsafeModify :: forall a b.
HasCallStack =>
(a -> (a, b)) -> Int -> Vector a %1 -> (Ur b, Vector a)
unsafeModify a -> (a, b)
f Int
ix (Vec Int
size' Array a
arr) =
  forall a. Int -> Array a %1 -> (Ur a, Array a)
Array.unsafeGet Int
ix Array a
arr forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur a
old, Array a
arr') ->
    case a -> (a, b)
f a
old of
      (a
a, b
b) ->
        forall a. Int -> a -> Array a %1 -> Array a
Array.unsafeSet Int
ix a
a Array a
arr' forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \Array a
arr'' ->
          (forall a. a -> Ur a
Ur b
b, forall a. Int -> Array a -> Vector a
Vec Int
size' Array a
arr'')

-- | Modify a value inside a vector, with an ability to return an extra
-- information. Errors if the index is out of bounds.
modify ::
  (HasCallStack) =>
  (a -> (a, b)) ->
  Int ->
  Vector a %1 ->
  (Ur b, Vector a)
modify :: forall a b.
HasCallStack =>
(a -> (a, b)) -> Int -> Vector a %1 -> (Ur b, Vector a)
modify a -> (a, b)
f Int
ix Vector a
vec = forall a b.
HasCallStack =>
(a -> (a, b)) -> Int -> Vector a %1 -> (Ur b, Vector a)
unsafeModify a -> (a, b)
f Int
ix (forall a. HasCallStack => Int -> Vector a %1 -> Vector a
assertIndexInRange Int
ix Vector a
vec)

-- | Same as 'modify', but without the ability to return extra information.
modify_ :: (HasCallStack) => (a -> a) -> Int -> Vector a %1 -> Vector a
modify_ :: forall a.
HasCallStack =>
(a -> a) -> Int -> Vector a %1 -> Vector a
modify_ a -> a
f Int
ix Vector a
vec =
  forall a b.
HasCallStack =>
(a -> (a, b)) -> Int -> Vector a %1 -> (Ur b, Vector a)
modify (\a
a -> (a -> a
f a
a, ())) Int
ix Vector a
vec
    forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur (), Vector a
vec') -> Vector a
vec'

-- | Return the vector elements as a lazy list.
toList :: Vector a %1 -> Ur [a]
toList :: forall a. Vector a %1 -> Ur [a]
toList (Vec Int
s Array a
arr) =
  forall a. Array a %1 -> Ur [a]
Array.toList Array a
arr forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur [a]
xs) ->
    forall a. a -> Ur a
Ur (forall a. Int -> [a] -> [a]
Prelude.take Int
s [a]
xs)

-- | Filters the vector in-place. It does not deallocate unused capacity,
-- use 'shrinkToFit' for that if necessary.
filter :: Vector a %1 -> (a -> Bool) -> Vector a
filter :: forall a. Vector a %1 -> (a -> Bool) -> Vector a
filter Vector a
v a -> Bool
f = forall a b. Vector a %1 -> (a -> Maybe b) -> Vector b
mapMaybe Vector a
v (\a
a -> if a -> Bool
f a
a then forall a. a -> Maybe a
Just a
a else forall a. Maybe a
Nothing)

-- TODO A slightly more efficient version exists, where we skip the writes
-- until the first time the predicate fails. However that requires duplicating
-- most of the logic at `mapMaybe`, so lets not until we have benchmarks to
-- see the advantage.

-- | A version of 'fmap' which can throw out elements.
mapMaybe :: Vector a %1 -> (a -> Maybe b) -> Vector b
mapMaybe :: forall a b. Vector a %1 -> (a -> Maybe b) -> Vector b
mapMaybe Vector a
vec (a -> Maybe b
f :: a -> Maybe b) =
  forall a. Vector a %1 -> (Ur Int, Vector a)
size Vector a
vec forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur Int
s, Vector a
vec') -> Int -> Int -> Int -> Vector a %1 -> Vector b
go Int
0 Int
0 Int
s Vector a
vec'
  where
    go ::
      Int -> -- read cursor
      Int -> -- write cursor
      Int -> -- input size
      Vector a %1 ->
      Vector b
    go :: Int -> Int -> Int -> Vector a %1 -> Vector b
go Int
r Int
w Int
s Vector a
vec'
      -- If we processed all elements, set the capacity after the last written
      -- index and coerce the result to the correct type.
      | Int
r forall a. Eq a => a %1 -> a %1 -> Bool
== Int
s =
          Vector a
vec' forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Vec Int
_ Array a
arr) ->
            forall a. Int -> Array a -> Vector a
Vec Int
w (forall a b. a %1 -> b
Unsafe.coerce Array a
arr)
      -- Otherwise, read an element, write if the predicate is true and advance
      -- the write cursor; otherwise keep the write cursor skipping the element.
      | Bool
otherwise =
          forall a. HasCallStack => Int -> Vector a %1 -> (Ur a, Vector a)
unsafeGet Int
r Vector a
vec' forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \case
            (Ur a
a, Vector a
vec'')
              | Just b
b <- a -> Maybe b
f a
a ->
                  Int -> Int -> Int -> Vector a %1 -> Vector b
go (Int
r forall a. Additive a => a %1 -> a %1 -> a
+ Int
1) (Int
w forall a. Additive a => a %1 -> a %1 -> a
+ Int
1) Int
s (forall a. HasCallStack => Int -> a -> Vector a %1 -> Vector a
unsafeSet Int
w (forall a b. a %1 -> b
Unsafe.coerce b
b) Vector a
vec'')
              | Bool
otherwise ->
                  Int -> Int -> Int -> Vector a %1 -> Vector b
go (Int
r forall a. Additive a => a %1 -> a %1 -> a
+ Int
1) Int
w Int
s Vector a
vec''

-- | Resize the vector to not have any wasted memory (size == capacity). This
-- returns a semantically identical vector.
shrinkToFit :: Vector a %1 -> Vector a
shrinkToFit :: forall a. Vector a %1 -> Vector a
shrinkToFit Vector a
vec =
  forall a. Vector a %1 -> (Ur Int, Vector a)
capacity Vector a
vec forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur Int
cap, Vector a
vec') ->
    forall a. Vector a %1 -> (Ur Int, Vector a)
size Vector a
vec' forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur Int
s', Vector a
vec'') ->
      if Int
cap forall a. Ord a => a %1 -> a %1 -> Bool
> Int
s'
        then forall a. HasCallStack => Int -> Vector a %1 -> Vector a
unsafeResize Int
s' Vector a
vec''
        else Vector a
vec''

-- | Return a slice of the vector with given size, starting from an offset.
--
-- Start offset + target size should be within the input vector, and both should
-- be non-negative.
--
-- This is a constant time operation if the start offset is 0. Use 'shrinkToFit'
-- to remove the possible wasted space if necessary.
slice :: Int -> Int -> Vector a %1 -> Vector a
slice :: forall a. Int -> Int -> Vector a %1 -> Vector a
slice Int
from Int
newSize (Vec Int
oldSize Array a
arr) =
  if Int
oldSize forall a. Ord a => a %1 -> a %1 -> Bool
< Int
from forall a. Additive a => a %1 -> a %1 -> a
+ Int
newSize
    then Array a
arr forall a b. Consumable a => a %1 -> b %1 -> b
`lseq` forall a. HasCallStack => [Char] -> a
error [Char]
"Slice index out of bounds"
    else
      if Int
from forall a. Eq a => a %1 -> a %1 -> Bool
== Int
0
        then forall a. Int -> Array a -> Vector a
Vec Int
newSize Array a
arr
        else
          forall a.
HasCallStack =>
Int -> Int -> Array a %1 -> (Array a, Array a)
Array.slice Int
from Int
newSize Array a
arr forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Array a
oldArr, Array a
newArr) ->
            Array a
oldArr forall a b. Consumable a => a %1 -> b %1 -> b
`lseq` forall a. HasCallStack => Array a %1 -> Vector a
fromArray Array a
newArr

-- | /O(1)/ Convert a 'Vector' to an immutable 'Vector.Vector' (from
-- 'vector' package).
freeze :: Vector a %1 -> Ur (Vector.Vector a)
freeze :: forall a. Vector a %1 -> Ur (Vector a)
freeze (Vec Int
sz Array a
arr) =
  forall a. Array a %1 -> Ur (Vector a)
Array.freeze Array a
arr
    forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur Vector a
vec) -> forall a. a -> Ur a
Ur (forall a. Int -> Vector a -> Vector a
Vector.take Int
sz Vector a
vec)

-- | Same as 'set', but takes the 'Vector' as the first parameter.
write :: (HasCallStack) => Vector a %1 -> Int -> a -> Vector a
write :: forall a. HasCallStack => Vector a %1 -> Int -> a -> Vector a
write Vector a
arr Int
i a
a = forall a. HasCallStack => Int -> a -> Vector a %1 -> Vector a
set Int
i a
a Vector a
arr

-- | Same as 'unsafeSafe', but takes the 'Vector' as the first parameter.
unsafeWrite :: Vector a %1 -> Int -> a -> Vector a
unsafeWrite :: forall a. Vector a %1 -> Int -> a -> Vector a
unsafeWrite Vector a
arr Int
i a
a = forall a. HasCallStack => Int -> a -> Vector a %1 -> Vector a
unsafeSet Int
i a
a Vector a
arr

-- | Same as 'get', but takes the 'Vector' as the first parameter.
read :: (HasCallStack) => Vector a %1 -> Int -> (Ur a, Vector a)
read :: forall a. HasCallStack => Vector a %1 -> Int -> (Ur a, Vector a)
read Vector a
arr Int
i = forall a. HasCallStack => Int -> Vector a %1 -> (Ur a, Vector a)
get Int
i Vector a
arr

-- | Same as 'unsafeGet', but takes the 'Vector' as the first parameter.
unsafeRead :: Vector a %1 -> Int -> (Ur a, Vector a)
unsafeRead :: forall a. Vector a %1 -> Int -> (Ur a, Vector a)
unsafeRead Vector a
arr Int
i = forall a. HasCallStack => Int -> Vector a %1 -> (Ur a, Vector a)
unsafeGet Int
i Vector a
arr

-- # Instances
-------------------------------------------------------------------------------

instance Consumable (Vector a) where
  consume :: Vector a %1 -> ()
consume (Vec Int
_ Array a
arr) = forall a. Consumable a => a %1 -> ()
consume Array a
arr

instance Dupable (Vector a) where
  dup2 :: Vector a %1 -> (Vector a, Vector a)
dup2 (Vec Int
i Array a
arr) =
    forall a. Dupable a => a %1 -> (a, a)
dup2 Array a
arr forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Array a
a1, Array a
a2) ->
      (forall a. Int -> Array a -> Vector a
Vec Int
i Array a
a1, forall a. Int -> Array a -> Vector a
Vec Int
i Array a
a2)

-- There is no way to get an unrestricted vector. So the below instance
-- is just to satisfy the linear Semigroup's constraint.
instance Prelude.Semigroup (Vector a) where
  Vector a
v1 <> :: Vector a -> Vector a -> Vector a
<> Vector a
v2 = Vector a
v1 forall a. Semigroup a => a %1 -> a %1 -> a
Data.Monoid.Linear.<> Vector a
v2

instance Semigroup (Vector a) where
  -- This operation tries to use the existing capacity of v1 when possible.
  Vector a
v1 <> :: Vector a %1 -> Vector a %1 -> Vector a
<> Vector a
v2 =
    forall a. Vector a %1 -> (Ur Int, Vector a)
size Vector a
v2 forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur Int
s2, Vector a
v2') ->
      forall a. HasCallStack => Int -> Vector a %1 -> Vector a
growToFit Int
s2 Vector a
v1 forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \Vector a
v1' ->
        forall a. Vector a %1 -> Ur [a]
toList Vector a
v2' forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur [a]
xs) ->
          [a] -> Vector a %1 -> Vector a
go [a]
xs Vector a
v1'
    where
      go :: [a] -> Vector a %1 -> Vector a
      go :: [a] -> Vector a %1 -> Vector a
go [] Vector a
vec = Vector a
vec
      go (a
x : [a]
xs) (Vec Int
sz Array a
arr) =
        forall a. HasCallStack => Int -> a -> Vector a %1 -> Vector a
unsafeSet Int
sz a
x (forall a. Int -> Array a -> Vector a
Vec (Int
sz forall a. Additive a => a %1 -> a %1 -> a
+ Int
1) Array a
arr)
          forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& [a] -> Vector a %1 -> Vector a
go [a]
xs

instance Data.Functor Vector where
  fmap :: forall a b. (a %1 -> b) -> Vector a %1 -> Vector b
fmap a %1 -> b
f Vector a
vec = forall a b. Vector a %1 -> (a -> Maybe b) -> Vector b
mapMaybe Vector a
vec (\a
a -> forall a. a -> Maybe a
Just (a %1 -> b
f a
a))

-- # Internal library
-------------------------------------------------------------------------------

-- | Grows the vector to the closest power of growthFactor to
-- fit at least n more elements.
growToFit :: (HasCallStack) => Int -> Vector a %1 -> Vector a
growToFit :: forall a. HasCallStack => Int -> Vector a %1 -> Vector a
growToFit Int
n Vector a
vec =
  forall a. Vector a %1 -> (Ur Int, Vector a)
capacity Vector a
vec forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur Int
cap, Vector a
vec') ->
    forall a. Vector a %1 -> (Ur Int, Vector a)
size Vector a
vec' forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur Int
s', Vector a
vec'') ->
      if Int
s' forall a. Additive a => a %1 -> a %1 -> a
+ Int
n forall a. Ord a => a %1 -> a %1 -> Bool
<= Int
cap
        then Vector a
vec''
        else
          let -- Calculate the closest power of growth factor
              -- larger than required size.
              newSize :: Int
newSize =
                Int
constGrowthFactor -- This constant is defined above.
                  forall a b. (Num a, Integral b) => a -> b -> a
^ (forall a b. (RealFrac a, Integral b) => a -> b
ceiling :: Double -> Int)
                    ( forall a. Floating a => a -> a -> a
logBase
                        (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
constGrowthFactor)
                        (forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
s' forall a. Additive a => a %1 -> a %1 -> a
+ Int
n)) -- this is always
                        -- > 0 because of
                        -- the if condition
                    )
           in forall a. HasCallStack => Int -> Vector a %1 -> Vector a
unsafeResize
                Int
newSize
                Vector a
vec''

-- | Resize the vector to a non-negative size. In-range elements are preserved,
-- the possible new elements are bottoms.
unsafeResize :: (HasCallStack) => Int -> Vector a %1 -> Vector a
unsafeResize :: forall a. HasCallStack => Int -> Vector a %1 -> Vector a
unsafeResize Int
newSize (Vec Int
size' Array a
ma) =
  forall a. Int -> Array a -> Vector a
Vec
    (forall a. (Dupable a, Ord a) => a %1 -> a %1 -> a
min Int
size' Int
newSize)
    ( forall a. HasCallStack => Int -> a -> Array a %1 -> Array a
Array.resize
        Int
newSize
        (forall a. HasCallStack => [Char] -> a
error [Char]
"access to uninitialized vector index")
        Array a
ma
    )

-- | Check if given index is within the Vector, otherwise panic.
assertIndexInRange :: (HasCallStack) => Int -> Vector a %1 -> Vector a
assertIndexInRange :: forall a. HasCallStack => Int -> Vector a %1 -> Vector a
assertIndexInRange Int
i Vector a
vec =
  forall a. Vector a %1 -> (Ur Int, Vector a)
size Vector a
vec forall a b (p :: Multiplicity) (q :: Multiplicity).
a %p -> (a %p -> b) %q -> b
& \(Ur Int
s, Vector a
vec') ->
    if Int
0 forall a. Ord a => a %1 -> a %1 -> Bool
<= Int
i Bool %1 -> Bool %1 -> Bool
&& Int
i forall a. Ord a => a %1 -> a %1 -> Bool
< Int
s
      then Vector a
vec'
      else Vector a
vec' forall a b. Consumable a => a %1 -> b %1 -> b
`lseq` forall a. HasCallStack => [Char] -> a
error [Char]
"Vector: index out of bounds"