module Data.SegmentTree.Interval ( R(..)
, Interval(..)
, Boundary(..)
, subinterval, intersects, inside
, merge ) where
import Text.Printf
data R v = MinusInf | R !v | PlusInf deriving (Eq, Ord)
instance Show v => Show (R v) where
show MinusInf = "-Inf"
show PlusInf = "+Inf"
show (R v) = show v
instance Bounded (R v) where
minBound = MinusInf
maxBound = PlusInf
data Boundary = Open | Closed deriving (Eq, Ord)
data Interval v = Interval { ltype :: ! Boundary
, low :: !(R v)
, high :: !(R v)
, htype :: ! Boundary
} deriving (Eq, Ord)
instance Show v => Show (Interval v) where
show (Interval o l h c) = printf "%s%s,%s%s" (opening o) (show l) (show h) (closing c)
where
opening Open = "("
opening Closed = "["
closing Open = ")"
closing Closed = "]"
subinterval smaller bigger = low smaller >= low bigger && high smaller <= high bigger
intersects one two = low one `inside` two || high one `inside` two ||
low two `inside` one || high two `inside` one
inside p (Interval ltype low high htype) = (cmp ltype) low p && (cmp htype) p high
where
cmp Open = (<)
cmp Closed = (<=)
merge i1 i2 | i1 <= i2 = Interval (ltype i1) (low i1) (high i2) (htype i2)
| otherwise = Interval (ltype i2) (low i2) (high i1) (htype i1)