Safe Haskell | None |
---|---|
Language | Haskell2010 |
PureSAT.SparseMaxHeap
Synopsis
- data SparseHeap s
- type Weight = Word
- sizeofSparseHeap :: SparseHeap s -> ST s Int
- newSparseHeap :: Int -> ST s (SparseHeap s)
- cloneSparseHeap :: SparseHeap s -> ST s (SparseHeap s)
- memberSparseHeap :: SparseHeap s -> Int -> ST s Bool
- insertSparseHeap :: SparseHeap s -> Int -> ST s ()
- deleteSparseHeap :: SparseHeap s -> Int -> ST s ()
- popSparseHeap :: SparseHeap s -> ST s (Maybe Int)
- popSparseHeap_ :: SparseHeap s -> ST s r -> (Int -> ST s r) -> ST s r
- elemsSparseHeap :: SparseHeap s -> ST s [Int]
- clearSparseHeap :: SparseHeap s -> ST s ()
- extendSparseHeap :: Int -> SparseHeap s -> ST s (SparseHeap s)
- drainSparseHeap :: SparseHeap s -> ST s [Int]
- modifyWeightSparseHeap :: SparseHeap s -> Int -> (Weight -> Weight) -> ST s ()
- scaleWeightsSparseHeap :: SparseHeap s -> (Weight -> Weight) -> ST s ()
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.
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
Arguments
:: Int | max integer |
-> ST s (SparseHeap s) |
Create new sparse heap.
>>>
runST $ newSparseHeap 100 >>= elemsSparseHeap
[]
cloneSparseHeap :: SparseHeap s -> ST s (SparseHeap s) Source #
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 }
[]
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
scaleWeightsSparseHeap :: SparseHeap s -> (Weight -> Weight) -> ST s () Source #