IntervalMap 0.6.2.1 → 0.6.2.3

raw patch · 5 files changed

+17/−98 lines, 5 filesdep −SegmentTreePVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies removed: SegmentTree

API changes (from Hackage documentation)

Files

• IntervalMap.cabal +5/−5
• README.md +2/−2
• bench/CompareTypes.hs +8/−61
• changelog +2/−0
• examples/GetttingStarted.lhs +0/−30

@@ -1,18 +1,18 @@ Name:                IntervalMap-Version:             0.6.2.1+Version:             0.6.2.3 Stability:           experimental Synopsis:            Containers for intervals, with efficient search.-Homepage:            http://www.chr-breitkopf.de/comp/IntervalMap+Homepage:            https://www.chr-breitkopf.de/comp/IntervalMap License:             BSD3 License-file:        LICENSE Author:              Christoph Breitkopf Maintainer:          Christoph Breitkopf <chbreitkopf@gmail.com> bug-reports:         mailto:chbreitkopf@gmail.com-Copyright:           2011-2020 Christoph Breitkopf+Copyright:           2011-2026 Christoph Breitkopf 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, GHC ==9.0.2+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, GHC ==9.6.7 Description:                      Ordered containers of intervals, with efficient search                      for all keys containing a point or overlapping an interval.@@ -119,7 +119,7 @@   hs-source-dirs:     . bench   main-is:            CompareTypes.hs   Build-depends:      base >= 4 && < 5,-                      containers, random, deepseq, fingertree >= 0.1, SegmentTree,+                      containers, random, deepseq, fingertree >= 0.1,                       criterion >= 1.0   default-language:    Haskell2010   ghc-options: -Wall

@@ -1,10 +1,10 @@-# IntervalMap [![Hackage](https://img.shields.io/hackage/v/IntervalMap.svg)](https://hackage.haskell.org/package/IntervalMap) [![Build Status](https://travis-ci.org/bokesan/IntervalMap.svg?branch=master)](https://travis-ci.org/bokesan/IntervalMap)+# IntervalMap [![Hackage](https://img.shields.io/hackage/v/IntervalMap.svg)](https://hackage.haskell.org/package/IntervalMap) ![Continuous Integration](https://github.com/bokesan/IntervalMap/actions/workflows/ci.yml/badge.svg)  Containers for intervals. Like `Data.Set` and `Data.Map` with Intervals as keys and functions for efficiently getting the subset of all intervals containing a point, intersecting an interval, and more. -Home page and documentation: [http://www.chr-breitkopf.de/comp/IntervalMap/index.html](http://www.chr-breitkopf.de/comp/IntervalMap/index.html)+Home page and documentation: [https://www.chr-breitkopf.de/comp/IntervalMap/index.html](https://www.chr-breitkopf.de/comp/IntervalMap/index.html)  ## Getting started 

