{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE LinearTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StrictData #-}
{-# OPTIONS_GHC -Wno-name-shadowing #-}

-- |
-- This module defines linear mutable sets.
--
-- The underlying implementation uses 'Data.HashMap.Linear', so it inherits
-- the time and memory characteristics of it.
--
-- Please import this module qualified to avoid name clashes.
module Data.Set.Mutable.Linear
  ( -- * Mutable Sets
    Set,
    empty,
    insert,
    delete,
    union,
    intersection,
    size,
    member,
    fromList,
    toList,
    Keyed,
  )
where

import qualified Data.HashMap.Mutable.Linear as Linear
import qualified Prelude.Linear as Linear hiding (insert)
import Prelude (Int, Bool)
import qualified Prelude
import Data.Monoid.Linear
import Data.Unrestricted.Linear


-- # Data Definitions
-------------------------------------------------------------------------------

-- XXX This representation could be improved on with AVL trees, for example
newtype Set a = Set (Linear.HashMap a ())

type Keyed a = Linear.Keyed a


-- # Constructors and Mutators
-------------------------------------------------------------------------------

empty :: Keyed a => Int -> (Set a %1-> Ur b) %1-> Ur b
empty :: forall a b. Keyed a => Int -> (Set a %1 -> Ur b) %1 -> Ur b
empty Int
s (Set a %1 -> Ur b
f :: Set a %1-> Ur b) =
  Int -> (HashMap a () %1 -> Ur b) %1 -> Ur b
forall k v b. Keyed k => Int -> (HashMap k v %1 -> Ur b) %1 -> Ur b
Linear.empty Int
s (\HashMap a ()
hm -> Set a %1 -> Ur b
f (HashMap a () %1 -> Set a
forall a. HashMap a () -> Set a
Set HashMap a ()
hm))

toList :: Keyed a => Set a %1-> Ur [a]
toList :: forall a. Keyed a => Set a %1 -> Ur [a]
toList (Set HashMap a ()
hm) =
  HashMap a () %1 -> Ur [(a, ())]
forall k v. HashMap k v %1 -> Ur [(k, v)]
Linear.toList HashMap a ()
hm
    Ur [(a, ())] %1 -> (Ur [(a, ())] %1 -> Ur [a]) %1 -> Ur [a]
forall a b. a %1 -> (a %1 -> b) %1 -> b
Linear.& \(Ur [(a, ())]
xs) -> [a] -> Ur [a]
forall a. a -> Ur a
Ur (((a, ()) -> a) -> [(a, ())] -> [a]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map (a, ()) -> a
forall a b. (a, b) -> a
Prelude.fst [(a, ())]
xs)

insert :: Keyed a => a -> Set a %1-> Set a
insert :: forall a. Keyed a => a -> Set a %1 -> Set a
insert a
a (Set HashMap a ()
hmap) = HashMap a () %1 -> Set a
forall a. HashMap a () -> Set a
Set (a -> () -> HashMap a () %1 -> HashMap a ()
forall k v. Keyed k => k -> v -> HashMap k v %1 -> HashMap k v
Linear.insert a
a () HashMap a ()
hmap)

delete :: Keyed a => a -> Set a %1-> Set a
delete :: forall a. Keyed a => a -> Set a %1 -> Set a
delete a
a (Set HashMap a ()
hmap) = HashMap a () %1 -> Set a
forall a. HashMap a () -> Set a
Set (a -> HashMap a () %1 -> HashMap a ()
forall k v. Keyed k => k -> HashMap k v %1 -> HashMap k v
Linear.delete a
a HashMap a ()
hmap)

union :: Keyed a => Set a %1-> Set a %1-> Set a
union :: forall a. Keyed a => Set a %1 -> Set a %1 -> Set a
union (Set HashMap a ()
hm1) (Set HashMap a ()
hm2) =
  HashMap a () %1 -> Set a
forall a. HashMap a () -> Set a
Set ((() -> () -> ())
-> HashMap a () %1 -> HashMap a () %1 -> HashMap a ()
forall k v.
Keyed k =>
(v -> v -> v) -> HashMap k v %1 -> HashMap k v %1 -> HashMap k v
Linear.unionWith (\()
_ ()
_ -> ()) HashMap a ()
hm1 HashMap a ()
hm2)

intersection :: Keyed a => Set a %1-> Set a %1-> Set a
intersection :: forall a. Keyed a => Set a %1 -> Set a %1 -> Set a
intersection (Set HashMap a ()
hm1) (Set HashMap a ()
hm2) =
  HashMap a () %1 -> Set a
forall a. HashMap a () -> Set a
Set ((() -> () -> ())
-> HashMap a () %1 -> HashMap a () %1 -> HashMap a ()
forall k a b c.
Keyed k =>
(a -> b -> c) -> HashMap k a %1 -> HashMap k b %1 -> HashMap k c
Linear.intersectionWith (\()
_ ()
_ -> ()) HashMap a ()
hm1 HashMap a ()
hm2)

-- # Accessors
-------------------------------------------------------------------------------

size :: Keyed a => Set a %1-> (Ur Int, Set a)
size :: forall a. Keyed a => Set a %1 -> (Ur Int, Set a)
size (Set HashMap a ()
hm) =
  HashMap a () %1 -> (Ur Int, HashMap a ())
forall k v. HashMap k v %1 -> (Ur Int, HashMap k v)
Linear.size HashMap a ()
hm (Ur Int, HashMap a ())
%1 -> ((Ur Int, HashMap a ()) %1 -> (Ur Int, Set a))
%1 -> (Ur Int, Set a)
forall a b. a %1 -> (a %1 -> b) %1 -> b
Linear.& \(Ur Int
s, HashMap a ()
hm') -> (Ur Int
s, HashMap a () %1 -> Set a
forall a. HashMap a () -> Set a
Set HashMap a ()
hm')

member :: Keyed a => a -> Set a %1-> (Ur Bool, Set a)
member :: forall a. Keyed a => a -> Set a %1 -> (Ur Bool, Set a)
member a
a (Set HashMap a ()
hm) =
  a -> HashMap a () %1 -> (Ur Bool, HashMap a ())
forall k v.
Keyed k =>
k -> HashMap k v %1 -> (Ur Bool, HashMap k v)
Linear.member a
a HashMap a ()
hm (Ur Bool, HashMap a ())
%1 -> ((Ur Bool, HashMap a ()) %1 -> (Ur Bool, Set a))
%1 -> (Ur Bool, Set a)
forall a b. a %1 -> (a %1 -> b) %1 -> b
Linear.& \(Ur Bool
b, HashMap a ()
hm') -> (Ur Bool
b, HashMap a () %1 -> Set a
forall a. HashMap a () -> Set a
Set HashMap a ()
hm')

fromList :: Keyed a => [a] -> (Set a %1-> Ur b) %1-> Ur b
fromList :: forall a b. Keyed a => [a] -> (Set a %1 -> Ur b) %1 -> Ur b
fromList [a]
xs Set a %1 -> Ur b
f =
  [(a, ())] -> (HashMap a () %1 -> Ur b) %1 -> Ur b
forall k v b.
Keyed k =>
[(k, v)] -> (HashMap k v %1 -> Ur b) %1 -> Ur b
Linear.fromList ((a -> (a, ())) -> [a] -> [(a, ())]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map (,()) [a]
xs) (\HashMap a ()
hm -> Set a %1 -> Ur b
f (HashMap a () %1 -> Set a
forall a. HashMap a () -> Set a
Set HashMap a ()
hm))

-- # Typeclass Instances
-------------------------------------------------------------------------------

instance Prelude.Semigroup (Set a) where
  <> :: Set a -> Set a -> Set a
(<>) = [Char] -> Set a -> Set a -> Set a
forall a. HasCallStack => [Char] -> a
Prelude.error [Char]
"Prelude.(<>): invariant violation, unrestricted Set"

instance Keyed a => Semigroup (Set a) where
  <> :: Set a %1 -> Set a %1 -> Set a
(<>) = Set a %1 -> Set a %1 -> Set a
forall a. Keyed a => Set a %1 -> Set a %1 -> Set a
union

instance Consumable (Set a) where
  consume :: Set a %1 -> ()
consume (Set HashMap a ()
hmap) = HashMap a () %1 -> ()
forall a. Consumable a => a %1 -> ()
consume HashMap a ()
hmap

instance Dupable (Set a) where
  dup2 :: Set a %1 -> (Set a, Set a)
dup2 (Set HashMap a ()
hm) = HashMap a () %1 -> (HashMap a (), HashMap a ())
forall a. Dupable a => a %1 -> (a, a)
dup2 HashMap a ()
hm (HashMap a (), HashMap a ())
%1 -> ((HashMap a (), HashMap a ()) %1 -> (Set a, Set a))
%1 -> (Set a, Set a)
forall a b. a %1 -> (a %1 -> b) %1 -> b
Linear.& \(HashMap a ()
hm1, HashMap a ()
hm2) ->
    (HashMap a () %1 -> Set a
forall a. HashMap a () -> Set a
Set HashMap a ()
hm1, HashMap a () %1 -> Set a
forall a. HashMap a () -> Set a
Set HashMap a ()
hm2)