IntervalMap 0.5.0.1 → 0.5.1.0

raw patch · 7 files changed

+123/−22 lines, 7 filesdep +weighPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies added: weigh

API changes (from Hackage documentation)

Files

• Data/IntervalMap/Generic/Base.hs +7/−5
• Data/IntervalMap/Generic/Interval.hs +15/−4
• Data/IntervalSet.hs +8/−6
• IntervalMap.cabal +12/−3
• bench/BenchIntervalSet.hs +9/−4
• bench/WeighAllocs.hs +70/−0
• changelog +2/−0

@@ -268,7 +268,7 @@     rnf Nil = ()     rnf (Node _ kx _ x l r) = kx `deepseq` x `deepseq` l `deepseq` r `deepseq` () -instance (Ord k, Read k, Read e, Interval i k, Ord i, Read i) => Read (IntervalMap i e) where+instance (Read e, Interval i k, Ord i, Read i) => Read (IntervalMap i e) where   readsPrec p = readParen (p > 10) $ \ r -> do     ("fromList",s) <- lex r     (xs,t) <- reads s@@ -304,8 +304,10 @@  -- interval with the greatest upper bound. The lower bound is ignored! maxByUpper :: (Interval i e) => i -> i -> i-maxByUpper a b | rightClosed a = if upperBound a >= upperBound b then a else b-               | otherwise     = if upperBound a >  upperBound b then a else b+maxByUpper a b = a `seq` b `seq`+                 case compareUpperBounds a b of+                   LT -> b+                   _  -> a  -- --------------------------------------------------------- @@ -1042,7 +1044,7 @@ keys m = [k | (k,_) <- toAscList m]  -- | /O(n)/. Set of the keys.-keysSet :: (Ord k) => IntervalMap k v -> Set.Set k+keysSet :: IntervalMap k v -> Set.Set k keysSet m =  Set.fromDistinctAscList (keys m)  -- | Same as 'toAscList'.@@ -1190,7 +1192,7 @@ -- | /O(n)/. Split around a point. -- Splits the map into three submaps: intervals below the point, -- intervals containing the point, and intervals above the point.-splitAt :: (Interval i k, Ord i) => IntervalMap i a -> k -> (IntervalMap i a, IntervalMap i a, IntervalMap i a)+splitAt :: (Interval i k) => IntervalMap i a -> k -> (IntervalMap i a, IntervalMap i a, IntervalMap i a) splitAt mp p = (fromUnion (lower mp), mp `containing` p, fromUnion (higher mp))   where     lower Nil = UEmpty

@@ -98,6 +98,16 @@   isEmpty i | leftClosed i && rightClosed i = lowerBound i >  upperBound i             | otherwise                     = lowerBound i >= upperBound i +  compareUpperBounds :: i -> i -> Ordering+  compareUpperBounds a b = case compare (upperBound a) (upperBound b) of+                             LT -> LT+                             GT -> GT+                             EQ -> case (rightClosed a, rightClosed b) of+                                     (False, True) -> LT+                                     (True, False) -> GT+                                     _             -> EQ++ {- -- sample instance for tuples: instance Ord e => Interval (e,e) e where@@ -105,18 +115,18 @@   upperBound (_,b) = b -} -genericEquals :: (Interval i e, Eq e) => i -> i -> Bool+genericEquals :: (Interval i e) => i -> i -> Bool genericEquals a b = lowerBound a == lowerBound b && upperBound a == upperBound b                     && leftClosed a == leftClosed b                     && rightClosed a == rightClosed b -genericCompare :: (Interval i e, Ord e) => i -> i -> Ordering+genericCompare :: (Interval i e) => i -> i -> Ordering genericCompare a b = case compareL a b of                        LT -> LT                        GT -> GT                        EQ -> compareU a b -compareL :: (Interval i e, Ord e) => i -> i -> Ordering+compareL :: (Interval i e) => i -> i -> Ordering compareL a b = case compare (lowerBound a) (lowerBound b) of                  LT -> LT                  GT -> GT@@ -125,7 +135,7 @@                          (False, True) -> GT                          _ -> EQ -compareU :: (Interval i e, Ord e) => i -> i -> Ordering+compareU :: (Interval i e) => i -> i -> Ordering compareU a b = case compare (upperBound a) (upperBound b) of                  LT -> LT                  GT -> GT@@ -147,3 +157,4 @@     below       = I.below     inside      = I.inside     isEmpty     = I.isEmpty+    compareUpperBounds = I.compareByUpper

