module Util.VisitedSet(
   VisitedSet,
   newVisitedSet, -- :: Ord key => IO (VisitedSet key)
   isVisited,
      -- :: Ord key => VisitedSet key -> key -> IO Bool
      -- return True if the element has already been visited, otherwise
      -- visit it.
   ) where

import Control.Concurrent
import qualified Data.Set as Set

newtype VisitedSet key = VisitedSet (MVar (Set.Set key))

newVisitedSet :: Ord key => IO (VisitedSet key)
newVisitedSet :: IO (VisitedSet key)
newVisitedSet =
   do
      MVar (Set key)
mVar <- Set key -> IO (MVar (Set key))
forall a. a -> IO (MVar a)
newMVar Set key
forall a. Set a
Set.empty
      VisitedSet key -> IO (VisitedSet key)
forall (m :: * -> *) a. Monad m => a -> m a
return (MVar (Set key) -> VisitedSet key
forall key. MVar (Set key) -> VisitedSet key
VisitedSet MVar (Set key)
mVar)

isVisited :: Ord key => VisitedSet key -> key -> IO Bool
isVisited :: VisitedSet key -> key -> IO Bool
isVisited (VisitedSet MVar (Set key)
mVar) key
key =
   MVar (Set key) -> (Set key -> IO (Set key, Bool)) -> IO Bool
forall a b. MVar a -> (a -> IO (a, b)) -> IO b
modifyMVar MVar (Set key)
mVar
      (\ Set key
set ->
         (Set key, Bool) -> IO (Set key, Bool)
forall (m :: * -> *) a. Monad m => a -> m a
return (if key -> Set key -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member key
key Set key
set
            then
               (Set key
set,Bool
True)
            else
               (key -> Set key -> Set key
forall a. Ord a => a -> Set a -> Set a
Set.insert key
key Set key
set,Bool
False)
            )
         )