{-|
    Module      :  AERN2.PQueue
    Description :  IntPSQ hiding keys and values
    Copyright   :  2016 (c) Michal Konecny
    License     :  BSD3

    Maintainer  :  mikkonecny@gmail.com
    Stability   :  experimental
    Portability :  portable

    IntPSQ with simplified API, hiding the keys
-}

module AERN2.PQueue
(
  -- * Type
  PQueue
  -- * Query
  , null
  , size
  -- * Construction
  , singleton
  , empty
  -- * Insertion
  , insert
  -- * Deletion
  , minView
)
where

import Prelude hiding (null)
-- import qualified Prelude as P

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