module Math.Common.ListSet where

import Data.List (group,sort)
-- versions of Data.List functions which assume that the lists are ascending sets (no repeated elements)

toListSet xs = map head $ group $ sort xs

isListSet (x1:x2:xs) = x1 < x2 && isListSet (x2:xs)
isListSet _ = True


union (x:xs) (y:ys) =
    case compare x y of
    LT -> x : union xs (y:ys)
    EQ -> x : union xs ys
    GT -> y : union (x:xs) ys
union [] ys = ys
union xs [] = xs

intersect (x:xs) (y:ys) =
    case compare x y of
    LT -> intersect xs (y:ys)
    EQ -> x : intersect xs ys
    GT -> intersect (x:xs) ys
intersect _ _ = []

(x:xs) \\ (y:ys) =
    case compare x y of
    LT -> x : (xs \\ (y:ys))
    EQ -> xs \\ ys
    GT -> (x:xs) \\ ys
[] \\ _ = []
xs \\ [] = xs

symDiff (x:xs) (y:ys) =
    case compare x y of
    LT -> x : symDiff xs (y:ys)
    EQ -> symDiff xs ys
    GT -> y : symDiff (x:xs) ys
symDiff [] ys = ys
symDiff xs [] = xs

disjoint xs ys = null (intersect xs ys)

isSubset (x:xs) (y:ys) =
    case compare x y of
    LT -> False
    EQ -> isSubset xs ys
    GT -> isSubset (x:xs) ys
isSubset [] _ = True
isSubset _ [] = False

-- Note that an ListSet.elem turned out to be slower than Data.List.elem
-- (Perhaps because it's slower when x `notElem` xs)