{-# OPTIONS_GHC -Wall #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  ToySolver.Combinatorial.HittingSet.Util
-- Copyright   :  (c) Masahiro Sakai 2012-2014
-- License     :  BSD-style
--
-- Maintainer  :  masahiro.sakai@gmail.com
-- Stability   :  provisional
-- Portability :  portable
--
-----------------------------------------------------------------------------
module ToySolver.Combinatorial.HittingSet.Util
  ( maintainNoSupersets
  ) where

import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet

maintainNoSupersets :: [IntSet] -> [IntSet]
maintainNoSupersets :: [IntSet] -> [IntSet]
maintainNoSupersets [IntSet]
xss = [IntSet] -> [IntSet] -> [IntSet]
go [] [IntSet]
xss
  where
    go :: [IntSet] -> [IntSet] -> [IntSet]
go [IntSet]
yss [] = [IntSet]
yss
    go [IntSet]
yss (IntSet
xs:[IntSet]
xss) = [IntSet] -> [IntSet] -> [IntSet]
go (IntSet
xs IntSet -> [IntSet] -> [IntSet]
forall a. a -> [a] -> [a]
: (IntSet -> Bool) -> [IntSet] -> [IntSet]
forall a. (a -> Bool) -> [a] -> [a]
filter IntSet -> Bool
p [IntSet]
yss) ((IntSet -> Bool) -> [IntSet] -> [IntSet]
forall a. (a -> Bool) -> [a] -> [a]
filter IntSet -> Bool
p [IntSet]
xss)
      where
        p :: IntSet -> Bool
p IntSet
zs = Bool -> Bool
not (IntSet
xs IntSet -> IntSet -> Bool
`IntSet.isSubsetOf` IntSet
zs)