{-# LANGUAGE TypeFamilies #-}

-- | Monoid action \(f: x \rightarrow x + d\).
--
-- @since 1.0.0.0
module AtCoder.Extra.Monoid.RangeAdd
  ( -- * RangeAdd
    RangeAdd (..),

    -- * Constructor
    new,
    unRangeAdd,

    -- * Actions
    act,
  )
where

import AtCoder.LazySegTree (SegAct (..))
import Data.Semigroup (stimes, Sum (..), Max(..), Min(..))
import Data.Vector.Generic qualified as VG
import Data.Vector.Generic.Mutable qualified as VGM
import Data.Vector.Unboxed qualified as VU
import Data.Vector.Unboxed.Mutable qualified as VUM

-- | Monoid action \(f: x \rightarrow x + d\).
--
-- ==== __Example__
-- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeAdd(..))
-- >>> import AtCoder.LazySegTree qualified as LST
-- >>> import Data.Semigroup (Max(..))
-- >>> seg <- LST.build @_ @(RangeAdd (Sum Int)) @(Sum Int) $ VU.generate 3 Sum -- [0, 1, 2]
-- >>> LST.applyIn seg 0 3 $ RangeAdd (Sum 5) -- [5, 6, 7]
-- >>> getSum <$> LST.prod seg 0 3
-- 18
--
-- @since 1.0.0.0
newtype RangeAdd a = RangeAdd a
  deriving newtype
    ( -- | @since 1.0.0.0
      RangeAdd a -> RangeAdd a -> Bool
(RangeAdd a -> RangeAdd a -> Bool)
-> (RangeAdd a -> RangeAdd a -> Bool) -> Eq (RangeAdd a)
forall a. Eq a => RangeAdd a -> RangeAdd a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => RangeAdd a -> RangeAdd a -> Bool
== :: RangeAdd a -> RangeAdd a -> Bool
$c/= :: forall a. Eq a => RangeAdd a -> RangeAdd a -> Bool
/= :: RangeAdd a -> RangeAdd a -> Bool
Eq,
      -- | @since 1.0.0.0
      Eq (RangeAdd a)
Eq (RangeAdd a) =>
(RangeAdd a -> RangeAdd a -> Ordering)
-> (RangeAdd a -> RangeAdd a -> Bool)
-> (RangeAdd a -> RangeAdd a -> Bool)
-> (RangeAdd a -> RangeAdd a -> Bool)
-> (RangeAdd a -> RangeAdd a -> Bool)
-> (RangeAdd a -> RangeAdd a -> RangeAdd a)
-> (RangeAdd a -> RangeAdd a -> RangeAdd a)
-> Ord (RangeAdd a)
RangeAdd a -> RangeAdd a -> Bool
RangeAdd a -> RangeAdd a -> Ordering
RangeAdd a -> RangeAdd a -> RangeAdd a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (RangeAdd a)
forall a. Ord a => RangeAdd a -> RangeAdd a -> Bool
forall a. Ord a => RangeAdd a -> RangeAdd a -> Ordering
forall a. Ord a => RangeAdd a -> RangeAdd a -> RangeAdd a
$ccompare :: forall a. Ord a => RangeAdd a -> RangeAdd a -> Ordering
compare :: RangeAdd a -> RangeAdd a -> Ordering
$c< :: forall a. Ord a => RangeAdd a -> RangeAdd a -> Bool
< :: RangeAdd a -> RangeAdd a -> Bool
$c<= :: forall a. Ord a => RangeAdd a -> RangeAdd a -> Bool
<= :: RangeAdd a -> RangeAdd a -> Bool
$c> :: forall a. Ord a => RangeAdd a -> RangeAdd a -> Bool
> :: RangeAdd a -> RangeAdd a -> Bool
$c>= :: forall a. Ord a => RangeAdd a -> RangeAdd a -> Bool
>= :: RangeAdd a -> RangeAdd a -> Bool
$cmax :: forall a. Ord a => RangeAdd a -> RangeAdd a -> RangeAdd a
max :: RangeAdd a -> RangeAdd a -> RangeAdd a
$cmin :: forall a. Ord a => RangeAdd a -> RangeAdd a -> RangeAdd a
min :: RangeAdd a -> RangeAdd a -> RangeAdd a
Ord,
      -- | @since 1.0.0.0
      Int -> RangeAdd a -> ShowS
[RangeAdd a] -> ShowS
RangeAdd a -> String
(Int -> RangeAdd a -> ShowS)
-> (RangeAdd a -> String)
-> ([RangeAdd a] -> ShowS)
-> Show (RangeAdd a)
forall a. Show a => Int -> RangeAdd a -> ShowS
forall a. Show a => [RangeAdd a] -> ShowS
forall a. Show a => RangeAdd a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> RangeAdd a -> ShowS
showsPrec :: Int -> RangeAdd a -> ShowS
$cshow :: forall a. Show a => RangeAdd a -> String
show :: RangeAdd a -> String
$cshowList :: forall a. Show a => [RangeAdd a] -> ShowS
showList :: [RangeAdd a] -> ShowS
Show
    )

