{-
%------------------------------------------------------------------------------
% Copyright (C) 1997, 1998, 2008 Joern Dinkla, www.dinkla.net
%------------------------------------------------------------------------------
%
% see
%     Joern Dinkla, Geometrische Algorithmen in Haskell, Diploma Thesis,
%     University of Bonn, Germany, 1998. 
%
-}

-- | Mengen von Indizes 
-- Mit Hilfe der 'ST'-Monade definiert King [K96, ch. 6.5] eine Menge 'Set' und
-- die Funktionen 'mkEmpty', 'contains' und 'include', die $O(1)$ Zeit benötigen.
-- See <http://www.macs.hw.ac.uk/~gnik/publications/singlesided-thesis.ps.gz>.

module GeomAlg.External.STUtils ( 
	Set, mkEmpty, contains, include, accumulate
) where

import Control.Monad.ST ( ST )
import Data.Array.ST ( STArray )
import Data.Array.MArray ( MArray, newArray, readArray, writeArray,
            freeze, getBounds) 
import qualified Array (Array, array)
import Data.Ix (Ix (..))

type Set s a = STArray s a Bool

mkEmpty :: Ix a => (a,a) -> ST s (Set s a)
mkEmpty bnds = newArray bnds False

contains :: Ix a => Set s a -> a -> ST s Bool
contains m v = readArray m v

include :: Ix a => Set s a -> a -> ST s ()
include m v  = writeArray m v True

accumulate        :: Monad m => [m a] -> m [a] 
accumulate []     = return [] 
accumulate (c:cs) = do x <- c 
                       xs <- accumulate cs 
                       return (x:xs)