IntervalMap 0.4.0.0 → 0.4.0.1

raw patch · 5 files changed

+52/−31 lines, 5 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Data/IntervalMap/Generic/Base.hs +6/−8
• Data/IntervalMap/Generic/Interval.hs +36/−10
• Data/IntervalMap/Generic/Lazy.hs +3/−3
• Data/IntervalMap/Generic/Strict.hs +6/−9
• IntervalMap.cabal +1/−1

@@ -4,7 +4,7 @@ -- License     :  BSD-style -- Maintainer  :  chbreitkopf@gmail.com -- Stability   :  experimental--- Portability :  portable+-- Portability :  non-portable (MPTC with FD) -- -- An implementation of maps from intervals to values. The key intervals may -- overlap, and the implementation contains efficient search functions@@ -12,7 +12,7 @@ -- Closed, open, and half-open intervals can be contained in the same map. -- -- An IntervalMap cannot contain duplicate keys - if you need to map a key--- to muiltiple values, use a collection as the value type, for+-- to multiple values, use a collection as the value type, for -- example: @IntervalMap /k/ [/v/]@. -- -- It is an error to insert an empty interval into a map. This precondition is not@@ -21,14 +21,12 @@ -- Since many function names (but not the type name) clash with -- /Prelude/ names, this module is usually imported @qualified@, e.g. ----- >  import Data.IntervalMap (IvMap)--- >  import qualified Data.IntervalMap as IvMap+-- >  import Data.Generic.IntervalMap.Strict (IntervalMap)+-- >  import qualified Data.Generic.IntervalMap.Strict as IM -- -- It offers most of the same functions as 'Data.Map', but the key type must be an--- instance of 'Interval'. Some of the functions need stricter type constraints to--- maintain the additional information for efficient interval searching,--- for example 'fromDistinctAscList' needs an 'Ord' /k/ constraint.--- Also, some functions differ in asymptotic performance (for example 'size') or have not+-- instance of 'Interval'.+-- Some functions differ in asymptotic performance (for example 'size') or have not -- been tuned for efficiency as much as their equivalents in 'Data.Map' (in -- particular the various set functions). --

