-- | A queue of passive critical pairs, using a memory-efficient representation.
{-# LANGUAGE TypeFamilies, RecordWildCards, FlexibleContexts, ScopedTypeVariables, StandaloneDeriving #-}
module Twee.PassiveQueue(
  Params(..),
  Queue,
  Passive(..),
  empty, insert, removeMin, mapMaybe, toList, queueSize) where

import qualified Data.Heap as Heap
import qualified Data.Vector.Unboxed as Vector
import Data.Int
import Data.List hiding (insert)
import qualified Data.Maybe
import Data.Ord
import Data.Proxy
import Twee.Utils

-- | A datatype representing all the type parameters of the queue.
class (Eq (Id params), Integral (Id params), Ord (Score params), Vector.Unbox (PackedScore params), Vector.Unbox (PackedId params)) => Params params where
  -- | The score assigned to critical pairs. Smaller scores are better.
  type Score params
  -- | The type of ID numbers used to name rules.
  type Id params

  -- | A 'Score' packed for storage into a 'Vector.Vector'. Must be an instance of 'Vector.Unbox'.
  type PackedScore params
  -- | An 'Id' packed for storage into a 'Vector.Vector'. Must be an instance of 'Vector.Unbox'.
  type PackedId params

  -- | Pack a 'Score'.
  packScore :: proxy params -> Score params -> PackedScore params
  -- | Unpack a 'PackedScore'.
  unpackScore :: proxy params -> PackedScore params -> Score params
  -- | Pack an 'Id'.
  packId :: proxy params -> Id params -> PackedId params
  -- | Unpack a 'PackedId'.
  unpackId :: proxy params -> PackedId params -> Id params

-- | A critical pair queue.
newtype Queue params =
  Queue (Heap.Heap (PassiveSet params))

-- All passive CPs generated from one given rule.
data PassiveSet params =
  PassiveSet {
    PassiveSet params -> Passive params
passiveset_best  :: {-# UNPACK #-} !(Passive params),
    PassiveSet params -> Id params
passiveset_rule  :: !(Id params),
    -- CPs where the rule is the left-hand rule
    PassiveSet params
-> Vector (PackedScore params, PackedId params, Int32)
passiveset_left  :: {-# UNPACK #-} !(Vector.Vector (PackedScore params, PackedId params, Int32)),
    -- CPs where the rule is the right-hand rule
    PassiveSet params
-> Vector (PackedScore params, PackedId params, Int32)
passiveset_right :: {-# UNPACK #-} !(Vector.Vector (PackedScore params, PackedId params, Int32)) }
instance Params params => Eq (PassiveSet params) where
  PassiveSet params
x == :: PassiveSet params -> PassiveSet params -> Bool
== PassiveSet params
y = PassiveSet params -> PassiveSet params -> Ordering
forall a. Ord a => a -> a -> Ordering
compare PassiveSet params
x PassiveSet params
y Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering
EQ
instance Params params => Ord (PassiveSet params) where
  compare :: PassiveSet params -> PassiveSet params -> Ordering
compare = (PassiveSet params -> Passive params)
-> PassiveSet params -> PassiveSet params -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing PassiveSet params -> Passive params
forall params. PassiveSet params -> Passive params
passiveset_best

-- A smart-ish constructor.
{-# INLINEABLE mkPassiveSet #-}
mkPassiveSet ::
  Params params =>
  Proxy params ->
  Id params ->
  Vector.Vector (PackedScore params, PackedId params, Int32) ->
  Vector.Vector (PackedScore params, PackedId params, Int32) ->
  Maybe (PassiveSet params)
mkPassiveSet :: Proxy params
-> Id params
-> Vector (PackedScore params, PackedId params, Int32)
-> Vector (PackedScore params, PackedId params, Int32)
-> Maybe (PassiveSet params)
mkPassiveSet Proxy params
proxy Id params
rule Vector (PackedScore params, PackedId params, Int32)
left Vector (PackedScore params, PackedId params, Int32)
right
  | Vector (PackedScore params, PackedId params, Int32) -> Bool
forall a. Unbox a => Vector a -> Bool
Vector.null Vector (PackedScore params, PackedId params, Int32)
left Bool -> Bool -> Bool
&& Vector (PackedScore params, PackedId params, Int32) -> Bool
forall a. Unbox a => Vector a -> Bool
Vector.null Vector (PackedScore params, PackedId params, Int32)
right = Maybe (PassiveSet params)
forall a. Maybe a
Nothing
  | Bool -> Bool
not (Vector (PackedScore params, PackedId params, Int32) -> Bool
forall a. Unbox a => Vector a -> Bool
Vector.null Vector (PackedScore params, PackedId params, Int32)
left) Bool -> Bool -> Bool
&&
    (Vector (PackedScore params, PackedId params, Int32) -> Bool
forall a. Unbox a => Vector a -> Bool
Vector.null Vector (PackedScore params, PackedId params, Int32)
right Bool -> Bool -> Bool
|| Passive params
l Passive params -> Passive params -> Bool
forall a. Ord a => a -> a -> Bool
<= Passive params
r) =
    PassiveSet params -> Maybe (PassiveSet params)
forall a. a -> Maybe a
Just PassiveSet :: forall params.
Passive params
-> Id params
-> Vector (PackedScore params, PackedId params, Int32)
-> Vector (PackedScore params, PackedId params, Int32)
-> PassiveSet params
PassiveSet {
      passiveset_best :: Passive params
passiveset_best  = Passive params
l,
      passiveset_rule :: Id params
passiveset_rule  = Id params
rule,
      passiveset_left :: Vector (PackedScore params, PackedId params, Int32)
passiveset_left  = Vector (PackedScore params, PackedId params, Int32)
-> Vector (PackedScore params, PackedId params, Int32)
forall a. Unbox a => Vector a -> Vector a
Vector.tail Vector (PackedScore params, PackedId params, Int32)
left,
      passiveset_right :: Vector (PackedScore params, PackedId params, Int32)
passiveset_right = Vector (PackedScore params, PackedId params, Int32)
right }
    -- In this case we must have not (Vector.null right).
  | Bool
otherwise =
    PassiveSet params -> Maybe (PassiveSet params)
forall a. a -> Maybe a
Just PassiveSet :: forall params.
Passive params
-> Id params
-> Vector (PackedScore params, PackedId params, Int32)
-> Vector (PackedScore params, PackedId params, Int32)
-> PassiveSet params
PassiveSet {
      passiveset_best :: Passive params
passiveset_best  = Passive params
r,
      passiveset_rule :: Id params
passiveset_rule  = Id params
rule,
      passiveset_left :: Vector (PackedScore params, PackedId params, Int32)
passiveset_left  = Vector (PackedScore params, PackedId params, Int32)
left,
      passiveset_right :: Vector (PackedScore params, PackedId params, Int32)
passiveset_right = Vector (PackedScore params, PackedId params, Int32)
-> Vector (PackedScore params, PackedId params, Int32)
forall a. Unbox a => Vector a -> Vector a
Vector.tail Vector (PackedScore params, PackedId params, Int32)
right }
  where
    l :: Passive params
l = Proxy params
-> Id params
-> Bool
-> (PackedScore params, PackedId params, Int32)
-> Passive params
forall params.
Params params =>
Proxy params
-> Id params
-> Bool
-> (PackedScore params, PackedId params, Int32)
-> Passive params
unpack Proxy params
proxy Id params
rule Bool
True (Vector (PackedScore params, PackedId params, Int32)
-> (PackedScore params, PackedId params, Int32)
forall a. Unbox a => Vector a -> a
Vector.head Vector (PackedScore params, PackedId params, Int32)
left)
    r :: Passive params
r = Proxy params
-> Id params
-> Bool
-> (PackedScore params, PackedId params, Int32)
-> Passive params
forall params.
Params params =>
Proxy params
-> Id params
-> Bool
-> (PackedScore params, PackedId params, Int32)
-> Passive params
unpack Proxy params
proxy Id params
rule Bool
False (Vector (PackedScore params, PackedId params, Int32)
-> (PackedScore params, PackedId params, Int32)
forall a. Unbox a => Vector a -> a
Vector.head Vector (PackedScore params, PackedId params, Int32)
right)

-- Unpack a triple into a Passive.
{-# INLINEABLE unpack #-}
unpack :: Params params => Proxy params -> Id params -> Bool -> (PackedScore params, PackedId params, Int32) -> Passive params
unpack :: Proxy params
-> Id params
-> Bool
-> (PackedScore params, PackedId params, Int32)
-> Passive params
unpack Proxy params
proxy Id params
rule Bool
isLeft (PackedScore params
score, PackedId params
id, Int32
pos) =
  Passive :: forall params.
Score params -> Id params -> Id params -> Int -> Passive params
Passive {
    passive_score :: Score params
passive_score = Proxy params -> PackedScore params -> Score params
forall params (proxy :: * -> *).
Params params =>
proxy params -> PackedScore params -> Score params
unpackScore Proxy params
proxy PackedScore params
score,
    passive_rule1 :: Id params
passive_rule1 = if Bool
isLeft then Id params
rule else Id params
rule',
    passive_rule2 :: Id params
passive_rule2 = if Bool
isLeft then Id params
rule' else Id params
rule,
    passive_pos :: Int
passive_pos = Int32 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int32
pos }
  where
    rule' :: Id params
rule' = Proxy params -> PackedId params -> Id params
forall params (proxy :: * -> *).
Params params =>
proxy params -> PackedId params -> Id params
unpackId Proxy params
proxy PackedId params
id

-- Make a PassiveSet from a list of Passives.
{-# INLINEABLE makePassiveSet #-}
makePassiveSet :: forall params. Params params => Id params -> [Passive params] -> Maybe (PassiveSet params)
makePassiveSet :: Id params -> [Passive params] -> Maybe (PassiveSet params)
makePassiveSet Id params
_ [] = Maybe (PassiveSet params)
forall a. Maybe a
Nothing
makePassiveSet Id params
rule [Passive params]
ps
  | [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [Passive params -> Id params
forall params. Passive params -> Id params
passive_rule2 Passive params
p Id params -> Id params -> Bool
forall a. Eq a => a -> a -> Bool
== Id params
rule | Passive params
p <- [Passive params]
right] =
    Proxy params
-> Id params
-> Vector (PackedScore params, PackedId params, Int32)
-> Vector (PackedScore params, PackedId params, Int32)
-> Maybe (PassiveSet params)
forall params.
Params params =>
Proxy params
-> Id params
-> Vector (PackedScore params, PackedId params, Int32)
-> Vector (PackedScore params, PackedId params, Int32)
-> Maybe (PassiveSet params)
mkPassiveSet Proxy params
proxy Id params
rule
      ([(PackedScore params, PackedId params, Int32)]
-> Vector (PackedScore params, PackedId params, Int32)
forall a. Unbox a => [a] -> Vector a
Vector.fromList ((Passive params -> (PackedScore params, PackedId params, Int32))
-> [Passive params]
-> [(PackedScore params, PackedId params, Int32)]
forall a b. (a -> b) -> [a] -> [b]
map (Bool
-> Passive params -> (PackedScore params, PackedId params, Int32)
pack Bool
True) ([Passive params] -> [Passive params]
forall a. Ord a => [a] -> [a]
sort [Passive params]
left)))
      ([(PackedScore params, PackedId params, Int32)]
-> Vector (PackedScore params, PackedId params, Int32)
forall a. Unbox a => [a] -> Vector a
Vector.fromList ((Passive params -> (PackedScore params, PackedId params, Int32))
-> [Passive params]
-> [(PackedScore params, PackedId params, Int32)]
forall a b. (a -> b) -> [a] -> [b]
map (Bool
-> Passive params -> (PackedScore params, PackedId params, Int32)
pack Bool
False) ([Passive params] -> [Passive params]
forall a. Ord a => [a] -> [a]
sort [Passive params]
right)))
  | Bool
otherwise = [Char] -> Maybe (PassiveSet params)
forall a. HasCallStack => [Char] -> a
error [Char]
"rule id does not occur in passive"
  where
    proxy :: Proxy params
    proxy :: Proxy params
proxy = Proxy params
forall k (t :: k). Proxy t
Proxy
    
    ([Passive params]
left, [Passive params]
right) = (Passive params -> Bool)
-> [Passive params] -> ([Passive params], [Passive params])
forall a. (a -> Bool) -> [a] -> ([a], [a])
partition (\Passive params
p -> Passive params -> Id params
forall params. Passive params -> Id params
passive_rule1 Passive params
p Id params -> Id params -> Bool
forall a. Eq a => a -> a -> Bool
== Id params
rule) [Passive params]
ps
    pack :: Bool
-> Passive params -> (PackedScore params, PackedId params, Int32)
pack Bool
isLeft Passive{Int
Score params
Id params
passive_pos :: Int
passive_rule2 :: Id params
passive_rule1 :: Id params
passive_score :: Score params
passive_pos :: forall params. Passive params -> Int
passive_rule2 :: forall params. Passive params -> Id params
passive_rule1 :: forall params. Passive params -> Id params
passive_score :: forall params. Passive params -> Score params
..} =
      (Proxy params -> Score params -> PackedScore params
forall params (proxy :: * -> *).
Params params =>
proxy params -> Score params -> PackedScore params
packScore Proxy params
proxy Score params
passive_score,
       Proxy params -> Id params -> PackedId params
forall params (proxy :: * -> *).
Params params =>
proxy params -> Id params -> PackedId params
packId Proxy params
proxy (if Bool
isLeft then Id params
passive_rule2 else Id params
passive_rule1),
       Int -> Int32
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
passive_pos)

-- Convert a PassiveSet back into a list of Passives.
{-# INLINEABLE unpackPassiveSet #-}
unpackPassiveSet :: forall params.Params params => PassiveSet params -> (Int, [Passive params])
unpackPassiveSet :: PassiveSet params -> (Int, [Passive params])
unpackPassiveSet PassiveSet{Vector (PackedScore params, PackedId params, Int32)
Passive params
Id params
passiveset_right :: Vector (PackedScore params, PackedId params, Int32)
passiveset_left :: Vector (PackedScore params, PackedId params, Int32)
passiveset_rule :: Id params
passiveset_best :: Passive params
passiveset_right :: forall params.
PassiveSet params
-> Vector (PackedScore params, PackedId params, Int32)
passiveset_left :: forall params.
PassiveSet params
-> Vector (PackedScore params, PackedId params, Int32)
passiveset_rule :: forall params. PassiveSet params -> Id params
passiveset_best :: forall params. PassiveSet params -> Passive params
..} =
  (Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Vector (PackedScore params, PackedId params, Int32) -> Int
forall a. Unbox a => Vector a -> Int
Vector.length Vector (PackedScore params, PackedId params, Int32)
passiveset_left Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Vector (PackedScore params, PackedId params, Int32) -> Int
forall a. Unbox a => Vector a -> Int
Vector.length Vector (PackedScore params, PackedId params, Int32)
passiveset_right,
   Passive params
passiveset_bestPassive params -> [Passive params] -> [Passive params]
forall a. a -> [a] -> [a]
:
   ((PackedScore params, PackedId params, Int32) -> Passive params)
-> [(PackedScore params, PackedId params, Int32)]
-> [Passive params]
forall a b. (a -> b) -> [a] -> [b]
map (Proxy params
-> Id params
-> Bool
-> (PackedScore params, PackedId params, Int32)
-> Passive params
forall params.
Params params =>
Proxy params
-> Id params
-> Bool
-> (PackedScore params, PackedId params, Int32)
-> Passive params
unpack Proxy params
proxy Id params
passiveset_rule Bool
True) (Vector (PackedScore params, PackedId params, Int32)
-> [(PackedScore params, PackedId params, Int32)]
forall a. Unbox a => Vector a -> [a]
Vector.toList Vector (PackedScore params, PackedId params, Int32)
passiveset_left) [Passive params] -> [Passive params] -> [Passive params]
forall a. [a] -> [a] -> [a]
++
   ((PackedScore params, PackedId params, Int32) -> Passive params)
-> [(PackedScore params, PackedId params, Int32)]
-> [Passive params]
forall a b. (a -> b) -> [a] -> [b]
map (Proxy params
-> Id params
-> Bool
-> (PackedScore params, PackedId params, Int32)
-> Passive params
forall params.
Params params =>
Proxy params
-> Id params
-> Bool
-> (PackedScore params, PackedId params, Int32)
-> Passive params
unpack Proxy params
proxy Id params
passiveset_rule Bool
False) (Vector (PackedScore params, PackedId params, Int32)
-> [(PackedScore params, PackedId params, Int32)]
forall a. Unbox a => Vector a -> [a]
Vector.toList Vector (PackedScore params, PackedId params, Int32)
passiveset_right))
  where
    proxy :: Proxy params
    proxy :: Proxy params
proxy = Proxy params
forall k (t :: k). Proxy t
Proxy

-- Find and remove the best element from a PassiveSet.
{-# INLINEABLE unconsPassiveSet #-}
unconsPassiveSet :: forall params. Params params => PassiveSet params -> (Passive params, Maybe (PassiveSet params))
unconsPassiveSet :: PassiveSet params -> (Passive params, Maybe (PassiveSet params))
unconsPassiveSet PassiveSet{Vector (PackedScore params, PackedId params, Int32)
Passive params
Id params
passiveset_right :: Vector (PackedScore params, PackedId params, Int32)
passiveset_left :: Vector (PackedScore params, PackedId params, Int32)
passiveset_rule :: Id params
passiveset_best :: Passive params
passiveset_right :: forall params.
PassiveSet params
-> Vector (PackedScore params, PackedId params, Int32)
passiveset_left :: forall params.
PassiveSet params
-> Vector (PackedScore params, PackedId params, Int32)
passiveset_rule :: forall params. PassiveSet params -> Id params
passiveset_best :: forall params. PassiveSet params -> Passive params
..} =
  (Passive params
passiveset_best, Proxy params
-> Id params
-> Vector (PackedScore params, PackedId params, Int32)
-> Vector (PackedScore params, PackedId params, Int32)
-> Maybe (PassiveSet params)
forall params.
Params params =>
Proxy params
-> Id params
-> Vector (PackedScore params, PackedId params, Int32)
-> Vector (PackedScore params, PackedId params, Int32)
-> Maybe (PassiveSet params)
mkPassiveSet (Proxy params
forall k (t :: k). Proxy t
Proxy :: Proxy params) Id params
passiveset_rule Vector (PackedScore params, PackedId params, Int32)
passiveset_left Vector (PackedScore params, PackedId params, Int32)
passiveset_right)

-- | A queued critical pair.
data Passive params =
  Passive {
    -- | The score of this critical pair.
    Passive params -> Score params
passive_score :: !(Score params),
    -- | The rule which does the outermost rewrite in this critical pair.
    Passive params -> Id params
passive_rule1 :: !(Id params),
    -- | The rule which does the innermost rewrite in this critical pair.
    Passive params -> Id params
passive_rule2 :: !(Id params),
    -- | The position of the overlap. See 'Twee.CP.overlap_pos'.
    Passive params -> Int
passive_pos   :: {-# UNPACK #-} !Int }

instance Params params => Eq (Passive params) where
  Passive params
x == :: Passive params -> Passive params -> Bool
== Passive params
y = Passive params -> Passive params -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Passive params
x Passive params
y Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering
EQ

instance Params params => Ord (Passive params) where
  compare :: Passive params -> Passive params -> Ordering
compare = (Passive params -> (Score params, Int, Int, Int))
-> Passive params -> Passive params -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing Passive params -> (Score params, Int, Int, Int)
forall params.
Integral (Id params) =>
Passive params -> (Score params, Int, Int, Int)
f
    where
      f :: Passive params -> (Score params, Int, Int, Int)
f Passive{Int
Score params
Id params
passive_pos :: Int
passive_rule2 :: Id params
passive_rule1 :: Id params
passive_score :: Score params
passive_pos :: forall params. Passive params -> Int
passive_rule2 :: forall params. Passive params -> Id params
passive_rule1 :: forall params. Passive params -> Id params
passive_score :: forall params. Passive params -> Score params
..} =
        (Score params
passive_score,
         Int -> Int -> Int
intMax (Id params -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Id params
passive_rule1) (Id params -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Id params
passive_rule2),
         Int -> Int -> Int
intMin (Id params -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Id params
passive_rule1) (Id params -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Id params
passive_rule2),
         Int
passive_pos)

-- | The empty queue.
empty :: Queue params
empty :: Queue params
empty = Heap (PassiveSet params) -> Queue params
forall params. Heap (PassiveSet params) -> Queue params
Queue Heap (PassiveSet params)
forall a. Heap a
Heap.empty

-- | Add a set of 'Passive's to the queue.
{-# INLINEABLE insert #-}
insert :: Params params => Id params -> [Passive params] -> Queue params -> Queue params
insert :: Id params -> [Passive params] -> Queue params -> Queue params
insert Id params
rule [Passive params]
passives (Queue Heap (PassiveSet params)
q) =
  Heap (PassiveSet params) -> Queue params
forall params. Heap (PassiveSet params) -> Queue params
Queue (Heap (PassiveSet params) -> Queue params)
-> Heap (PassiveSet params) -> Queue params
forall a b. (a -> b) -> a -> b
$
  case Id params -> [Passive params] -> Maybe (PassiveSet params)
forall params.
Params params =>
Id params -> [Passive params] -> Maybe (PassiveSet params)
makePassiveSet Id params
rule [Passive params]
passives of
    Maybe (PassiveSet params)
Nothing -> Heap (PassiveSet params)
q
    Just PassiveSet params
p -> PassiveSet params
-> Heap (PassiveSet params) -> Heap (PassiveSet params)
forall a. Ord a => a -> Heap a -> Heap a
Heap.insert PassiveSet params
p Heap (PassiveSet params)
q

-- | Remove the minimum 'Passive' from the queue.
{-# INLINEABLE removeMin #-}
removeMin :: Params params => Queue params -> Maybe (Passive params, Queue params)
removeMin :: Queue params -> Maybe (Passive params, Queue params)
removeMin (Queue Heap (PassiveSet params)
q) = do
  (PassiveSet params
passiveset, Heap (PassiveSet params)
q) <- Heap (PassiveSet params)
-> Maybe (PassiveSet params, Heap (PassiveSet params))
forall a. Ord a => Heap a -> Maybe (a, Heap a)
Heap.removeMin Heap (PassiveSet params)
q
  case PassiveSet params -> (Passive params, Maybe (PassiveSet params))
forall params.
Params params =>
PassiveSet params -> (Passive params, Maybe (PassiveSet params))
unconsPassiveSet PassiveSet params
passiveset of
    (Passive params
passive, Just PassiveSet params
passiveset') ->
      (Passive params, Queue params)
-> Maybe (Passive params, Queue params)
forall a. a -> Maybe a
Just (Passive params
passive, Heap (PassiveSet params) -> Queue params
forall params. Heap (PassiveSet params) -> Queue params
Queue (PassiveSet params
-> Heap (PassiveSet params) -> Heap (PassiveSet params)
forall a. Ord a => a -> Heap a -> Heap a
Heap.insert PassiveSet params
passiveset' Heap (PassiveSet params)
q))
    (Passive params
passive, Maybe (PassiveSet params)
Nothing) ->
      (Passive params, Queue params)
-> Maybe (Passive params, Queue params)
forall a. a -> Maybe a
Just (Passive params
passive, Heap (PassiveSet params) -> Queue params
forall params. Heap (PassiveSet params) -> Queue params
Queue Heap (PassiveSet params)
q)

-- | Map a function over all 'Passive's.
{-# INLINEABLE mapMaybe #-}
mapMaybe :: Params params => (Passive params -> Maybe (Passive params)) -> Queue params -> Queue params
mapMaybe :: (Passive params -> Maybe (Passive params))
-> Queue params -> Queue params
mapMaybe Passive params -> Maybe (Passive params)
f (Queue Heap (PassiveSet params)
q) = Heap (PassiveSet params) -> Queue params
forall params. Heap (PassiveSet params) -> Queue params
Queue ((PassiveSet params -> Maybe (PassiveSet params))
-> Heap (PassiveSet params) -> Heap (PassiveSet params)
forall a b. Ord b => (a -> Maybe b) -> Heap a -> Heap b
Heap.mapMaybe PassiveSet params -> Maybe (PassiveSet params)
g Heap (PassiveSet params)
q)
  where
    g :: PassiveSet params -> Maybe (PassiveSet params)
g passiveSet :: PassiveSet params
passiveSet@PassiveSet{Vector (PackedScore params, PackedId params, Int32)
Passive params
Id params
passiveset_right :: Vector (PackedScore params, PackedId params, Int32)
passiveset_left :: Vector (PackedScore params, PackedId params, Int32)
passiveset_rule :: Id params
passiveset_best :: Passive params
passiveset_right :: forall params.
PassiveSet params
-> Vector (PackedScore params, PackedId params, Int32)
passiveset_left :: forall params.
PassiveSet params
-> Vector (PackedScore params, PackedId params, Int32)
passiveset_rule :: forall params. PassiveSet params -> Id params
passiveset_best :: forall params. PassiveSet params -> Passive params
..} =
      Id params -> [Passive params] -> Maybe (PassiveSet params)
forall params.
Params params =>
Id params -> [Passive params] -> Maybe (PassiveSet params)
makePassiveSet Id params
passiveset_rule ([Passive params] -> Maybe (PassiveSet params))
-> [Passive params] -> Maybe (PassiveSet params)
forall a b. (a -> b) -> a -> b
$ (Passive params -> Maybe (Passive params))
-> [Passive params] -> [Passive params]
forall a b. (a -> Maybe b) -> [a] -> [b]
Data.Maybe.mapMaybe Passive params -> Maybe (Passive params)
f ([Passive params] -> [Passive params])
-> [Passive params] -> [Passive params]
forall a b. (a -> b) -> a -> b
$
        (Int, [Passive params]) -> [Passive params]
forall a b. (a, b) -> b
snd (PassiveSet params -> (Int, [Passive params])
forall params.
Params params =>
PassiveSet params -> (Int, [Passive params])
unpackPassiveSet PassiveSet params
passiveSet)

-- | Convert a queue into a list of 'Passive's.
-- The 'Passive's are produced in batches, with each batch labelled
-- with its size.
{-# INLINEABLE toList #-}
toList :: Params params => Queue params -> [(Int, [Passive params])]
toList :: Queue params -> [(Int, [Passive params])]
toList (Queue Heap (PassiveSet params)
h) = (PassiveSet params -> (Int, [Passive params]))
-> [PassiveSet params] -> [(Int, [Passive params])]
forall a b. (a -> b) -> [a] -> [b]
map PassiveSet params -> (Int, [Passive params])
forall params.
Params params =>
PassiveSet params -> (Int, [Passive params])
unpackPassiveSet (Heap (PassiveSet params) -> [PassiveSet params]
forall a. Heap a -> [a]
Heap.toList Heap (PassiveSet params)
h)

queueSize :: Params params => Queue params -> Int
queueSize :: Queue params -> Int
queueSize = [Int] -> Int
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ([Int] -> Int) -> (Queue params -> [Int]) -> Queue params -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, [Passive params]) -> Int)
-> [(Int, [Passive params])] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (Int, [Passive params]) -> Int
forall a b. (a, b) -> a
fst ([(Int, [Passive params])] -> [Int])
-> (Queue params -> [(Int, [Passive params])])
-> Queue params
-> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Queue params -> [(Int, [Passive params])]
forall params.
Params params =>
Queue params -> [(Int, [Passive params])]
toList