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

PureSAT.SparseMaxHeap

Synopsis

Documentation

data SparseHeap s Source #

Like sparse set https://research.swtch.com/sparse, but also a max heap https://en.wikipedia.org/wiki/Heap_(data_structure)

i.e. pop returns minimum element.

type Weight = Word Source #

sizeofSparseHeap :: SparseHeap s -> ST s Int Source #

Size of sparse heap.

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insertSparseHeap set) [3,5,7,11,13,11]; sizeofSparseHeap set }
5

newSparseHeap Source #

Arguments

:: Int

max integer

-> ST s (SparseHeap s) 

Create new sparse heap.

>>> runST $ newSparseHeap 100 >>= elemsSparseHeap
[]

memberSparseHeap :: SparseHeap s -> Int -> ST s Bool Source #

Test for membership.

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

insertSparseHeap :: SparseHeap s -> Int -> ST s () Source #

Insert into the heap.

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insertSparseHeap set) [3,5,7,11,13,11]; elemsSparseHeap set }
[3,5,7,11,13]

deleteSparseHeap :: SparseHeap s -> Int -> ST s () Source #

Delete element from the heap.

>>> runST $ do { set <- newSparseHeap 100; deleteSparseHeap set 10; elemsSparseHeap set }
[]
>>> let insert heap x = modifyWeightSparseHeap heap x (\_ -> fromIntegral $ 100 - x) >> insertSparseHeap heap x;
>>> runST $ do { set <- newSparseHeap 100; mapM_ (insert set) [3,5,7,11,13,11]; deleteSparseHeap set 10; elemsSparseHeap set }
[3,5,7,11,13]
>>> runST $ do { set <- newSparseHeap 100; mapM_ (insert set) [3,5,7,11,13,11]; deleteSparseHeap set 13; elemsSparseHeap set }
[3,5,7,11]
>>> runST $ do { set <- newSparseHeap 100; mapM_ (insert set) [3,5,7,11,13,11]; deleteSparseHeap set 11; elemsSparseHeap set }
[3,5,7,13]
>>> runST $ do { set <- newSparseHeap 100; mapM_ (insert set) [3,5,7,11,13,11]; deleteSparseHeap set 3; elemsSparseHeap set }
[5,11,7,13]
>>> runST $ do { set <- newSparseHeap 100; mapM_ (insert set) $ [0,2..20] ++ [19,17..3]; deleteSparseHeap set 10; elemsSparseHeap set }
[0,2,4,5,3,17,12,9,6,8,20,19,18,15,13,14,11,16,7]

popSparseHeap :: SparseHeap s -> ST s (Maybe Int) Source #

Pop element from the heap.

>>> let insert heap x = modifyWeightSparseHeap heap x (\_ -> - fromIntegral x) >> insertSparseHeap heap x;
>>> runST $ do { heap <- newSparseHeap 100; mapM_ (insert heap) [5,3,7,11,13,11]; popSparseHeap heap }
Just 3
>>> runST $ do { heap <- newSparseHeap 500; mapM_ (insert heap) [1..400]; drainSparseHeap heap }
[1,2...,400]

popSparseHeap_ :: SparseHeap s -> ST s r -> (Int -> ST s r) -> ST s r Source #

elemsSparseHeap :: SparseHeap s -> ST s [Int] Source #

Elements of the heap.

Returns elements as they are internally stored.

clearSparseHeap :: SparseHeap s -> ST s () Source #

Clear sparse heap.

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insertSparseHeap set) [3,5,7,11,13,11]; clearSparseHeap set; elemsSparseHeap set }
[]

extendSparseHeap Source #

Arguments

:: Int

new capacity

-> SparseHeap s 
-> ST s (SparseHeap s) 

Extend sparse heap to fit new capacity.

drainSparseHeap :: SparseHeap s -> ST s [Int] Source #

Drain element from the heap.

>>> let insert heap x = modifyWeightSparseHeap heap x (\_ -> - fromIntegral x) >> insertSparseHeap heap x;
>>> runST $ do { set <- newSparseHeap 100; mapM_ (insert set) [3,5,7,11,13,11]; drainSparseHeap set }
[3,5,7,11,13]

modifyWeightSparseHeap :: SparseHeap s -> Int -> (Weight -> Weight) -> ST s () Source #

Modify weight of the element.

>>> let insert heap x = modifyWeightSparseHeap heap x (\_ -> fromIntegral $ 100 - x) >> insertSparseHeap heap x;
>>> let populate heap = mapM_ (insert heap) [5,3,7,11,13,11]
>>> let populate' heap = mapM_ (insertSparseHeap heap) [5,3,7,11,13,11]
>>> runST $ do { heap <- newSparseHeap 100; populate heap; popSparseHeap heap }
Just 3
>>> runST $ do { heap <- newSparseHeap 100; populate heap; modifyWeightSparseHeap heap 3 (\_ -> 0); popSparseHeap heap }
Just 5

Weight are preserved even if element is not in the heap at the moment

>>> runST $ do { heap <- newSparseHeap 100; modifyWeightSparseHeap heap 7 (\_ -> 100); populate' heap; popSparseHeap heap }
Just 7