-- |
-- Copyright   : Anders Claesson 2014
-- Maintainer  : Anders Claesson <anders.claesson@gmail.com>
--

module Sym.Internal.Util
    (
      minima
    , maxima
    , kSubsets
    , powerset
    , nubSort
    ) where

import Data.List
import Data.Ord
import Data.Set (Set)
import qualified Data.Set as S

-- | The list of minimal sets with respect to inclusion.
minima :: Ord a => [Set a] -> [Set a]
minima :: forall a. Ord a => [Set a] -> [Set a]
minima = [Set a] -> [Set a]
forall a. Ord a => [Set a] -> [Set a]
minima' ([Set a] -> [Set a]) -> ([Set a] -> [Set a]) -> [Set a] -> [Set a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Set a -> Set a -> Ordering) -> [Set a] -> [Set a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy ((Set a -> Int) -> Set a -> Set a -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing Set a -> Int
forall a. Set a -> Int
S.size)
  where
    minima' :: [Set a] -> [Set a]
minima' [] = []
    minima' (Set a
x:[Set a]
xs) = Set a
x Set a -> [Set a] -> [Set a]
forall a. a -> [a] -> [a]
: [Set a] -> [Set a]
minima' [ Set a
y | Set a
y<-[Set a]
xs, Bool -> Bool
not (Set a
x Set a -> Set a -> Bool
forall a. Ord a => Set a -> Set a -> Bool
`S.isSubsetOf` Set a
y) ]

-- | The list of maximal sets with respect to inclusion.
maxima :: Ord a => [Set a] -> [Set a]
maxima :: forall a. Ord a => [Set a] -> [Set a]
maxima = [Set a] -> [Set a]
forall a. Ord a => [Set a] -> [Set a]
maxima' ([Set a] -> [Set a]) -> ([Set a] -> [Set a]) -> [Set a] -> [Set a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Set a -> Set a -> Ordering) -> [Set a] -> [Set a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy ((Set a -> Int) -> Set a -> Set a -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing ((Set a -> Int) -> Set a -> Set a -> Ordering)
-> (Set a -> Int) -> Set a -> Set a -> Ordering
forall a b. (a -> b) -> a -> b
$ \Set a
x -> -Set a -> Int
forall a. Set a -> Int
S.size Set a
x)
  where
    maxima' :: [Set a] -> [Set a]
maxima' [] = []
    maxima' (Set a
x:[Set a]
xs) = Set a
x Set a -> [Set a] -> [Set a]
forall a. a -> [a] -> [a]
: [Set a] -> [Set a]
maxima' [ Set a
y | Set a
y<-[Set a]
xs, Bool -> Bool
not (Set a
y Set a -> Set a -> Bool
forall a. Ord a => Set a -> Set a -> Bool
`S.isSubsetOf` Set a
x) ]

-- | A list of all k element subsets of the given set.
kSubsets :: Ord a => Int -> Set a -> [Set a]
kSubsets :: forall a. Ord a => Int -> Set a -> [Set a]
kSubsets Int
0 Set a
_    = [ Set a
forall a. Set a
S.empty ]
kSubsets Int
k Set a
s 
    | Set a -> Bool
forall a. Set a -> Bool
S.null Set a
s  = []
    | Bool
otherwise = Int -> Set a -> [Set a]
forall a. Ord a => Int -> Set a -> [Set a]
kSubsets Int
k Set a
t [Set a] -> [Set a] -> [Set a]
forall a. [a] -> [a] -> [a]
++ (Set a -> Set a) -> [Set a] -> [Set a]
forall a b. (a -> b) -> [a] -> [b]
map (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
S.insert a
x) (Int -> Set a -> [Set a]
forall a. Ord a => Int -> Set a -> [Set a]
kSubsets (Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Set a
t)
  where
    (a
x,Set a
t) = Set a -> (a, Set a)
forall a. Set a -> (a, Set a)
S.deleteFindMin Set a
s

-- | A list of all subsets of the given set.
powerset :: Ord a => Set a -> [Set a]
powerset :: forall a. Ord a => Set a -> [Set a]
powerset Set a
s 
    | Set a -> Bool
forall a. Set a -> Bool
S.null Set a
s  = [Set a
s]
    | Bool
otherwise = [Set a]
ts [Set a] -> [Set a] -> [Set a]
forall a. [a] -> [a] -> [a]
++ (Set a -> Set a) -> [Set a] -> [Set a]
forall a b. (a -> b) -> [a] -> [b]
map (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
S.insert a
x) [Set a]
ts
  where
    (a
x,Set a
t) = Set a -> (a, Set a)
forall a. Set a -> (a, Set a)
S.deleteFindMin Set a
s; ts :: [Set a]
ts = Set a -> [Set a]
forall a. Ord a => Set a -> [Set a]
powerset Set a
t

-- | Sort and remove duplicates.
nubSort :: Ord a => [a] -> [a]
nubSort :: forall a. Ord a => [a] -> [a]
nubSort = ([a] -> a) -> [[a]] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map [a] -> a
forall a. HasCallStack => [a] -> a
head ([[a]] -> [a]) -> ([a] -> [[a]]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [[a]]
forall a. Eq a => [a] -> [[a]]
group ([a] -> [[a]]) -> ([a] -> [a]) -> [a] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. Ord a => [a] -> [a]
sort