{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DeriveAnyClass #-}

module Language.REST.Internal.MultiSet
  ( MultiSet
  , delete
  , deleteMany
  , distinctElems
  , empty
  , filter
  , insert
  , member
  , null
  , toList
  , toOccurList
  , singleton
  , fromList
  , toSet
  ) where

import Prelude hiding (null, filter)

import GHC.Generics
import Data.Hashable
import qualified Data.List as L
import qualified Data.HashMap.Strict as M
import qualified Data.HashSet as S

newtype MultiSet a = MultiSet (M.HashMap a Int) deriving (MultiSet a -> MultiSet a -> Bool
forall a. Eq a => MultiSet a -> MultiSet a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: MultiSet a -> MultiSet a -> Bool
$c/= :: forall a. Eq a => MultiSet a -> MultiSet a -> Bool
== :: MultiSet a -> MultiSet a -> Bool
$c== :: forall a. Eq a => MultiSet a -> MultiSet a -> Bool
Eq, forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (MultiSet a) x -> MultiSet a
forall a x. MultiSet a -> Rep (MultiSet a) x
$cto :: forall a x. Rep (MultiSet a) x -> MultiSet a
$cfrom :: forall a x. MultiSet a -> Rep (MultiSet a) x
Generic, forall a. Eq a -> (Int -> a -> Int) -> (a -> Int) -> Hashable a
forall {a}. Hashable a => Eq (MultiSet a)
forall a. Hashable a => Int -> MultiSet a -> Int
forall a. Hashable a => MultiSet a -> Int
hash :: MultiSet a -> Int
$chash :: forall a. Hashable a => MultiSet a -> Int
hashWithSalt :: Int -> MultiSet a -> Int
$chashWithSalt :: forall a. Hashable a => Int -> MultiSet a -> Int
Hashable, MultiSet a -> MultiSet a -> Bool
MultiSet a -> MultiSet a -> Ordering
MultiSet a -> MultiSet a -> MultiSet 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 (MultiSet a)
forall a. Ord a => MultiSet a -> MultiSet a -> Bool
forall a. Ord a => MultiSet a -> MultiSet a -> Ordering
forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
min :: MultiSet a -> MultiSet a -> MultiSet a
$cmin :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
max :: MultiSet a -> MultiSet a -> MultiSet a
$cmax :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
>= :: MultiSet a -> MultiSet a -> Bool
$c>= :: forall a. Ord a => MultiSet a -> MultiSet a -> Bool
> :: MultiSet a -> MultiSet a -> Bool
$c> :: forall a. Ord a => MultiSet a -> MultiSet a -> Bool
<= :: MultiSet a -> MultiSet a -> Bool
$c<= :: forall a. Ord a => MultiSet a -> MultiSet a -> Bool
< :: MultiSet a -> MultiSet a -> Bool
$c< :: forall a. Ord a => MultiSet a -> MultiSet a -> Bool
compare :: MultiSet a -> MultiSet a -> Ordering
$ccompare :: forall a. Ord a => MultiSet a -> MultiSet a -> Ordering
Ord)

instance Show a => Show (MultiSet a) where
  show :: MultiSet a -> String
show MultiSet a
ms = String
"{" forall a. [a] -> [a] -> [a]
++ forall a. [a] -> [[a]] -> [a]
L.intercalate String
", " (forall a b. (a -> b) -> [a] -> [b]
map forall a. Show a => a -> String
show forall a b. (a -> b) -> a -> b
$ forall a. MultiSet a -> [a]
toList MultiSet a
ms) forall a. [a] -> [a] -> [a]
++ String
"}"

-- | @delete k m@ removes a single instance of @k@ from the multiset @m.
--   If @k is not in the multiset, the original multiset is returned
delete :: (Hashable a, Eq a) => a -> MultiSet a -> MultiSet a
delete :: forall a. (Hashable a, Eq a) => a -> MultiSet a -> MultiSet a
delete a
k = forall a.
(Hashable a, Eq a) =>
a -> Int -> MultiSet a -> MultiSet a
deleteMany a
k Int
1

-- | @delete k n m@ removes @n@ instances of @k@ from the multiset @m@.
--   If there are less than @n@ instances of @k@ in the multiset, all
--   instances are removed.
deleteMany :: (Hashable a, Eq a) => a -> Int -> MultiSet a -> MultiSet a
deleteMany :: forall a.
(Hashable a, Eq a) =>
a -> Int -> MultiSet a -> MultiSet a
deleteMany a
k Int
v (MultiSet HashMap a Int
ms) | Just Int
c <- forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
M.lookup a
k HashMap a Int
ms
                             , Int
c forall a. Ord a => a -> a -> Bool
> Int
v = forall a. HashMap a Int -> MultiSet a
MultiSet forall a b. (a -> b) -> a -> b
$ forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
M.insert a
k (Int
c forall a. Num a => a -> a -> a
- Int
v) HashMap a Int
ms
deleteMany a
k Int
_ (MultiSet HashMap a Int
ms)  = forall a. HashMap a Int -> MultiSet a
MultiSet forall a b. (a -> b) -> a -> b
$ forall k v. (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v
M.delete a
k HashMap a Int
ms

distinctElems :: MultiSet a -> [a]
distinctElems :: forall a. MultiSet a -> [a]
distinctElems (MultiSet HashMap a Int
ms) = forall k v. HashMap k v -> [k]
M.keys HashMap a Int
ms

empty :: MultiSet a
empty :: forall a. MultiSet a
empty = forall a. HashMap a Int -> MultiSet a
MultiSet forall k v. HashMap k v
M.empty

toOccurList :: MultiSet a -> [(a, Int)]
toOccurList :: forall a. MultiSet a -> [(a, Int)]
toOccurList (MultiSet HashMap a Int
ms) = forall k v. HashMap k v -> [(k, v)]
M.toList HashMap a Int
ms

filter :: (a -> Bool) -> MultiSet a -> MultiSet a
filter :: forall a. (a -> Bool) -> MultiSet a -> MultiSet a
filter a -> Bool
f (MultiSet HashMap a Int
ms) = forall a. HashMap a Int -> MultiSet a
MultiSet forall a b. (a -> b) -> a -> b
$ forall k v. (k -> v -> Bool) -> HashMap k v -> HashMap k v
M.filterWithKey forall {p}. a -> p -> Bool
f' HashMap a Int
ms
  where
    f' :: a -> p -> Bool
f' a
k p
_ = a -> Bool
f a
k

null :: MultiSet a -> Bool
null :: forall a. MultiSet a -> Bool
null (MultiSet HashMap a Int
ms) = forall k v. HashMap k v -> Bool
M.null HashMap a Int
ms

-- | @member k m@ returns @true@ iff there is at least one instance of @k@
--   in @m@
member :: (Eq a, Hashable a) => a -> MultiSet a -> Bool
member :: forall a. (Eq a, Hashable a) => a -> MultiSet a -> Bool
member a
k (MultiSet HashMap a Int
ms) = forall k a. (Eq k, Hashable k) => k -> HashMap k a -> Bool
M.member a
k HashMap a Int
ms

toList :: MultiSet a -> [a]
toList :: forall a. MultiSet a -> [a]
toList MultiSet a
ms = forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap forall {a}. (a, Int) -> [a]
go (forall a. MultiSet a -> [(a, Int)]
toOccurList MultiSet a
ms)
  where
    go :: (a, Int) -> [a]
go (a
k, Int
num) = forall a. Int -> a -> [a]
replicate Int
num a
k

insert :: (Eq a, Hashable a) => a -> MultiSet a -> MultiSet a
insert :: forall a. (Eq a, Hashable a) => a -> MultiSet a -> MultiSet a
insert a
k (MultiSet HashMap a Int
ms) | Just Int
c <- forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
M.lookup a
k HashMap a Int
ms
                       = forall a. HashMap a Int -> MultiSet a
MultiSet forall a b. (a -> b) -> a -> b
$ forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
M.insert a
k (Int
c forall a. Num a => a -> a -> a
+ Int
1) HashMap a Int
ms
insert a
k (MultiSet HashMap a Int
ms)
                       = forall a. HashMap a Int -> MultiSet a
MultiSet forall a b. (a -> b) -> a -> b
$ forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
M.insert a
k Int
1 HashMap a Int
ms

singleton :: (Eq a, Hashable a) => a -> MultiSet a
singleton :: forall a. (Eq a, Hashable a) => a -> MultiSet a
singleton a
k = forall a. HashMap a Int -> MultiSet a
MultiSet (forall k v. Hashable k => k -> v -> HashMap k v
M.singleton a
k Int
1)

fromList  :: (Eq a, Hashable a) => [a] -> MultiSet a
fromList :: forall a. (Eq a, Hashable a) => [a] -> MultiSet a
fromList = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl (forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a. (Eq a, Hashable a) => a -> MultiSet a -> MultiSet a
insert) forall a. MultiSet a
empty

toSet :: MultiSet a -> S.HashSet a
toSet :: forall a. MultiSet a -> HashSet a
toSet (MultiSet HashMap a Int
ms) = forall k a. HashMap k a -> HashSet k
M.keysSet HashMap a Int
ms