IntervalMap 0.2.2 → 0.2.3

raw patch · 4 files changed

+86/−13 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/IntervalMap.hs +72/−9
• IntervalMap.cabal +1/−1
• examples/Example.lhs +3/−3
• test/IntervalMapTests.hs +10/−0

@@ -157,12 +157,12 @@              , split                      , splitLookup   -            {-              -- * Submap             , isSubmapOf, isSubmapOfBy             , isProperSubmapOf, isProperSubmapOfBy +            {-             -- * Indexed              , lookupIndex             , findIndex@@ -183,12 +183,10 @@             , updateMax             , updateMinWithKey             , updateMaxWithKey-            {-             , minView             , maxView             , minViewWithKey             , maxViewWithKey-            -}              -- * Debugging             , valid@@ -452,7 +450,7 @@ -- @'insertWithKey' f key value mp@  -- will insert the pair (key, value) into @mp@ if key does -- not exist in the map. If the key does exist, the function will--- insert the pair @(key,f key new_value old_value)@.+-- insert the pair @(key, f key new_value old_value)@. -- Note that the key passed to f is the same key passed to 'insertWithKey'. 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)@@ -656,6 +654,37 @@                          Just v' -> setMaxValue v' m                          Nothing -> deleteMax m +-- | /O(log n)/. Retrieves the minimal (key,value) pair of the map, and+-- the map stripped of that element, or 'Nothing' if passed an empty map.+--+-- > minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")+-- > minViewWithKey empty == Nothing++minViewWithKey :: Ord k => IntervalMap k a -> Maybe ((Interval k, a), IntervalMap k a)+minViewWithKey Nil = Nothing+minViewWithKey x   = Just (deleteFindMin x)++-- | /O(log n)/. Retrieves the maximal (key,value) pair of the map, and+-- the map stripped of that element, or 'Nothing' if passed an empty map.+maxViewWithKey :: Ord k => IntervalMap k a -> Maybe ((Interval k, a), IntervalMap k a)+maxViewWithKey Nil = Nothing+maxViewWithKey x   = Just (deleteFindMax x)++-- | /O(log n)/. Retrieves the value associated with minimal key of the+-- map, and the map stripped of that element, or 'Nothing' if passed an+-- empty map.+minView :: Ord k => IntervalMap k a -> Maybe (a, IntervalMap k a)+minView Nil = Nothing+minView x   = case deleteFindMin x of ((_,a), x') -> Just (a, x')++-- | /O(log n)/. Retrieves the value associated with maximal key of the+-- map, and the map stripped of that element, or 'Nothing' if passed an+-- empty map.+maxView :: Ord k => IntervalMap k a -> Maybe (a, IntervalMap k a)+maxView Nil = Nothing+maxView x   = case deleteFindMax x of ((_,a), x') -> Just (a, x')++ setMinValue :: v -> IntervalMap k v -> IntervalMap k v setMinValue _  Nil = Nil setMinValue v' (Node c k m _ Nil r) = Node c k m v' Nil r@@ -1094,12 +1123,10 @@ -- is strictly monotonic. -- That is, for any values @x@ and @y@, if @x@ < @y@ then @f x@ < @f y@. -- /The precondition is not checked./------ This function is currently identical to 'mapKeys', but will eventually be rewritten to have better--- better performance (/O(n)/). mapKeysMonotonic :: Ord k2 => (Interval k1 -> Interval k2) -> IntervalMap k1 a -> IntervalMap k2 a--- TODO: optimize-mapKeysMonotonic f m = mapKeys f m+mapKeysMonotonic _ Nil = Nil+mapKeysMonotonic f (Node c k _ x l r) =+    mNode c (f k) x (mapKeysMonotonic f l) (mapKeysMonotonic f r)  -- | /O(n)/. Filter values satisfying a predicate. filter :: Ord k => (a -> Bool) -> IntervalMap k a -> IntervalMap k a@@ -1173,6 +1200,42 @@   where     less    = [e | e@(k,_) <- toAscList m, k < x]     greater = [e | e@(k,_) <- toAscList m, k > x]++-- submaps++-- | /O(n+m)/. This function is defined as (@'isSubmapOf' = 'isSubmapOfBy' (==)@).+isSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool+isSubmapOf m1 m2 = isSubmapOfBy (==) m1 m2++{- | /O(n+m)/.+ The expression (@'isSubmapOfBy' f t1 t2@) returns 'True' if+ all keys in @t1@ are in tree @t2@, and @f@ returns 'True' when+ applied to their respective values.+-}+isSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool+isSubmapOfBy f m1 m2 = go (toAscList m1) (toAscList m2)+  where+    go []    _  =  True+    go (_:_) [] =  False+    go s1@((k1,v1):r1) ((k2,v2):r2) =+       case compare k1 k2 of+         GT -> go s1 r2+         EQ -> f v1 v2 && go r1 r2+         LT -> False++-- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal). +-- Defined as (@'isProperSubmapOf' = 'isProperSubmapOfBy' (==)@).+isProperSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool+isProperSubmapOf m1 m2 = isProperSubmapOfBy (==) m1 m2++{- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal).+ The expression (@'isProperSubmapOfBy' f m1 m2@) returns 'True' when+ @m1@ and @m2@ are not equal,+ all keys in @m1@ are in @m2@, and when @f@ returns 'True' when+ applied to their respective values.+-}+isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool+isProperSubmapOfBy f t1 t2 = size t1 < size t2 && isSubmapOfBy f t1 t2   -- debugging

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

@@ -15,8 +15,8 @@ > type Person = String > type Details = String -For readability, I use strings to represent timestamps. Also, to keep it shorter,-I will omit the date and only use the time of the day in this example.+Again for readability, I use strings to represent timestamps. Also, to keep it shorter,+I will omit the date and only use the time of the day in this example, e.g.: "09:00", "12:47".  > type Time = String > type TimeSpan = Interval Time@@ -28,7 +28,7 @@ > mkTimeSpan :: Time -> Time -> TimeSpan > mkTimeSpan from to = IntervalCO from to -An appointment consists or the timespan, the person, and the appointment details:+An appointment consists of the timespan, the person, and the appointment details:  > type Appointment = (TimeSpan, Person, Details) 

@@ -358,6 +358,15 @@ prop_mapAccum (IMI m) =  M.valid m' && acc == sum (M.elems m) && sum (M.elems m') == 2 * acc   where (acc, m') = M.mapAccum (\a v -> (a+v, 2*v)) 0 m +-- submap++prop_submap (IMI m1) (IMI m2)+  | m1 `M.isSubmapOf` m2 = M.size m1 <= M.size m2+                           && all (==True) [k `M.member` m2 && m1 M.! k == m2 M.! k | k <- M.keys m1]+  | otherwise            = M.size m1 > M.size m2+                           || any (==True) [k `M.notMember` m2 || m1 M.! k /= m2 M.! k | k <- M.keys m1]++ -- filter  prop_filter (IMI m) =  M.valid m' && all odd (M.elems m') && M.size m' == odds@@ -434,6 +443,7 @@ 	  check prop_partition "partition" 	  check prop_splitLookup "splitLookup" 	  check prop_mapKeysWith "mapKeysWith"+          check prop_submap "submap" 	  putStrLn ("deep100L: " ++ show (M.showStats deep100L)) 	  putStrLn ("deep100R: " ++ show (M.showStats deep100R)) 	  exitSuccess