{-# LANGUAGE TypeFamilies #-}

-- | Range add monoid action for \([l, r)\) intervals. Works on ideomponent monoids such as `Max`
-- or `Min` only.
--
-- @since 1.0.0.0
module AtCoder.Extra.Monoid.RangeAddId
  ( -- * RangeAddId
    RangeAddId (..),
    -- * Constructor
    new,
    -- * Action
    act,
  )
where

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

-- | Range add monoid action.
--
-- ==== Example
-- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeAddId(..))
-- >>> import AtCoder.LazySegTree qualified as LST
-- >>> import Data.Semigroup (Max(..))
-- >>> seg <- LST.build @_ @(RangeAddId Int) @(Max Int) $ VU.generate 3 Max -- [0, 1, 2]
-- >>> LST.applyIn seg 0 3 $ RangeAddId 5 -- [5, 6, 7]
-- >>> getMax <$> LST.prod seg 0 3
-- 7
--
-- @since 1.0.0.0
newtype RangeAddId a = RangeAddId a
  deriving newtype
    ( -- | @since 1.0.0.0
      RangeAddId a -> RangeAddId a -> Bool
(RangeAddId a -> RangeAddId a -> Bool)
-> (RangeAddId a -> RangeAddId a -> Bool) -> Eq (RangeAddId a)
forall a. Eq a => RangeAddId a -> RangeAddId a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => RangeAddId a -> RangeAddId a -> Bool
== :: RangeAddId a -> RangeAddId a -> Bool
$c/= :: forall a. Eq a => RangeAddId a -> RangeAddId a -> Bool
/= :: RangeAddId a -> RangeAddId a -> Bool
Eq,
      -- | @since 1.0.0.0
      Eq (RangeAddId a)
Eq (RangeAddId a) =>
(RangeAddId a -> RangeAddId a -> Ordering)
-> (RangeAddId a -> RangeAddId a -> Bool)
-> (RangeAddId a -> RangeAddId a -> Bool)
-> (RangeAddId a -> RangeAddId a -> Bool)
-> (RangeAddId a -> RangeAddId a -> Bool)
-> (RangeAddId a -> RangeAddId a -> RangeAddId a)
-> (RangeAddId a -> RangeAddId a -> RangeAddId a)
-> Ord (RangeAddId a)
RangeAddId a -> RangeAddId a -> Bool
RangeAddId a -> RangeAddId a -> Ordering
RangeAddId a -> RangeAddId a -> RangeAddId 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 (RangeAddId a)
forall a. Ord a => RangeAddId a -> RangeAddId a -> Bool
forall a. Ord a => RangeAddId a -> RangeAddId a -> Ordering
forall a. Ord a => RangeAddId a -> RangeAddId a -> RangeAddId a
$ccompare :: forall a. Ord a => RangeAddId a -> RangeAddId a -> Ordering
compare :: RangeAddId a -> RangeAddId a -> Ordering
$c< :: forall a. Ord a => RangeAddId a -> RangeAddId a -> Bool
< :: RangeAddId a -> RangeAddId a -> Bool
$c<= :: forall a. Ord a => RangeAddId a -> RangeAddId a -> Bool
<= :: RangeAddId a -> RangeAddId a -> Bool
$c> :: forall a. Ord a => RangeAddId a -> RangeAddId a -> Bool
> :: RangeAddId a -> RangeAddId a -> Bool
$c>= :: forall a. Ord a => RangeAddId a -> RangeAddId a -> Bool
>= :: RangeAddId a -> RangeAddId a -> Bool
$cmax :: forall a. Ord a => RangeAddId a -> RangeAddId a -> RangeAddId a
max :: RangeAddId a -> RangeAddId a -> RangeAddId a
$cmin :: forall a. Ord a => RangeAddId a -> RangeAddId a -> RangeAddId a
min :: RangeAddId a -> RangeAddId a -> RangeAddId a
Ord,
      -- | @since 1.0.0.0
      Int -> RangeAddId a -> ShowS
[RangeAddId a] -> ShowS
RangeAddId a -> String
(Int -> RangeAddId a -> ShowS)
-> (RangeAddId a -> String)
-> ([RangeAddId a] -> ShowS)
-> Show (RangeAddId a)
forall a. Show a => Int -> RangeAddId a -> ShowS
forall a. Show a => [RangeAddId a] -> ShowS
forall a. Show a => RangeAddId a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> RangeAddId a -> ShowS
showsPrec :: Int -> RangeAddId a -> ShowS
$cshow :: forall a. Show a => RangeAddId a -> String
show :: RangeAddId a -> String
$cshowList :: forall a. Show a => [RangeAddId a] -> ShowS
showList :: [RangeAddId a] -> ShowS
Show
    )

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

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

-- | @since 1.0.0.0
instance (Num a) => Semigroup (RangeAddId a) where
  {-# INLINE (<>) #-}
  (RangeAddId a
a) <> :: RangeAddId a -> RangeAddId a -> RangeAddId a
<> (RangeAddId a
b) = a -> RangeAddId a
forall a. a -> RangeAddId a
RangeAddId (a -> RangeAddId a) -> a -> RangeAddId 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.0
instance (Num a) => Monoid (RangeAddId a) where
  {-# INLINE mempty #-}
  mempty :: RangeAddId a
mempty = a -> RangeAddId a
forall a. a -> RangeAddId a
RangeAddId a
0

-- | @since 1.0.0.0
instance (Num a) => SegAct (RangeAddId a) (Max a) where
  {-# INLINE segAct #-}
  segAct :: RangeAddId a -> Max a -> Max a
segAct RangeAddId a
f (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
$! RangeAddId a -> a -> a
forall a. Num a => RangeAddId a -> a -> a
act RangeAddId a
f a
x

-- | @since 1.0.0.0
instance (Num a) => SegAct (RangeAddId a) (Min a) where
  {-# INLINE segAct #-}
  segAct :: RangeAddId a -> Min a -> Min a
segAct RangeAddId a
f (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
$! RangeAddId a -> a -> a
forall a. Num a => RangeAddId a -> a -> a
act RangeAddId a
f a
x

-- not works as SegAct for Sum and Product.

-- | @since 1.0.0.0
newtype instance VU.MVector s (RangeAddId a) = MV_RangeAddId (VU.MVector s a)

-- | @since 1.0.0.0
newtype instance VU.Vector (RangeAddId a) = V_RangeAddId (VU.Vector a)

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

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

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