@@ -185,7 +185,7 @@     rnf Nil = ()     rnf (Node _ kx _ l r) = kx `deepseq` l `deepseq` r `deepseq` () -instance (Ord k, Read k, Interval i k, Ord i, Read i) => Read (IntervalSet i) where+instance (Interval i k, Ord i, Read i) => Read (IntervalSet i) where   readsPrec p = readParen (p > 10) $ \ r -> do     ("fromList",s) <- lex r     (xs,t) <- reads s@@ -221,8 +221,10 @@  -- interval with the greatest upper bound. The lower bound is ignored! maxByUpper :: (Interval i e) => i -> i -> i-maxByUpper a b | rightClosed a = if upperBound a >= upperBound b then a else b-               | otherwise     = if upperBound a >  upperBound b then a else b+maxByUpper a b = a `seq` b `seq`+                 case compareUpperBounds a b of+                   LT -> b+                   _  -> a  -- --------------------------------------------------------- @@ -619,7 +621,7 @@     go v [] = [v]     go v (y:ys) | v == y    = go v ys                 | otherwise = v : go y ys-                              + -- Strict tuple data T2 a b = T2 !a !b @@ -679,7 +681,7 @@ -- -- The size of the result may be smaller if @f@ maps two or more distinct -- elements to the same value.-map :: (Interval a e1, Interval b e2, Ord b) => (a -> b) -> IntervalSet a -> IntervalSet b+map :: (Interval b e2, Ord b) => (a -> b) -> IntervalSet a -> IntervalSet b map f s = fromList [f x | x <- toList s]  -- | /O(n)/. @'mapMonotonic' f s == 'map' f s@, but works only when @f@@@ -745,7 +747,7 @@ -- | /O(n)/. Split around a point. -- Splits the set into three subsets: intervals below the point, -- intervals containing the point, and intervals above the point.-splitAt :: (Interval i k, Ord i) => IntervalSet i -> k -> (IntervalSet i, IntervalSet i, IntervalSet i)+splitAt :: (Interval i k) => IntervalSet i -> k -> (IntervalSet i, IntervalSet i, IntervalSet i) splitAt set p = (fromUnion (lower set), set `containing` p, fromUnion (higher set))   where     lower Nil = UEmpty

@@ -1,5 +1,5 @@ Name:                IntervalMap-Version:             0.5.0.1+Version:             0.5.1.0 Stability:           experimental Synopsis:            Containers for intervals, with efficient search. Homepage:            http://www.chr-breitkopf.de/comp/IntervalMap@@ -8,11 +8,11 @@ Author:              Christoph Breitkopf Maintainer:          Christoph Breitkopf <chbreitkopf@gmail.com> bug-reports:         mailto:chbreitkopf@gmail.com-Copyright:           2011-2015 Christoph Breitkopf+Copyright:           2011-2016 Christoph Breitkopf Category:            Data Build-type:          Simple Cabal-version:       >= 1.8-Tested-With:         GHC ==7.4.2, GHC ==7.6.3, GHC ==7.8.4, GHC ==7.10.2+Tested-With:         GHC ==7.4.2, GHC ==7.6.3, GHC ==7.8.4, GHC ==7.10.2, GHC ==8.0.1 Description:                      Ordered containers of intervals, with efficient search                      for all keys containing a point or overlapping an interval.@@ -112,6 +112,15 @@   Build-depends:      base >= 4 && < 5,                       containers, random, deepseq,                       criterion >= 1.0+  ghc-options: -Wall -with-rtsopts=-K1K++benchmark weigh-allocs+  type:               exitcode-stdio-1.0+  hs-source-dirs:     . bench+  main-is:            WeighAllocs.hs+  Build-depends:      base >= 4 && < 5,+                      containers, random, deepseq,+                      weigh   ghc-options: -Wall -with-rtsopts=-K1K  benchmark bench-compare-types

