-----------------------------------------------------------------------------
-- |
-- Module      :  Data.List.UniqueStrict
-- Copyright   :  (c) Volodymyr Yashchenko
-- License     :  BSD3
--
-- Maintainer  :  ualinuxcn@gmail.com
-- Stability   :  Unstable
-- Portability :  portable
--
-- Library provides functions to find unique and duplicate elements in the list.
-- Unlike Data.List.Unique this one uses Data.Map.Strict for calculations.
-- So it's much faster and it uses less memory.

module Data.List.UniqueStrict
        ( sortUniq
        , isUnique
        , isRepeated
        , repeated
        , repeatedBy
        , unique
        , allUnique
        , count
        , count_
        , occurrences )
        where

import qualified Data.Map.Strict    as MS (Map, filter, fromListWith, keys,
                                           toList, lookup, map, foldr')
import qualified Data.IntMap.Strict as IM (fromAscListWith, toList)
import qualified Data.Set           as DS (fromList, toList)

import Data.List                          (sortBy)
import Data.Function                      (on)


countMap :: Ord a => [a] -> MS.Map a Int
countMap = MS.fromListWith (+) . flip zip (repeat 1)

-- | 'isUnique' function is to check whether the given element is unique in the list or not.
--
-- It returns Nothing when the element does not present in the list. Examples:
--
-- > isUnique 'f' "foo bar" == Just True
-- > isUnique 'o' "foo bar" == Just False
-- > isUnique '!' "foo bar" == Nothing
--
-- Since 0.4.7.2
--

isUnique :: Ord a => a -> [a] -> Maybe Bool
isUnique x = fmap (== 1) . MS.lookup x . countMap

-- | 'isRepeated' is a reverse function to 'isUnique'
--
-- Since 0.4.5

isRepeated :: Ord a => a -> [a] -> Maybe Bool
isRepeated x = fmap not . isUnique x

-- | 'sortUniq' sorts the list and removes the duplicates of elements. Example:
--
-- > sortUniq "foo bar" == " abfor"

sortUniq :: Ord a => [a] -> [a]
sortUniq = DS.toList . DS.fromList

-- | The 'repeatedBy' function behaves just like repeated, except it uses a user-supplied equality predicate.
--
-- > repeatedBy (>2) "This is the test line" == " eist"

repeatedBy :: Ord a => (Int -> Bool) -> [a] -> [a]
repeatedBy p = MS.keys . MS.filter p . countMap

-- | 'repeated' finds only the elements that are present more than once in the list. Example:
--
-- > repeated  "foo bar" == "o"

repeated :: Ord a => [a] -> [a]
repeated = repeatedBy (>1)

-- | 'unique' gets only unique elements, that do not have duplicates.
-- It sorts them. Example:
--
-- > unique  "foo bar" == " abfr"

unique :: Ord a => [a] -> [a]
unique = repeatedBy (==1)

-- | 'allUnique' checks whether all elements of the list are unique
--
-- > allUnique "foo bar" == False
-- > allUnique ['a'..'z'] == True
-- > allUnique [] == True (!)
-- Since 0.4.7.2

allUnique :: Ord a => [a] -> Bool
allUnique = MS.foldr' (&&) True . MS.map (==1) . countMap

-- | 'count' of each element in the list, it sorts by keys (elements). Example:
--
-- > count "foo bar" == [(' ',1),('a',1),('b',1),('f',1),('o',2),('r',1)]

count :: Ord a => [a] -> [(a, Int)]
count = MS.toList . countMap

-- | 'count_' of each elements in the list, it sorts by their number. Example:
--
-- > count_ "foo bar" == [(' ',1),('a',1),('b',1),('f',1),('r',1),('o',2)]

count_ :: Ord a => [a] -> [(a, Int)]
count_ = sortBy (compare `on` snd) . MS.toList . countMap

-- | 'occurrences' like 'count' or 'count_' but shows the list of elements that occur X times
--
-- > occurrences "This is the test line" == [(1,"Tln"),(2,"h"),(3,"eist"),(4," ")]
-- Since 0.4.7.5
--

occurrences :: Ord a => [a] -> [(Int, [a])]
occurrences = IM.toList . IM.fromAscListWith (++) . map (\(k , x) -> (x, [k]) ) . count_