IntervalMap 0.6.1.2 → 0.6.2.0
raw patch · 8 files changed
+45/−36 lines, 8 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- Data/IntervalMap/Generic/Base.hs +1/−3
- Data/IntervalMap/Generic/Interval.hs +1/−2
- Data/IntervalMap/Interval.hs +19/−16
- Data/IntervalSet.hs +0/−2
- IntervalMap.cabal +2/−2
- changelog +2/−0
- test/IntervalMapTests.hs +16/−11
- test/IntervalTests.hs +4/−0
Data/IntervalMap/Generic/Base.hs view
@@ -41,9 +41,7 @@ -- The red-black tree deletion is based on code from llrbtree by Kazu Yamamoto. -- Of course, any errors are mine. ---{-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE UndecidableInstances #-}-{-# LANGUAGE FlexibleContexts #-} module Data.IntervalMap.Generic.Base ( -- * re-export Interval(..)@@ -431,7 +429,7 @@ EQ -> Just (key,v) GT -> go1 key v r --- | /O(log n)/. Find the smallest key larger than the given one+-- | /O(log n)/. Find the smallest key equal to or larger than the given one -- and return it along with its value. lookupGE :: (Ord k) => k -> IntervalMap k v -> Maybe (k,v) lookupGE k m = go m
Data/IntervalMap/Generic/Interval.hs view
@@ -15,13 +15,12 @@ -- Empty intervals, i.e. intervals where 'lowerBound >= upperBound' should be avoided -- if possible. If you must use empty intervals, you need to provide implementations -- for all operations, as the default implementations do not necessarily work correctly.--- for example, the default implementation of 'inside' returns 'True' if the point+-- For example, the default implementation of 'inside' returns 'True' for a point that -- is equal to the lowerBound of a left-closed interval even if it is larger than -- the upper bound. {-# LANGUAGE FunctionalDependencies #-} {-# LANGUAGE FlexibleInstances #-}-{-# LANGUAGE UndecidableInstances #-} module Data.IntervalMap.Generic.Interval ( -- * Interval type Interval(..),
Data/IntervalMap/Interval.hs view
@@ -173,25 +173,28 @@ -- | Do the two intervals overlap? overlaps :: (Ord a) => Interval a -> Interval a -> Bool -overlaps (ClosedInterval lo1 hi1) (ClosedInterval lo2 hi2) = lo1 <= hi2 && hi1 >= lo2-overlaps (ClosedInterval lo1 hi1) (OpenInterval lo2 hi2) = lo1 < hi2 && hi1 > lo2-overlaps (ClosedInterval lo1 hi1) (IntervalCO lo2 hi2) = lo1 < hi2 && hi1 >= lo2-overlaps (ClosedInterval lo1 hi1) (IntervalOC lo2 hi2) = lo1 <= hi2 && hi1 > lo2+overlaps a@(ClosedInterval lo1 hi1) b@(ClosedInterval lo2 hi2) = lo1 <= hi2 && hi1 >= lo2 && bothNonEmpty a b+overlaps a@(ClosedInterval lo1 hi1) b@(OpenInterval lo2 hi2) = lo1 < hi2 && hi1 > lo2 && bothNonEmpty a b+overlaps a@(ClosedInterval lo1 hi1) b@(IntervalCO lo2 hi2) = lo1 < hi2 && hi1 >= lo2 && bothNonEmpty a b+overlaps a@(ClosedInterval lo1 hi1) b@(IntervalOC lo2 hi2) = lo1 <= hi2 && hi1 > lo2 && bothNonEmpty a b -overlaps (OpenInterval lo1 hi1) (ClosedInterval lo2 hi2) = lo1 < hi2 && hi1 > lo2-overlaps (OpenInterval lo1 hi1) (OpenInterval lo2 hi2) = lo1 < hi2 && hi1 > lo2-overlaps (OpenInterval lo1 hi1) (IntervalCO lo2 hi2) = lo1 < hi2 && hi1 > lo2-overlaps (OpenInterval lo1 hi1) (IntervalOC lo2 hi2) = lo1 < hi2 && hi1 > lo2+overlaps a@(OpenInterval lo1 hi1) b@(ClosedInterval lo2 hi2) = lo1 < hi2 && hi1 > lo2 && bothNonEmpty a b+overlaps a@(OpenInterval lo1 hi1) b@(OpenInterval lo2 hi2) = lo1 < hi2 && hi1 > lo2 && bothNonEmpty a b+overlaps a@(OpenInterval lo1 hi1) b@(IntervalCO lo2 hi2) = lo1 < hi2 && hi1 > lo2 && bothNonEmpty a b+overlaps a@(OpenInterval lo1 hi1) b@(IntervalOC lo2 hi2) = lo1 < hi2 && hi1 > lo2 && bothNonEmpty a b -overlaps (IntervalCO lo1 hi1) (ClosedInterval lo2 hi2) = lo1 <= hi2 && hi1 > lo2-overlaps (IntervalCO lo1 hi1) (OpenInterval lo2 hi2) = lo1 < hi2 && hi1 > lo2-overlaps (IntervalCO lo1 hi1) (IntervalCO lo2 hi2) = lo1 < hi2 && hi1 > lo2-overlaps (IntervalCO lo1 hi1) (IntervalOC lo2 hi2) = lo1 <= hi2 && hi1 > lo2+overlaps a@(IntervalCO lo1 hi1) b@(ClosedInterval lo2 hi2) = lo1 <= hi2 && hi1 > lo2 && bothNonEmpty a b+overlaps a@(IntervalCO lo1 hi1) b@(OpenInterval lo2 hi2) = lo1 < hi2 && hi1 > lo2 && bothNonEmpty a b+overlaps a@(IntervalCO lo1 hi1) b@(IntervalCO lo2 hi2) = lo1 < hi2 && hi1 > lo2 && bothNonEmpty a b+overlaps a@(IntervalCO lo1 hi1) b@(IntervalOC lo2 hi2) = lo1 <= hi2 && hi1 > lo2 && bothNonEmpty a b -overlaps (IntervalOC lo1 hi1) (ClosedInterval lo2 hi2) = lo1 < hi2 && hi1 >= lo2-overlaps (IntervalOC lo1 hi1) (OpenInterval lo2 hi2) = lo1 < hi2 && hi1 > lo2-overlaps (IntervalOC lo1 hi1) (IntervalCO lo2 hi2) = lo1 < hi2 && hi1 >= lo2-overlaps (IntervalOC lo1 hi1) (IntervalOC lo2 hi2) = lo1 < hi2 && hi1 > lo2+overlaps a@(IntervalOC lo1 hi1) b@(ClosedInterval lo2 hi2) = lo1 < hi2 && hi1 >= lo2 && bothNonEmpty a b+overlaps a@(IntervalOC lo1 hi1) b@(OpenInterval lo2 hi2) = lo1 < hi2 && hi1 > lo2 && bothNonEmpty a b+overlaps a@(IntervalOC lo1 hi1) b@(IntervalCO lo2 hi2) = lo1 < hi2 && hi1 >= lo2 && bothNonEmpty a b+overlaps a@(IntervalOC lo1 hi1) b@(IntervalOC lo2 hi2) = lo1 < hi2 && hi1 > lo2 && bothNonEmpty a b++bothNonEmpty :: (Ord a) => Interval a -> Interval a -> Bool+bothNonEmpty a b = not (isEmpty a || isEmpty b) -- | Does the first interval completely contain the second?
Data/IntervalSet.hs view
@@ -37,9 +37,7 @@ -- The red-black tree deletion is based on code from llrbtree by Kazu Yamamoto. -- Of course, any errors are mine. ---{-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE UndecidableInstances #-}-{-# LANGUAGE FlexibleContexts #-} module Data.IntervalSet ( -- * re-export Interval(..)
IntervalMap.cabal view
@@ -1,5 +1,5 @@ Name: IntervalMap-Version: 0.6.1.2+Version: 0.6.2.0 Stability: experimental Synopsis: Containers for intervals, with efficient search. Homepage: http://www.chr-breitkopf.de/comp/IntervalMap@@ -12,7 +12,7 @@ Category: Data Build-type: Simple Cabal-version: >= 1.10-Tested-With: GHC ==8.0.2, GHC ==8.2.1, GHC ==8.4.1, GHC ==8.6.5, GHC ==8.8.3+Tested-With: GHC ==8.0.2, GHC ==8.2.1, GHC ==8.4.1, GHC ==8.6.5, GHC ==8.8.3, GHC ==9.0.2 Description: Ordered containers of intervals, with efficient search for all keys containing a point or overlapping an interval.
changelog view
@@ -1,3 +1,5 @@+0.6.2.0 Bugfix: Interval.overlaps could be true for empty intervals+0.6.1.3 Remove unneeded languages pragmas. 0.6.1.2 Enable and fix more warnings. 0.6.1.1 Improve Semigroup instances. 0.6.1.0 Add safe versions of find... functions.
test/IntervalMapTests.hs view
@@ -19,18 +19,18 @@ arbitrary = do x <- arbitrary fmap II (interval (abs x)) +-- In contrast to the other test suites, this will generate empty intervals, too interval :: Int -> Gen (Interval Int) interval x = do- y <- sized (\n -> choose (x, x + abs n))- if x == y then return (ClosedInterval x y)- else oneof [return (ClosedInterval x y),- return (OpenInterval x y),- return (IntervalCO x y),- return (IntervalOC x y)]+ y <- sized (\n -> choose (x, x + n))+ oneof [return (ClosedInterval x y),+ return (OpenInterval x y),+ return (IntervalCO x y),+ return (IntervalOC x y)] instance Arbitrary IMI where arbitrary = do xs <- orderedList- return (IMI (fromAscList [(v, lowerBound v) | (II v) <- xs]))+ return (IMI (fromAscList [(v, lowerBound v) | (II v) <- xs, not (isEmpty v)])) emptyM, single46 :: M.IntervalMap Int String@@ -79,7 +79,10 @@ sameElements ["single46"] [v|(_,v) <- toAscList (bal3' `containing` 5)] && sameElements ["o58", "single46"] [v|(_,v) <- toAscList (bal3' `containing` 6)] +prop_intersectingEmpty =+ M.null (M.intersecting (M.fromList [(IntervalCO 0 2, "0_2")]) (IntervalCO 1 1)) + deep100L :: M.IntervalMap Int Int deep100L = construct 100 M.empty where construct n m | n <= 0 = m@@ -454,11 +457,12 @@ prop_splitIntersecting (II i) (IMI m) = let (lo,c,hi) = M.splitIntersecting m i in M.valid lo && M.valid c && M.valid hi &&- lo == mfilter (i `after`) m &&- c == mfilter (i `overlaps`) m &&- hi == mfilter (i `before`) m && M.unions [lo,c,hi] == m &&- M.size lo + M.size c + M.size hi == M.size m+ c == mfilter (i `overlaps`) m &&+ (isEmpty i || (+ lo == mfilter (i `after`) m &&+ hi == mfilter (i `before`) m &&+ M.size lo + M.size c + M.size hi == M.size m)) mfilter :: (Ord k) => (Interval k -> Bool) -> IntervalMap k a -> IntervalMap k a mfilter p m = M.filterWithKey (\k _ -> p k) m@@ -497,6 +501,7 @@ check prop_tests1 "tests1" check prop_tests2 "tests2" check prop_tests3 "tests3"+ check prop_intersectingEmpty "intersecting with empty interval" check prop_mapKeys "mapKeys" check prop_valid "valid" check prop_singleton "singleton"
test/IntervalTests.hs view
@@ -62,6 +62,9 @@ (c15 `overlaps` IntervalOC 0 1) && not (c15 `overlaps` IntervalCO 0 1) +prop_overlapsEmpty =+ not (overlaps (IntervalCO 1 1) (IntervalCO 0 2))+ prop_subsumes1 = (c15 `subsumes` o15) && -- closed subsumes open not (o15 `subsumes` c15) && -- ~? "open does not subsume closed", not (co15 `subsumes` c15) && -- "open does not subsume closed",@@ -208,6 +211,7 @@ check prop_compare_openness_closedness_upper_bound "compare_openness_closedness_upper_bound" check prop_contains1 "contains1" check prop_overlaps "overlaps"+ check prop_overlapsEmpty "empty does not overlap" check prop_subsumes1 "subsumes1" check prop_not_empty "not empty" check prop_below "below"