{-# OPTIONS -Wall #-}
module Main where

import Data.List (sort)
import Data.List.NonEmpty (NonEmpty(..))


data Iv a = Iv a a
  deriving (Show, Eq, Ord)
-- Actually it doesn't matter how Iv a b and Iv a c are sorted relative to each other

-- Returns all gaps between outermost endpoints of a list of intervals
gaps :: Ord a => [Iv a] -> [Iv a]
gaps = gaps' . sort

-- Returns all gaps between outermost endpoints of a list of intervals, assuming sorted
gaps' :: Ord a => [Iv a] -> [Iv a]
gaps' [] = []
gaps' (iv:ivs) =
  case getBlock (iv :| ivs) of
    (_, []) -> []
    (Iv _ to, rest@(Iv next _ : _)) ->
      Iv to next : gaps' rest

-- Returns first contiguous block and remaining intervals, assuming sorted
getBlock :: Ord a => NonEmpty (Iv a) -> (Iv a, [Iv a])
getBlock (iv :| []) = (iv, [])
getBlock (Iv a b :| Iv c d : rest)
  | c <= b = getBlock (Iv a d :| rest)
  | otherwise = (Iv a b, Iv c d : rest)

main :: IO ()
main = do
  print $ gaps @Int [Iv 2 3, Iv 4 5, Iv 0 3]