@@ -4,8 +4,14 @@ -- License     :  BSD-style -- Maintainer  :  chbreitkopf@gmail.com -- Stability   :  experimental--- Portability :  portable+-- Portability :  non-portable (MPTC with FD) --+-- Type class for IntervalMap keys.+--+-- As there is no sensible default, no instances for prelude types+-- are provided (E.g. you might want to have tuples as closed+-- intervals in one case, and open in another).+ {-# LANGUAGE FunctionalDependencies #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE UndecidableInstances #-}@@ -20,13 +26,14 @@   -- | Intervals with endpoints of type @e@.--- A minimal instance declaration needs to define 'con', 'lowerBound', and 'upperBound'.+-- A minimal instance declaration for a closed interval needs only+-- to define 'lowerBound' and 'upperBound'. class Ord e => Interval i e | i -> e where-  --  Construct interval from endpoints-  -- con :: e -> e -> i e+  -- | lower bound+  lowerBound :: i -> e -  -- | lower and upper bound-  lowerBound, upperBound :: i -> e+  -- | upper bound+  upperBound :: i -> e    -- | Does the interval include its lower bound?   -- Default is True for all values, i.e. closed intervals.@@ -38,25 +45,44 @@   rightClosed :: i -> Bool   rightClosed _ = True -  overlaps, subsumes, before, after :: i -> i -> Bool+  -- | Interval strictly before another?+  -- True if the upper bound of the first interval is below the lower bound of the second.+  before :: i -> i -> Bool   a `before` b = upperBound a < lowerBound b                  || (upperBound a == lowerBound b && not (rightClosed a && leftClosed b))-  a `after` b  = lowerBound a > upperBound b-                 || (lowerBound a == upperBound b && not (leftClosed a && rightClosed b))++  -- | Interval strictly after another?+  -- Same as 'flip before'.+  after :: i -> i -> Bool+  a `after` b  = b `before` a++  -- | Does the first interval completely contain the second?+  subsumes :: i -> i -> Bool   a `subsumes` b = (lowerBound a < lowerBound b || (lowerBound a == lowerBound b && (leftClosed a || not (leftClosed b))))                    &&                    (upperBound a > upperBound b || (upperBound a == upperBound b && (rightClosed a || not (rightClosed b))))++  -- | Do the two intervals overlap?+  overlaps :: i -> i -> Bool   a `overlaps` b = (lowerBound a < upperBound b || (lowerBound a == upperBound b && leftClosed a && rightClosed b))                    &&                    (upperBound a > lowerBound b || (upperBound a == lowerBound b && rightClosed a && leftClosed b)) -  above, below, inside :: e -> i -> Bool+  -- | Is a point strictly less than lower bound?+  below :: e -> i -> Bool   p `below` i | leftClosed i  = p <  lowerBound i               | otherwise     = p <= lowerBound i++  -- | Is a point strictly greater than upper bound?+  above :: e -> i -> Bool   p `above` i | rightClosed i = p >  upperBound i               | otherwise     = p >= upperBound i++  -- | Does the interval contain a given point?+  inside :: e -> i -> Bool   p `inside` i = not ((p `above` i) || (p `below` i))  +  -- | Is the interval empty?   isEmpty :: i -> Bool   isEmpty i | leftClosed i && rightClosed i = lowerBound i >  upperBound i             | otherwise                     = lowerBound i >= upperBound i

@@ -1,17 +1,17 @@ {- | Module      :  Data.IntervalMap.Lazy-Copyright   :  (c) Christoph Breitkopf 2011+Copyright   :  (c) Christoph Breitkopf 2014 License     :  BSD-style Maintainer  :  chbreitkopf@gmail.com Stability   :  experimental-Portability :  portable+Portability :  non-portable (MPTC with FD)  An implementation of maps from intervals to values. The key intervals may overlap, and the implementation contains efficient search functions for all keys containing a point or overlapping an interval. Closed, open, and half-open intervals can be contained in the same map. -This module implements the same functions as "Data.IntervalMap.Strict",+This module implements the same functions as "Data.IntervalMap.Generic.Strict", but with value-lazy semantics. -} module Data.IntervalMap.Generic.Lazy (

@@ -4,7 +4,7 @@ License     :  BSD-style Maintainer  :  chbreitkopf@gmail.com Stability   :  experimental-Portability :  portable+Portability :  non-portable (MPTC with FD)  An implementation of maps from intervals to values. The key intervals may overlap, and the implementation contains efficient search@@ -28,15 +28,12 @@ Since many function names (but not the type name) clash with /Prelude/ names, this module is usually imported @qualified@, e.g. ->  import Data.IntervalMap (IvMap)->  import qualified Data.IntervalMap as IvMap+>  import Data.Generic.IntervalMap.Strict (IntervalMap)+>  import qualified Data.Generic.IntervalMap.Strict as IM -It offers most of the same functions as 'Data.Map', but uses-'Interval' /k/ instead of just /k/ as the key type. Some of the-functions need stricter type constraints to maintain the additional-information for efficient interval searching, for example-'fromDistinctAscList' needs an 'Ord' /k/ constraint. Also, some-functions differ in asymptotic performance (for example 'size') or+It offers most of the same functions as 'Data.Map', but the+key type must be an instance of 'Interval'.+Some functions differ in asymptotic performance (for example 'size') or have not been tuned for efficiency as much as their equivalents in 'Data.Map' (in particular the various set functions). 

@@ -1,5 +1,5 @@ Name:                IntervalMap-Version:             0.4.0.0+Version:             0.4.0.1 Stability:           experimental Synopsis:            Maps from Intervals to values, with efficient search. Homepage:            http://www.chr-breitkopf.de/comp/IntervalMap