module Data.List.Extended
  ( duplicates,
    uniques,
    getDifference,
    getDifferenceOn,
    getOverlapWith,
    longestCommonPrefix,
    appendToNonEmpty,
    module L,
  )
where

import Data.Function (on)
import Data.HashMap.Strict.Extended qualified as Map
import Data.HashSet qualified as Set
import Data.Hashable (Hashable)
import Data.List qualified as L
import Data.List.NonEmpty qualified as NE
import Data.Set qualified as S
import Prelude

duplicates :: (Eq a, Hashable a) => [a] -> Set.HashSet a
duplicates :: [a] -> HashSet a
duplicates =
  [a] -> HashSet a
forall a. (Eq a, Hashable a) => [a] -> HashSet a
Set.fromList ([a] -> HashSet a) -> ([a] -> [a]) -> [a] -> HashSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap a Int -> [a]
forall k v. HashMap k v -> [k]
Map.keys (HashMap a Int -> [a]) -> ([a] -> HashMap a Int) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Bool) -> HashMap a Int -> HashMap a Int
forall v k. (v -> Bool) -> HashMap k v -> HashMap k v
Map.filter (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
1) (HashMap a Int -> HashMap a Int)
-> ([a] -> HashMap a Int) -> [a] -> HashMap a Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Int -> Int) -> [(a, Int)] -> HashMap a Int
forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> [(k, v)] -> HashMap k v
Map.fromListWith Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) ([(a, Int)] -> HashMap a Int)
-> ([a] -> [(a, Int)]) -> [a] -> HashMap a Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (a, Int)) -> [a] -> [(a, Int)]
forall a b. (a -> b) -> [a] -> [b]
map (,Int
1 :: Int)

uniques :: (Ord a) => [a] -> [a]
uniques :: [a] -> [a]
uniques = Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> ([a] -> Set a) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList

getDifference :: (Eq a, Hashable a) => [a] -> [a] -> Set.HashSet a
getDifference :: [a] -> [a] -> HashSet a
getDifference = HashSet a -> HashSet a -> HashSet a
forall a. (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
Set.difference (HashSet a -> HashSet a -> HashSet a)
-> ([a] -> HashSet a) -> [a] -> [a] -> HashSet a
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` [a] -> HashSet a
forall a. (Eq a, Hashable a) => [a] -> HashSet a
Set.fromList

getDifferenceOn :: (Eq k, Hashable k) => (v -> k) -> [v] -> [v] -> [v]
getDifferenceOn :: (v -> k) -> [v] -> [v] -> [v]
getDifferenceOn v -> k
f [v]
l = HashMap k v -> [v]
forall k v. HashMap k v -> [v]
Map.elems (HashMap k v -> [v]) -> ([v] -> HashMap k v) -> [v] -> [v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (v -> k) -> [v] -> [v] -> HashMap k v
forall k (t :: * -> *) v.
(Eq k, Hashable k, Foldable t) =>
(v -> k) -> t v -> t v -> HashMap k v
Map.differenceOn v -> k
f [v]
l

getOverlapWith :: (Eq k, Hashable k) => (v -> k) -> [v] -> [v] -> [(v, v)]
getOverlapWith :: (v -> k) -> [v] -> [v] -> [(v, v)]
getOverlapWith v -> k
getKey [v]
left [v]
right =
  HashMap k (v, v) -> [(v, v)]
forall k v. HashMap k v -> [v]
Map.elems (HashMap k (v, v) -> [(v, v)]) -> HashMap k (v, v) -> [(v, v)]
forall a b. (a -> b) -> a -> b
$ (v -> v -> (v, v))
-> HashMap k v -> HashMap k v -> HashMap k (v, v)
forall k v1 v2 v3.
(Eq k, Hashable k) =>
(v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3
Map.intersectionWith (,) ([v] -> HashMap k v
mkMap [v]
left) ([v] -> HashMap k v
mkMap [v]
right)
  where
    mkMap :: [v] -> HashMap k v
mkMap = [(k, v)] -> HashMap k v
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
Map.fromList ([(k, v)] -> HashMap k v)
-> ([v] -> [(k, v)]) -> [v] -> HashMap k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (v -> (k, v)) -> [v] -> [(k, v)]
forall a b. (a -> b) -> [a] -> [b]
map (\v
v -> (v -> k
getKey v
v, v
v))

-- | Returns the longest prefix common to all given lists. Returns an empty list on an empty list.
--
-- >>> longestCommonPrefix ["abcd", "abce", "abgh"]
-- "ab"
--
-- >>> longestCommonPrefix []
-- []
longestCommonPrefix :: Eq a => [[a]] -> [a]
longestCommonPrefix :: [[a]] -> [a]
longestCommonPrefix [] = []
longestCommonPrefix ([a]
x : [[a]]
xs) = ([a] -> [a] -> [a]) -> [a] -> [[a]] -> [a]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr [a] -> [a] -> [a]
forall b. Eq b => [b] -> [b] -> [b]
prefix [a]
x [[a]]
xs
  where
    prefix :: [b] -> [b] -> [b]
prefix [b]
l1 [b]
l2 = ((b, b) -> b) -> [(b, b)] -> [b]
forall a b. (a -> b) -> [a] -> [b]
map (b, b) -> b
forall a b. (a, b) -> a
fst ([(b, b)] -> [b]) -> [(b, b)] -> [b]
forall a b. (a -> b) -> a -> b
$ ((b, b) -> Bool) -> [(b, b)] -> [(b, b)]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile ((b -> b -> Bool) -> (b, b) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry b -> b -> Bool
forall a. Eq a => a -> a -> Bool
(==)) ([(b, b)] -> [(b, b)]) -> [(b, b)] -> [(b, b)]
forall a b. (a -> b) -> a -> b
$ [b] -> [b] -> [(b, b)]
forall a b. [a] -> [b] -> [(a, b)]
zip [b]
l1 [b]
l2

appendToNonEmpty :: NE.NonEmpty a -> [a] -> NE.NonEmpty a
appendToNonEmpty :: NonEmpty a -> [a] -> NonEmpty a
appendToNonEmpty (a
neHead NE.:| [a]
neList) [a]
list =
  a
neHead a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
NE.:| ([a]
neList [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> [a]
list)