{-# LANGUAGE TypeFamilies #-}

-- | Monoid action for setting interval \([l, r)\).
--
-- @since 1.0.0
module AtCoder.Extra.Monoid.RangeAdd
  ( -- * RangeAdd
    RangeAdd (..),

    -- * Constructor
    new,

    -- * Action
    act,
  )
where

import AtCoder.LazySegTree (SegAct (..))
import Data.Semigroup (Sum (..))
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

-- | Range set monoid action.
--
-- ==== Example
-- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeAdd(..))
-- >>> import AtCoder.LazySegTree qualified as LST
-- >>> import Data.Semigroup (Max(..))
-- >>> seg <- LST.build @_ @(RangeAdd Int) @(Sum Int) $ VU.generate 3 Sum -- [0, 1, 2]
-- >>> LST.applyIn seg 0 3 $ RangeAdd 5 -- [5, 6, 7]
-- >>> getSum <$> LST.prod seg 0 3
-- 18
--
-- @since 1.0.0
newtype RangeAdd a = RangeAdd a
  deriving newtype
    ( -- | @since 1.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
      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
      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
{-# INLINE new #-}
new :: a -> RangeAdd a
new :: forall a. a -> RangeAdd a
new = a -> RangeAdd a
forall a. a -> RangeAdd a
RangeAdd

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

-- | Acts on @a@ with length in terms of `SegAct`.
--
-- @since 1.0.0
{-# INLINE actWithLength #-}
actWithLength :: (Num a) => Int -> RangeAdd a -> a -> a
actWithLength :: forall a. Num a => Int -> RangeAdd a -> a -> a
actWithLength Int
len (RangeAdd a
f) a
x = Int -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
len a -> a -> a
forall a. Num a => a -> a -> a
* a
f a -> a -> a
forall a. Num a => a -> a -> a
+ a
x

-- | @since 1.0.0
instance (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.0.0
instance (Num a) => Monoid (RangeAdd a) where
  {-# INLINE mempty #-}
  mempty :: RangeAdd a
mempty = a -> RangeAdd a
forall a. a -> RangeAdd a
RangeAdd a
0

-- | @since 1.0.0
instance (Num a) => SegAct (RangeAdd a) (Sum a) where
  {-# INLINE segActWithLength #-}
  segActWithLength :: Int -> RangeAdd a -> Sum a -> Sum a
segActWithLength Int
len RangeAdd a
a (Sum a
x) = a -> Sum a
forall a. a -> Sum a
Sum (a -> Sum a) -> a -> Sum a
forall a b. (a -> b) -> a -> b
$! Int -> RangeAdd a -> a -> a
forall a. Num a => Int -> RangeAdd a -> a -> a
actWithLength Int
len RangeAdd a
a a
x

-- not works as SegAct for Product, Min, and Max.

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

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

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

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

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