IntervalMap 0.2.3 → 0.2.3.1
raw patch · 3 files changed
+30/−47 lines, 3 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- Data/IntervalMap.hs +29/−43
- Data/IntervalMap/Interval.hs +0/−3
- IntervalMap.cabal +1/−1
Data/IntervalMap.hs view
@@ -7,21 +7,30 @@ -- Portability : portable -- -- An implementation of maps from intervals to values. The key intervals may--- overlap, and the implementation supports an efficient stabbing query.+-- 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. --+-- An IntervalMap cannot contain duplicate keys - if you need to map a key+-- to muiltiple 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+-- checked by the various construction functions.+-- -- Since many function names (but not the type name) clash with--- "Prelude" names, this module is usually imported @qualified@, e.g.+-- /Prelude/ names, this module is usually imported @qualified@, e.g. -- -- > import Data.IntervalMap (IvMap) -- > import qualified Data.IntervalMap as IvMap ----- It offers most of the functions in Data.Map, but 'Interval' /k/ instead of+-- 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.------ Index-based access and some set functions have not been implemented, and many non-core--- functions, for example the set operations, have not been tuned for efficiency yet.+-- Also, 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). -- -- In addition, there are functions specific to maps of intervals, for example to search -- for all keys containing a given point or contained in a given interval.@@ -29,12 +38,7 @@ -- To stay compatible with standard Haskell, this implementation uses a fixed data -- type for intervals, and not a multi-parameter type class. Thus, it's currently -- not possible to define e.g. a 2-tuple as an instance of interval and use that--- map key. Instead you must convert your keys to 'Data.IntervalMap.Interval'.------ Closed, open, and half-open intervals can be contained in the same map.------ It is an error to insert an empty interval into a map. This precondition is not--- checked by the various insertion functions.+-- map key. Instead, you must convert your keys to 'Interval'. -- -- The implementation is a red-black tree augmented with the maximum upper bound -- of all keys.@@ -325,6 +329,9 @@ null _ = False -- | /O(n)/. Number of keys in the map.+--+-- Caution: unlike 'Data.Map.size', which takes constant time, this is linear in the+-- number of keys! size :: IntervalMap k v -> Int size t = h 0 t where@@ -338,10 +345,12 @@ height (Node _ _ _ _ l r) = 1 + max (height l) (height r) -- | The maximum height of a red-black tree with the given number of nodes.+-- For testing/debugging only. maxHeight :: Int -> Int maxHeight nodes = 2 * log2 (nodes + 1) --- | Tree statistics (size, height, maxHeight size)+-- | Tree statistics (size, height, maxHeight size).+-- For testing/debugging only. showStats :: IntervalMap k a -> (Int, Int, Int) showStats m = (n, height m, maxHeight n) where n = size m@@ -429,7 +438,6 @@ -- changed to the new value. insert :: (Ord k) => Interval k -> v -> IntervalMap k v -> IntervalMap k v insert = insertWithKey' (\_ v _ -> v)-{-# INLINE insert #-} -- | /O(log n)/. Insert with a function, combining new value and old value. -- @'insertWith' f key value mp@ @@ -438,13 +446,11 @@ -- insert the pair @(key, f new_value old_value)@. insertWith :: (Ord k) => (v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k v insertWith f = insertWithKey (\_ new old -> f new old)-{-# INLINE insertWith #-} -- | Same as 'insertWith', but the combining function is applied strictly. -- This is often the most desirable behavior. insertWith' :: (Ord k) => (v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k v insertWith' f = insertWithKey' (\_ new old -> f new old)-{-# INLINE insertWith' #-} -- | /O(log n)/. Insert with a function, combining key, new value and old value. -- @'insertWithKey' f key value mp@ @@ -791,7 +797,6 @@ -- a member of the map, the original map is returned. adjust :: Ord k => (a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a adjust f k m = adjustWithKey (\_ v -> f v) k m-{-# INLINE adjust #-} -- | /O(log n)/. Adjust a value at a specific key. When the key is not -- a member of the map, the original map is returned.@@ -808,7 +813,6 @@ -- deleted. If it is (@'Just' y@), the key @k@ is bound to the new value @y@. update :: Ord k => (a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a update f k m = updateWithKey (\_ v -> f v) k m-{-# INLINE update #-} -- | /O(log n)/. The expression (@'updateWithKey' f k map@) updates the -- value @x@ at @k@ (if it is in the map). If (@f k x@) is 'Nothing',@@ -816,7 +820,6 @@ -- to the new value @y@. updateWithKey :: Ord k => (Interval k -> a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a updateWithKey f k m = snd (updateLookupWithKey f k m)-{-# INLINE updateWithKey #-} -- | /O(log n)/. Lookup and update. See also 'updateWithKey'. -- The function returns changed value, if it is updated.@@ -846,12 +849,10 @@ -- i.e. (@'union' == 'unionWith' 'const'@). union :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a union m1 m2 = unionWith const m1 m2-{-# INLINE union #-} -- | /O(n+m)/. Union with a combining function. unionWith :: Ord k => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a unionWith f m1 m2 = unionWithKey (\_ v1 v2 -> f v1 v2) m1 m2-{-# INLINE unionWith #-} -- | /O(n+m)/. Union with a combining function. unionWithKey :: Ord k => (Interval k -> a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a@@ -871,7 +872,6 @@ -- Return elements of the first map not existing in the second map. difference :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a difference m1 m2 = differenceWithKey (\_ _ _ -> Nothing) m1 m2-{-# INLINE difference #-} -- | /O(n+m)/. Difference with a combining function. -- When two equal keys are@@ -880,7 +880,6 @@ -- it returns (@'Just' y@), the element is updated with a new value @y@. differenceWith :: Ord k => (a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a differenceWith f m1 m2 = differenceWithKey (\_ v1 v2 -> f v1 v2) m1 m2-{-# INLINE differenceWith #-} -- | /O(n+m)/. Difference with a combining function. When two equal keys are -- encountered, the combining function is applied to the key and both values.@@ -894,12 +893,10 @@ -- (@'intersection' m1 m2 == 'intersectionWith' 'const' m1 m2@). intersection :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a intersection m1 m2 = intersectionWithKey (\_ v _ -> v) m1 m2-{-# INLINE intersection #-} -- | /O(n+m)/. Intersection with a combining function. intersectionWith :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c intersectionWith f m1 m2 = intersectionWithKey (\_ v1 v2 -> f v1 v2) m1 m2-{-# INLINE intersectionWith #-} -- | /O(n+m)/. Intersection with a combining function. intersectionWithKey :: Ord k => (Interval k -> a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c@@ -1001,7 +998,7 @@ | isPerfect n = buildB n xs | otherwise = buildR n (log2 n) xs - buildB n xs | n <= 0 = error "fromDictinctAscList: buildB 0"+ buildB n xs | xs `seq` n <= 0 = error "fromDictinctAscList: buildB 0" | n == 1 = case xs of ((k,v):xs') -> (Node B k k v Nil Nil, xs') | otherwise = case n `quot` 2 of { n' ->@@ -1009,7 +1006,7 @@ case buildB n' xs' of { (r, xs'') -> (mNode B k v l r, xs'') }}} - buildR n d xs | d `seq` n == 0 = (Nil, xs)+ buildR n d xs | d `seq` xs `seq` n == 0 = (Nil, xs) | n == 1 = case xs of ((k,v):xs') -> (Node (if d==0 then R else B) k k v Nil Nil, xs') | otherwise = case n `quot` 2 of { n' ->@@ -1020,13 +1017,12 @@ -- is n a perfect binary tree size (2^m-1)? isPerfect :: Int -> Bool isPerfect n = (n .&. (n + 1)) == 0-{-# INLINE isPerfect #-} log2 :: Int -> Int log2 m = h (-1) m where- h r n | n <= 0 = r- | otherwise = h (r + 1) (n `shiftR` 1)+ h r n | r `seq` n <= 0 = r+ | otherwise = h (r + 1) (n `shiftR` 1) -- | /O(n)/. List of all values in the map, in ascending order of their keys.@@ -1044,14 +1040,12 @@ -- | Same as 'toAscList'. assocs :: IntervalMap k v -> [(Interval k, v)] assocs m = toAscList m-{-# INLINE assocs #-} -- --- Mapping --- -- | /O(n)/. Map a function over all values in the map. map :: (a -> b) -> IntervalMap k a -> IntervalMap k b map f = mapWithKey (\_ x -> f x)-{-# INLINE map #-} -- | /O(n)/. Map a function over all values in the map. mapWithKey :: (Interval k -> a -> b) -> IntervalMap k a -> IntervalMap k b@@ -1067,7 +1061,6 @@ -- > mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")]) mapAccum :: (a -> b -> (a,c)) -> a -> IntervalMap k b -> (a, IntervalMap k c) mapAccum f a m = mapAccumWithKey (\a' _ x' -> f a' x') a m-{-# INLINE mapAccum #-} -- | /O(n)/. The function 'mapAccumWithKey' threads an accumulating -- argument through the map in ascending order of keys.@@ -1076,7 +1069,6 @@ -- > mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")]) mapAccumWithKey :: (a -> Interval k -> b -> (a,c)) -> a -> IntervalMap k b -> (a, IntervalMap k c) mapAccumWithKey f a t = mapAccumL f a t-{-# INLINE mapAccumWithKey #-} -- | /O(n)/. The function 'mapAccumL' threads an accumulating -- argument throught the map in ascending order of keys.@@ -1131,19 +1123,16 @@ -- | /O(n)/. Filter values satisfying a predicate. filter :: Ord k => (a -> Bool) -> IntervalMap k a -> IntervalMap k a filter p m = filterWithKey (\_ v -> p v) m-{-# INLINE filter #-} -- | /O(n)/. Filter keys\/values satisfying a predicate. filterWithKey :: Ord k => (Interval k -> a -> Bool) -> IntervalMap k a -> IntervalMap k a filterWithKey p m = mapMaybeWithKey (\k v -> if p k v then Just v else Nothing) m-{-# INLINE filterWithKey #-} -- | /O(n)/. Partition the map according to a predicate. The first -- map contains all elements that satisfy the predicate, the second all -- elements that fail the predicate. See also 'split'. partition :: Ord k => (a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a) partition p m = partitionWithKey (\_ v -> p v) m-{-# INLINE partition #-} -- | /O(n)/. Partition the map according to a predicate. The first -- map contains all elements that satisfy the predicate, the second all@@ -1153,12 +1142,10 @@ where p' k v | p k v = Left v | otherwise = Right v-{-# INLINE partitionWithKey #-} -- | /O(n)/. Map values and collect the 'Just' results. mapMaybe :: Ord k => (a -> Maybe b) -> IntervalMap k a -> IntervalMap k b mapMaybe f m = mapMaybeWithKey (\_ v -> f v) m-{-# INLINE mapMaybe #-} -- | /O(n)/. Map keys\/values and collect the 'Just' results. mapMaybeWithKey :: Ord k => (Interval k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b@@ -1173,7 +1160,6 @@ -- | /O(n)/. Map values and separate the 'Left' and 'Right' results. mapEither :: Ord k => (a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c) mapEither f m = mapEitherWithKey (\_ v -> f v) m-{-# INLINE mapEither #-} -- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results. mapEitherWithKey :: Ord k => (Interval k -> a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)@@ -1191,7 +1177,6 @@ split :: Ord k => Interval k -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a) split x m = (l, r) where (l, _, r) = splitLookup x m-{-# INLINE split #-} -- | /O(n)/. The expression (@'splitLookup' k map@) splits a map just -- like 'split' but also returns @'lookup' k map@. @@ -1241,8 +1226,9 @@ -- debugging -- | Check red-black-tree and interval search augmentation invariants.+-- For testing/debugging only. valid :: Ord k => IntervalMap k v -> Bool-valid mp = ({-# SCC "scc_test" #-} test mp) && height mp <= maxHeight (size mp) && validColor mp+valid mp = test mp && height mp <= maxHeight (size mp) && validColor mp where test Nil = True test n@(Node _ _ _ _ l r) = validOrder n && validMax n && test l && test r@@ -1256,7 +1242,7 @@ validOrder Nil = True -- validColor parentColor blackCount tree- validColor n = {-# SCC "scc_blackDepth" #-} blackDepth n >= 0+ validColor n = blackDepth n >= 0 -- return -1 if subtrees have diffrent black depths or two consecutive red nodes are encountered blackDepth :: IntervalMap k v -> Int
Data/IntervalMap/Interval.hs view
@@ -94,7 +94,6 @@ compareL (IntervalOC a _) (ClosedInterval b _) = if a < b then LT else GT compareL (IntervalOC a _) (OpenInterval b _) = compare a b compareL (IntervalOC a _) (IntervalOC b _) = compare a b-{-# INLINE compareL #-} -- compare only the upper bound compareU :: Ord a => Interval a -> Interval a -> Ordering@@ -114,7 +113,6 @@ compareU (IntervalOC _ a) (ClosedInterval _ b) = compare a b compareU (IntervalOC _ a) (OpenInterval _ b) = if a < b then LT else GT compareU (IntervalOC _ a) (IntervalOC _ b) = compare a b-{-# INLINE compareU #-} instance Ord a => Ord (Interval a) where compare a b = case compareL a b of@@ -237,7 +235,6 @@ -- Same as 'flip before'. after :: Ord a => Interval a -> Interval a -> Bool r `after` l = l `before` r-{-# INLINE after #-} -- | Does the interval contain a given point?
IntervalMap.cabal view
@@ -1,5 +1,5 @@ Name: IntervalMap-Version: 0.2.3+Version: 0.2.3.1 Stability: experimental Synopsis: Maps from Intervals to values, with efficient search. Homepage: http://www.chr-breitkopf.de/comp/IntervalMap