{-# LANGUAGE TypeFamilies #-}

-- | Range set 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.RangeSetId
  ( -- * RangeSetId
    RangeSetId (..),

    -- * Constructor
    new,

    -- * Action
    act,
  )
where

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

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

-- | `RangeSetId` internal representation. The first value represents if it is an identity action.
-- Tuples are not the fastest representation, but it's easier to implement
-- `Data.Vector.Unboxed.Unbox`.
--
-- @since 1.0.0.0
type RangeSetIdRepr a = (Bit, a)

-- | Creates a new `RangeSet` action.
--
-- @since 1.0.0.0
{-# INLINE new #-}
new :: a -> RangeSetId a
new :: forall a. a -> RangeSetId a
new = RangeSetIdRepr a -> RangeSetId a
forall a. RangeSetIdRepr a -> RangeSetId a
RangeSetId (RangeSetIdRepr a -> RangeSetId a)
-> (a -> RangeSetIdRepr a) -> a -> RangeSetId a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Bool -> Bit
Bit Bool
True,)

-- | Applies one-length range set: \(f: x \rightarrow y\).
--
-- @since 1.0.0.0
{-# INLINE act #-}
act :: RangeSetId a -> a -> a
act :: forall a. RangeSetId a -> a -> a
act (RangeSetId (Bit Bool
True, !a
f)) a
_ = a
f
act (RangeSetId (Bit Bool
False, !a
_)) a
x = a
x

-- segActWithLength works for ideomponent monoids only.

-- | @since 1.0.0.0
instance Semigroup (RangeSetId a) where
  {-# INLINE (<>) #-}
  RangeSetId (Bit Bool
False, !a
_) <> :: RangeSetId a -> RangeSetId a -> RangeSetId a
<> RangeSetId a
old = RangeSetId a
old
  RangeSetId a
new_ <> RangeSetId a
_ = RangeSetId a
new_
  {-# INLINE stimes #-}
  stimes :: forall b. Integral b => b -> RangeSetId a -> RangeSetId a
stimes b
_ RangeSetId a
x = RangeSetId a
x

-- The `Monoid` constraint is just for their default value.

-- | @since 1.0.0.0
instance (Monoid a) => Monoid (RangeSetId a) where
  {-# INLINE mempty #-}
  mempty :: RangeSetId a
mempty = RangeSetIdRepr a -> RangeSetId a
forall a. RangeSetIdRepr a -> RangeSetId a
RangeSetId (Bool -> Bit
Bit Bool
False, a
forall a. Monoid a => a
mempty)
  {-# INLINE mconcat #-}
  -- find the first non-mempty
  mconcat :: [RangeSetId a] -> RangeSetId a
mconcat [] = RangeSetId a
forall a. Monoid a => a
mempty
  mconcat (RangeSetId (Bit Bool
False, !a
_) : [RangeSetId a]
as) = [RangeSetId a] -> RangeSetId a
forall a. Monoid a => [a] -> a
mconcat [RangeSetId a]
as
  mconcat (RangeSetId a
a : [RangeSetId a]
_) = RangeSetId a
a

-- The target is limited to ideomponent monoids. The `Monoid` constraint is just for their default
-- value.

-- | @since 1.0.0.0
instance (Ord a, Bounded a) => SegAct (RangeSetId (Max a)) (Max a) where
  {-# INLINE segAct #-}
  segAct :: RangeSetId (Max a) -> Max a -> Max a
segAct = RangeSetId (Max a) -> Max a -> Max a
forall a. RangeSetId a -> a -> a
act

-- The target is limited to ideomponent monoids. The `Monoid` constraint is just for their default
-- value.

-- | @since 1.0.0.0
instance (Ord a, Bounded a) => SegAct (RangeSetId (Min a)) (Min a) where
  {-# INLINE segAct #-}
  segAct :: RangeSetId (Min a) -> Min a -> Min a
segAct = RangeSetId (Min a) -> Min a -> Min a
forall a. RangeSetId a -> a -> a
act

-- | @since 1.0.0.0
newtype instance VU.MVector s (RangeSetId a) = MV_RangeSetId (VU.MVector s (RangeSetIdRepr a))

-- | @since 1.0.0.0
newtype instance VU.Vector (RangeSetId a) = V_RangeSetId (VU.Vector (RangeSetIdRepr a))

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

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

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