-- | Creates `RangeAdd`.
--
-- @since 1.0.0.0
{-# INLINE new #-}
new :: a -> RangeAdd a
new :: forall a. a -> RangeAdd a
new = a -> RangeAdd a
forall a. a -> RangeAdd a
RangeAdd

-- | \(O(1)\) Retrieves the internal value of `RangeAdd`.
--
-- @since 1.1.0.0
{-# INLINE unRangeAdd #-}
unRangeAdd :: RangeAdd a -> a
unRangeAdd :: forall a. RangeAdd a -> a
unRangeAdd (RangeAdd a
a) = a
a

-- | \(O(1)\) Applies one-length range add: \(f: x \rightarrow d + x\).
--
-- @since 1.0.0.0
{-# INLINE act #-}
act :: (Semigroup a) => RangeAdd a -> a -> a
act :: forall a. Semigroup a => RangeAdd a -> a -> a
act (RangeAdd a
dx) a
x = a
dx a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
x

-- | \(O(1)\) Acts on @a@ with length in terms of `SegAct`.
--
-- @since 1.0.0.0
{-# INLINE actWithLength #-}
actWithLength :: (Semigroup a) => Int -> RangeAdd a -> a -> a
actWithLength :: forall a. Semigroup a => Int -> RangeAdd a -> a -> a
actWithLength Int
len (RangeAdd a
f) a
x = Int -> a -> a
forall b. Integral b => b -> a -> a
forall a b. (Semigroup a, Integral b) => b -> a -> a
stimes Int
len a
f a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
x

-- | @since 1.0.0.0
instance (Semigroup a) => Semigroup (RangeAdd a) where
  {-# INLINE (<>) #-}
  (RangeAdd a
a) <> :: RangeAdd a -> RangeAdd a -> RangeAdd a
<> (RangeAdd a
b) = a -> RangeAdd a
forall a. a -> RangeAdd a
RangeAdd (a -> RangeAdd a) -> a -> RangeAdd a
forall a b. (a -> b) -> a -> b
$! a
a a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
b

-- | @since 1.1.0.0
instance (Monoid a) => Monoid (RangeAdd a) where
  {-# INLINE mempty #-}
  mempty :: RangeAdd a
mempty = a -> RangeAdd a
forall a. a -> RangeAdd a
RangeAdd a
forall a. Monoid a => a
mempty

-- | @since 1.1.0.0
instance (Monoid (Sum a)) => SegAct (RangeAdd (Sum a)) (Sum a) where
  {-# INLINE segActWithLength #-}
  segActWithLength :: Int -> RangeAdd (Sum a) -> Sum a -> Sum a
segActWithLength Int
len RangeAdd (Sum a)
f Sum a
x = Int -> RangeAdd (Sum a) -> Sum a -> Sum a
forall a. Semigroup a => Int -> RangeAdd a -> a -> a
actWithLength Int
len RangeAdd (Sum a)
f Sum a
x

-- | @since 1.1.0.0
instance (Monoid (Max a)) => SegAct (RangeAdd (Max a)) (Max a) where
  {-# INLINE segActWithLength #-}
  segActWithLength :: Int -> RangeAdd (Max a) -> Max a -> Max a
segActWithLength Int
len RangeAdd (Max a)
f Max a
x = Int -> RangeAdd (Max a) -> Max a -> Max a
forall a. Semigroup a => Int -> RangeAdd a -> a -> a
actWithLength Int
len RangeAdd (Max a)
f Max a
x

-- | @since 1.1.0.0
instance (Monoid (Min a)) => SegAct (RangeAdd (Min a)) (Min a) where
  {-# INLINE segActWithLength #-}
  segActWithLength :: Int -> RangeAdd (Min a) -> Min a -> Min a
segActWithLength Int
len RangeAdd (Min a)
f Min a
x = Int -> RangeAdd (Min a) -> Min a -> Min a
forall a. Semigroup a => Int -> RangeAdd a -> a -> a
actWithLength Int
len RangeAdd (Min a)
f Min a
x

-- | @since 1.0.0.0
newtype instance VU.MVector s (RangeAdd a) = MV_RangeAdd (VU.MVector s a)

-- | @since 1.0.0.0
newtype instance VU.Vector (RangeAdd a) = V_RangeAdd (VU.Vector a)

-- | @since 1.0.0.0
deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (RangeAdd a)

-- | @since 1.0.0.0
deriving instance (VU.Unbox a) => VG.Vector VU.Vector (RangeAdd a)

-- | @since 1.0.0.0
instance (VU.Unbox a) => VU.Unbox (RangeAdd a)