@@ -89,9 +89,14 @@            bench "spi2"         $ whnf (\s -> sum [maxValue (spi2 s i) | i <- rndIvs]) set,            bench "spi3"         $ whnf (\s -> sum [maxValue (spi3 s i) | i <- rndIvs]) set          ],-         bgroup "mapKeys" [-           bench "mapKeys"      $ nf (S.map (move 1)) set,-           bench "monotonic"    $ nf (S.mapMonotonic (move 1)) set+         bgroup "map" [+           bench "map"      $ nf (S.map (move 1)) set,+           bench "monotonic" $ nf (S.mapMonotonic (move 1)) set+         ],+         bgroup "delete" [+           bench "deleteMin"    $ nf S.deleteMin set,+           bench "deleteMax"    $ nf S.deleteMax set,+           bench "delete"       $ nf (\(k,s) -> S.delete k s) (head rndIvs, set)          ]        ] @@ -116,7 +121,7 @@                Nothing -> 0                Just (IV lo _) -> lo              -splitAt1, splitAt2, splitAt3 :: (Interval i e, Ord i) => S.IntervalSet i -> e -> S.IntervalSet i+splitAt1, splitAt2, splitAt3 :: (Interval i e) => S.IntervalSet i -> e -> S.IntervalSet i splitAt1 s p = case S.splitAt s p of (lo,_,_) -> lo splitAt2 s p = case S.splitAt s p of (_,c,_) -> c splitAt3 s p = case S.splitAt s p of (_,_,hi) -> hi

@@ -0,0 +1,70 @@+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE MultiParamTypeClasses #-}++import Weigh++import Control.DeepSeq+import Prelude hiding (lookup, max, foldr)+import System.Random+import Data.Foldable (foldr)++import Data.IntervalMap.Generic.Interval+import qualified Data.IntervalSet as S+import qualified Data.Set as C+++seed :: Int+seed = 54321++ensure :: NFData a => a -> IO a+ensure xs = xs `deepseq` return xs++forceRange :: Int -> Int -> Int -> Int+forceRange lo hi n | n >= lo && n <= hi = n+                   | n < 0              = forceRange lo hi (0 - n)+                   | otherwise          = lo + (n `rem` (1 + hi - lo))++genRandomIntervals :: Int -> Int -> Int -> [(Int,Int)]+genRandomIntervals max lap n = genIvs . take (2*n) . randoms . mkStdGen $ seed+  where+    genIvs [] = []+    genIvs [_] = []+    genIvs (x:y:xs) = let lo = forceRange 1 max x+                          sz = forceRange 0 lap y+                      in (lo, lo + sz) : genIvs xs+++cDATA_SIZE :: Int+cDATA_SIZE =  1000++data IV = IV {-# UNPACK #-} !Int {-# UNPACK #-} !Int+          deriving (Eq, Ord)++instance NFData IV where+  rnf a = a `seq` ()++instance Interval IV Int where+  lowerBound (IV l _) = l+  upperBound (IV _ u) = u++main :: IO ()+main =+  do+      let ivs  = genRandomIntervals cDATA_SIZE 50 cDATA_SIZE+      let n = show cDATA_SIZE+      ivsP   <- ensure $ [IV lo hi | (lo,hi) <- ivs]+      cS     <- ensure $ C.fromList ivsP+      sS     <- ensure $ S.fromList ivsP+      oIvsP  <- ensure $ C.toAscList cS+      daIvsP <- ensure $ [IV x x | x <- [1 .. cDATA_SIZE]]+      mainWith+       (do+         func ("Data.Set    fromList " ++ n)            C.fromList ivsP+         func ("IntervalSet fromList " ++ n)            S.fromList ivsP+         func ("Data.Set    fromAscList " ++ n)         C.fromAscList oIvsP+         func ("IntervalSet fromAscList " ++ n)         S.fromAscList oIvsP+         func ("Data.Set    fromDistinctAscList " ++ n) C.fromDistinctAscList daIvsP+         func ("IntervalSet fromDistinctAscList " ++ n) S.fromDistinctAscList daIvsP+         func ("Data.Set    mapMonotonic " ++ n)        (C.mapMonotonic id) cS+         func ("IntervalSet mapMonotonic " ++ n)        (S.mapMonotonic id) sS+         )

@@ -1,3 +1,5 @@+0.5.1.0  Major performance improvements.+ 0.5.0.1  Improve performance of combine. 	 Fix wrong doc comments.