{- |
Alternative to "Math.SetCover.Queue.Set"
that represents sets by bit masks and uses the faster Int priority queue.
-}
module Math.SetCover.Queue.Bit (Methods, methods) where

import qualified Math.SetCover.Queue as Queue
import Math.SetCover.Queue (SetId)

import qualified Math.SetCover.EnumMap as EnumMapX
import qualified Math.SetCover.BitPosition as BitPos
import qualified Math.SetCover.BitSet as BitSet

import qualified Data.IntPSQ as PSQ
import qualified Data.EnumSet as EnumSet; import Data.EnumSet (EnumSet)
import qualified Data.IntMap as IntMap
import qualified Data.List as List
import Data.Tuple.HT (swap, mapFst, thd3)


type
   Methods bits =
      Queue.Methods (PSQ.IntPSQ Int (EnumSet SetId)) (BitSet.Set bits)

methods :: BitPos.C bits => Methods bits
methods =
   Queue.Methods {
      Queue.fromEnumMap =
         PSQ.fromList . map (\(elm, ns) -> (elm, EnumSet.size ns, ns)) .
         IntMap.toList . EnumMapX.transposeBitSet,
      Queue.partition =
         \q -> mapFst EnumSet.unions . partitionPSQ q . BitPos.unpack,
      Queue.difference = \q ->
         foldl (flip deleteSetFromPSQ) q .
         IntMap.toList . EnumMapX.transposeBitSet,
      Queue.findMin = fmap thd3 . PSQ.findMin,
      Queue.null = PSQ.null
   }


{- |
The list of keys must be a subset of the queue keys.
-}
partitionPSQ :: (Ord p) => PSQ.IntPSQ p v -> [Int] -> ([v], PSQ.IntPSQ p v)
partitionPSQ =
   (swap .) .
   List.mapAccumL
      (\q0 k ->
         maybe
            (error "partitionPSQ: key not contained in queue's key set")
            (\(_p,v,q1) -> (q1, v)) $
         PSQ.deleteView k q0)

deleteSetFromPSQ ::
   (Int, EnumSet e) -> PSQ.IntPSQ Int (EnumSet e) ->
   PSQ.IntPSQ Int (EnumSet e)
deleteSetFromPSQ (elm, ns) =
   updatePSQ (flip differenceSizedSet ns) elm

differenceSizedSet :: (Int, EnumSet e) -> EnumSet e -> (Int, EnumSet e)
differenceSizedSet (size, a) b =
   let section = EnumSet.intersection a b
   in  (size - EnumSet.size section, EnumSet.difference a section)

updatePSQ ::
   (Ord p) => ((p, v) -> (p, v)) -> Int -> PSQ.IntPSQ p v -> PSQ.IntPSQ p v
updatePSQ f k = snd . PSQ.alter ((,) () . fmap f) k