puresat-0.1: Pure Haskell SAT-solver
Safe HaskellNone
LanguageHaskell2010

PureSAT.SparseSet

Synopsis

Documentation

data SparseSet s Source #

https://research.swtch.com/sparse

An Int set which support efficient popping (popSparseSet).

Constructors

SS 

Fields

sizeofSparseSet :: SparseSet s -> ST s Int Source #

Size of sparse set.

>>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; sizeofSparseSet set }
5

indexSparseSet :: SparseSet s -> Int -> ST s Int Source #

newSparseSet Source #

Arguments

:: Int

max integer

-> ST s (SparseSet s) 

Create new sparse set

>>> runST $ newSparseSet 100 >>= elemsSparseSet
[]

memberSparseSet :: SparseSet s -> Int -> ST s Bool Source #

Test for membership

>>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; memberSparseSet set 10 }
False
>>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; memberSparseSet set 13 }
True

insertSparseSet :: SparseSet s -> Int -> ST s () Source #

Insert into set

>>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; elemsSparseSet set }
[3,5,7,11,13]

deleteSparseSet :: SparseSet s -> Int -> ST s () Source #

Delete from set

>>> runST $ do { set <- newSparseSet 100; deleteSparseSet set 10; elemsSparseSet set }
[]
>>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; deleteSparseSet set 10; elemsSparseSet set }
[3,5,7,11,13]
>>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; deleteSparseSet set 13; elemsSparseSet set }
[3,5,7,11]
>>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; deleteSparseSet set 11; elemsSparseSet set }
[3,5,7,13]

popSparseSet :: SparseSet s -> ST s (Maybe Int) Source #

Pop element from the set.

>>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; popSparseSet set }
Just 13

popSparseSet_ :: SparseSet s -> ST s r -> (Int -> ST s r) -> ST s r Source #

elemsSparseSet :: SparseSet s -> ST s [Int] Source #

Elements of the set

clearSparseSet :: SparseSet s -> ST s () Source #

Clear sparse set.

>>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; clearSparseSet set; elemsSparseSet set }
[]