IntervalMap 0.3.0.0 → 0.3.0.1
raw patch · 3 files changed
+324/−40 lines, 3 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- Data/IntervalMap/Base.hs +2/−39
- Data/IntervalMap/Strict.hs +321/−0
- IntervalMap.cabal +1/−1
Data/IntervalMap/Base.hs view
@@ -77,11 +77,8 @@ -- ** Insertion , insert , insertWith- , insertWith' , insertWithKey- , insertWithKey' , insertLookupWithKey- , insertLookupWithKey' -- ** Delete\/Update , delete@@ -187,6 +184,7 @@ , Color(..) , balanceL, balanceR , turnBlack+ , setMinValue, setMaxValue -- * Debugging , valid@@ -433,7 +431,7 @@ -- | /O(log n)/. Insert a new key/value pair. If the map already contains the key, its value is -- changed to the new value. insert :: (Ord k) => Interval k -> v -> IntervalMap k v -> IntervalMap k v-insert = insertWithKey' (\_ v _ -> v)+insert = insertWithKey (\_ v _ -> v) -- | /O(log n)/. Insert with a function, combining new value and old value. -- @'insertWith' f key value mp@ @@ -443,11 +441,6 @@ insertWith :: (Ord k) => (v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k v insertWith f = insertWithKey (\_ new old -> f new old) --- | 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)- -- | /O(log n)/. Insert with a function, combining key, new value and old value. -- @'insertWithKey' f key value mp@ -- will insert the pair (key, value) into @mp@ if key does@@ -465,19 +458,6 @@ GT -> balanceR color k v l (ins r) EQ -> Node color k m (f k value v) l r --- | Same as 'insertWithKey', but the combining function is applied strictly.-insertWithKey' :: (Ord k) => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k v-insertWithKey' f key value mp = key `seq` turnBlack (ins mp)- where- singletonR k v = Node R k k v Nil Nil- ins Nil = value `seq` singletonR key value- ins (Node color k m v l r) =- case compare key k of- LT -> balanceL color k v (ins l) r- GT -> balanceR color k v l (ins r)- EQ -> let v' = f k value v in v' `seq` Node color k m v' l r-- -- | /O(log n)/. Combine insert with old values retrieval. insertLookupWithKey :: (Ord k) => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v) insertLookupWithKey f key value mp = key `seq` (oldval, turnBlack mp')@@ -494,23 +474,6 @@ (x@(Just _), t') -> (x, Node color k m v l t') (Nothing, t') -> (Nothing, balanceR color k v l t') EQ -> (Just v, Node color k m (f k value v) l r)---- | /O(log n)/. A strict version of 'insertLookupWithKey'.-insertLookupWithKey' :: (Ord k) => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v)-insertLookupWithKey' f key value mp = key `seq` (oldval, turnBlack mp')- where- (oldval, mp') = ins mp- singletonR k v = Node R k k v Nil Nil- ins Nil = value `seq` (Nothing, singletonR key value)- ins (Node color k m v l r) =- case compare key k of- LT -> case ins l of- (x@(Just _), t') -> (x, Node color k m v t' r)- (Nothing, t') -> (Nothing, balanceL color k v t' r)- GT -> case ins r of- (x@(Just _), t') -> (x, Node color k m v l t')- (Nothing, t') -> (Nothing, balanceR color k v l t')- EQ -> let v' = f k value v in v' `seq` (Just v, Node color k m v' l r) balanceL :: Ord k => Color -> Interval k -> v -> IntervalMap k v -> IntervalMap k v -> IntervalMap k v
Data/IntervalMap/Strict.hs view
@@ -197,12 +197,47 @@ ) where import Prelude hiding (null, lookup, map, filter, foldr, foldl)+import qualified Data.List as L import Data.IntervalMap.Base as M hiding ( singleton , insert , insertWith , insertWithKey , findWithDefault+ , insertLookupWithKey+ , adjust+ , adjustWithKey+ , update+ , updateWithKey+ , updateLookupWithKey+ , alter+ , unionWith+ , unionWithKey+ , unionsWith+ , differenceWith+ , differenceWithKey+ , intersectionWith+ , intersectionWithKey+ , map+ , mapWithKey+ , mapAccum+ , mapAccumWithKey+ , mapAccumRWithKey+ , mapKeysWith+ , fromList+ , fromListWith+ , fromListWithKey+ , fromAscList+ , fromAscListWith+ , fromAscListWithKey+ , mapMaybe+ , mapMaybeWithKey+ , mapEither+ , mapEitherWithKey+ , updateMin+ , updateMax+ , updateMinWithKey+ , updateMaxWithKey ) -- | /O(1)/. A map with one entry.@@ -250,3 +285,289 @@ LT -> balanceL color k v (ins l) r GT -> balanceR color k v l (ins r) EQ -> let v' = f k value v in v' `seq` Node color k m v' l r+++-- | /O(log n)/. Combine insert with old values retrieval.+insertLookupWithKey :: (Ord k) => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v)+insertLookupWithKey f key value mp = key `seq` (oldval, turnBlack mp')+ where+ (oldval, mp') = ins mp+ singletonR k v = Node R k k v Nil Nil+ ins Nil = value `seq` (Nothing, singletonR key value)+ ins (Node color k m v l r) =+ case compare key k of+ LT -> case ins l of+ (x@(Just _), t') -> (x, Node color k m v t' r)+ (Nothing, t') -> (Nothing, balanceL color k v t' r)+ GT -> case ins r of+ (x@(Just _), t') -> (x, Node color k m v l t')+ (Nothing, t') -> (Nothing, balanceR color k v l t')+ EQ -> let v' = f k value v in v' `seq` (Just v, Node color k m v' l r)+++-- | /O(log n)/. Update a value at a specific key with the result of the provided function.+-- When the key is not+-- 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++-- | /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.+adjustWithKey :: Ord k => (Interval k -> a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a+adjustWithKey _ _ Nil = Nil+adjustWithKey f x (Node c k m v l r) =+ case compare x k of+ LT -> Node c k m v (adjustWithKey f x l) r+ GT -> Node c k m v l (adjustWithKey f x r)+ EQ -> let v' = f k v in v' `seq` Node c k m v' l r++-- | /O(log n)/. Update or delete value at minimum key.+updateMin :: Ord k => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v+updateMin f m = updateMinWithKey (\_ v -> f v) m++-- | /O(log n)/. Update or delete value at maximum key.+updateMax :: Ord k => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v+updateMax f m = updateMaxWithKey (\_ v -> f v) m++-- | /O(log n)/. Update or delete value at minimum key.+updateMinWithKey :: Ord k => (Interval k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v+updateMinWithKey _ Nil = Nil+updateMinWithKey f m = let (k,v) = findMin m in+ case f k v of+ Just v' -> v' `seq` setMinValue v' m+ Nothing -> deleteMin m++-- | /O(log n)/. Update or delete value at maximum key.+updateMaxWithKey :: Ord k => (Interval k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v+updateMaxWithKey _ Nil = Nil+updateMaxWithKey f m = let (k,v) = findMax m in+ case f k v of+ Just v' -> v' `seq` setMaxValue v' m+ Nothing -> deleteMax m++-- | /O(n log n)/. Build a map from a list of key\/value pairs. See also 'fromAscList'.+-- If the list contains more than one value for the same key, the last value+-- for the key is retained.+fromList :: Ord k => [(Interval k,v)] -> IntervalMap k v+fromList xs = L.foldl' (\m (k,v) -> insert k v m) empty xs++-- | /O(n log n)/. Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'.+fromListWith :: Ord k => (a -> a -> a) -> [(Interval k,a)] -> IntervalMap k a +fromListWith f xs = fromListWithKey (\_ x y -> f x y) xs++-- | /O(n log n)/. Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'.+fromListWithKey :: Ord k => (Interval k -> a -> a -> a) -> [(Interval k,a)] -> IntervalMap k a +fromListWithKey f xs = L.foldl' ins empty xs+ where+ ins t (k,x) = insertWithKey f k x t++-- | /O(n)/. Build a map from an ascending list in linear time.+-- /The precondition (input list is ascending) is not checked./+fromAscList :: Ord k => [(Interval k,v)] -> IntervalMap k v+fromAscList xs = fromAscListWith (\_ b -> b) xs++-- | /O(n)/. Build a map from an ascending list in linear time with a combining function for equal keys.+-- /The precondition (input list is ascending) is not checked./+fromAscListWith :: Ord k => (a -> a -> a) -> [(Interval k,a)] -> IntervalMap k a +fromAscListWith f xs = fromAscListWithKey (\_ a b -> f a b) xs++-- | /O(n)/. Build a map from an ascending list in linear time with a combining function for equal keys.+-- /The precondition (input list is ascending) is not checked./+fromAscListWithKey :: Ord k => (Interval k -> a -> a -> a) -> [(Interval k,a)] -> IntervalMap k a +fromAscListWithKey f xs = fromDistinctAscList (combineEq f xs)++combineEq :: Eq k => (k -> a -> a -> a) -> [(k,a)] -> [(k,a)]+combineEq _ [] = []+combineEq _ xs@[_] = xs+combineEq f (x@(xk,xv) : xs@((yk,yv) : xs'))+ | xk == yk = let v' = f xk xv yv in v' `seq` combineEq f ((xk, v') : xs')+ | otherwise = x : combineEq f xs+++-- | /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)++-- | /O(n)/. Map a function over all values in the map.+mapWithKey :: (Interval k -> a -> b) -> IntervalMap k a -> IntervalMap k b+mapWithKey f = go+ where+ go Nil = Nil+ go (Node c k m v l r) = let v' = f k v in v' `seq` Node c k m v' (go l) (go r)++-- | /O(n)/. The function 'mapAccum' threads an accumulating+-- argument through the map in ascending order of keys.+--+-- > let f a b = (a ++ b, b ++ "X")+-- > 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++-- | /O(n)/. The function 'mapAccumWithKey' threads an accumulating+-- argument through the map in ascending order of keys.+--+-- > let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")+-- > 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 = go+ where+ go a Nil = (a,Nil)+ go a (Node c kx m x l r) =+ let (a1,l') = go a l+ (a2,x') = f a1 kx x+ (a3,r') = go a2 r+ in x' `seq` (a3, Node c kx m x' l' r')++-- | /O(n)/. The function 'mapAccumRWithKey' threads an accumulating+-- argument through the map in descending order of keys.+mapAccumRWithKey :: (a -> Interval k -> b -> (a,c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)+mapAccumRWithKey f = go+ where+ go a Nil = (a, Nil)+ go a (Node c kx m x l r) =+ let (a1,r') = go a r+ (a2,x') = f a1 kx x+ (a3,l') = go a2 l+ in x' `seq` (a3, Node c kx m x' l' r')+++-- | /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++-- | /O(n)/. Map keys\/values and collect the 'Just' results.+mapMaybeWithKey :: Ord k => (Interval k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b+mapMaybeWithKey f m = fromDistinctAscList (mapf [] m)+ where+ mapf z Nil = z+ mapf z (Node _ k _ v l r) = mapf (f' k v z r) l+ f' k v z r = case f k v of+ Nothing -> mapf z r+ Just v' -> v' `seq` (k,v') : mapf z r++-- | /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++-- | /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)+mapEitherWithKey f m = (fromDistinctAscList l, fromDistinctAscList r)+ where+ (l, r) = part [] [] (toDescList m)+ part ls rs [] = (ls, rs)+ part ls rs ((k,v):xs) = case f k v of+ Left v' -> v' `seq` part ((k,v'):ls) rs xs+ Right v' -> v' `seq` part ls ((k,v'):rs) xs+++-- | /O(log n)/. The expression (@'alter' f k map@) alters the value @x@ at @k@, or absence thereof.+-- 'alter' can be used to insert, delete, or update a value in a 'Map'.+-- In short : @'lookup' k ('alter' f k m) = f ('lookup' k m)@.+alter :: Ord k => (Maybe a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a+alter f x m = case lookup x m of+ Nothing -> case f Nothing of+ Nothing -> m+ Just v -> insert x v m+ y -> case f y of+ Nothing -> delete x m+ Just v' -> adjust (const v') x m+++-- | /O(n log n)/. @'mapKeysWith' c f s@ is the map obtained by applying @f@ to each key of @s@.+-- +-- The size of the result may be smaller if @f@ maps two or more distinct+-- keys to the same new key. In this case the associated values will be+-- combined using @c@.+mapKeysWith :: Ord k2 => (a -> a -> a) -> (Interval k1 -> Interval k2) -> IntervalMap k1 a -> IntervalMap k2 a+mapKeysWith c f m = fromListWith c [ (f k, v) | (k, v) <- toAscList m ]++-- | /O(log n)/. The expression (@'update' f k map@) updates the value @x@+-- at @k@ (if it is in the map). If (@f x@) is 'Nothing', the element is+-- 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++-- | /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',+-- the element is deleted. If it is (@'Just' y@), the key @k@ is bound+-- 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)++-- | /O(log n)/. Lookup and update. See also 'updateWithKey'.+-- The function returns changed value, if it is updated.+-- Returns the original key value if the map entry is deleted.+updateLookupWithKey :: Ord k => (Interval k -> a -> Maybe a) -> Interval k -> IntervalMap k a -> (Maybe a, IntervalMap k a)+updateLookupWithKey f x m = case lookup x m of+ Nothing -> (Nothing, m)+ r@(Just v) -> case f x v of+ Nothing -> (r, delete x m)+ r'@(Just v') -> (r', adjust (const v') x m)+++-- | /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++-- | /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+unionWithKey f m1 m2 = fromDistinctAscList (ascListUnion f (toAscList m1) (toAscList m2))++-- | The union of a list of maps, with a combining operation:+-- (@'unionsWith' f == 'Prelude.foldl' ('unionWith' f) 'empty'@).+unionsWith :: Ord k => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a+unionsWith f = L.foldl (unionWith f) empty++-- | /O(n+m)/. Difference with a combining function. +-- When two equal keys are+-- encountered, the combining function is applied to the values of these keys.+-- If it returns 'Nothing', the element is discarded (proper set difference). If+-- 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++-- | /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.+-- If it returns 'Nothing', the element is discarded (proper set difference). If+-- it returns (@'Just' y@), the element is updated with a new value @y@. +differenceWithKey :: Ord k => (Interval k -> a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a+differenceWithKey f m1 m2 = fromDistinctAscList (ascListDifference f (toAscList m1) (toAscList m2))++-- | /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++-- | /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+intersectionWithKey f m1 m2 = fromDistinctAscList (ascListIntersection f (toAscList m1) (toAscList m2))+++ascListUnion :: Ord k => (k -> a -> a -> a) -> [(k,a)] -> [(k,a)] -> [(k,a)]+ascListUnion _ [] [] = []+ascListUnion _ [] ys = ys+ascListUnion _ xs [] = xs+ascListUnion f xs@(x@(xk,xv):xs') ys@(y@(yk,yv):ys') =+ case compare xk yk of+ LT -> x : ascListUnion f xs' ys+ GT -> y : ascListUnion f xs ys'+ EQ -> let v' = f xk xv yv in v' `seq` (xk, v') : ascListUnion f xs' ys'++ascListDifference :: Ord k => (k -> a -> b -> Maybe a) -> [(k,a)] -> [(k,b)] -> [(k,a)]+ascListDifference _ [] _ = []+ascListDifference _ xs [] = xs+ascListDifference f xs@(x@(xk,xv):xs') ys@((yk,yv):ys') =+ case compare xk yk of+ LT -> x : ascListDifference f xs' ys+ GT -> ascListDifference f xs ys'+ EQ -> case f xk xv yv of+ Nothing -> ascListDifference f xs' ys'+ Just v' -> v' `seq` (xk,v') : ascListDifference f xs' ys'++ascListIntersection :: Ord k => (k -> a -> b -> c) -> [(k,a)] -> [(k,b)] -> [(k,c)]+ascListIntersection _ [] _ = []+ascListIntersection _ _ [] = []+ascListIntersection f xs@((xk,xv):xs') ys@((yk,yv):ys') =+ case compare xk yk of+ LT -> ascListIntersection f xs' ys+ GT -> ascListIntersection f xs ys'+ EQ -> let v' = f xk xv yv in v' `seq` (xk, v') : ascListIntersection f xs' ys'
IntervalMap.cabal view
@@ -1,5 +1,5 @@ Name: IntervalMap-Version: 0.3.0.0+Version: 0.3.0.1 Stability: experimental Synopsis: Maps from Intervals to values, with efficient search. Homepage: http://www.chr-breitkopf.de/comp/IntervalMap