{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE QuantifiedConstraints #-}
--------------------------------------------------------------------------------
-- |
-- Module      :  HGeometry.Cyclic
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
--
-- Representing Cyclic Sequences
--
--------------------------------------------------------------------------------
module HGeometry.Cyclic
  ( Cyclic(..)
  , HasDirectedTraversals(..)
  , ShiftedEq(..)
  ) where

--------------------------------------------------------------------------------

import           Control.DeepSeq (NFData)
import           Control.Lens
import           Control.Monad (forM_)
import           Data.Aeson
import qualified Data.Foldable as F
import           Data.Functor.Apply (Apply, (<.*>), MaybeApply(..))
import qualified Data.List.NonEmpty as NonEmpty
import           Data.Maybe (isJust)
import           Data.Semigroup.Foldable
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV
import qualified Data.Vector.NonEmpty as NV
import           GHC.Generics (Generic)
import           HGeometry.Foldable.Util
import           HGeometry.Sequence.NonEmpty
import           HGeometry.StringSearch.KMP (isSubStringOf)
import           HGeometry.Vector.NonEmpty.Util ()

--------------------------------------------------------------------------------

-- | A cyclic sequence type
newtype Cyclic v a = Cyclic (v a)
 deriving newtype ((forall a b. (a -> b) -> Cyclic v a -> Cyclic v b)
-> (forall a b. a -> Cyclic v b -> Cyclic v a)
-> Functor (Cyclic v)
forall a b. a -> Cyclic v b -> Cyclic v a
forall a b. (a -> b) -> Cyclic v a -> Cyclic v b
forall (v :: * -> *) a b.
Functor v =>
a -> Cyclic v b -> Cyclic v a
forall (v :: * -> *) a b.
Functor v =>
(a -> b) -> Cyclic v a -> Cyclic v b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall (v :: * -> *) a b.
Functor v =>
(a -> b) -> Cyclic v a -> Cyclic v b
fmap :: forall a b. (a -> b) -> Cyclic v a -> Cyclic v b
$c<$ :: forall (v :: * -> *) a b.
Functor v =>
a -> Cyclic v b -> Cyclic v a
<$ :: forall a b. a -> Cyclic v b -> Cyclic v a
Functor,(forall m. Monoid m => Cyclic v m -> m)
-> (forall m a. Monoid m => (a -> m) -> Cyclic v a -> m)
-> (forall m a. Monoid m => (a -> m) -> Cyclic v a -> m)
-> (forall a b. (a -> b -> b) -> b -> Cyclic v a -> b)
-> (forall a b. (a -> b -> b) -> b -> Cyclic v a -> b)
-> (forall b a. (b -> a -> b) -> b -> Cyclic v a -> b)
-> (forall b a. (b -> a -> b) -> b -> Cyclic v a -> b)
-> (forall a. (a -> a -> a) -> Cyclic v a -> a)
-> (forall a. (a -> a -> a) -> Cyclic v a -> a)
-> (forall a. Cyclic v a -> [a])
-> (forall a. Cyclic v a -> Bool)
-> (forall a. Cyclic v a -> Int)
-> (forall a. Eq a => a -> Cyclic v a -> Bool)
-> (forall a. Ord a => Cyclic v a -> a)
-> (forall a. Ord a => Cyclic v a -> a)
-> (forall a. Num a => Cyclic v a -> a)
-> (forall a. Num a => Cyclic v a -> a)
-> Foldable (Cyclic v)
forall a. Eq a => a -> Cyclic v a -> Bool
forall a. Num a => Cyclic v a -> a
forall a. Ord a => Cyclic v a -> a
forall m. Monoid m => Cyclic v m -> m
forall a. Cyclic v a -> Bool
forall a. Cyclic v a -> Int
forall a. Cyclic v a -> [a]
forall a. (a -> a -> a) -> Cyclic v a -> a
forall m a. Monoid m => (a -> m) -> Cyclic v a -> m
forall b a. (b -> a -> b) -> b -> Cyclic v a -> b
forall a b. (a -> b -> b) -> b -> Cyclic v a -> b
forall (v :: * -> *) a.
(Foldable v, Eq a) =>
a -> Cyclic v a -> Bool
forall (v :: * -> *) a. (Foldable v, Num a) => Cyclic v a -> a
forall (v :: * -> *) a. (Foldable v, Ord a) => Cyclic v a -> a
forall (v :: * -> *) m. (Foldable v, Monoid m) => Cyclic v m -> m
forall (v :: * -> *) a. Foldable v => Cyclic v a -> Bool
forall (v :: * -> *) a. Foldable v => Cyclic v a -> Int
forall (v :: * -> *) a. Foldable v => Cyclic v a -> [a]
forall (v :: * -> *) a.
Foldable v =>
(a -> a -> a) -> Cyclic v a -> a
forall (v :: * -> *) m a.
(Foldable v, Monoid m) =>
(a -> m) -> Cyclic v a -> m
forall (v :: * -> *) b a.
Foldable v =>
(b -> a -> b) -> b -> Cyclic v a -> b
forall (v :: * -> *) a b.
Foldable v =>
(a -> b -> b) -> b -> Cyclic v a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall (v :: * -> *) m. (Foldable v, Monoid m) => Cyclic v m -> m
fold :: forall m. Monoid m => Cyclic v m -> m
$cfoldMap :: forall (v :: * -> *) m a.
(Foldable v, Monoid m) =>
(a -> m) -> Cyclic v a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Cyclic v a -> m
$cfoldMap' :: forall (v :: * -> *) m a.
(Foldable v, Monoid m) =>
(a -> m) -> Cyclic v a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> Cyclic v a -> m
$cfoldr :: forall (v :: * -> *) a b.
Foldable v =>
(a -> b -> b) -> b -> Cyclic v a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Cyclic v a -> b
$cfoldr' :: forall (v :: * -> *) a b.
Foldable v =>
(a -> b -> b) -> b -> Cyclic v a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Cyclic v a -> b
$cfoldl :: forall (v :: * -> *) b a.
Foldable v =>
(b -> a -> b) -> b -> Cyclic v a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Cyclic v a -> b
$cfoldl' :: forall (v :: * -> *) b a.
Foldable v =>
(b -> a -> b) -> b -> Cyclic v a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> Cyclic v a -> b
$cfoldr1 :: forall (v :: * -> *) a.
Foldable v =>
(a -> a -> a) -> Cyclic v a -> a
foldr1 :: forall a. (a -> a -> a) -> Cyclic v a -> a
$cfoldl1 :: forall (v :: * -> *) a.
Foldable v =>
(a -> a -> a) -> Cyclic v a -> a
foldl1 :: forall a. (a -> a -> a) -> Cyclic v a -> a
$ctoList :: forall (v :: * -> *) a. Foldable v => Cyclic v a -> [a]
toList :: forall a. Cyclic v a -> [a]
$cnull :: forall (v :: * -> *) a. Foldable v => Cyclic v a -> Bool
null :: forall a. Cyclic v a -> Bool
$clength :: forall (v :: * -> *) a. Foldable v => Cyclic v a -> Int
length :: forall a. Cyclic v a -> Int
$celem :: forall (v :: * -> *) a.
(Foldable v, Eq a) =>
a -> Cyclic v a -> Bool
elem :: forall a. Eq a => a -> Cyclic v a -> Bool
$cmaximum :: forall (v :: * -> *) a. (Foldable v, Ord a) => Cyclic v a -> a
maximum :: forall a. Ord a => Cyclic v a -> a
$cminimum :: forall (v :: * -> *) a. (Foldable v, Ord a) => Cyclic v a -> a
minimum :: forall a. Ord a => Cyclic v a -> a
$csum :: forall (v :: * -> *) a. (Foldable v, Num a) => Cyclic v a -> a
sum :: forall a. Num a => Cyclic v a -> a
$cproduct :: forall (v :: * -> *) a. (Foldable v, Num a) => Cyclic v a -> a
product :: forall a. Num a => Cyclic v a -> a
Foldable,Foldable (Cyclic v)
Foldable (Cyclic v) =>
(forall m. Semigroup m => Cyclic v m -> m)
-> (forall m a. Semigroup m => (a -> m) -> Cyclic v a -> m)
-> (forall m a. Semigroup m => (a -> m) -> Cyclic v a -> m)
-> (forall a. Cyclic v a -> NonEmpty a)
-> (forall a. Ord a => Cyclic v a -> a)
-> (forall a. Ord a => Cyclic v a -> a)
-> (forall a. Cyclic v a -> a)
-> (forall a. Cyclic v a -> a)
-> (forall a b. (a -> b) -> (a -> b -> b) -> Cyclic v a -> b)
-> (forall a b. (a -> b) -> (b -> a -> b) -> Cyclic v a -> b)
-> (forall a b. (a -> b) -> (b -> a -> b) -> Cyclic v a -> b)
-> (forall a b. (a -> b) -> (a -> b -> b) -> Cyclic v a -> b)
-> Foldable1 (Cyclic v)
forall a. Ord a => Cyclic v a -> a
forall m. Semigroup m => Cyclic v m -> m
forall a. Cyclic v a -> a
forall a. Cyclic v a -> NonEmpty a
forall m a. Semigroup m => (a -> m) -> Cyclic v a -> m
forall a b. (a -> b) -> (a -> b -> b) -> Cyclic v a -> b
forall a b. (a -> b) -> (b -> a -> b) -> Cyclic v a -> b
forall (t :: * -> *).
Foldable t =>
(forall m. Semigroup m => t m -> m)
-> (forall m a. Semigroup m => (a -> m) -> t a -> m)
-> (forall m a. Semigroup m => (a -> m) -> t a -> m)
-> (forall a. t a -> NonEmpty a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. t a -> a)
-> (forall a. t a -> a)
-> (forall a b. (a -> b) -> (a -> b -> b) -> t a -> b)
-> (forall a b. (a -> b) -> (b -> a -> b) -> t a -> b)
-> (forall a b. (a -> b) -> (b -> a -> b) -> t a -> b)
-> (forall a b. (a -> b) -> (a -> b -> b) -> t a -> b)
-> Foldable1 t
forall (v :: * -> *). Foldable1 v => Foldable (Cyclic v)
forall (v :: * -> *) a. (Foldable1 v, Ord a) => Cyclic v a -> a
forall (v :: * -> *) m.
(Foldable1 v, Semigroup m) =>
Cyclic v m -> m
forall (v :: * -> *) a. Foldable1 v => Cyclic v a -> a
forall (v :: * -> *) a. Foldable1 v => Cyclic v a -> NonEmpty a
forall (v :: * -> *) m a.
(Foldable1 v, Semigroup m) =>
(a -> m) -> Cyclic v a -> m
forall (v :: * -> *) a b.
Foldable1 v =>
(a -> b) -> (a -> b -> b) -> Cyclic v a -> b
forall (v :: * -> *) a b.
Foldable1 v =>
(a -> b) -> (b -> a -> b) -> Cyclic v a -> b
$cfold1 :: forall (v :: * -> *) m.
(Foldable1 v, Semigroup m) =>
Cyclic v m -> m
fold1 :: forall m. Semigroup m => Cyclic v m -> m
$cfoldMap1 :: forall (v :: * -> *) m a.
(Foldable1 v, Semigroup m) =>
(a -> m) -> Cyclic v a -> m
foldMap1 :: forall m a. Semigroup m => (a -> m) -> Cyclic v a -> m
$cfoldMap1' :: forall (v :: * -> *) m a.
(Foldable1 v, Semigroup m) =>
(a -> m) -> Cyclic v a -> m
foldMap1' :: forall m a. Semigroup m => (a -> m) -> Cyclic v a -> m
$ctoNonEmpty :: forall (v :: * -> *) a. Foldable1 v => Cyclic v a -> NonEmpty a
toNonEmpty :: forall a. Cyclic v a -> NonEmpty a
$cmaximum :: forall (v :: * -> *) a. (Foldable1 v, Ord a) => Cyclic v a -> a
maximum :: forall a. Ord a => Cyclic v a -> a
$cminimum :: forall (v :: * -> *) a. (Foldable1 v, Ord a) => Cyclic v a -> a
minimum :: forall a. Ord a => Cyclic v a -> a
$chead :: forall (v :: * -> *) a. Foldable1 v => Cyclic v a -> a
head :: forall a. Cyclic v a -> a
$clast :: forall (v :: * -> *) a. Foldable1 v => Cyclic v a -> a
last :: forall a. Cyclic v a -> a
$cfoldrMap1 :: forall (v :: * -> *) a b.
Foldable1 v =>
(a -> b) -> (a -> b -> b) -> Cyclic v a -> b
foldrMap1 :: forall a b. (a -> b) -> (a -> b -> b) -> Cyclic v a -> b
$cfoldlMap1' :: forall (v :: * -> *) a b.
Foldable1 v =>
(a -> b) -> (b -> a -> b) -> Cyclic v a -> b
foldlMap1' :: forall a b. (a -> b) -> (b -> a -> b) -> Cyclic v a -> b
$cfoldlMap1 :: forall (v :: * -> *) a b.
Foldable1 v =>
(a -> b) -> (b -> a -> b) -> Cyclic v a -> b
foldlMap1 :: forall a b. (a -> b) -> (b -> a -> b) -> Cyclic v a -> b
$cfoldrMap1' :: forall (v :: * -> *) a b.
Foldable1 v =>
(a -> b) -> (a -> b -> b) -> Cyclic v a -> b
foldrMap1' :: forall a b. (a -> b) -> (a -> b -> b) -> Cyclic v a -> b
Foldable1,Cyclic v a -> ()
(Cyclic v a -> ()) -> NFData (Cyclic v a)
forall a. (a -> ()) -> NFData a
forall k (v :: k -> *) (a :: k). NFData (v a) => Cyclic v a -> ()
$crnf :: forall k (v :: k -> *) (a :: k). NFData (v a) => Cyclic v a -> ()
rnf :: Cyclic v a -> ()
NFData,Cyclic v a -> Cyclic v a -> Bool
(Cyclic v a -> Cyclic v a -> Bool)
-> (Cyclic v a -> Cyclic v a -> Bool) -> Eq (Cyclic v a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k (v :: k -> *) (a :: k).
Eq (v a) =>
Cyclic v a -> Cyclic v a -> Bool
$c== :: forall k (v :: k -> *) (a :: k).
Eq (v a) =>
Cyclic v a -> Cyclic v a -> Bool
== :: Cyclic v a -> Cyclic v a -> Bool
$c/= :: forall k (v :: k -> *) (a :: k).
Eq (v a) =>
Cyclic v a -> Cyclic v a -> Bool
/= :: Cyclic v a -> Cyclic v a -> Bool
Eq,[Cyclic v a] -> Value
[Cyclic v a] -> Encoding
Cyclic v a -> Bool
Cyclic v a -> Value
Cyclic v a -> Encoding
(Cyclic v a -> Value)
-> (Cyclic v a -> Encoding)
-> ([Cyclic v a] -> Value)
-> ([Cyclic v a] -> Encoding)
-> (Cyclic v a -> Bool)
-> ToJSON (Cyclic v a)
forall a.
(a -> Value)
-> (a -> Encoding)
-> ([a] -> Value)
-> ([a] -> Encoding)
-> (a -> Bool)
-> ToJSON a
forall k (v :: k -> *) (a :: k).
ToJSON (v a) =>
[Cyclic v a] -> Value
forall k (v :: k -> *) (a :: k).
ToJSON (v a) =>
[Cyclic v a] -> Encoding
forall k (v :: k -> *) (a :: k). ToJSON (v a) => Cyclic v a -> Bool
forall k (v :: k -> *) (a :: k).
ToJSON (v a) =>
Cyclic v a -> Value
forall k (v :: k -> *) (a :: k).
ToJSON (v a) =>
Cyclic v a -> Encoding
$ctoJSON :: forall k (v :: k -> *) (a :: k).
ToJSON (v a) =>
Cyclic v a -> Value
toJSON :: Cyclic v a -> Value
$ctoEncoding :: forall k (v :: k -> *) (a :: k).
ToJSON (v a) =>
Cyclic v a -> Encoding
toEncoding :: Cyclic v a -> Encoding
$ctoJSONList :: forall k (v :: k -> *) (a :: k).
ToJSON (v a) =>
[Cyclic v a] -> Value
toJSONList :: [Cyclic v a] -> Value
$ctoEncodingList :: forall k (v :: k -> *) (a :: k).
ToJSON (v a) =>
[Cyclic v a] -> Encoding
toEncodingList :: [Cyclic v a] -> Encoding
$comitField :: forall k (v :: k -> *) (a :: k). ToJSON (v a) => Cyclic v a -> Bool
omitField :: Cyclic v a -> Bool
ToJSON,Maybe (Cyclic v a)
Value -> Parser [Cyclic v a]
Value -> Parser (Cyclic v a)
(Value -> Parser (Cyclic v a))
-> (Value -> Parser [Cyclic v a])
-> Maybe (Cyclic v a)
-> FromJSON (Cyclic v a)
forall a.
(Value -> Parser a)
-> (Value -> Parser [a]) -> Maybe a -> FromJSON a
forall k (v :: k -> *) (a :: k).
FromJSON (v a) =>
Maybe (Cyclic v a)
forall k (v :: k -> *) (a :: k).
FromJSON (v a) =>
Value -> Parser [Cyclic v a]
forall k (v :: k -> *) (a :: k).
FromJSON (v a) =>
Value -> Parser (Cyclic v a)
$cparseJSON :: forall k (v :: k -> *) (a :: k).
FromJSON (v a) =>
Value -> Parser (Cyclic v a)
parseJSON :: Value -> Parser (Cyclic v a)
$cparseJSONList :: forall k (v :: k -> *) (a :: k).
FromJSON (v a) =>
Value -> Parser [Cyclic v a]
parseJSONList :: Value -> Parser [Cyclic v a]
$comittedField :: forall k (v :: k -> *) (a :: k).
FromJSON (v a) =>
Maybe (Cyclic v a)
omittedField :: Maybe (Cyclic v a)
FromJSON)
 deriving stock ((forall x. Cyclic v a -> Rep (Cyclic v a) x)
-> (forall x. Rep (Cyclic v a) x -> Cyclic v a)
-> Generic (Cyclic v a)
forall x. Rep (Cyclic v a) x -> Cyclic v a
forall x. Cyclic v a -> Rep (Cyclic v a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k (v :: k -> *) (a :: k) x. Rep (Cyclic v a) x -> Cyclic v a
forall k (v :: k -> *) (a :: k) x. Cyclic v a -> Rep (Cyclic v a) x
$cfrom :: forall k (v :: k -> *) (a :: k) x. Cyclic v a -> Rep (Cyclic v a) x
from :: forall x. Cyclic v a -> Rep (Cyclic v a) x
$cto :: forall k (v :: k -> *) (a :: k) x. Rep (Cyclic v a) x -> Cyclic v a
to :: forall x. Rep (Cyclic v a) x -> Cyclic v a
Generic)
-- not sure if we want this Eq instance or not .


instance Traversable1 v => Traversable1 (Cyclic v) where
  traverse1 :: forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> Cyclic v a -> f (Cyclic v b)
traverse1 a -> f b
f (Cyclic v a
v) = v b -> Cyclic v b
forall {k} (v :: k -> *) (a :: k). v a -> Cyclic v a
Cyclic (v b -> Cyclic v b) -> f (v b) -> f (Cyclic v b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> v a -> f (v b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b. Apply f => (a -> f b) -> v a -> f (v b)
traverse1 a -> f b
f v a
v
instance Traversable v => Traversable (Cyclic v) where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Cyclic v a -> f (Cyclic v b)
traverse a -> f b
f (Cyclic v a
v) = v b -> Cyclic v b
forall {k} (v :: k -> *) (a :: k). v a -> Cyclic v a
Cyclic (v b -> Cyclic v b) -> f (v b) -> f (Cyclic v b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> v a -> f (v b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> v a -> f (v b)
traverse a -> f b
f v a
v


instance FunctorWithIndex i v => FunctorWithIndex i (Cyclic v) where
  imap :: forall a b. (i -> a -> b) -> Cyclic v a -> Cyclic v b
imap i -> a -> b
f (Cyclic v a
v) = v b -> Cyclic v b
forall {k} (v :: k -> *) (a :: k). v a -> Cyclic v a
Cyclic (v b -> Cyclic v b) -> v b -> Cyclic v b
forall a b. (a -> b) -> a -> b
$ (i -> a -> b) -> v a -> v b
forall a b. (i -> a -> b) -> v a -> v b
forall i (f :: * -> *) a b.
FunctorWithIndex i f =>
(i -> a -> b) -> f a -> f b
imap i -> a -> b
f v a
v
instance FoldableWithIndex i v => FoldableWithIndex i (Cyclic v) where
  ifoldMap :: forall m a. Monoid m => (i -> a -> m) -> Cyclic v a -> m
ifoldMap i -> a -> m
f (Cyclic v a
v) = (i -> a -> m) -> v a -> m
forall m a. Monoid m => (i -> a -> m) -> v a -> m
forall i (f :: * -> *) m a.
(FoldableWithIndex i f, Monoid m) =>
(i -> a -> m) -> f a -> m
ifoldMap i -> a -> m
f v a
v
instance TraversableWithIndex i v => TraversableWithIndex i (Cyclic v) where
  itraverse :: forall (f :: * -> *) a b.
Applicative f =>
(i -> a -> f b) -> Cyclic v a -> f (Cyclic v b)
itraverse i -> a -> f b
f (Cyclic v a
v) = v b -> Cyclic v b
forall {k} (v :: k -> *) (a :: k). v a -> Cyclic v a
Cyclic (v b -> Cyclic v b) -> f (v b) -> f (Cyclic v b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (i -> a -> f b) -> v a -> f (v b)
forall i (t :: * -> *) (f :: * -> *) a b.
(TraversableWithIndex i t, Applicative f) =>
(i -> a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(i -> a -> f b) -> v a -> f (v b)
itraverse i -> a -> f b
f v a
v

instance HasFromFoldable v => HasFromFoldable (Cyclic v)  where
  fromFoldable :: forall (g :: * -> *) a. Foldable g => g a -> Cyclic v a
fromFoldable = v a -> Cyclic v a
forall {k} (v :: k -> *) (a :: k). v a -> Cyclic v a
Cyclic (v a -> Cyclic v a) -> (g a -> v a) -> g a -> Cyclic v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. g a -> v a
forall (f :: * -> *) (g :: * -> *) a.
(HasFromFoldable f, Foldable g) =>
g a -> f a
forall (g :: * -> *) a. Foldable g => g a -> v a
fromFoldable
  fromList :: forall a. [a] -> Cyclic v a
fromList = v a -> Cyclic v a
forall {k} (v :: k -> *) (a :: k). v a -> Cyclic v a
Cyclic (v a -> Cyclic v a) -> ([a] -> v a) -> [a] -> Cyclic v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> v a
forall a. [a] -> v a
forall (f :: * -> *) a. HasFromFoldable f => [a] -> f a
fromList

instance HasFromFoldable1 v => HasFromFoldable1 (Cyclic v)  where
  fromFoldable1 :: forall (g :: * -> *) a. Foldable1 g => g a -> Cyclic v a
fromFoldable1 = v a -> Cyclic v a
forall {k} (v :: k -> *) (a :: k). v a -> Cyclic v a
Cyclic (v a -> Cyclic v a) -> (g a -> v a) -> g a -> Cyclic v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. g a -> v a
forall (f :: * -> *) (g :: * -> *) a.
(HasFromFoldable1 f, Foldable1 g) =>
g a -> f a
forall (g :: * -> *) a. Foldable1 g => g a -> v a
fromFoldable1
  fromNonEmpty :: forall a. NonEmpty a -> Cyclic v a
fromNonEmpty  = v a -> Cyclic v a
forall {k} (v :: k -> *) (a :: k). v a -> Cyclic v a
Cyclic (v a -> Cyclic v a)
-> (NonEmpty a -> v a) -> NonEmpty a -> Cyclic v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty a -> v a
forall a. NonEmpty a -> v a
forall (f :: * -> *) a. HasFromFoldable1 f => NonEmpty a -> f a
fromNonEmpty

type instance Index   (Cyclic v a) = Index   (v a)
type instance IxValue (Cyclic v a) = IxValue (v a)

instance (Index (v a) ~ Int, Foldable v, Ixed (v a)) => Ixed (Cyclic v a) where
  ix :: Index (Cyclic v a)
-> Traversal' (Cyclic v a) (IxValue (Cyclic v a))
ix Index (Cyclic v a)
i = \IxValue (Cyclic v a) -> f (IxValue (Cyclic v a))
f (Cyclic v a
v) -> let n :: Int
n  = v a -> Int
forall a. v a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
F.length v a
v
                          in v a -> Cyclic v a
forall {k} (v :: k -> *) (a :: k). v a -> Cyclic v a
Cyclic (v a -> Cyclic v a) -> f (v a) -> f (Cyclic v a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Index (v a) -> Traversal' (v a) (IxValue (v a))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix (Int
Index (Cyclic v a)
i Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
n) IxValue (v a) -> f (IxValue (v a))
IxValue (Cyclic v a) -> f (IxValue (Cyclic v a))
f v a
v

instance Reversing (v a) => Reversing (Cyclic v a) where
  reversing :: Cyclic v a -> Cyclic v a
reversing (Cyclic v a
v) = v a -> Cyclic v a
forall {k} (v :: k -> *) (a :: k). v a -> Cyclic v a
Cyclic (v a -> v a
forall t. Reversing t => t -> t
reversing v a
v)

-- | Class that models that some type has a cyclic traversal starting
-- from a particular index.
class HasDirectedTraversals v where
  -- | A rightward-traversal over all elements starting from the given one.
  --
  -- running time : \(O(n)\)
  traverseRightFrom          :: Index (v a) -> IndexedTraversal1' (Index (v a)) (v a) a

  -- | A rightward-traversal over all elements starting from the given one.
  --
  -- running time : \(O(n)\)
  traverseLeftFrom          :: Index (v a) -> IndexedTraversal1' (Index (v a)) (v a) a

instance HasDirectedTraversals v => HasDirectedTraversals (Cyclic v) where
  traverseRightFrom :: forall a.
Index (Cyclic v a)
-> IndexedTraversal1' (Index (Cyclic v a)) (Cyclic v a) a
traverseRightFrom Index (Cyclic v a)
s p a (f a)
paFa (Cyclic v a
v) = v a -> Cyclic v a
forall {k} (v :: k -> *) (a :: k). v a -> Cyclic v a
Cyclic (v a -> Cyclic v a) -> f (v a) -> f (Cyclic v a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Index (v a) -> IndexedTraversal1' (Index (v a)) (v a) a
forall a. Index (v a) -> IndexedTraversal1' (Index (v a)) (v a) a
forall (v :: * -> *) a.
HasDirectedTraversals v =>
Index (v a) -> IndexedTraversal1' (Index (v a)) (v a) a
traverseRightFrom Index (v a)
Index (Cyclic v a)
s p a (f a)
paFa v a
v
  traverseLeftFrom :: forall a.
Index (Cyclic v a)
-> IndexedTraversal1' (Index (Cyclic v a)) (Cyclic v a) a
traverseLeftFrom  Index (Cyclic v a)
s p a (f a)
paFa (Cyclic v a
v) = v a -> Cyclic v a
forall {k} (v :: k -> *) (a :: k). v a -> Cyclic v a
Cyclic (v a -> Cyclic v a) -> f (v a) -> f (Cyclic v a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Index (v a) -> IndexedTraversal1' (Index (v a)) (v a) a
forall a. Index (v a) -> IndexedTraversal1' (Index (v a)) (v a) a
forall (v :: * -> *) a.
HasDirectedTraversals v =>
Index (v a) -> IndexedTraversal1' (Index (v a)) (v a) a
traverseLeftFrom  Index (v a)
Index (Cyclic v a)
s p a (f a)
paFa v a
v

instance HasDirectedTraversals NV.NonEmptyVector where
  traverseRightFrom :: forall a.
Index (NonEmptyVector a)
-> IndexedTraversal1'
     (Index (NonEmptyVector a)) (NonEmptyVector a) a
traverseRightFrom Index (NonEmptyVector a)
s p a (f a)
paFa NonEmptyVector a
v = NonEmpty Int -> IndexedTraversal1' Int (NonEmptyVector a) a
forall a.
NonEmpty Int -> IndexedTraversal1' Int (NonEmptyVector a) a
traverseByOrder NonEmpty Int
indices' p a (f a)
paFa NonEmptyVector a
v
    where
      n :: Int
n        = NonEmptyVector a -> Int
forall a. NonEmptyVector a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
F.length NonEmptyVector a
v
      indices' :: NonEmpty Int
indices' = [Int] -> NonEmpty Int
forall a. HasCallStack => [a] -> NonEmpty a
NonEmpty.fromList [Int
Index (NonEmptyVector a)
s..(Int
Index (NonEmptyVector a)
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)]

  traverseLeftFrom :: forall a.
Index (NonEmptyVector a)
-> IndexedTraversal1'
     (Index (NonEmptyVector a)) (NonEmptyVector a) a
traverseLeftFrom Index (NonEmptyVector a)
s p a (f a)
paFa NonEmptyVector a
v = NonEmpty Int -> IndexedTraversal1' Int (NonEmptyVector a) a
forall a.
NonEmpty Int -> IndexedTraversal1' Int (NonEmptyVector a) a
traverseByOrder NonEmpty Int
indices' p a (f a)
paFa NonEmptyVector a
v
    where
      n :: Int
n        = NonEmptyVector a -> Int
forall a. NonEmptyVector a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
F.length NonEmptyVector a
v
      indices' :: NonEmpty Int
indices' = [Int] -> NonEmpty Int
forall a. HasCallStack => [a] -> NonEmpty a
NonEmpty.fromList [Int
Index (NonEmptyVector a)
s,Int
Index (NonEmptyVector a)
sInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1..(Int
Index (NonEmptyVector a)
sInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)]

-- | Helper to build traversal1's
wrapMaybeApply :: (Indexable Int p, Apply f) => p a (f b) -> p a (MaybeApply f b)
wrapMaybeApply :: forall (p :: * -> * -> *) (f :: * -> *) a b.
(Indexable Int p, Apply f) =>
p a (f b) -> p a (MaybeApply f b)
wrapMaybeApply = (f b -> MaybeApply f b) -> p a (f b) -> p a (MaybeApply f b)
forall b c a. (b -> c) -> p a b -> p a c
forall (p :: * -> * -> *) b c a.
Profunctor p =>
(b -> c) -> p a b -> p a c
rmap (Either (f b) b -> MaybeApply f b
forall (f :: * -> *) a. Either (f a) a -> MaybeApply f a
MaybeApply (Either (f b) b -> MaybeApply f b)
-> (f b -> Either (f b) b) -> f b -> MaybeApply f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f b -> Either (f b) b
forall a b. a -> Either a b
Left)


instance HasDirectedTraversals ViewL1 where
  traverseRightFrom :: forall a.
Index (ViewL1 a)
-> IndexedTraversal1' (Index (ViewL1 a)) (ViewL1 a) a
traverseRightFrom Index (ViewL1 a)
i = \p a (f a)
paFb ViewL1 a
xs -> let i' :: Int
i'    = Int
Index (ViewL1 a)
i Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` ViewL1 a -> Int
forall a. ViewL1 a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
F.length ViewL1 a
xs
                                        paFb' :: p a (MaybeApply f a)
paFb' = p a (f a) -> p a (MaybeApply f a)
forall (p :: * -> * -> *) (f :: * -> *) a b.
(Indexable Int p, Apply f) =>
p a (f b) -> p a (MaybeApply f b)
wrapMaybeApply p a (f a)
paFb
                                        combine :: ViewL1 a -> Seq a -> ViewL1 a
combine (a
x :<< Seq a
sa) Seq a
sb = a
x a -> Seq a -> ViewL1 a
forall a. a -> Seq a -> ViewL1 a
:<< (Seq a
sa Seq a -> Seq a -> Seq a
forall a. Semigroup a => a -> a -> a
<> Seq a
sb)
                                    in case Int -> ViewL1 a -> Maybe (Seq a, a, Seq a)
forall a. Int -> ViewL1 a -> Maybe (Seq a, a, Seq a)
splitL1At Int
i' ViewL1 a
xs of
      Maybe (Seq a, a, Seq a)
Nothing            -> p a (f a) -> ViewL1 a -> f (ViewL1 a)
forall (f :: * -> *) a b.
Traversable1 f =>
IndexedTraversal1 Int (f a) (f b) a b
IndexedTraversal1 Int (ViewL1 a) (ViewL1 a) a a
traversed1 p a (f a)
paFb ViewL1 a
xs
      Just (Seq a
pref,a
x,Seq a
suff) -> ViewL1 a -> Seq a -> ViewL1 a
forall {a}. ViewL1 a -> Seq a -> ViewL1 a
combine (ViewL1 a -> Seq a -> ViewL1 a)
-> f (ViewL1 a) -> f (Seq a -> ViewL1 a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>  (Int -> Int)
-> (Indexed Int a (f a) -> ViewL1 a -> f (ViewL1 a))
-> p a (f a)
-> ViewL1 a
-> f (ViewL1 a)
forall j (p :: * -> * -> *) i a b r.
Indexable j p =>
(i -> j) -> (Indexed i a b -> r) -> p a b -> r
reindexed (Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
i') Indexed Int a (f a) -> ViewL1 a -> f (ViewL1 a)
forall (f :: * -> *) a b.
Traversable1 f =>
IndexedTraversal1 Int (f a) (f b) a b
IndexedTraversal1 Int (ViewL1 a) (ViewL1 a) a a
traversed1 p a (f a)
paFb (a
x a -> Seq a -> ViewL1 a
forall a. a -> Seq a -> ViewL1 a
:<< Seq a
suff)
                                    f (Seq a -> ViewL1 a) -> MaybeApply f (Seq a) -> f (ViewL1 a)
forall (f :: * -> *) a b.
Apply f =>
f (a -> b) -> MaybeApply f a -> f b
<.*> p a (MaybeApply f a) -> Seq a -> MaybeApply f (Seq a)
forall i (t :: * -> *) a b.
TraversableWithIndex i t =>
IndexedTraversal i (t a) (t b) a b
IndexedTraversal Int (Seq a) (Seq a) a a
itraversed p a (MaybeApply f a)
paFb' Seq a
pref

  traverseLeftFrom :: forall a.
Index (ViewL1 a)
-> IndexedTraversal1' (Index (ViewL1 a)) (ViewL1 a) a
traverseLeftFrom Index (ViewL1 a)
i = \p a (f a)
paFb ViewL1 a
xs ->
                         let i' :: Int
i'    = Int
Index (ViewL1 a)
i Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` ViewL1 a -> Int
forall a. ViewL1 a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
F.length ViewL1 a
xs
                             paFb' :: p a (MaybeApply f a)
paFb' = p a (f a) -> p a (MaybeApply f a)
forall (p :: * -> * -> *) (f :: * -> *) a b.
(Indexable Int p, Apply f) =>
p a (f b) -> p a (MaybeApply f b)
wrapMaybeApply p a (f a)
paFb
                             combine :: ViewR1 a -> Seq a -> ViewL1 a
combine ViewR1 a
r1 Seq a
rs = ViewR1 a -> ViewL1 a
forall a. ViewR1 a -> ViewL1 a
viewl1 (ViewR1 a -> ViewL1 a) -> ViewR1 a -> ViewL1 a
forall a b. (a -> b) -> a -> b
$ ViewR1 a
r1 ViewR1 a -> Seq a -> ViewR1 a
forall a. ViewR1 a -> Seq a -> ViewR1 a
<>> Seq a
rs
                         in case Int -> ViewL1 a -> Maybe (Seq a, a, Seq a)
forall a. Int -> ViewL1 a -> Maybe (Seq a, a, Seq a)
splitL1At Int
i' ViewL1 a
xs of
      Maybe (Seq a, a, Seq a)
Nothing            -> Optical p (->) (Backwards f) (ViewL1 a) (ViewL1 a) a a
-> p a (f a) -> ViewL1 a -> f (ViewL1 a)
forall (p :: * -> * -> *) (q :: * -> * -> *) (f :: * -> *) s t a b.
(Profunctor p, Profunctor q) =>
Optical p q (Backwards f) s t a b -> Optical p q f s t a b
backwards Optical p (->) (Backwards f) (ViewL1 a) (ViewL1 a) a a
forall (f :: * -> *) a b.
Traversable1 f =>
IndexedTraversal1 Int (f a) (f b) a b
IndexedTraversal1 Int (ViewL1 a) (ViewL1 a) a a
traversed1 p a (f a)
paFb ViewL1 a
xs
      Just (Seq a
pref,a
x,Seq a
suff) -> ViewR1 a -> Seq a -> ViewL1 a
forall {a}. ViewR1 a -> Seq a -> ViewL1 a
combine (ViewR1 a -> Seq a -> ViewL1 a)
-> f (ViewR1 a) -> f (Seq a -> ViewL1 a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>  Optical p (->) (Backwards f) (ViewR1 a) (ViewR1 a) a a
-> Optical p (->) f (ViewR1 a) (ViewR1 a) a a
forall (p :: * -> * -> *) (q :: * -> * -> *) (f :: * -> *) s t a b.
(Profunctor p, Profunctor q) =>
Optical p q (Backwards f) s t a b -> Optical p q f s t a b
backwards Optical p (->) (Backwards f) (ViewR1 a) (ViewR1 a) a a
forall (f :: * -> *) a b.
Traversable1 f =>
IndexedTraversal1 Int (f a) (f b) a b
IndexedTraversal1 Int (ViewR1 a) (ViewR1 a) a a
traversed1 p a (f a)
paFb (Seq a
pref Seq a -> a -> ViewR1 a
forall a. Seq a -> a -> ViewR1 a
:>> a
x)
                                    f (Seq a -> ViewL1 a) -> MaybeApply f (Seq a) -> f (ViewL1 a)
forall (f :: * -> *) a b.
Apply f =>
f (a -> b) -> MaybeApply f a -> f b
<.*> Optical p (->) (Backwards (MaybeApply f)) (Seq a) (Seq a) a a
-> Optical p (->) (MaybeApply f) (Seq a) (Seq a) a a
forall (p :: * -> * -> *) (q :: * -> * -> *) (f :: * -> *) s t a b.
(Profunctor p, Profunctor q) =>
Optical p q (Backwards f) s t a b -> Optical p q f s t a b
backwards ((Int -> Int)
-> (Indexed Int a (Backwards (MaybeApply f) a)
    -> Seq a -> Backwards (MaybeApply f) (Seq a))
-> Optical p (->) (Backwards (MaybeApply f)) (Seq a) (Seq a) a a
forall j (p :: * -> * -> *) i a b r.
Indexable j p =>
(i -> j) -> (Indexed i a b -> r) -> p a b -> r
reindexed (\Int
j -> Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i' Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
j) Indexed Int a (Backwards (MaybeApply f) a)
-> Seq a -> Backwards (MaybeApply f) (Seq a)
forall i (t :: * -> *) a b.
TraversableWithIndex i t =>
IndexedTraversal i (t a) (t b) a b
IndexedTraversal Int (Seq a) (Seq a) a a
itraversed)
                                                   p a (MaybeApply f a)
paFb' Seq a
suff

-- | traverse the vector in the given order
traverseByOrder                 :: NonEmpty.NonEmpty Int
                                -> IndexedTraversal1' Int (NV.NonEmptyVector a) a
traverseByOrder :: forall a.
NonEmpty Int -> IndexedTraversal1' Int (NonEmptyVector a) a
traverseByOrder NonEmpty Int
indices' p a (f a)
paFa NonEmptyVector a
v = NonEmpty (Int, a) -> NonEmptyVector a
build (NonEmpty (Int, a) -> NonEmptyVector a)
-> f (NonEmpty (Int, a)) -> f (NonEmptyVector a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (NonEmpty (Int, a))
xs
  where
    n :: Int
n = NonEmptyVector a -> Int
forall a. NonEmptyVector a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
F.length NonEmptyVector a
v
    xs :: f (NonEmpty (Int, a))
xs = (Int -> f (Int, a)) -> NonEmpty Int -> f (NonEmpty (Int, a))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> NonEmpty a -> f (NonEmpty b)
traverse1 (\Int
i' -> let i :: Int
i = Int
i' Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
n
                           in (Int
i,) (a -> (Int, a)) -> f a -> f (Int, a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> p a (f a) -> Int -> a -> f a
forall a b. p a b -> Int -> a -> b
forall i (p :: * -> * -> *) a b.
Indexable i p =>
p a b -> i -> a -> b
indexed p a (f a)
paFa Int
i (NonEmptyVector a
v NonEmptyVector a -> Int -> a
forall a. NonEmptyVector a -> Int -> a
NV.! Int
i)
                   ) NonEmpty Int
indices'
    build :: NonEmpty (Int, a) -> NonEmptyVector a
build NonEmpty (Int, a)
ys = Vector a -> NonEmptyVector a
forall a. Vector a -> NonEmptyVector a
NV.unsafeFromVector (Vector a -> NonEmptyVector a) -> Vector a -> NonEmptyVector a
forall a b. (a -> b) -> a -> b
$ (forall s. ST s (MVector s a)) -> Vector a
forall a. (forall s. ST s (MVector s a)) -> Vector a
V.create ((forall s. ST s (MVector s a)) -> Vector a)
-> (forall s. ST s (MVector s a)) -> Vector a
forall a b. (a -> b) -> a -> b
$ do
                   MVector s a
v' <- Int -> ST s (MVector (PrimState (ST s)) a)
forall (m :: * -> *) a.
PrimMonad m =>
Int -> m (MVector (PrimState m) a)
MV.unsafeNew Int
n
                   NonEmpty (Int, a) -> ((Int, a) -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ NonEmpty (Int, a)
ys (((Int, a) -> ST s ()) -> ST s ())
-> ((Int, a) -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \(Int
i,a
y) ->
                     MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> a -> m ()
MV.write MVector s a
MVector (PrimState (ST s)) a
v' Int
i a
y
                   MVector s a -> ST s (MVector s a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure MVector s a
v'

-- | Test if the circular list is a cyclic shift of the second
-- list.
--
-- Running time: \(O(n+m)\), where \(n\) and \(m\) are the sizes of
-- the lists.
isShiftOfI         :: (Eq a, Foldable1 v) => Cyclic v a -> Cyclic v a -> Bool
Cyclic v a
xs isShiftOfI :: forall a (v :: * -> *).
(Eq a, Foldable1 v) =>
Cyclic v a -> Cyclic v a -> Bool
`isShiftOfI` Cyclic v a
ys = let twice :: Cyclic v a -> NonEmptyVector a
twice Cyclic v a
zs     = let zs' :: NonEmptyVector a
zs' = Cyclic v a -> NonEmptyVector a
forall {a}. Cyclic v a -> NonEmptyVector a
leftElements Cyclic v a
zs in NonEmptyVector a
zs' NonEmptyVector a -> NonEmptyVector a -> NonEmptyVector a
forall a. Semigroup a => a -> a -> a
<> NonEmptyVector a
zs'
                         once :: Cyclic v a -> NonEmptyVector a
once         = Cyclic v a -> NonEmptyVector a
forall {a}. Cyclic v a -> NonEmptyVector a
leftElements
                         leftElements :: Cyclic v a -> NonEmptyVector a
leftElements = NonEmpty a -> NonEmptyVector a
forall a. NonEmpty a -> NonEmptyVector a
NV.fromNonEmpty (NonEmpty a -> NonEmptyVector a)
-> (Cyclic v a -> NonEmpty a) -> Cyclic v a -> NonEmptyVector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Cyclic v a -> NonEmpty a
forall a. Cyclic v a -> NonEmpty a
forall (t :: * -> *) a. Foldable1 t => t a -> NonEmpty a
toNonEmpty
                         check :: Cyclic v a -> Cyclic v a -> Bool
check Cyclic v a
as Cyclic v a
bs  = Maybe Int -> Bool
forall a. Maybe a -> Bool
isJust (Maybe Int -> Bool) -> Maybe Int -> Bool
forall a b. (a -> b) -> a -> b
$ Cyclic v a -> NonEmptyVector a
once Cyclic v a
as NonEmptyVector a -> NonEmptyVector a -> Maybe Int
forall a (p :: * -> *) (t :: * -> *).
(Eq a, Foldable p, Foldable t) =>
p a -> t a -> Maybe Int
`isSubStringOf` Cyclic v a -> NonEmptyVector a
twice Cyclic v a
bs
                     in Cyclic v a -> Int
forall a. Cyclic v a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length Cyclic v a
xs Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Cyclic v a -> Int
forall a. Cyclic v a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length Cyclic v a
ys Bool -> Bool -> Bool
&& Cyclic v a -> Cyclic v a -> Bool
check Cyclic v a
xs Cyclic v a
ys

--------------------------------------------------------------------------------

-- | Class for types that have an Equality test up to cyclic shifts
class ShiftedEq t where
  -- | The type of the elements stored in this cyclic container.
  type ElemCyclic t
  -- | Given a and b, test if a is a shifted version of the other.
  isShiftOf :: Eq (ElemCyclic t) => t -> t -> Bool

  -- TODO: It may be nice to have a version that actually returns the index, if it is a
  -- shift.

instance Foldable1 v => ShiftedEq (Cyclic v a) where
  type ElemCyclic (Cyclic v a) = a
  -- ^ runs in linear time in the inputs.
  isShiftOf :: Eq (ElemCyclic (Cyclic v a)) => Cyclic v a -> Cyclic v a -> Bool
isShiftOf = Cyclic v a -> Cyclic v a -> Bool
forall a (v :: * -> *).
(Eq a, Foldable1 v) =>
Cyclic v a -> Cyclic v a -> Bool
isShiftOfI