{-# 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 :: (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
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 :: (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