-- Copyright 2013 Evan Laforge
-- This program is distributed under the terms of the GNU General Public
-- License 3.0, see COPYING or http://www.gnu.org/licenses/gpl-3.0.txt

{- | Generic functions over vectors of 'Sample's.

    The samples should be sorted, though this is currently not enforced by
    the constructors.  TODO fix that

    By default, this defines a piecewise-constant function, where each sample
    maintains its value until the next one.  However, samples can have
    coincident Xs, and this is used for a linear segment based implementation
    built on top of this.
-}
module Util.TimeVector (
    module Util.TimeVector
    , module Util.TimeVectorStorable
    , module Data.Vector.Generic
) where
import Prelude hiding (head, last, take)
import qualified Control.Monad.State.Strict as State
import qualified Data.Vector as Vector
import qualified Data.Vector.Generic as V
import Data.Vector.Generic
       (all, drop, foldl', length, null, take, toList, unsafeIndex)
import qualified Data.Vector.Storable as Storable

import qualified Foreign

import qualified Util.CallStack as CallStack
import qualified Util.Pretty as Pretty
import qualified Util.Lists as Lists
import Util.TimeVectorStorable (X, Sample(..))

import qualified Perform.RealTime as RealTime

import Global


x_to_double :: X -> Double
x_to_double :: X -> UnboxedY
x_to_double = X -> UnboxedY
RealTime.to_seconds

double_to_x :: Double -> X
double_to_x :: UnboxedY -> X
double_to_x = UnboxedY -> X
RealTime.seconds

type Boxed y = Vector.Vector (Sample y)

-- * unboxed

-- A number of functions in here are SPECIALIZEd on Unboxed.  This improves
-- performance significantly since the functions are heavily used and the
-- specialization likely enables some unboxing in inner loops.

-- There's no monoid instance for Boxed or Unboxed, and I leave it that way.
-- Implementations should implement their own Monoid with their own rules,
-- perhaps using 'merge_left', which is for piecewise-constant signals.

type Unboxed = Storable.Vector (Sample UnboxedY)
type UnboxedY = Double

to_foreign_ptr :: Storable.Storable a =>
    Storable.Vector a -> (Foreign.ForeignPtr a, Int)
to_foreign_ptr :: forall a. Storable a => Vector a -> (ForeignPtr a, Int)
to_foreign_ptr = forall a. Vector a -> (ForeignPtr a, Int)
Storable.unsafeToForeignPtr0

with_ptr :: Storable.Storable a =>
    Storable.Vector a -> (Foreign.Ptr a -> Int -> IO b) -> IO b
with_ptr :: forall a b.
Storable a =>
Vector a -> (Ptr a -> Int -> IO b) -> IO b
with_ptr Vector a
v Ptr a -> Int -> IO b
action = forall a b. Storable a => Vector a -> (Ptr a -> IO b) -> IO b
Storable.unsafeWith Vector a
v forall a b. (a -> b) -> a -> b
$ \Ptr a
ptr -> Ptr a -> Int -> IO b
action Ptr a
ptr (forall (v :: * -> *) a. Vector v a => v a -> Int
V.length Vector a
v)

-- * implementation

index :: V.Vector v a => v a -> Int -> a
index :: forall (v :: * -> *) a. Vector v a => v a -> Int -> a
index = forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
(V.!)

head, last :: V.Vector v a => v a -> Maybe a
head :: forall (v :: * -> *) a. Vector v a => v a -> Maybe a
head v a
v
    | forall (v :: * -> *) a. Vector v a => v a -> Bool
V.null v a
v = forall a. Maybe a
Nothing
    | Bool
otherwise = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => v a -> Int -> a
V.unsafeIndex v a
v Int
0
last :: forall (v :: * -> *) a. Vector v a => v a -> Maybe a
last v a
v
    | forall (v :: * -> *) a. Vector v a => v a -> Bool
V.null v a
v = forall a. Maybe a
Nothing
    | Bool
otherwise = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => v a -> a
V.last v a
v

uncons :: V.Vector v a => v a -> Maybe (a, v a)
uncons :: forall (v :: * -> *) a. Vector v a => v a -> Maybe (a, v a)
uncons v a
v
    | forall (v :: * -> *) a. Vector v a => v a -> Bool
V.null v a
v = forall a. Maybe a
Nothing
    | Bool
otherwise = forall a. a -> Maybe a
Just (forall (v :: * -> *) a. Vector v a => v a -> a
V.unsafeHead v a
v, forall (v :: * -> *) a. Vector v a => v a -> v a
V.unsafeTail v a
v)

-- ** TimeVector specific

-- | Construct a TimeVector from a list.
{-# SPECIALIZE from_pairs :: [(X, UnboxedY)] -> Unboxed #-}
{-# INLINEABLE from_pairs #-}
from_pairs :: V.Vector v (Sample y) => [(X, y)] -> v (Sample y)
from_pairs :: forall (v :: * -> *) y.
Vector v (Sample y) =>
[(X, y)] -> v (Sample y)
from_pairs = forall (v :: * -> *) a. Vector v a => [a] -> v a
V.fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall y. X -> y -> Sample y
Sample)

to_pairs :: V.Vector v (Sample y) => v (Sample y) -> [(X, y)]
to_pairs :: forall (v :: * -> *) y.
Vector v (Sample y) =>
v (Sample y) -> [(X, y)]
to_pairs = forall a b. (a -> b) -> [a] -> [b]
map forall y. Sample y -> (X, y)
to_pair forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vector v a => v a -> [a]
V.toList

-- | Set the signal value, with a discontinuity.  See
-- NOTE [signal-discontinuity].
set :: V.Vector v (Sample y) => Maybe y -> X -> y -> v (Sample y)
set :: forall (v :: * -> *) y.
Vector v (Sample y) =>
Maybe y -> X -> y -> v (Sample y)
set Maybe y
prev_y X
x y
y = forall (v :: * -> *) y.
Vector v (Sample y) =>
[(X, y)] -> v (Sample y)
from_pairs forall a b. (a -> b) -> a -> b
$ forall b a. b -> (a -> b) -> Maybe a -> b
maybe forall a. a -> a
id ((:) forall b c a. (b -> c) -> (a -> b) -> a -> c
. (X
x,)) Maybe y
prev_y [(X
x, y
y)]

{-# SPECIALIZE constant :: UnboxedY -> Unboxed #-}
{-# INLINEABLE constant #-}
constant :: V.Vector v (Sample y) => y -> v (Sample y)
constant :: forall (v :: * -> *) y. Vector v (Sample y) => y -> v (Sample y)
constant y
y = forall (v :: * -> *) a. Vector v a => a -> v a
V.singleton (forall y. X -> y -> Sample y
Sample (-X
RealTime.larger) y
y)

constant_val :: Unboxed -> Maybe UnboxedY
constant_val :: Unboxed -> Maybe UnboxedY
constant_val Unboxed
vec = case forall (v :: * -> *) a. Vector v a => v a -> Maybe (a, v a)
uncons Unboxed
vec of
    Maybe (Sample UnboxedY, Unboxed)
Nothing -> forall a. a -> Maybe a
Just UnboxedY
0
    Just (Sample X
x0 UnboxedY
y0, Unboxed
rest)
        -- I compare multiple samples because a track might have redundant
        -- values, but I still want to detect if it's constant.
        | X
x0 forall a. Ord a => a -> a -> Bool
<= -X
RealTime.large Bool -> Bool -> Bool
&& forall (v :: * -> *) a. Vector v a => (a -> Bool) -> v a -> Bool
V.all ((forall a. Eq a => a -> a -> Bool
==UnboxedY
y0) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall y. Sample y -> y
sy) Unboxed
rest -> forall a. a -> Maybe a
Just UnboxedY
y0
        | forall (v :: * -> *) a. Vector v a => (a -> Bool) -> v a -> Bool
V.all ((forall a. Eq a => a -> a -> Bool
==UnboxedY
0) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall y. Sample y -> y
sy) Unboxed
vec -> forall a. a -> Maybe a
Just UnboxedY
0
        | Bool
otherwise -> forall a. Maybe a
Nothing

to_pair :: Sample y -> (X, y)
to_pair :: forall y. Sample y -> (X, y)
to_pair (Sample X
x y
y) = (X
x, y
y)

instance Pretty y => Pretty (Sample y) where
    format :: Sample y -> Doc
format (Sample X
x y
y) = forall a. Pretty a => a -> Doc
Pretty.format X
x forall a. Semigroup a => a -> a -> a
<> Char -> Doc
Pretty.char Char
':' forall a. Semigroup a => a -> a -> a
<> forall a. Pretty a => a -> Doc
Pretty.format y
y

-- | TimeVectors should be sorted by the X value.  Return warnings for where
-- that's not true.
{-# SPECIALIZE check :: Unboxed -> [String] #-}
{-# INLINEABLE check #-}
check :: V.Vector v (Sample y) => v (Sample y) -> [String]
check :: forall (v :: * -> *) y.
Vector v (Sample y) =>
v (Sample y) -> [String]
check = forall a. [a] -> [a]
reverse forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> a
fst forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) b a.
Vector v b =>
(a -> b -> a) -> a -> v b -> a
V.foldl' forall {a} {y}.
(Num a, Show a) =>
([String], (a, X)) -> Sample y -> ([String], (a, X))
check ([], (Integer
0, X
0))
    where
    check :: ([String], (a, X)) -> Sample y -> ([String], (a, X))
check ([String]
warns, (a
i, X
prev_x)) (Sample X
x y
_)
        | X
x forall a. Ord a => a -> a -> Bool
< X
prev_x = forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (String
msg:) ([String], (a, X))
next
        | Bool
otherwise = ([String], (a, X))
next
        where
        msg :: String
msg = String
"index " forall a. Semigroup a => a -> a -> a
<> forall a. Show a => a -> String
show a
i forall a. Semigroup a => a -> a -> a
<> String
": x decreased: " forall a. Semigroup a => a -> a -> a
<> forall a. Show a => a -> String
show X
x forall a. Semigroup a => a -> a -> a
<> String
" < "
            forall a. Semigroup a => a -> a -> a
<> forall a. Show a => a -> String
show X
prev_x
        next :: ([String], (a, X))
next = ([String]
warns, (a
i forall a. Num a => a -> a -> a
+ a
1, X
x))

-- | This is a merge where the vectors to the right will win in the case of
-- overlap.
{-# SPECIALIZE merge_right :: [Unboxed] -> Unboxed #-}
{-# INLINEABLE merge_right #-}
merge_right :: V.Vector v (Sample y) => [v (Sample y)] -> v (Sample y)
merge_right :: forall (v :: * -> *) y.
Vector v (Sample y) =>
[v (Sample y)] -> v (Sample y)
merge_right [v (Sample y)
v] = v (Sample y)
v
merge_right [v (Sample y)]
vs = case forall {v :: * -> *} {y}.
Vector v (Sample y) =>
[v (Sample y)] -> Maybe (v (Sample y), [v (Sample y)], X)
next_start (forall a. [a] -> [a]
reverse [v (Sample y)]
vs) of
    Maybe (v (Sample y), [v (Sample y)], X)
Nothing -> forall (v :: * -> *) a. Vector v a => v a
V.empty
    Just (v (Sample y)
v, [v (Sample y)]
vs, X
x) -> forall (v :: * -> *) a. Vector v a => [v a] -> v a
V.concat forall a b. (a -> b) -> a -> b
$ forall a. [a] -> [a]
reverse forall a b. (a -> b) -> a -> b
$ v (Sample y)
v forall a. a -> [a] -> [a]
: forall {v :: * -> *} {y}.
Vector v (Sample y) =>
X -> [v (Sample y)] -> [v (Sample y)]
trim X
x [v (Sample y)]
vs
    where
    -- I don't really like the double reverse, but it's easiest this way.
    trim :: X -> [v (Sample y)] -> [v (Sample y)]
trim X
prev_start (v (Sample y)
v : [v (Sample y)]
vs) =
        v (Sample y)
clipped forall a. a -> [a] -> [a]
: X -> [v (Sample y)] -> [v (Sample y)]
trim (forall b a. b -> (a -> b) -> Maybe a -> b
maybe X
prev_start forall y. Sample y -> X
sx (forall (v :: * -> *) a. Vector v a => v a -> Maybe a
head v (Sample y)
clipped)) [v (Sample y)]
vs
        where clipped :: v (Sample y)
clipped = forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
V.take (forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
bsearch_below X
prev_start v (Sample y)
v) v (Sample y)
v
    trim X
_ [] = []
    next_start :: [v (Sample y)] -> Maybe (v (Sample y), [v (Sample y)], X)
next_start [] = forall a. Maybe a
Nothing
    next_start (v (Sample y)
v:[v (Sample y)]
vs) = forall b a. b -> (a -> b) -> Maybe a -> b
maybe ([v (Sample y)] -> Maybe (v (Sample y), [v (Sample y)], X)
next_start [v (Sample y)]
vs) (\Sample y
s -> (forall a. a -> Maybe a
Just (v (Sample y)
v, [v (Sample y)]
vs, forall y. Sample y -> X
sx Sample y
s)))
        (forall (v :: * -> *) a. Vector v a => v a -> Maybe a
head v (Sample y)
v)

-- | This is a merge where the vectors to the left will win in the case of
-- overlap.
{-# SPECIALIZE merge_left :: [Unboxed] -> Unboxed #-}
{-# INLINEABLE merge_left #-}
merge_left :: V.Vector v (Sample y) => [v (Sample y)] -> v (Sample y)
merge_left :: forall (v :: * -> *) y.
Vector v (Sample y) =>
[v (Sample y)] -> v (Sample y)
merge_left [v (Sample y)
v] = v (Sample y)
v
merge_left [v (Sample y)]
vs = case forall {v :: * -> *} {y}.
Vector v (Sample y) =>
[v (Sample y)] -> Maybe (v (Sample y), [v (Sample y)], X)
next_end [v (Sample y)]
vs of
    Maybe (v (Sample y), [v (Sample y)], X)
Nothing -> forall (v :: * -> *) a. Vector v a => v a
V.empty
    Just (v (Sample y)
v, [v (Sample y)]
vs, X
x) -> forall (v :: * -> *) a. Vector v a => [v a] -> v a
V.concat forall a b. (a -> b) -> a -> b
$ v (Sample y)
v forall a. a -> [a] -> [a]
: forall {v :: * -> *} {y}.
Vector v (Sample y) =>
X -> [v (Sample y)] -> [v (Sample y)]
trim X
x [v (Sample y)]
vs
    where
    trim :: X -> [v (Sample y)] -> [v (Sample y)]
trim X
prev_end (v (Sample y)
v : [v (Sample y)]
vs) =
        v (Sample y)
clipped forall a. a -> [a] -> [a]
: X -> [v (Sample y)] -> [v (Sample y)]
trim (forall b a. b -> (a -> b) -> Maybe a -> b
maybe X
prev_end forall y. Sample y -> X
sx (forall (v :: * -> *) a. Vector v a => v a -> Maybe a
last v (Sample y)
clipped)) [v (Sample y)]
vs
        where clipped :: v (Sample y)
clipped = forall (v :: * -> *) a. Vector v a => (a -> Bool) -> v a -> v a
V.dropWhile ((forall a. Ord a => a -> a -> Bool
<=X
prev_end) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall y. Sample y -> X
sx) v (Sample y)
v
    trim X
_ [] = []
    next_end :: [v (Sample y)] -> Maybe (v (Sample y), [v (Sample y)], X)
next_end [] = forall a. Maybe a
Nothing
    next_end (v (Sample y)
v:[v (Sample y)]
vs) = forall b a. b -> (a -> b) -> Maybe a -> b
maybe ([v (Sample y)] -> Maybe (v (Sample y), [v (Sample y)], X)
next_end [v (Sample y)]
vs) (\Sample y
s -> (forall a. a -> Maybe a
Just (v (Sample y)
v, [v (Sample y)]
vs, forall y. Sample y -> X
sx Sample y
s))) (forall (v :: * -> *) a. Vector v a => v a -> Maybe a
last v (Sample y)
v)
    -- |--->        => |--->
    --   |--->             |->
    --     |--->             |->

-- | When signals are 'merge_left'd, the later one overrides the first one.
-- This is the other way: the first one will override the second.
{-# SPECIALIZE prepend :: Unboxed -> Unboxed -> Unboxed #-}
{-# INLINEABLE prepend #-}
prepend :: V.Vector v (Sample y) => v (Sample y) -> v (Sample y)
    -> v (Sample y)
prepend :: forall (v :: * -> *) y.
Vector v (Sample y) =>
v (Sample y) -> v (Sample y) -> v (Sample y)
prepend v (Sample y)
vec1 v (Sample y)
vec2 = case forall (v :: * -> *) a. Vector v a => v a -> Maybe a
last v (Sample y)
vec1 of
    Maybe (Sample y)
Nothing -> v (Sample y)
vec2
    Just (Sample X
x y
_) ->
        v (Sample y)
vec1 forall (v :: * -> *) a. Vector v a => v a -> v a -> v a
V.++ forall (v :: * -> *) a. Vector v a => (a -> Bool) -> v a -> v a
V.dropWhile ((forall a. Ord a => a -> a -> Bool
<=X
x) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall y. Sample y -> X
sx) (forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> v (Sample y)
drop_before_strict X
x v (Sample y)
vec2)

-- | Same as 'sample_at', except don't return the X.
{-# SPECIALIZE at :: X -> Unboxed -> Maybe UnboxedY #-}
{-# INLINEABLE at #-}
at :: V.Vector v (Sample y) => X -> v (Sample y) -> Maybe y
at :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Maybe y
at X
x = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Maybe (X, y)
sample_at X
x

-- | Find the sample at or before X.  Nothing if the X is before the first
-- sample.
{-# SPECIALIZE sample_at :: X -> Unboxed -> Maybe (X, UnboxedY) #-}
{-# INLINEABLE sample_at #-}
sample_at :: V.Vector v (Sample y) => X -> v (Sample y) -> Maybe (X, y)
sample_at :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Maybe (X, y)
sample_at X
x v (Sample y)
vec
    | Int
i forall a. Ord a => a -> a -> Bool
>= Int
0 = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall y. Sample y -> (X, y)
to_pair forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => v a -> Int -> a
V.unsafeIndex v (Sample y)
vec Int
i
    | Bool
otherwise = forall a. Maybe a
Nothing
    where i :: Int
i = forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
highest_index X
x v (Sample y)
vec

-- | Find the sample before the given X.
{-# SPECIALIZE before :: X -> Unboxed -> Maybe (Sample UnboxedY) #-}
{-# INLINEABLE before #-}
before :: V.Vector v (Sample y) => X -> v (Sample y) -> Maybe (Sample y)
before :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Maybe (Sample y)
before X
x v (Sample y)
vec
    | Int
i forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => v a -> Int -> a
V.unsafeIndex v (Sample y)
vec (Int
iforall a. Num a => a -> a -> a
-Int
1)
    | Bool
otherwise = forall a. Maybe a
Nothing
    where i :: Int
i = forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
bsearch_below X
x v (Sample y)
vec

-- | Samples at and above the given time.
ascending :: V.Vector v (Sample y) => X -> v (Sample y) -> [Sample y]
ascending :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> [Sample y]
ascending X
x v (Sample y)
vec =
    [ forall (v :: * -> *) a. Vector v a => v a -> Int -> a
V.unsafeIndex v (Sample y)
vec Int
i
    | Int
i <- forall a. (Num a, Ord a) => a -> a -> a -> [a]
Lists.range' (forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
bsearch_below X
x v (Sample y)
vec) (forall (v :: * -> *) a. Vector v a => v a -> Int
V.length v (Sample y)
vec) Int
1
    ]

-- | Descending samples, starting below the time.
descending :: V.Vector v (Sample y) => X -> v (Sample y) -> [Sample y]
descending :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> [Sample y]
descending X
x v (Sample y)
vec =
    [forall (v :: * -> *) a. Vector v a => v a -> Int -> a
V.unsafeIndex v (Sample y)
vec Int
i | Int
i <- forall a. (Num a, Ord a) => a -> a -> a -> [a]
Lists.range (forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
bsearch_below X
x v (Sample y)
vec forall a. Num a => a -> a -> a
- Int
1) Int
0 (-Int
1)]

-- * transform

-- | Shift the signal in time.
shift :: V.Vector v (Sample y) => X -> v (Sample y) -> v (Sample y)
shift :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> v (Sample y)
shift X
offset v (Sample y)
vec
    | X
offset forall a. Eq a => a -> a -> Bool
== X
0 = v (Sample y)
vec
    | Bool
otherwise = forall (v :: * -> *) y.
Vector v (Sample y) =>
(X -> X) -> v (Sample y) -> v (Sample y)
map_x (forall a. Num a => a -> a -> a
+X
offset) v (Sample y)
vec

-- | Truncate a signal so it doesn't include the given X - RealTime.eta.  It's
-- just a view of the old signal, so it doesn't allocate a new signal.
{-# SPECIALIZE drop_at_after :: X -> Unboxed -> Unboxed #-}
{-# INLINEABLE drop_at_after #-}
drop_at_after :: V.Vector v (Sample y) => X -> v (Sample y) -> v (Sample y)
drop_at_after :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> v (Sample y)
drop_at_after X
x v (Sample y)
vec = forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
V.take (forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
bsearch_below (X
x forall a. Num a => a -> a -> a
- X
RealTime.eta) v (Sample y)
vec) v (Sample y)
vec

drop_after :: V.Vector v (Sample y) => X -> v (Sample y) -> v (Sample y)
drop_after :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> v (Sample y)
drop_after X
x = forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> v (Sample y)
drop_at_after (X
x forall a. Num a => a -> a -> a
+ X
RealTime.eta forall a. Num a => a -> a -> a
+ X
RealTime.eta)

-- | Like 'drop_before_strict', except if there is no sample at @x@, keep one
-- sample before it to preserve the value at @x@.  If there are multiple
-- samples at @x@, drop all but the last one.  This is because they indicate
-- a discontinuity, but if you don't care about the previous value, then you
-- don't need the discontinuity.
{-# SPECIALIZE drop_before :: X -> Unboxed -> Unboxed #-}
{-# INLINEABLE drop_before #-}
drop_before :: V.Vector v (Sample y) => X -> v (Sample y) -> v (Sample y)
drop_before :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> v (Sample y)
drop_before X
x v (Sample y)
vec
    | Int
i forall a. Eq a => a -> a -> Bool
== -Int
1 = v (Sample y)
vec
    | Int
i forall a. Ord a => a -> a -> Bool
< forall (v :: * -> *) a. Vector v a => v a -> Int
V.length v (Sample y)
vec = forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
V.drop Int
i v (Sample y)
vec
    | Bool
otherwise = forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
V.drop (forall (v :: * -> *) a. Vector v a => v a -> Int
V.length v (Sample y)
vec forall a. Num a => a -> a -> a
- Int
1) v (Sample y)
vec
    where i :: Int
i = forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
highest_index X
x v (Sample y)
vec

-- | The reverse of 'drop_at_after': trim a signal's head up until, but not
-- including, the given X.
drop_before_strict :: V.Vector v (Sample y) => X -> v (Sample y) -> v (Sample y)
drop_before_strict :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> v (Sample y)
drop_before_strict X
x v (Sample y)
vec = forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
V.drop (forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
bsearch_below X
x v (Sample y)
vec) v (Sample y)
vec

-- | Like 'drop_before_strict', but also drop samples at the X.
drop_before_at :: V.Vector v (Sample y) => X -> v (Sample y) -> v (Sample y)
drop_before_at :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> v (Sample y)
drop_before_at X
x = forall (v :: * -> *) a. Vector v a => (a -> Bool) -> v a -> v a
V.dropWhile ((forall a. Ord a => a -> a -> Bool
<=X
x) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall y. Sample y -> X
sx) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> v (Sample y)
drop_before_strict X
x

-- | Return samples to set the value at start and until end.  This means
-- samples start <= t < end, along with one < start if necessary to set
-- the initial value, and the end sample if start == end.
within :: V.Vector v (Sample y) => X -> X -> v (Sample y) -> v (Sample y)
within :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> X -> v (Sample y) -> v (Sample y)
within X
start X
end = (if X
start forall a. Eq a => a -> a -> Bool
== X
end then forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> v (Sample y)
drop_after X
end else forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> v (Sample y)
drop_at_after X
end)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> v (Sample y)
drop_before X
start

map_x :: V.Vector v (Sample y) => (X -> X) -> v (Sample y) -> v (Sample y)
map_x :: forall (v :: * -> *) y.
Vector v (Sample y) =>
(X -> X) -> v (Sample y) -> v (Sample y)
map_x X -> X
f = forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
V.map forall a b. (a -> b) -> a -> b
$ \(Sample X
x y
y) -> forall y. X -> y -> Sample y
Sample (X -> X
f X
x) y
y

map_y :: V.Vector v (Sample y) => (y -> y) -> v (Sample y) -> v (Sample y)
map_y :: forall (v :: * -> *) y.
Vector v (Sample y) =>
(y -> y) -> v (Sample y) -> v (Sample y)
map_y y -> y
f = forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
V.map forall a b. (a -> b) -> a -> b
$ \(Sample X
x y
y) -> forall y. X -> y -> Sample y
Sample X
x (y -> y
f y
y)

{-# SPECIALIZE map_err :: (Sample UnboxedY -> Either err (Sample UnboxedY))
    -> Unboxed -> (Unboxed, [err]) #-}
{-# INLINEABLE map_err #-}
-- | A map that can return error msgs.
map_err :: V.Vector v a => (a -> Either err a) -> v a -> (v a, [err])
map_err :: forall (v :: * -> *) a err.
Vector v a =>
(a -> Either err a) -> v a -> (v a, [err])
map_err a -> Either err a
f v a
vec = forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second forall a. [a] -> [a]
reverse forall a b. (a -> b) -> a -> b
$ forall s a. State s a -> s -> (a, s)
State.runState (forall (m :: * -> *) (v :: * -> *) a b.
(Monad m, Vector v a, Vector v b) =>
(a -> m b) -> v a -> m (v b)
V.mapM forall {m :: * -> *}. MonadState [err] m => a -> m a
go v a
vec) []
    where
    go :: a -> m a
go a
sample =
        forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either (\err
err -> forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
State.modify (err
err:) forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> forall (m :: * -> *) a. Monad m => a -> m a
return a
sample) forall (m :: * -> *) a. Monad m => a -> m a
return (a -> Either err a
f a
sample)

{-# SPECIALIZE sig_op :: UnboxedY -> (UnboxedY -> UnboxedY -> UnboxedY)
    -> Unboxed -> Unboxed -> Unboxed #-}
{-# INLINEABLE sig_op #-}
-- | Combine two vectors with the given function.  They will be resampled so
-- they have samples at the same time.
sig_op :: V.Vector v (Sample y) =>
    y -- ^ The implicit y value of a vector before its first sample.  It should
    -- probably be the identity for the operator.
    -> (y -> y -> y) -> v (Sample y) -> v (Sample y) -> v (Sample y)
sig_op :: forall (v :: * -> *) y.
Vector v (Sample y) =>
y -> (y -> y -> y) -> v (Sample y) -> v (Sample y) -> v (Sample y)
sig_op y
initial y -> y -> y
combine v (Sample y)
vec1 v (Sample y)
vec2 = forall (v :: * -> *) a b.
Vector v a =>
(b -> Maybe (a, b)) -> b -> v a
V.unfoldr (y, y, Int, Int) -> Maybe (Sample y, (y, y, Int, Int))
go (y
initial, y
initial, Int
0, Int
0)
    where
    go :: (y, y, Int, Int) -> Maybe (Sample y, (y, y, Int, Int))
go (y
prev_ay, y
prev_by, Int
i1, Int
i2) =
        case forall (v1 :: * -> *) y1 (v2 :: * -> *) y2.
(Vector v1 (Sample y1), Vector v2 (Sample y2)) =>
y1
-> y2
-> Int
-> Int
-> Int
-> Int
-> v1 (Sample y1)
-> v2 (Sample y2)
-> Maybe (X, y1, y2, Int, Int)
resample1 y
prev_ay y
prev_by Int
len1 Int
len2 Int
i1 Int
i2 v (Sample y)
vec1 v (Sample y)
vec2 of
            Maybe (X, y, y, Int, Int)
Nothing -> forall a. Maybe a
Nothing
            Just (X
x, y
ay, y
by, Int
i1, Int
i2) ->
                forall a. a -> Maybe a
Just (forall y. X -> y -> Sample y
Sample X
x (y -> y -> y
combine y
ay y
by), (y
ay, y
by, Int
i1, Int
i2))
    len1 :: Int
len1 = forall (v :: * -> *) a. Vector v a => v a -> Int
V.length v (Sample y)
vec1
    len2 :: Int
len2 = forall (v :: * -> *) a. Vector v a => v a -> Int
V.length v (Sample y)
vec2

-- | Polymorphic variant of 'sig_op'.
--
-- The signature is specialized to Boxed since you might as well use 'sig_op'
-- for Unboxed vectors.
sig_op_poly :: y1 -> y2 -> (y1 -> y2 -> y3) -> Boxed y1 -> Boxed y2 -> Boxed y3
sig_op_poly :: forall y1 y2 y3.
y1 -> y2 -> (y1 -> y2 -> y3) -> Boxed y1 -> Boxed y2 -> Boxed y3
sig_op_poly y1
initial1 y2
initial2 y1 -> y2 -> y3
combine Boxed y1
vec1 Boxed y2
vec2 =
    forall (v :: * -> *) a b.
Vector v a =>
(b -> Maybe (a, b)) -> b -> v a
V.unfoldr (y1, y2, Int, Int) -> Maybe (Sample y3, (y1, y2, Int, Int))
go (y1
initial1, y2
initial2, Int
0, Int
0)
    where
    -- Yeah I could probably make 'sig_op' a specialization of this, but can't
    -- be bothered at the moment.
    go :: (y1, y2, Int, Int) -> Maybe (Sample y3, (y1, y2, Int, Int))
go (y1
prev_ay, y2
prev_by, Int
i1, Int
i2) =
        case forall (v1 :: * -> *) y1 (v2 :: * -> *) y2.
(Vector v1 (Sample y1), Vector v2 (Sample y2)) =>
y1
-> y2
-> Int
-> Int
-> Int
-> Int
-> v1 (Sample y1)
-> v2 (Sample y2)
-> Maybe (X, y1, y2, Int, Int)
resample1 y1
prev_ay y2
prev_by Int
len1 Int
len2 Int
i1 Int
i2 Boxed y1
vec1 Boxed y2
vec2 of
            Maybe (X, y1, y2, Int, Int)
Nothing -> forall a. Maybe a
Nothing
            Just (X
x, y1
ay, y2
by, Int
i1, Int
i2) ->
                forall a. a -> Maybe a
Just (forall y. X -> y -> Sample y
Sample X
x (y1 -> y2 -> y3
combine y1
ay y2
by), (y1
ay, y2
by, Int
i1, Int
i2))
    len1 :: Int
len1 = forall (v :: * -> *) a. Vector v a => v a -> Int
V.length Boxed y1
vec1
    len2 :: Int
len2 = forall (v :: * -> *) a. Vector v a => v a -> Int
V.length Boxed y2
vec2

{-# INLINE resample1 #-}
resample1 :: (V.Vector v1 (Sample y1), V.Vector v2 (Sample y2)) => y1 -> y2
    -> Int -> Int -> Int -> Int
    -> v1 (Sample y1) -> v2 (Sample y2) -> Maybe (X, y1, y2, Int, Int)
resample1 :: forall (v1 :: * -> *) y1 (v2 :: * -> *) y2.
(Vector v1 (Sample y1), Vector v2 (Sample y2)) =>
y1
-> y2
-> Int
-> Int
-> Int
-> Int
-> v1 (Sample y1)
-> v2 (Sample y2)
-> Maybe (X, y1, y2, Int, Int)
resample1 y1
prev_ay y2
prev_by Int
len1 Int
len2 Int
i1 Int
i2 v1 (Sample y1)
vec1 v2 (Sample y2)
vec2
    | Int
i1 forall a. Ord a => a -> a -> Bool
>= Int
len1 Bool -> Bool -> Bool
&& Int
i2 forall a. Ord a => a -> a -> Bool
>= Int
len2 = forall a. Maybe a
Nothing
    | Int
i1 forall a. Ord a => a -> a -> Bool
>= Int
len1 = forall a. a -> Maybe a
Just (X
bx, y1
prev_ay, y2
by, Int
i1, Int
i2forall a. Num a => a -> a -> a
+Int
1)
    | Int
i2 forall a. Ord a => a -> a -> Bool
>= Int
len2 = forall a. a -> Maybe a
Just (X
ax, y1
ay, y2
prev_by, Int
i1forall a. Num a => a -> a -> a
+Int
1, Int
i2)
    | X
ax forall a. Eq a => a -> a -> Bool
== X
bx = forall a. a -> Maybe a
Just (X
ax, y1
ay, y2
by, Int
i1forall a. Num a => a -> a -> a
+Int
1, Int
i2forall a. Num a => a -> a -> a
+Int
1)
    | X
ax forall a. Ord a => a -> a -> Bool
< X
bx = forall a. a -> Maybe a
Just (X
ax, y1
ay, y2
prev_by, Int
i1forall a. Num a => a -> a -> a
+Int
1, Int
i2)
    | Bool
otherwise = forall a. a -> Maybe a
Just (X
bx, y1
prev_ay, y2
by, Int
i1, Int
i2forall a. Num a => a -> a -> a
+Int
1)
    where
    Sample X
ax y1
ay = forall (v :: * -> *) a. Vector v a => v a -> Int -> a
V.unsafeIndex v1 (Sample y1)
vec1 Int
i1
    Sample X
bx y2
by = forall (v :: * -> *) a. Vector v a => v a -> Int -> a
V.unsafeIndex v2 (Sample y2)
vec2 Int
i2

-- * util

{-# SPECIALIZE find_nonascending :: Unboxed -> [(X, UnboxedY)] #-}
{-# INLINEABLE find_nonascending #-}
-- | Find samples whose 'sx' is <= the previous X.
find_nonascending :: V.Vector v (Sample y) => v (Sample y) -> [(X, y)]
find_nonascending :: forall (v :: * -> *) y.
Vector v (Sample y) =>
v (Sample y) -> [(X, y)]
find_nonascending v (Sample y)
vec = case forall (v :: * -> *) a. Vector v a => v a -> Maybe (a, v a)
uncons v (Sample y)
vec of
    Maybe (Sample y, v (Sample y))
Nothing -> []
    Just (Sample y
x, v (Sample y)
xs) -> forall a b. (a -> b) -> [a] -> [b]
map forall y. Sample y -> (X, y)
to_pair forall a b. (a -> b) -> a -> b
$ forall a. [a] -> [a]
reverse forall a b. (a -> b) -> a -> b
$ forall a b. (a, b) -> b
snd forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) b a.
Vector v b =>
(a -> b -> a) -> a -> v b -> a
V.foldl' forall {y}. (X, [Sample y]) -> Sample y -> (X, [Sample y])
go (forall y. Sample y -> X
sx Sample y
x, []) v (Sample y)
xs
    where
    go :: (X, [Sample y]) -> Sample y -> (X, [Sample y])
go (X
prev, [Sample y]
acc) Sample y
s
        | forall y. Sample y -> X
sx Sample y
s forall a. Ord a => a -> a -> Bool
<= X
prev = (forall y. Sample y -> X
sx Sample y
s, Sample y
s forall a. a -> [a] -> [a]
: [Sample y]
acc)
        | Bool
otherwise = (forall y. Sample y -> X
sx Sample y
s, [Sample y]
acc)

{-# SPECIALIZE unfoldr :: (state -> Maybe ((X, UnboxedY), state)) -> state
    -> Unboxed #-}
{-# INLINEABLE unfoldr #-}
unfoldr :: V.Vector v (Sample y) => (state -> Maybe ((X, y), state)) -> state
    -> v (Sample y)
unfoldr :: forall (v :: * -> *) y state.
Vector v (Sample y) =>
(state -> Maybe ((X, y), state)) -> state -> v (Sample y)
unfoldr state -> Maybe ((X, y), state)
f = forall (v :: * -> *) a b.
Vector v a =>
(b -> Maybe (a, b)) -> b -> v a
V.unfoldr forall a b. (a -> b) -> a -> b
$ \state
st -> case state -> Maybe ((X, y), state)
f state
st of
    Maybe ((X, y), state)
Nothing -> forall a. Maybe a
Nothing
    Just ((X
x, y
y), state
next) -> forall a. a -> Maybe a
Just (forall y. X -> y -> Sample y
Sample X
x y
y, state
next)

-- | Given a line defined by the two points, find the y at the given x.
-- Crashes if called on a vertical line (y0==y1).  Yeah, it's inconsistent
-- with 'x_at'.
y_at :: CallStack.Stack => X -> Double -> X -> Double -> X -> Double
y_at :: HasCallStack => X -> UnboxedY -> X -> UnboxedY -> X -> UnboxedY
y_at X
x0 UnboxedY
y0 X
x1 UnboxedY
y1 X
x
    | X
x0 forall a. Eq a => a -> a -> Bool
== X
x1 = forall a. HasCallStack => Text -> a
errorStack forall a b. (a -> b) -> a -> b
$ Text
"y_at on vertical line: "
        forall a. Semigroup a => a -> a -> a
<> forall a. Show a => a -> Text
showt ((X
x0, UnboxedY
y0), (X
x1, UnboxedY
y1), X
x)
    | Bool
otherwise = (UnboxedY
y1 forall a. Num a => a -> a -> a
- UnboxedY
y0) forall a. Fractional a => a -> a -> a
/ X -> UnboxedY
x_to_double (X
x1 forall a. Num a => a -> a -> a
- X
x0) forall a. Num a => a -> a -> a
* X -> UnboxedY
x_to_double (X
x forall a. Num a => a -> a -> a
- X
x0) forall a. Num a => a -> a -> a
+ UnboxedY
y0

-- | Given a line defined by the two points, find the x at the given y.
x_at :: X -> Double -> X -> Double -> Double -> Maybe X
x_at :: X -> UnboxedY -> X -> UnboxedY -> UnboxedY -> Maybe X
x_at X
x0 UnboxedY
y0 X
x1 UnboxedY
y1 UnboxedY
y
    | UnboxedY
y0 forall a. Eq a => a -> a -> Bool
== UnboxedY
y1 = forall a. Maybe a
Nothing -- line is horizontal
    | Bool
otherwise = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$
        UnboxedY -> X
double_to_x (UnboxedY
y forall a. Num a => a -> a -> a
- UnboxedY
y0) forall a. Fractional a => a -> a -> a
/ (UnboxedY -> X
double_to_x (UnboxedY
y1 forall a. Num a => a -> a -> a
- UnboxedY
y0) forall a. Fractional a => a -> a -> a
/ (X
x1 forall a. Num a => a -> a -> a
- X
x0)) forall a. Num a => a -> a -> a
+ X
x0

-- | Binary search for the highest index of the given X.  So the next value is
-- guaranteed to be >X, if it exists.  Return -1 if @x@ is before
-- the first element.  'RealTime.eta' is added to @x@, so a sample that's
-- almost the same will still be considered a match.
{-# SPECIALIZE highest_index :: X -> Unboxed -> Int #-}
{-# SPECIALIZE highest_index :: X -> Boxed y -> Int #-}
{-# INLINEABLE highest_index #-}
highest_index :: V.Vector v (Sample y) => X -> v (Sample y) -> Int
highest_index :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
highest_index X
x v (Sample y)
vec
    | forall (v :: * -> *) a. Vector v a => v a -> Bool
V.null v (Sample y)
vec = -Int
1
    | Bool
otherwise = Int
i forall a. Num a => a -> a -> a
- Int
1
    where i :: Int
i = forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
bsearch_above (X
x forall a. Num a => a -> a -> a
+ X
RealTime.eta) v (Sample y)
vec

-- | 'bsearch_below', but if you use it with take, it includes the first
-- element ==x.  TODO not sure how to explain it.
{-# SPECIALIZE bsearch_below_1 :: X -> Unboxed -> Int #-}
{-# INLINEABLE bsearch_below_1 #-}
bsearch_below_1 :: V.Vector v (Sample y) => X -> v (Sample y) -> Int
bsearch_below_1 :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
bsearch_below_1 X
x v (Sample y)
vec = case v (Sample y)
vec forall (v :: * -> *) a. Vector v a => v a -> Int -> Maybe a
V.!? Int
i of
    Just Sample y
vi | forall y. Sample y -> X
sx Sample y
vi forall a. Eq a => a -> a -> Bool
== X
x -> Int
i forall a. Num a => a -> a -> a
+ Int
1
    Maybe (Sample y)
_ -> Int
i
    where i :: Int
i = forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
bsearch_below X
x v (Sample y)
vec

-- | Search for the last index <x, or -1 if the first sample is already >x.
{-# SPECIALIZE index_below :: X -> Unboxed -> Int #-}
{-# INLINEABLE index_below #-}
index_below :: V.Vector v (Sample y) => X -> v (Sample y) -> Int
index_below :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
index_below X
x v (Sample y)
vec
    | Int
i forall a. Eq a => a -> a -> Bool
== Int
0 = case v (Sample y)
vec forall (v :: * -> *) a. Vector v a => v a -> Int -> Maybe a
V.!? Int
i of
        Just (Sample X
x1 y
_) | X
x1 forall a. Eq a => a -> a -> Bool
== X
x -> Int
0
        Maybe (Sample y)
_ -> -Int
1
    | Bool
otherwise = Int
i forall a. Num a => a -> a -> a
- Int
1
    where i :: Int
i = forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
bsearch_below X
x v (Sample y)
vec

-- | Binary search for the index of the first element that is >x, or one past
-- the end of the vector.
{-# SPECIALIZE bsearch_above :: X -> Unboxed -> Int #-}
{-# SPECIALIZE bsearch_above :: X -> Boxed y -> Int #-}
{-# INLINEABLE bsearch_above #-}
bsearch_above :: V.Vector v (Sample y) => X -> v (Sample y) -> Int
bsearch_above :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
bsearch_above X
x v (Sample y)
vec = Int -> Int -> Int
go Int
0 (forall (v :: * -> *) a. Vector v a => v a -> Int
V.length v (Sample y)
vec)
    where
    go :: Int -> Int -> Int
go Int
low Int
high
        | Int
low forall a. Eq a => a -> a -> Bool
== Int
high = Int
low
        | X
x forall a. Ord a => a -> a -> Bool
>= forall y. Sample y -> X
sx (forall (v :: * -> *) a. Vector v a => v a -> Int -> a
V.unsafeIndex v (Sample y)
vec Int
mid) = Int -> Int -> Int
go (Int
midforall a. Num a => a -> a -> a
+Int
1) Int
high
        | Bool
otherwise = Int -> Int -> Int
go Int
low Int
mid
        where mid :: Int
mid = (Int
low forall a. Num a => a -> a -> a
+ Int
high) forall a. Integral a => a -> a -> a
`div` Int
2

-- | Binary search for the index of the first element ==x, or the last one <x.
-- So it will be <=x, or one past the end of the vector.  If you ues it with
-- take, it's everything <x.
{-# SPECIALIZE bsearch_below :: X -> Unboxed -> Int #-}
{-# SPECIALIZE bsearch_below :: X -> Boxed y -> Int #-}
{-# INLINEABLE bsearch_below #-}
bsearch_below :: V.Vector v (Sample y) => X -> v (Sample y) -> Int
bsearch_below :: forall (v :: * -> *) y.
Vector v (Sample y) =>
X -> v (Sample y) -> Int
bsearch_below X
x v (Sample y)
vec = Int -> Int -> Int
go Int
0 (forall (v :: * -> *) a. Vector v a => v a -> Int
V.length v (Sample y)
vec)
    where
    go :: Int -> Int -> Int
go Int
low Int
high
        | Int
low forall a. Eq a => a -> a -> Bool
== Int
high = Int
low
        | X
x forall a. Ord a => a -> a -> Bool
<= forall y. Sample y -> X
sx (forall (v :: * -> *) a. Vector v a => v a -> Int -> a
V.unsafeIndex v (Sample y)
vec Int
mid) = Int -> Int -> Int
go Int
low Int
mid
        | Bool
otherwise = Int -> Int -> Int
go (Int
midforall a. Num a => a -> a -> a
+Int
1) Int
high
        where mid :: Int
mid = (Int
low forall a. Num a => a -> a -> a
+ Int
high) forall a. Integral a => a -> a -> a
`div` Int
2