----------------------------------------------------------------------------- -- | -- Module : Data.Interval -- Copyright : (c) Dmitry Astapov 2010 -- License : BSD-style -- Maintainer : dastapov@gmail.com -- Stability : experimental -- Portability : portable -- -- Simple open and closed intervals ----------------------------------------------------------------------------- module Data.SegmentTree.Interval ( R(..) , Interval(..) , Boundary(..) , subinterval, intersects, inside , merge ) where import Text.Printf -- | Extension of the type `v' that includes plus and minus infinity 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 -- | An interval. The lower bound should be less than or equal to the higher bound. 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 = "]" -- | Checks whether smaller interval is a proper subinterval of a larger interval subinterval smaller bigger = low smaller >= low bigger && high smaller <= high bigger -- | Checks whether two intervals intersect each other intersects one two = low one `inside` two || high one `inside` two || low two `inside` one || high two `inside` one -- | Checks whether point is inside the interval inside p (Interval ltype low high htype) = (cmp ltype) low p && (cmp htype) p high where cmp Open = (<) cmp Closed = (<=) -- | Merge two intervals that share a common boundary merge i1 i2 | i1 <= i2 = Interval (ltype i1) (low i1) (high i2) (htype i2) | otherwise = Interval (ltype i2) (low i2) (high i1) (htype i1)