module AERN2.PQueue
(
PQueue
, null
, size
, singleton
, empty
, insert
, minView
)
where
import Prelude hiding (null)
import qualified Data.IntPSQ as Q
data PQueue p = PQueue { PQueue p -> IntPSQ p ()
pq_queue :: Q.IntPSQ p (), PQueue p -> Int
pq_nextKey :: Int }
null :: PQueue p -> Bool
null :: PQueue p -> Bool
null = IntPSQ p () -> Bool
forall p v. IntPSQ p v -> Bool
Q.null (IntPSQ p () -> Bool)
-> (PQueue p -> IntPSQ p ()) -> PQueue p -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PQueue p -> IntPSQ p ()
forall p. PQueue p -> IntPSQ p ()
pq_queue
size :: PQueue p -> Int
size :: PQueue p -> Int
size = IntPSQ p () -> Int
forall p v. IntPSQ p v -> Int
Q.size (IntPSQ p () -> Int)
-> (PQueue p -> IntPSQ p ()) -> PQueue p -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PQueue p -> IntPSQ p ()
forall p. PQueue p -> IntPSQ p ()
pq_queue
singleton :: (Ord p) => p -> PQueue p
singleton :: p -> PQueue p
singleton p
p = IntPSQ p () -> Int -> PQueue p
forall p. IntPSQ p () -> Int -> PQueue p
PQueue (Int -> p -> () -> IntPSQ p ()
forall p v. Ord p => Int -> p -> v -> IntPSQ p v
Q.singleton Int
0 p
p ()) Int
1
empty :: (Ord p) => PQueue p
empty :: PQueue p
empty = IntPSQ p () -> Int -> PQueue p
forall p. IntPSQ p () -> Int -> PQueue p
PQueue IntPSQ p ()
forall p v. IntPSQ p v
Q.empty Int
0
insert :: (Ord p) => p -> PQueue p -> PQueue p
insert :: p -> PQueue p -> PQueue p
insert p
p PQueue p
q
| Int
nextKey Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 =
IntPSQ p () -> Int -> PQueue p
forall p. IntPSQ p () -> Int -> PQueue p
PQueue (Int -> p -> () -> IntPSQ p () -> IntPSQ p ()
forall p v. Ord p => Int -> p -> v -> IntPSQ p v -> IntPSQ p v
Q.insert Int
nextKey p
p () (PQueue p -> IntPSQ p ()
forall p. PQueue p -> IntPSQ p ()
pq_queue PQueue p
q)) (Int
nextKey Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
| Bool
otherwise =
[Char] -> PQueue p
forall a. HasCallStack => [Char] -> a
error [Char]
"PQueue insert: key overflow"
where
nextKey :: Int
nextKey = PQueue p -> Int
forall p. PQueue p -> Int
pq_nextKey PQueue p
q
minView :: (Ord p) => PQueue p -> Maybe (p, PQueue p)
minView :: PQueue p -> Maybe (p, PQueue p)
minView PQueue p
q =
case IntPSQ p () -> Maybe (Int, p, (), IntPSQ p ())
forall p v. Ord p => IntPSQ p v -> Maybe (Int, p, v, IntPSQ p v)
Q.minView (PQueue p -> IntPSQ p ()
forall p. PQueue p -> IntPSQ p ()
pq_queue PQueue p
q) of
Just (Int
_,p
p,()
_,IntPSQ p ()
qq) -> (p, PQueue p) -> Maybe (p, PQueue p)
forall a. a -> Maybe a
Just (p
p, PQueue p
q { pq_queue :: IntPSQ p ()
pq_queue = IntPSQ p ()
qq })
Maybe (Int, p, (), IntPSQ p ())
Nothing -> Maybe (p, PQueue p)
forall a. Maybe a
Nothing