    {-# LANGUAGE CPP #-}
    {-# LANGUAGE BangPatterns #-}
    #ifdef __GLASGOW_HASKELL__
    {-# LANGUAGE Trustworthy #-}
    #endif

    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Data.Containers.ListUtils
    -- Copyright   :  (c) Gershom Bazerman 2018
    -- License     :  BSD-style
    -- Maintainer  :  libraries@haskell.org
    -- Portability :  portable
    --
    -- This module provides efficient containers-based functions on the list type.
    --
    -- In the documentation, \(n\) is the number of elements in the list while
    -- \(d\) is the number of distinct elements in the list. \(W\) is the number
    -- of bits in an 'Int'.
    --
    -- @since 0.6.0.1
    -----------------------------------------------------------------------------

    module Data.Containers.ListUtils (
           nubOrd,
           nubOrdOn,
           nubInt,
           nubIntOn
           ) where

    import Data.Set (Set)
    import qualified Data.Set as Set
    import qualified Data.IntSet as IntSet
    import Data.IntSet (IntSet)
    #ifdef __GLASGOW_HASKELL__
    import GHC.Exts ( build )
    #endif

    -- *** Ord-based nubbing ***

    -- | \( O(n \log d) \). The @nubOrd@ function removes duplicate elements from a
    -- list. In particular, it keeps only the first occurrence of each element. By
    -- using a 'Set' internally it has better asymptotics than the standard
    -- 'Data.List.nub' function.
    --
    -- ==== Strictness
    --
    -- @nubOrd@ is strict in the elements of the list.
    --
    -- ==== Efficiency note
    --
    -- When applicable, it is almost always better to use 'nubInt' or 'nubIntOn'
    -- instead of this function, although it can be a little worse in certain
    -- pathological cases. For example, to nub a list of characters, use
    --
    -- @ nubIntOn fromEnum xs @
    --
    -- @since 0.6.0.1
    nubOrd :: Ord a => [a] -> [a]
    nubOrd :: forall a. Ord a => [a] -> [a]
    nubOrd = (a -> a) -> [a] -> [a]
    forall b a. Ord b => (a -> b) -> [a] -> [a]
    nubOrdOn a -> a
    forall a. a -> a
    id
    {-# INLINE nubOrd #-}

    -- | The @nubOrdOn@ function behaves just like 'nubOrd' except it performs
    -- comparisons not on the original datatype, but a user-specified projection
    -- from that datatype.
    --
    -- ==== Strictness
    --
    -- @nubOrdOn@ is strict in the values of the function applied to the
    -- elements of the list.
    --
    -- @since 0.6.0.1
    nubOrdOn :: Ord b => (a -> b) -> [a] -> [a]
    -- For some reason we need to write an explicit lambda here to allow this
    -- to inline when only applied to a function.
    nubOrdOn :: forall b a. Ord b => (a -> b) -> [a] -> [a]
    nubOrdOn a -> b
    f = \[a]
    xs -> (a -> b) -> Set b -> [a] -> [a]
    forall b a. Ord b => (a -> b) -> Set b -> [a] -> [a]
    nubOrdOnExcluding a -> b
    f Set b
    forall a. Set a
    Set.empty [a]
    xs
    {-# INLINE nubOrdOn #-}

    -- Splitting nubOrdOn like this means that we don't have to worry about
    -- matching specifically on Set.empty in the rewrite-back rule.
    nubOrdOnExcluding :: Ord b => (a -> b) -> Set b -> [a] -> [a]
    nubOrdOnExcluding :: forall b a. Ord b => (a -> b) -> Set b -> [a] -> [a]
    nubOrdOnExcluding a -> b
    f = Set b -> [a] -> [a]
    go
      where
        go :: Set b -> [a] -> [a]
    go Set b
    _ [] = []
        go Set b
    s (a
    x:[a]
    xs)
          | b
    fx b -> Set b -> Bool
    forall a. Ord a => a -> Set a -> Bool
    `Set.member` Set b
    s = Set b -> [a] -> [a]
    go Set b
    s [a]
    xs
          | Bool
    otherwise = a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : Set b -> [a] -> [a]
    go (b -> Set b -> Set b
    forall a. Ord a => a -> Set a -> Set a
    Set.insert b
    fx Set b
    s) [a]
    xs
          where !fx :: b
    fx = a -> b
    f a
    x

    #ifdef __GLASGOW_HASKELL__
    -- We want this inlinable to specialize to the necessary Ord instance.
    {-# INLINABLE [1] nubOrdOnExcluding #-}

    {-# RULES
    -- Rewrite to a fusible form.
    "nubOrdOn" [~1] forall f as s. nubOrdOnExcluding  f s as =
      build (\c n -> foldr (nubOrdOnFB f c) (constNubOn n) as s)

    -- Rewrite back to a plain form
    "nubOrdOnList" [1] forall f as s.
        foldr (nubOrdOnFB f (:)) (constNubOn []) as s =
           nubOrdOnExcluding f s as
     #-}

    nubOrdOnFB :: Ord b
               => (a -> b)
               -> (a -> r -> r)
               -> a
               -> (Set b -> r)
               -> Set b
               -> r
    nubOrdOnFB :: forall b a r.
    Ord b =>
    (a -> b) -> (a -> r -> r) -> a -> (Set b -> r) -> Set b -> r
    nubOrdOnFB a -> b
    f a -> r -> r
    c a
    x Set b -> r
    r Set b
    s
      | b
    fx b -> Set b -> Bool
    forall a. Ord a => a -> Set a -> Bool
    `Set.member` Set b
    s = Set b -> r
    r Set b
    s
      | Bool
    otherwise = a
    x a -> r -> r
    `c` Set b -> r
    r (b -> Set b -> Set b
    forall a. Ord a => a -> Set a -> Set a
    Set.insert b
    fx Set b
    s)
      where !fx :: b
    fx = a -> b
    f a
    x
    {-# INLINABLE [0] nubOrdOnFB #-}

    constNubOn :: a -> b -> a
    constNubOn :: forall a b. a -> b -> a
    constNubOn a
    x b
    _ = a
    x
    {-# INLINE [0] constNubOn #-}
    #endif

    -- *** Int-based nubbing ***

    -- | \( O(n \min(d,W)) \). The @nubInt@ function removes duplicate 'Int'
    -- values from a list. In particular, it keeps only the first occurrence
    -- of each element. By using an 'IntSet' internally, it attains better
    -- asymptotics than the standard 'Data.List.nub' function.
    --
    -- See also 'nubIntOn', a more widely applicable generalization.
    --
    -- ==== Strictness
    --
    -- @nubInt@ is strict in the elements of the list.
    --
    -- @since 0.6.0.1
    nubInt :: [Int] -> [Int]
    nubInt :: [Int] -> [Int]
    nubInt = (Int -> Int) -> [Int] -> [Int]
    forall a. (a -> Int) -> [a] -> [a]
    nubIntOn Int -> Int
    forall a. a -> a
    id
    {-# INLINE nubInt #-}

    -- | The @nubIntOn@ function behaves just like 'nubInt' except it performs
    -- comparisons not on the original datatype, but a user-specified projection
    -- from that datatype. For example, @nubIntOn 'fromEnum'@ can be used to
    -- nub characters and typical fixed-with numerical types efficiently.
    --
    -- ==== Strictness
    --
    -- @nubIntOn@ is strict in the values of the function applied to the
    -- elements of the list.
    --
    -- @since 0.6.0.1
    nubIntOn :: (a -> Int) -> [a] -> [a]
    -- For some reason we need to write an explicit lambda here to allow this
    -- to inline when only applied to a function.
    nubIntOn :: forall a. (a -> Int) -> [a] -> [a]
    nubIntOn a -> Int
    f = \[a]
    xs -> (a -> Int) -> IntSet -> [a] -> [a]
    forall a. (a -> Int) -> IntSet -> [a] -> [a]
    nubIntOnExcluding a -> Int
    f IntSet
    IntSet.empty [a]
    xs
    {-# INLINE nubIntOn #-}

    -- Splitting nubIntOn like this means that we don't have to worry about
    -- matching specifically on IntSet.empty in the rewrite-back rule.
    nubIntOnExcluding :: (a -> Int) -> IntSet -> [a] -> [a]
    nubIntOnExcluding :: forall a. (a -> Int) -> IntSet -> [a] -> [a]
    nubIntOnExcluding a -> Int
    f = IntSet -> [a] -> [a]
    go
      where
        go :: IntSet -> [a] -> [a]
    go IntSet
    _ [] = []
        go IntSet
    s (a
    x:[a]
    xs)
          | Int
    fx Int -> IntSet -> Bool
    `IntSet.member` IntSet
    s = IntSet -> [a] -> [a]
    go IntSet
    s [a]
    xs
          | Bool
    otherwise = a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : IntSet -> [a] -> [a]
    go (Int -> IntSet -> IntSet
    IntSet.insert Int
    fx IntSet
    s) [a]
    xs
          where !fx :: Int
    fx = a -> Int
    f a
    x

    #ifdef __GLASGOW_HASKELL__
    -- We don't mark this INLINABLE because it doesn't seem obviously useful
    -- to inline it anywhere; the elements the function operates on are actually
    -- pulled from a list and installed in a list; the situation is very different
    -- when fusion occurs. In this case, we let GHC make the call.
    {-# NOINLINE [1] nubIntOnExcluding #-}

    {-# RULES
    "nubIntOn" [~1] forall f as s. nubIntOnExcluding  f s as =
      build (\c n -> foldr (nubIntOnFB f c) (constNubOn n) as s)
    "nubIntOnList" [1] forall f as s. foldr (nubIntOnFB f (:)) (constNubOn []) as s =
      nubIntOnExcluding f s as
     #-}

    nubIntOnFB :: (a -> Int)
               -> (a -> r -> r)
               -> a
               -> (IntSet -> r)
               -> IntSet
               -> r
    nubIntOnFB :: forall a r.
    (a -> Int) -> (a -> r -> r) -> a -> (IntSet -> r) -> IntSet -> r
    nubIntOnFB a -> Int
    f a -> r -> r
    c a
    x IntSet -> r
    r IntSet
    s
      | Int
    fx Int -> IntSet -> Bool
    `IntSet.member` IntSet
    s = IntSet -> r
    r IntSet
    s
      | Bool
    otherwise = a
    x a -> r -> r
    `c` IntSet -> r
    r (Int -> IntSet -> IntSet
    IntSet.insert Int
    fx IntSet
    s)
      where !fx :: Int
    fx = a -> Int
    f a
    x
    {-# INLINABLE [0] nubIntOnFB #-}
    #endif