{-# language
BangPatterns
, CPP
, DeriveAnyClass
, DeriveFunctor
, DeriveGeneric
, DerivingStrategies
, InstanceSigs
, ScopedTypeVariables
, TemplateHaskell
, TypeApplications
#-}
module Data.Vector.Circular
(
CircularVector(..)
, singleton
, toVector
, toNonEmptyVector
, fromVector
, unsafeFromVector
, fromList
, fromListN
, unsafeFromList
, unsafeFromListN
, vec
, rotateLeft
, rotateRight
, equivalent
, canonise
, leastRotation
, Data.Vector.Circular.foldMap
, Data.Vector.Circular.foldMap'
, Data.Vector.Circular.foldr
, Data.Vector.Circular.foldl
, Data.Vector.Circular.foldr'
, Data.Vector.Circular.foldl'
, Data.Vector.Circular.foldr1
, Data.Vector.Circular.foldl1
, Data.Vector.Circular.foldMap1
, Data.Vector.Circular.foldMap1'
, Data.Vector.Circular.toNonEmpty
, Data.Vector.Circular.all
, Data.Vector.Circular.any
, Data.Vector.Circular.and
, Data.Vector.Circular.or
, Data.Vector.Circular.sum
, Data.Vector.Circular.product
, Data.Vector.Circular.maximum
, Data.Vector.Circular.maximumBy
, Data.Vector.Circular.minimum
, Data.Vector.Circular.minimumBy
, rotateToMinimumBy
, rotateToMaximumBy
, index
, head
, last
, Data.Vector.Circular.zipWith
, Data.Vector.Circular.zipWith3
, Data.Vector.Circular.zip
, Data.Vector.Circular.zip3
, Data.Vector.Circular.reverse
) where
import Control.Monad (when, forM_)
import Control.Monad.ST (ST, runST)
import Control.DeepSeq
#if MIN_VERSION_base(4,13,0)
import Data.Foldable (foldMap')
#endif /* MIN_VERSION_base(4,13,0) */
import Data.List.NonEmpty (NonEmpty)
import Data.Primitive.MutVar
import Data.Semigroup.Foldable.Class (Foldable1)
import Data.Monoid (All(..))
import Data.Vector (Vector)
import Data.Vector.NonEmpty (NonEmptyVector)
import GHC.Base (modInt)
import GHC.Generics (Generic)
import Prelude hiding (head, length, last)
import Language.Haskell.TH.Syntax
import qualified Data.Foldable as Foldable
import qualified Data.Semigroup.Foldable.Class as Foldable1
import qualified Data.Vector as Vector
import qualified Data.Vector.Mutable as MVector
import qualified Data.Vector.NonEmpty as NonEmpty
import qualified Prelude
data CircularVector a = CircularVector
{ CircularVector a -> NonEmptyVector a
vector :: {-# UNPACK #-} !(NonEmptyVector a)
, CircularVector a -> Int
rotation :: {-# UNPACK #-} !Int
}
deriving stock
( Functor
, Generic
, Ord
, Read
, Show
)
deriving anyclass
( NFData
)
instance Traversable CircularVector where
traverse :: (Applicative f) => (a -> f b) -> CircularVector a -> f (CircularVector b)
traverse :: (a -> f b) -> CircularVector a -> f (CircularVector b)
traverse a -> f b
f (CircularVector NonEmptyVector a
v Int
rot) =
NonEmptyVector b -> Int -> CircularVector b
forall a. NonEmptyVector a -> Int -> CircularVector a
CircularVector (NonEmptyVector b -> Int -> CircularVector b)
-> f (NonEmptyVector b) -> f (Int -> CircularVector b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> NonEmptyVector a -> f (NonEmptyVector b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f NonEmptyVector a
v f (Int -> CircularVector b) -> f Int -> f (CircularVector b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Int -> f Int
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
rot
instance Eq a => Eq (CircularVector a) where
(==) :: CircularVector a -> CircularVector a -> Bool
c0 :: CircularVector a
c0@(CircularVector NonEmptyVector a
x Int
rx) == :: CircularVector a -> CircularVector a -> Bool
== c1 :: CircularVector a
c1@(CircularVector NonEmptyVector a
y Int
ry)
| NonEmptyVector a -> Int
forall a. NonEmptyVector a -> Int
NonEmpty.length NonEmptyVector a
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= NonEmptyVector a -> Int
forall a. NonEmptyVector a -> Int
NonEmpty.length NonEmptyVector a
y = Bool
False
| Int
rx Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
ry = NonEmptyVector a
x NonEmptyVector a -> NonEmptyVector a -> Bool
forall a. Eq a => a -> a -> Bool
== NonEmptyVector a
y
| Bool
otherwise = All -> Bool
getAll (All -> Bool) -> All -> Bool
forall a b. (a -> b) -> a -> b
$ ((Int -> All) -> [Int] -> All) -> [Int] -> (Int -> All) -> All
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Int -> All) -> [Int] -> All
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
Prelude.foldMap [Int
0..NonEmptyVector a -> Int
forall a. NonEmptyVector a -> Int
NonEmpty.length NonEmptyVector a
xInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> All) -> All) -> (Int -> All) -> All
forall a b. (a -> b) -> a -> b
$ \Int
i -> Bool -> All
All (CircularVector a -> Int -> a
forall a. CircularVector a -> Int -> a
index CircularVector a
c0 Int
i a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== CircularVector a -> Int -> a
forall a. CircularVector a -> Int -> a
index CircularVector a
c1 Int
i)
instance Semigroup (CircularVector a) where
(<>) :: CircularVector a -> CircularVector a -> CircularVector a
CircularVector a
lhs <> :: CircularVector a -> CircularVector a -> CircularVector a
<> CircularVector a
rhs = NonEmptyVector a -> Int -> CircularVector a
forall a. NonEmptyVector a -> Int -> CircularVector a
CircularVector NonEmptyVector a
v Int
0
where
szLhs :: Int
szLhs = CircularVector a -> Int
forall a. CircularVector a -> Int
length CircularVector a
lhs
szRhs :: Int
szRhs = CircularVector a -> Int
forall a. CircularVector a -> Int
length CircularVector a
rhs
sz :: Int
sz = Int
szLhs Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
szRhs
v :: NonEmptyVector a
v = Vector a -> NonEmptyVector a
forall a. Vector a -> NonEmptyVector a
NonEmpty.unsafeFromVector
(Vector a -> NonEmptyVector a) -> Vector a -> NonEmptyVector a
forall a b. (a -> b) -> a -> b
$ Int -> (Int -> a) -> Vector a
forall a. Int -> (Int -> a) -> Vector a
Vector.generate Int
sz
((Int -> a) -> Vector a) -> (Int -> a) -> Vector a
forall a b. (a -> b) -> a -> b
$ \Int
ix -> if Int
ix Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
szLhs
then CircularVector a -> Int -> a
forall a. CircularVector a -> Int -> a
index CircularVector a
lhs Int
ix
else CircularVector a -> Int -> a
forall a. CircularVector a -> Int -> a
index CircularVector a
rhs (Int
ix Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
szLhs)
{-# inline (<>) #-}
instance Foldable CircularVector where
foldMap :: Monoid m => (a -> m) -> CircularVector a -> m
foldMap :: (a -> m) -> CircularVector a -> m
foldMap = (a -> m) -> CircularVector a -> m
forall m a. Monoid m => (a -> m) -> CircularVector a -> m
Data.Vector.Circular.foldMap
{-# inline foldMap #-}
#if MIN_VERSION_base(4,13,0)
foldMap' :: Monoid m => (a -> m) -> CircularVector a -> m
foldMap' :: (a -> m) -> CircularVector a -> m
foldMap' = (a -> m) -> CircularVector a -> m
forall m a. Monoid m => (a -> m) -> CircularVector a -> m
Data.Vector.Circular.foldMap'
{-# inline foldMap' #-}
#endif /* MIN_VERSION_base(4,13,0) */
null :: CircularVector a -> Bool
null :: CircularVector a -> Bool
null CircularVector a
_ = Bool
False
{-# inline null #-}
length :: CircularVector a -> Int
length :: CircularVector a -> Int
length = CircularVector a -> Int
forall a. CircularVector a -> Int
Data.Vector.Circular.length
{-# inline length #-}
instance Foldable1 CircularVector where
foldMap1 :: Semigroup m => (a -> m) -> CircularVector a -> m
foldMap1 :: (a -> m) -> CircularVector a -> m
foldMap1 = (a -> m) -> CircularVector a -> m
forall m a. Semigroup m => (a -> m) -> CircularVector a -> m
Data.Vector.Circular.foldMap1
{-# inline foldMap1 #-}
instance Lift a => Lift (CircularVector a) where
lift :: CircularVector a -> Q Exp
lift CircularVector a
c = do
Exp
v <- [|NonEmpty.toVector (vector c)|]
Exp
r <- [|rotation c|]
Exp -> Q Exp
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Exp -> Q Exp) -> Exp -> Q Exp
forall a b. (a -> b) -> a -> b
$ Name -> Exp
ConE ''CircularVector
Exp -> Exp -> Exp
`AppE` (Name -> Exp
VarE 'NonEmpty.unsafeFromVector Exp -> Exp -> Exp
`AppE` Exp
v)
Exp -> Exp -> Exp
`AppE` Exp
r
#if MIN_VERSION_template_haskell(2,16,0)
liftTyped :: CircularVector a -> Q (TExp (CircularVector a))
liftTyped = Q Exp -> Q (TExp (CircularVector a))
forall a. Q Exp -> Q (TExp a)
unsafeTExpCoerce (Q Exp -> Q (TExp (CircularVector a)))
-> (CircularVector a -> Q Exp)
-> CircularVector a
-> Q (TExp (CircularVector a))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector a -> Q Exp
forall t. Lift t => t -> Q Exp
lift
#endif /* MIN_VERSION_template_haskell(2,16,0) */
length :: CircularVector a -> Int
length :: CircularVector a -> Int
length (CircularVector NonEmptyVector a
v Int
_) = NonEmptyVector a -> Int
forall a. NonEmptyVector a -> Int
NonEmpty.length NonEmptyVector a
v
{-# inline length #-}
foldMap :: Monoid m => (a -> m) -> CircularVector a -> m
foldMap :: (a -> m) -> CircularVector a -> m
foldMap a -> m
f = \CircularVector a
v ->
let len :: Int
len = CircularVector a -> Int
forall a. CircularVector a -> Int
Data.Vector.Circular.length CircularVector a
v
go :: Int -> m
go !Int
ix
| Int
ix Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
len = a -> m
f (CircularVector a -> Int -> a
forall a. CircularVector a -> Int -> a
index CircularVector a
v Int
ix) m -> m -> m
forall a. Semigroup a => a -> a -> a
<> Int -> m
go (Int
ix Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
| Bool
otherwise = m
forall a. Monoid a => a
mempty
in Int -> m
go Int
0
{-# inline foldMap #-}
foldMap' :: Monoid m => (a -> m) -> CircularVector a -> m
foldMap' :: (a -> m) -> CircularVector a -> m
foldMap' a -> m
f = \CircularVector a
v ->
let len :: Int
len = CircularVector a -> Int
forall a. CircularVector a -> Int
Data.Vector.Circular.length CircularVector a
v
go :: Int -> m -> m
go !Int
ix !m
acc
| Int
ix Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
len = Int -> m -> m
go (Int
ix Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (m
acc m -> m -> m
forall a. Semigroup a => a -> a -> a
<> a -> m
f (CircularVector a -> Int -> a
forall a. CircularVector a -> Int -> a
index CircularVector a
v Int
ix))
| Bool
otherwise = m
acc
in Int -> m -> m
go Int
0 m
forall a. Monoid a => a
mempty
{-# inline foldMap' #-}
foldr :: (a -> b -> b) -> b -> CircularVector a -> b
foldr :: (a -> b -> b) -> b -> CircularVector a -> b
foldr = (a -> b -> b) -> b -> CircularVector a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr
foldl :: (b -> a -> b) -> b -> CircularVector a -> b
foldl :: (b -> a -> b) -> b -> CircularVector a -> b
foldl = (b -> a -> b) -> b -> CircularVector a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Foldable.foldl
foldr' :: (a -> b -> b) -> b -> CircularVector a -> b
foldr' :: (a -> b -> b) -> b -> CircularVector a -> b
foldr' = (a -> b -> b) -> b -> CircularVector a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr'
foldl' :: (b -> a -> b) -> b -> CircularVector a -> b
foldl' :: (b -> a -> b) -> b -> CircularVector a -> b
foldl' = (b -> a -> b) -> b -> CircularVector a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Foldable.foldl'
foldr1 :: (a -> a -> a) -> CircularVector a -> a
foldr1 :: (a -> a -> a) -> CircularVector a -> a
foldr1 = (a -> a -> a) -> CircularVector a -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
Foldable.foldr1
foldl1 :: (a -> a -> a) -> CircularVector a -> a
foldl1 :: (a -> a -> a) -> CircularVector a -> a
foldl1 = (a -> a -> a) -> CircularVector a -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
Foldable.foldl1
toNonEmpty :: CircularVector a -> NonEmpty a
toNonEmpty :: CircularVector a -> NonEmpty a
toNonEmpty = CircularVector a -> NonEmpty a
forall (t :: * -> *) a. Foldable1 t => t a -> NonEmpty a
Foldable1.toNonEmpty
foldMap1 :: Semigroup m => (a -> m) -> CircularVector a -> m
foldMap1 :: (a -> m) -> CircularVector a -> m
foldMap1 a -> m
f = \CircularVector a
v ->
let len :: Int
len = CircularVector a -> Int
forall a. CircularVector a -> Int
Data.Vector.Circular.length CircularVector a
v
go :: Int -> m
go !Int
ix
| Int
ix Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
lenInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1 = a -> m
f (CircularVector a -> Int -> a
forall a. CircularVector a -> Int -> a
index CircularVector a
v Int
ix) m -> m -> m
forall a. Semigroup a => a -> a -> a
<> Int -> m
go (Int
ix Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
| Bool
otherwise = a -> m
f (CircularVector a -> a
forall a. CircularVector a -> a
last CircularVector a
v)
in Int -> m
go Int
0
{-# inline foldMap1 #-}
foldMap1' :: Semigroup m => (a -> m) -> CircularVector a -> m
foldMap1' :: (a -> m) -> CircularVector a -> m
foldMap1' a -> m
f = \CircularVector a
v ->
let len :: Int
len = CircularVector a -> Int
forall a. CircularVector a -> Int
Data.Vector.Circular.length CircularVector a
v
go :: Int -> m -> m
go !Int
ix !m
acc
| Int
ix Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
len = Int -> m -> m
go (Int
ix Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (m
acc m -> m -> m
forall a. Semigroup a => a -> a -> a
<> a -> m
f (CircularVector a -> Int -> a
forall a. CircularVector a -> Int -> a
index CircularVector a
v Int
ix))
| Bool
otherwise = m
acc
in Int -> m -> m
go Int
1 (a -> m
f (CircularVector a -> a
forall a. CircularVector a -> a
head CircularVector a
v))
{-# inline foldMap1' #-}
toVector :: CircularVector a -> Vector a
toVector :: CircularVector a -> Vector a
toVector CircularVector a
v = Int -> (Int -> a) -> Vector a
forall a. Int -> (Int -> a) -> Vector a
Vector.generate (CircularVector a -> Int
forall a. CircularVector a -> Int
length CircularVector a
v) (CircularVector a -> Int -> a
forall a. CircularVector a -> Int -> a
index CircularVector a
v)
toNonEmptyVector :: CircularVector a -> NonEmptyVector a
toNonEmptyVector :: CircularVector a -> NonEmptyVector a
toNonEmptyVector CircularVector a
v = Int -> (Int -> a) -> NonEmptyVector a
forall a. Int -> (Int -> a) -> NonEmptyVector a
NonEmpty.generate1 (CircularVector a -> Int
forall a. CircularVector a -> Int
length CircularVector a
v) (CircularVector a -> Int -> a
forall a. CircularVector a -> Int -> a
index CircularVector a
v)
fromVector :: NonEmptyVector a -> CircularVector a
fromVector :: NonEmptyVector a -> CircularVector a
fromVector NonEmptyVector a
v = NonEmptyVector a -> Int -> CircularVector a
forall a. NonEmptyVector a -> Int -> CircularVector a
CircularVector NonEmptyVector a
v Int
0
{-# inline fromVector #-}
unsafeFromVector :: Vector a -> CircularVector a
unsafeFromVector :: Vector a -> CircularVector a
unsafeFromVector = NonEmptyVector a -> CircularVector a
forall a. NonEmptyVector a -> CircularVector a
fromVector (NonEmptyVector a -> CircularVector a)
-> (Vector a -> NonEmptyVector a) -> Vector a -> CircularVector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector a -> NonEmptyVector a
forall a. Vector a -> NonEmptyVector a
NonEmpty.unsafeFromVector
fromList :: [a] -> Maybe (CircularVector a)
fromList :: [a] -> Maybe (CircularVector a)
fromList [a]
xs = Int -> [a] -> Maybe (CircularVector a)
forall a. Int -> [a] -> Maybe (CircularVector a)
fromListN ([a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
Prelude.length [a]
xs) [a]
xs
{-# inline fromList #-}
fromListN :: Int -> [a] -> Maybe (CircularVector a)
fromListN :: Int -> [a] -> Maybe (CircularVector a)
fromListN Int
n [a]
xs = NonEmptyVector a -> CircularVector a
forall a. NonEmptyVector a -> CircularVector a
fromVector (NonEmptyVector a -> CircularVector a)
-> Maybe (NonEmptyVector a) -> Maybe (CircularVector a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Int -> [a] -> Maybe (NonEmptyVector a)
forall a. Int -> [a] -> Maybe (NonEmptyVector a)
NonEmpty.fromListN Int
n [a]
xs)
{-# inline fromListN #-}
unsafeFromList :: [a] -> CircularVector a
unsafeFromList :: [a] -> CircularVector a
unsafeFromList [a]
xs = Int -> [a] -> CircularVector a
forall a. Int -> [a] -> CircularVector a
unsafeFromListN ([a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
Prelude.length [a]
xs) [a]
xs
unsafeFromListN :: Int -> [a] -> CircularVector a
unsafeFromListN :: Int -> [a] -> CircularVector a
unsafeFromListN Int
n [a]
xs
| Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = String -> CircularVector a
forall a. HasCallStack => String -> a
error String
"Data.Vector.Circular.unsafeFromListN: invalid length!"
| Bool
otherwise = Vector a -> CircularVector a
forall a. Vector a -> CircularVector a
unsafeFromVector (Int -> [a] -> Vector a
forall a. Int -> [a] -> Vector a
Vector.fromListN Int
n [a]
xs)
singleton :: a -> CircularVector a
singleton :: a -> CircularVector a
singleton = NonEmptyVector a -> CircularVector a
forall a. NonEmptyVector a -> CircularVector a
fromVector (NonEmptyVector a -> CircularVector a)
-> (a -> NonEmptyVector a) -> a -> CircularVector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> NonEmptyVector a
forall a. a -> NonEmptyVector a
NonEmpty.singleton
{-# inline singleton #-}
index :: CircularVector a -> Int -> a
index :: CircularVector a -> Int -> a
index (CircularVector NonEmptyVector a
v Int
r) = \ !Int
ix ->
let len :: Int
len = NonEmptyVector a -> Int
forall a. NonEmptyVector a -> Int
NonEmpty.length NonEmptyVector a
v
in NonEmptyVector a -> Int -> a
forall a. NonEmptyVector a -> Int -> a
NonEmpty.unsafeIndex NonEmptyVector a
v (Int -> Int -> Int
unsafeMod (Int
ix Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
r) Int
len)
{-# inline index #-}
head :: CircularVector a -> a
head :: CircularVector a -> a
head CircularVector a
v = CircularVector a -> Int -> a
forall a. CircularVector a -> Int -> a
index CircularVector a
v Int
0
{-# inline head #-}
last :: CircularVector a -> a
last :: CircularVector a -> a
last CircularVector a
v = CircularVector a -> Int -> a
forall a. CircularVector a -> Int -> a
index CircularVector a
v (CircularVector a -> Int
forall a. CircularVector a -> Int
Data.Vector.Circular.length CircularVector a
v Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
{-# inline last #-}
rotateRight :: Int -> CircularVector a -> CircularVector a
rotateRight :: Int -> CircularVector a -> CircularVector a
rotateRight Int
r' (CircularVector NonEmptyVector a
v Int
r) = NonEmptyVector a -> Int -> CircularVector a
forall a. NonEmptyVector a -> Int -> CircularVector a
CircularVector NonEmptyVector a
v Int
h
where
len :: Int
len = NonEmptyVector a -> Int
forall a. NonEmptyVector a -> Int
NonEmpty.length NonEmptyVector a
v
h :: Int
h = Int -> Int -> Int
unsafeMod (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int -> Int
unsafeMod Int
r' Int
len) Int
len
{-# inline rotateRight #-}
rotateLeft :: Int -> CircularVector a -> CircularVector a
rotateLeft :: Int -> CircularVector a -> CircularVector a
rotateLeft Int
r' (CircularVector NonEmptyVector a
v Int
r) = NonEmptyVector a -> Int -> CircularVector a
forall a. NonEmptyVector a -> Int -> CircularVector a
CircularVector NonEmptyVector a
v Int
h
where
len :: Int
len = NonEmptyVector a -> Int
forall a. NonEmptyVector a -> Int
NonEmpty.length NonEmptyVector a
v
h :: Int
h = Int -> Int -> Int
unsafeMod (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int -> Int -> Int
unsafeMod Int
r' Int
len) Int
len
{-# inline rotateLeft #-}
vec :: Lift a => [a] -> Q (TExp (CircularVector a))
vec :: [a] -> Q (TExp (CircularVector a))
vec [] = String -> Q (TExp (CircularVector a))
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"Cannot create an empty CircularVector!"
vec [a]
xs =
#if MIN_VERSION_template_haskell(2,16,0)
CircularVector a -> Q (TExp (CircularVector a))
forall t. Lift t => t -> Q (TExp t)
liftTyped ([a] -> CircularVector a
forall a. [a] -> CircularVector a
unsafeFromList [a]
xs)
#else
unsafeTExpCoerce [|unsafeFromList xs|]
#endif /* MIN_VERSION_template_haskell(2,16,0) */
equivalent :: Ord a => CircularVector a -> CircularVector a -> Bool
equivalent :: CircularVector a -> CircularVector a -> Bool
equivalent CircularVector a
x CircularVector a
y = CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
vector (CircularVector a -> CircularVector a
forall a. Ord a => CircularVector a -> CircularVector a
canonise CircularVector a
x) NonEmptyVector a -> NonEmptyVector a -> Bool
forall a. Eq a => a -> a -> Bool
== CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
vector (CircularVector a -> CircularVector a
forall a. Ord a => CircularVector a -> CircularVector a
canonise CircularVector a
y)
canonise :: Ord a => CircularVector a -> CircularVector a
canonise :: CircularVector a -> CircularVector a
canonise (CircularVector NonEmptyVector a
v Int
r) = NonEmptyVector a -> Int -> CircularVector a
forall a. NonEmptyVector a -> Int -> CircularVector a
CircularVector NonEmptyVector a
v' (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
lr)
where
lr :: Int
lr = Vector a -> Int
forall a. Ord a => Vector a -> Int
leastRotation (NonEmptyVector a -> Vector a
forall a. NonEmptyVector a -> Vector a
NonEmpty.toVector NonEmptyVector a
v)
v' :: NonEmptyVector a
v' = CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
toNonEmptyVector (Int -> CircularVector a -> CircularVector a
forall a. Int -> CircularVector a -> CircularVector a
rotateRight Int
lr (NonEmptyVector a -> Int -> CircularVector a
forall a. NonEmptyVector a -> Int -> CircularVector a
CircularVector NonEmptyVector a
v Int
0))
leastRotation :: forall a. (Ord a) => Vector a -> Int
leastRotation :: Vector a -> Int
leastRotation Vector a
v = (forall s. ST s Int) -> Int
forall a. (forall s. ST s a) -> a
runST forall s. ST s Int
go
where
go :: forall s. ST s Int
go :: ST s Int
go = do
let s :: Vector a
s = Vector a
v Vector a -> Vector a -> Vector a
forall a. Semigroup a => a -> a -> a
<> Vector a
v
let len :: Int
len = Vector a -> Int
forall a. Vector a -> Int
Vector.length Vector a
s
MVector s Int
f <- Int -> Int -> ST s (MVector (PrimState (ST s)) Int)
forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (MVector (PrimState m) a)
MVector.replicate @_ @Int Int
len (-Int
1)
MutVar s Int
kVar <- Int -> ST s (MutVar (PrimState (ST s)) Int)
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar @_ @Int Int
0
[Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
1..Int
lenInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
j -> do
a
sj <- Vector a -> Int -> ST s a
forall (m :: * -> *) a. Monad m => Vector a -> Int -> m a
Vector.indexM Vector a
s Int
j
Int
i0 <- MutVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s Int
MutVar (PrimState (ST s)) Int
kVar ST s Int -> (Int -> ST s Int) -> ST s Int
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \Int
k -> MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> m a
MVector.read MVector s Int
MVector (PrimState (ST s)) Int
f (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
let loop :: Int -> ST s Int
loop Int
i = do
a
a <- MutVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s Int
MutVar (PrimState (ST s)) Int
kVar ST s Int -> (Int -> ST s a) -> ST s a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \Int
k -> Vector a -> Int -> ST s a
forall (m :: * -> *) a. Monad m => Vector a -> Int -> m a
Vector.indexM Vector a
s (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
if (Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= (-Int
1) Bool -> Bool -> Bool
&& a
sj a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
a)
then do
Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (a
sj a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
a) (MutVar (PrimState (ST s)) Int -> Int -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar s Int
MutVar (PrimState (ST s)) Int
kVar (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1))
Int -> ST s Int
loop (Int -> ST s Int) -> ST s Int -> ST s Int
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> m a
MVector.read MVector s Int
MVector (PrimState (ST s)) Int
f Int
i
else Int -> ST s Int
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
i
Int
i <- Int -> ST s Int
loop Int
i0
a
a <- MutVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s Int
MutVar (PrimState (ST s)) Int
kVar ST s Int -> (Int -> ST s a) -> ST s a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \Int
k -> Vector a -> Int -> ST s a
forall (m :: * -> *) a. Monad m => Vector a -> Int -> m a
Vector.indexM Vector a
s (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
if a
sj a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
a
then do
MutVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s Int
MutVar (PrimState (ST s)) Int
kVar ST s Int -> (Int -> ST s ()) -> ST s ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \Int
k -> Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (a
sj a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< (Vector a
s Vector a -> Int -> a
forall a. Vector a -> Int -> a
Vector.! Int
k)) (MutVar (PrimState (ST s)) Int -> Int -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar s Int
MutVar (PrimState (ST s)) Int
kVar Int
j)
MutVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s Int
MutVar (PrimState (ST s)) Int
kVar ST s Int -> (Int -> ST s ()) -> ST s ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \Int
k -> MVector (PrimState (ST s)) Int -> Int -> Int -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> a -> m ()
MVector.write MVector s Int
MVector (PrimState (ST s)) Int
f (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
k) (-Int
1)
else do
MutVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s Int
MutVar (PrimState (ST s)) Int
kVar ST s Int -> (Int -> ST s ()) -> ST s ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \Int
k -> MVector (PrimState (ST s)) Int -> Int -> Int -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> a -> m ()
MVector.write MVector s Int
MVector (PrimState (ST s)) Int
f (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
k) (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
MutVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s Int
MutVar (PrimState (ST s)) Int
kVar
unsafeMod :: Int -> Int -> Int
unsafeMod :: Int -> Int -> Int
unsafeMod = Int -> Int -> Int
GHC.Base.modInt
{-# inline unsafeMod #-}
zipWith :: (a -> b -> c) -> CircularVector a -> CircularVector b -> CircularVector c
zipWith :: (a -> b -> c)
-> CircularVector a -> CircularVector b -> CircularVector c
zipWith a -> b -> c
f CircularVector a
a CircularVector b
b = NonEmptyVector c -> CircularVector c
forall a. NonEmptyVector a -> CircularVector a
fromVector (NonEmptyVector c -> CircularVector c)
-> NonEmptyVector c -> CircularVector c
forall a b. (a -> b) -> a -> b
$ (a -> b -> c)
-> NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c
forall a b c.
(a -> b -> c)
-> NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c
NonEmpty.zipWith a -> b -> c
f (CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
toNonEmptyVector CircularVector a
a) (CircularVector b -> NonEmptyVector b
forall a. CircularVector a -> NonEmptyVector a
toNonEmptyVector CircularVector b
b)
zipWith3 :: (a -> b -> c -> d) -> CircularVector a -> CircularVector b -> CircularVector c
-> CircularVector d
zipWith3 :: (a -> b -> c -> d)
-> CircularVector a
-> CircularVector b
-> CircularVector c
-> CircularVector d
zipWith3 a -> b -> c -> d
f CircularVector a
a CircularVector b
b CircularVector c
c = NonEmptyVector d -> CircularVector d
forall a. NonEmptyVector a -> CircularVector a
fromVector (NonEmptyVector d -> CircularVector d)
-> NonEmptyVector d -> CircularVector d
forall a b. (a -> b) -> a -> b
$
(a -> b -> c -> d)
-> NonEmptyVector a
-> NonEmptyVector b
-> NonEmptyVector c
-> NonEmptyVector d
forall a b c d.
(a -> b -> c -> d)
-> NonEmptyVector a
-> NonEmptyVector b
-> NonEmptyVector c
-> NonEmptyVector d
NonEmpty.zipWith3 a -> b -> c -> d
f (CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
toNonEmptyVector CircularVector a
a) (CircularVector b -> NonEmptyVector b
forall a. CircularVector a -> NonEmptyVector a
toNonEmptyVector CircularVector b
b) (CircularVector c -> NonEmptyVector c
forall a. CircularVector a -> NonEmptyVector a
toNonEmptyVector CircularVector c
c)
zip :: CircularVector a -> CircularVector b -> CircularVector (a,b)
zip :: CircularVector a -> CircularVector b -> CircularVector (a, b)
zip CircularVector a
a CircularVector b
b = NonEmptyVector (a, b) -> CircularVector (a, b)
forall a. NonEmptyVector a -> CircularVector a
fromVector (NonEmptyVector (a, b) -> CircularVector (a, b))
-> NonEmptyVector (a, b) -> CircularVector (a, b)
forall a b. (a -> b) -> a -> b
$ NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector (a, b)
forall a b.
NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector (a, b)
NonEmpty.zip (CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
toNonEmptyVector CircularVector a
a) (CircularVector b -> NonEmptyVector b
forall a. CircularVector a -> NonEmptyVector a
toNonEmptyVector CircularVector b
b)
zip3 :: CircularVector a -> CircularVector b -> CircularVector c -> CircularVector (a,b,c)
zip3 :: CircularVector a
-> CircularVector b -> CircularVector c -> CircularVector (a, b, c)
zip3 CircularVector a
a CircularVector b
b CircularVector c
c = NonEmptyVector (a, b, c) -> CircularVector (a, b, c)
forall a. NonEmptyVector a -> CircularVector a
fromVector (NonEmptyVector (a, b, c) -> CircularVector (a, b, c))
-> NonEmptyVector (a, b, c) -> CircularVector (a, b, c)
forall a b. (a -> b) -> a -> b
$ NonEmptyVector a
-> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector (a, b, c)
forall a b c.
NonEmptyVector a
-> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector (a, b, c)
NonEmpty.zip3 (CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
toNonEmptyVector CircularVector a
a) (CircularVector b -> NonEmptyVector b
forall a. CircularVector a -> NonEmptyVector a
toNonEmptyVector CircularVector b
b) (CircularVector c -> NonEmptyVector c
forall a. CircularVector a -> NonEmptyVector a
toNonEmptyVector CircularVector c
c)
reverse :: CircularVector a -> CircularVector a
reverse :: CircularVector a -> CircularVector a
reverse = NonEmptyVector a -> CircularVector a
forall a. NonEmptyVector a -> CircularVector a
fromVector (NonEmptyVector a -> CircularVector a)
-> (CircularVector a -> NonEmptyVector a)
-> CircularVector a
-> CircularVector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmptyVector a -> NonEmptyVector a
forall a. NonEmptyVector a -> NonEmptyVector a
NonEmpty.reverse (NonEmptyVector a -> NonEmptyVector a)
-> (CircularVector a -> NonEmptyVector a)
-> CircularVector a
-> NonEmptyVector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
toNonEmptyVector
rotateToMinimumBy :: (a -> a -> Ordering) -> CircularVector a -> CircularVector a
rotateToMinimumBy :: (a -> a -> Ordering) -> CircularVector a -> CircularVector a
rotateToMinimumBy a -> a -> Ordering
f (CircularVector NonEmptyVector a
v Int
_rot) =
NonEmptyVector a -> Int -> CircularVector a
forall a. NonEmptyVector a -> Int -> CircularVector a
CircularVector NonEmptyVector a
v ((a -> a -> Ordering) -> NonEmptyVector a -> Int
forall a. (a -> a -> Ordering) -> NonEmptyVector a -> Int
NonEmpty.minIndexBy a -> a -> Ordering
f NonEmptyVector a
v)
rotateToMaximumBy :: (a -> a -> Ordering) -> CircularVector a -> CircularVector a
rotateToMaximumBy :: (a -> a -> Ordering) -> CircularVector a -> CircularVector a
rotateToMaximumBy a -> a -> Ordering
f (CircularVector NonEmptyVector a
v Int
_rot) =
NonEmptyVector a -> Int -> CircularVector a
forall a. NonEmptyVector a -> Int -> CircularVector a
CircularVector NonEmptyVector a
v ((a -> a -> Ordering) -> NonEmptyVector a -> Int
forall a. (a -> a -> Ordering) -> NonEmptyVector a -> Int
NonEmpty.maxIndexBy a -> a -> Ordering
f NonEmptyVector a
v)
all :: (a -> Bool) -> CircularVector a -> Bool
all :: (a -> Bool) -> CircularVector a -> Bool
all a -> Bool
f = (a -> Bool) -> NonEmptyVector a -> Bool
forall a. (a -> Bool) -> NonEmptyVector a -> Bool
NonEmpty.all a -> Bool
f (NonEmptyVector a -> Bool)
-> (CircularVector a -> NonEmptyVector a)
-> CircularVector a
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
vector
any :: (a -> Bool) -> CircularVector a -> Bool
any :: (a -> Bool) -> CircularVector a -> Bool
any a -> Bool
f = (a -> Bool) -> NonEmptyVector a -> Bool
forall a. (a -> Bool) -> NonEmptyVector a -> Bool
NonEmpty.any a -> Bool
f (NonEmptyVector a -> Bool)
-> (CircularVector a -> NonEmptyVector a)
-> CircularVector a
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
vector
and :: CircularVector Bool -> Bool
and :: CircularVector Bool -> Bool
and = NonEmptyVector Bool -> Bool
NonEmpty.and (NonEmptyVector Bool -> Bool)
-> (CircularVector Bool -> NonEmptyVector Bool)
-> CircularVector Bool
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector Bool -> NonEmptyVector Bool
forall a. CircularVector a -> NonEmptyVector a
vector
or :: CircularVector Bool -> Bool
or :: CircularVector Bool -> Bool
or = NonEmptyVector Bool -> Bool
NonEmpty.or (NonEmptyVector Bool -> Bool)
-> (CircularVector Bool -> NonEmptyVector Bool)
-> CircularVector Bool
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector Bool -> NonEmptyVector Bool
forall a. CircularVector a -> NonEmptyVector a
vector
sum :: Num a => CircularVector a -> a
sum :: CircularVector a -> a
sum = NonEmptyVector a -> a
forall a. Num a => NonEmptyVector a -> a
NonEmpty.sum (NonEmptyVector a -> a)
-> (CircularVector a -> NonEmptyVector a) -> CircularVector a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
vector
product :: Num a => CircularVector a -> a
product :: CircularVector a -> a
product = NonEmptyVector a -> a
forall a. Num a => NonEmptyVector a -> a
NonEmpty.sum (NonEmptyVector a -> a)
-> (CircularVector a -> NonEmptyVector a) -> CircularVector a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
vector
maximum :: Ord a => CircularVector a -> a
maximum :: CircularVector a -> a
maximum = NonEmptyVector a -> a
forall a. Ord a => NonEmptyVector a -> a
NonEmpty.maximum (NonEmptyVector a -> a)
-> (CircularVector a -> NonEmptyVector a) -> CircularVector a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
vector
maximumBy :: (a -> a -> Ordering) -> CircularVector a -> a
maximumBy :: (a -> a -> Ordering) -> CircularVector a -> a
maximumBy a -> a -> Ordering
f = (a -> a -> Ordering) -> NonEmptyVector a -> a
forall a. (a -> a -> Ordering) -> NonEmptyVector a -> a
NonEmpty.maximumBy a -> a -> Ordering
f (NonEmptyVector a -> a)
-> (CircularVector a -> NonEmptyVector a) -> CircularVector a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
vector
minimum :: Ord a => CircularVector a -> a
minimum :: CircularVector a -> a
minimum = NonEmptyVector a -> a
forall a. Ord a => NonEmptyVector a -> a
NonEmpty.minimum (NonEmptyVector a -> a)
-> (CircularVector a -> NonEmptyVector a) -> CircularVector a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
vector
minimumBy :: (a -> a -> Ordering) -> CircularVector a -> a
minimumBy :: (a -> a -> Ordering) -> CircularVector a -> a
minimumBy a -> a -> Ordering
f = (a -> a -> Ordering) -> NonEmptyVector a -> a
forall a. (a -> a -> Ordering) -> NonEmptyVector a -> a
NonEmpty.minimumBy a -> a -> Ordering
f (NonEmptyVector a -> a)
-> (CircularVector a -> NonEmptyVector a) -> CircularVector a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector a -> NonEmptyVector a
forall a. CircularVector a -> NonEmptyVector a
vector