Spans.hs

-- This module contains every function that purely performs operations on spans.
module Data.Range.Typed.Spans where

import Data.Range.Typed.Data
import Data.Range.Typed.Util

-- Assume that both inputs are sorted spans
insertionSortSpans :: (Ord a) => [(Bound a, Bound a)] -> [(Bound a, Bound a)] -> [(Bound a, Bound a)]
insertionSortSpans = insertionSort (\a b -> compareLower (fst a) (fst b))

spanCmp :: (Ord a) => (Bound a, Bound a) -> (Bound a, Bound a) -> Ordering
spanCmp x@(_, xHighValue) y@(yLowValue, _) =
  if boundsOverlapType x y /= Separate
    then EQ
    else if boundValue xHighValue <= boundValue yLowValue then LT else GT

intersectSpans :: (Ord a) => [(Bound a, Bound a)] -> [(Bound a, Bound a)] -> [(Bound a, Bound a)]
intersectSpans (x@(xlow, xup) : xs) (y@(ylow, yup) : ys) =
  case spanCmp x y of
    EQ -> if not (isEmptySpan intersectedSpan) then intersectedSpan : equalNext else equalNext
    LT -> intersectSpans xs (y : ys)
    GT -> intersectSpans (x : xs) ys
  where
    intersectedSpan = (maxBoundsIntersection xlow ylow, minBoundsIntersection xup yup)

    lessThanNext = intersectSpans xs (y : ys)
    greaterThanNext = intersectSpans (x : xs) ys
    equalNext = if boundValue xup < boundValue yup then lessThanNext else greaterThanNext
intersectSpans _ _ = []

-- Assume that you are given a sorted list of spans
joinSpans :: (Eq a, Enum a) => [(Bound a, Bound a)] -> [(Bound a, Bound a)]
joinSpans (f@(a, b) : s@(x, y) : xs) =
  if (succ . highestValueInUpperBound $ b) == lowestValueInLowerBound x
    then joinSpans $ (a, y) : xs
    else f : joinSpans (s : xs)
joinSpans xs = xs

-- Assume that you are given a sorted list of spans
unionSpans :: (Ord a) => [(Bound a, Bound a)] -> [(Bound a, Bound a)]
unionSpans (f@(a, b) : s@(_, y) : xs) =
  if boundsOverlapType f s /= Separate
    then unionSpans ((a, maxBounds b y) : xs)
    else f : unionSpans (s : xs)
unionSpans xs = xs

-- Assume that you are given a sorted and joined list of spans
invertSpans :: [(Bound a, Bound a)] -> [(Bound a, Bound a)]
invertSpans ((_, x) : s@(y, _) : xs) = (invertBound x, invertBound y) : invertSpans (s : xs)
invertSpans _ = []