@@ -15,45 +15,15 @@ import qualified Data.IntervalMap.Generic.Strict as RB import qualified IvMapSortedList as SL import qualified Data.IntervalMap.FingerTree as FT-import qualified Data.SegmentTree as ST   instance Ord a => Interval (FT.Interval a) a where   lowerBound = FT.low   upperBound = FT.high -instance Ord a => Interval (ST.Interval a) a where-  lowerBound (ST.Interval _ (ST.R a) _ _) = a-  lowerBound _ = error "interval lower"-  upperBound (ST.Interval _ _ (ST.R a) _) = a-  upperBound _ = error "interval upper"---instance NFData a => NFData (FT.Interval a) where-  rnf (FT.Interval a b) = a `deepseq` b `deepseq` ()--instance NFData a => NFData (ST.Interval a) where-  rnf (ST.Interval _ (ST.R a) (ST.R b) _) = a `deepseq` b `deepseq` ()-  rnf a = a `seq` ()--instance (NFData k, NFData v) => NFData (FT.IntervalMap k v) where-  -- FIXME-  rnf a = a `seq` ()--instance NFData v => NFData (ST.STree v Int) where-  rnf (ST.Leaf a b) = a `deepseq` b `deepseq`()-  rnf (ST.Branch a b c d) = a `deepseq` b `deepseq` c `deepseq` d `deepseq` ()- ftFromList :: Ord k => [(FT.Interval k, v)] -> FT.IntervalMap k v ftFromList =  foldr (\(k,v) m -> FT.insert k v m) FT.empty -stFromList :: [(Int,Int)] -> ST.STree [ST.Interval Int] Int-stFromList = ST.fromList--stLoBound :: ST.Interval Int -> Int-stLoBound (ST.Interval{ST.low=(ST.R v)}) = v-stLoBound _ = error "stLoBound"- cSEED, cSEED2 :: Int cSEED  = 54321 cSEED2 = 12345@@ -103,15 +73,7 @@   where    toIv (IntRange a b) = FT.Interval a b -stEnv :: Int -> IO ([ST.Interval Int], ST.STree [ST.Interval Int] Int)-stEnv n = do-   let ivs  = genRandomIntervals n 20 n-   let ivsFt = [(lo,hi) | (IntRange lo hi) <- nub ivs]-   return (map toIv (mkKeys n), stFromList ivsFt)-  where-   toIv (IntRange a b) = ST.Interval ST.Closed (ST.R a) (ST.R b) ST.Closed - runInsert :: Interval k a => (k -> a -> m -> m) -> m -> [k] -> m runInsert ins m keys = foldr (\k mp -> ins k (lowerBound k) mp) m keys @@ -139,58 +101,43 @@     bench "containing"  $ nf (\ks -> sum [v | k <- ks, (_,v) <- FT.search (FT.low k) m]) keys   ] -benchST :: ([ST.Interval Int], ST.STree [ST.Interval Int] Int) -> Benchmark-benchST ~(keys,m) = bgroup "SegmentTree" [-    bench "insert"      $ whnf (runInsert (\k _ mp -> ST.insert mp k) m) keys,-    bench "containing"  $ nf (\ks -> sum [stLoBound v | k <- ks, v <- ST.stabbingQuery m (stLoBound k)]) keys-  ] -- main :: IO () main = defaultMainWith benchConfig [         bgroup "10" [            env (slEnv 10) benchSL,            env (rbEnv 10) benchRB,-           env (ftEnv 10) benchFT,-           env (stEnv 10) benchST+           env (ftEnv 10) benchFT          ],          bgroup "100" [            env (slEnv 100) benchSL,            env (rbEnv 100) benchRB,-           env (ftEnv 100) benchFT,-           env (stEnv 100) benchST+           env (ftEnv 100) benchFT          ],          bgroup "1000" [            env (slEnv 1000) benchSL,            env (rbEnv 1000) benchRB,-           env (ftEnv 1000) benchFT,-           env (stEnv 1000) benchST+           env (ftEnv 1000) benchFT          ],          bgroup "2500" [            env (slEnv 2500) benchSL,            env (rbEnv 2500) benchRB,-           env (ftEnv 2500) benchFT,-           env (stEnv 2500) benchST+           env (ftEnv 2500) benchFT          ],          bgroup "10000" [            env (rbEnv 10000) benchRB,-           env (ftEnv 10000) benchFT,-           env (stEnv 10000) benchST+           env (ftEnv 10000) benchFT          ],          bgroup "20000" [            env (rbEnv 20000) benchRB,-           env (ftEnv 20000) benchFT,-           env (stEnv 20000) benchST+           env (ftEnv 20000) benchFT          ],          bgroup "50000" [            env (rbEnv 50000) benchRB,-           env (ftEnv 50000) benchFT,-           env (stEnv 50000) benchST+           env (ftEnv 50000) benchFT          ],          bgroup "100000" [            env (rbEnv 100000) benchRB,-           env (ftEnv 100000) benchFT,-           env (stEnv 100000) benchST+           env (ftEnv 100000) benchFT          ]        ]

@@ -1,3 +1,5 @@+0.6.2.3  Fix benchmark broken by fingertree adding its own NFData instance+0.6.2.2  Remove SegmentTree from benchmarks because it does not compile with current ghc/cabal 0.6.2.1  Future-proof against potential Prelude.foldl' 0.6.2.0  Bugfix: Interval.overlaps could be true for empty intervals 0.6.1.3  Remove unneeded languages pragmas.

@@ -1,30 +0,0 @@-You need some language extensions to be able to-define Interval Instances:--> {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}--In most cases, you should use the value-strict version:--> import qualified Data.IntervalMap.Generic.Strict as IM--Make tuples an instance of Interval:--> instance Ord e => IM.Interval (e,e) e where->   lowerBound (a,_) = a->   upperBound (_,b) = b->   rightClosed _ = False--By using `rightClosed _ = False` we have defined tuples to be half-open-intervals - they include the starting value, but not the end value.--Now we can put them into a Map:--> type MyMap = IM.IntervalMap (Int,Int) String->-> sample :: MyMap-> sample = IM.fromList [((1,6), "Foo"), ((2,4), "Bar"), ((4,7), "Baz")]--Lookup intervals containing a given point ("stabbing query"):--> main = print (IM.toAscList $ sample `IM.containing` 3)-