{-# LANGUAGE DerivingStrategies #-}
{-# 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 (Max (..), Min (..), Sum (..), stimes)
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 (action on @Sum@)__
-- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeAdd(..))
-- >>> import AtCoder.LazySegTree qualified as LST
-- >>> import Data.Semigroup (Sum(..))
-- >>> 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
--
-- ==== __Example (action on @Max@)__
-- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeAdd(..))
-- >>> import AtCoder.LazySegTree qualified as LST
-- >>> import Data.Semigroup (Max(..))
-- >>> seg <- LST.build @_ @(RangeAdd (Max Int)) @(Max Int) $ VU.generate 3 Max -- [0, 1, 2]
-- >>> LST.applyIn seg 0 3 $ RangeAdd (Max 5) -- [5, 6, 7]
-- >>> getMax <$> LST.prod seg 0 3
-- 7
--
-- @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`. Be warned that it doesn't work well with
-- idempotent monoids such as `Max` or `Min`.
--
-- @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.2.0.0
instance (Semigroup a, Num 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. Num a => a -> a -> a
+ a
b

-- | @since 1.2.0.0
instance (Num a, Semigroup a) => Monoid (RangeAdd a) where
  {-# INLINE mempty #-}
  mempty :: RangeAdd a
mempty = a -> RangeAdd a
forall a. a -> RangeAdd a
RangeAdd a
0

-- | @since 1.2.0.0
instance (Num a) => SegAct (RangeAdd (Sum a)) (Sum a) where
  {-# INLINE segActWithLength #-}
  segActWithLength :: Int -> RangeAdd (Sum a) -> Sum a -> Sum a
segActWithLength = Int -> RangeAdd (Sum a) -> Sum a -> Sum a
forall a. Semigroup a => Int -> RangeAdd a -> a -> a
actWithLength

-- | @since 1.1.0.0
instance (Num a, Monoid (Max a)) => SegAct (RangeAdd (Max a)) (Max a) where
  {-# INLINE segAct #-}
  segAct :: RangeAdd (Max a) -> Max a -> Max a
segAct (RangeAdd (Max a
dx)) (Max a
x) = a -> Max a
forall a. a -> Max a
Max (a -> Max a) -> a -> Max a
forall a b. (a -> b) -> a -> b
$! a
dx a -> a -> a
forall a. Num a => a -> a -> a
+ a
x

-- | @since 1.1.0.0
instance (Num a, Monoid (Min a)) => SegAct (RangeAdd (Min a)) (Min a) where
  {-# INLINE segAct #-}
  segAct :: RangeAdd (Min a) -> Min a -> Min a
segAct (RangeAdd (Min a
dx)) (Min a
x) = a -> Min a
forall a. a -> Min a
Min (a -> Min a) -> a -> Min a
forall a b. (a -> b) -> a -> b
$! a
dx a -> a -> a
forall a. Num a => a -> a -> a
+ 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)