packages feed

IntervalMap 0.2.1 → 0.2.2

raw patch · 4 files changed

+105/−51 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

Data/IntervalMap.hs view
@@ -455,13 +455,28 @@ -- 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 k v m =  snd (insertLookupWithKey f k v m)-{-# INLINE insertWithKey #-}+insertWithKey f key value mp  =  key `seq` turnBlack (ins mp)+  where+    singletonR k v = Node R k k v Nil Nil+    ins Nil = 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 -> 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 k v m =  snd (insertLookupWithKey' f k v m)-{-# INLINE insertWithKey' #-}+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)
IntervalMap.cabal view
@@ -1,5 +1,5 @@ Name:                IntervalMap-Version:             0.2.1+Version:             0.2.2 Stability:           experimental Synopsis:            Maps from Intervals to values, with efficient search. Homepage:            http://www.chr-breitkopf.de/comp/IntervalMap@@ -16,11 +16,12 @@ Description:                      A map from intervals to values, with efficient search                      for all keys containing a point or overlapping an interval.+                     See the example code on the home page for a quick introduction.  extra-source-files:   README   test/*.hs-  examples/*.hs+  examples/*.lhs  Library   Exposed-modules:     Data.IntervalMap, Data.IntervalMap.Interval
− examples/Example.hs 
@@ -1,45 +0,0 @@-import Data.IntervalMap as IM--type Person = String-type Details = String---- For readability, represent timestamps as strings. Also, to keep it shorter,--- we will only use time of the day in this example.-type Time = String-type TimeSpan = Interval Time---- We have a time span include its start time but not its end time.-mkTimeSpan :: Time -> Time -> TimeSpan-mkTimeSpan from to = IntervalCO from to--type Appointments = IM.IntervalMap Time [(Person, Details)]--noAppointments :: Appointments-noAppointments = IM.empty--addAppointment :: Person -> Time -> Time -> Details -> Appointments -> Appointments-addAppointment who from to what apps = IM.insertWith (++) (mkTimeSpan from to) [(who, what)] apps--sampleApps :: Appointments-sampleApps = addAppointment "Paul" "09:00" "11:00" "Dentist" $-             addAppointment "John" "10:00" "11:30" "Meeting" $-             addAppointment "Rosy" "10:00" "11:30" "Shopping" $-             addAppointment "Lisa" "08:45" "09:15" "Bank" $-             noAppointments--appointmentsAt :: Time -> Appointments -> [(TimeSpan, Person, Details)]-appointmentsAt t apps = [ (ts, p, d) | (ts, ps) <- hits, (p,d) <- ps ]-  where-    hits :: [(TimeSpan, [(Person, Details)])]-    hits = apps `containing` t--appointmentsDuring :: Time -> Time -> Appointments -> [(TimeSpan, Person, Details)]-appointmentsDuring from to apps = [ (ts, p, d) | (ts, ps) <- hits, (p,d) <- ps ]-  where-    hits :: [(TimeSpan, [(Person, Details)])]-    hits =  apps `intersecting` mkTimeSpan from to--main :: IO ()-main = do putStrLn (show (appointmentsAt "09:00" sampleApps))-          putStrLn (show (appointmentsDuring "09:30" "10:30" sampleApps))-	  putStrLn (show (IM.toAscList sampleApps))
+ examples/Example.lhs view
@@ -0,0 +1,83 @@+In this example I use an IntervalMap to store a set of appointments.+The appointments are for several people, so it's clear that they can overlap.++This is a literate Haskell file, you can [download it](Example.lhs) and compile it with+ghc or run in in ghci. You must first install IntervalMap, if you have not already done so:+`cabal install IntervalMap`.++First I have to import the module:++> import Data.IntervalMap++For readability, here are simple type synonyms for our data types. In production+code, one would of course use newtype or data for this.++> 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.++> type Time = String+> type TimeSpan = Interval Time++I have a time span include its start time but not its end time.+So I use the *IntervalCO* constructor to get an interval that is closed at the startpoint+but open at the endpoint:++> mkTimeSpan :: Time -> Time -> TimeSpan+> mkTimeSpan from to = IntervalCO from to++An appointment consists or the timespan, the person, and the appointment details:++> type Appointment = (TimeSpan, Person, Details)++For a set of possible overlapping appointments, I store a list of (person, details)+tuples for each timespan:++> type Appointments = IntervalMap Time [(Person, Details)]++Not that the key type is *Time*, not *TimeSpan*. That is, you specify the type of the+endpoints, not the type of the interval itself.++Now I can define some helper functions.++A set containing no appointments:++> noAppointments :: Appointments+> noAppointments =  empty++To add an appointment to a set, I use (++) as a combining function to add+the new appointment:++> addAppointment :: Person -> Time -> Time -> Details -> Appointments -> Appointments+> addAppointment who from to what = insertWith (++) (mkTimeSpan from to) [(who, what)]++To look up all appointments at a given time, just get all entries _containing_+that time:++> appointmentsAt :: Time -> Appointments -> [Appointment]+> appointmentsAt t apps = [ (time, person, details)+>                           | (time, pds) <- apps `containing` t,+>                             (person, details) <- pds ]++The function to get all appointments that overlap a given timespan is almost+the same, just using _intersecting_ instead:++> appointmentsDuring :: Time -> Time -> Appointments -> [Appointment]+> appointmentsDuring from to apps = [ (time, person, details)+>                                     | (time, pds) <- apps `intersecting` mkTimeSpan from to,+>                                       (person, details) <- pds ]++Here is a sample set of appointments and a main function to show some test results:++> sampleApps :: Appointments+> sampleApps = addAppointment "Paul" "09:00" "11:00" "Dentist" $+>              addAppointment "John" "10:00" "11:30" "Meeting" $+>              addAppointment "Rosy" "10:00" "11:30" "Shopping" $+>              addAppointment "Lisa" "08:45" "09:15" "Bank" $+>              noAppointments+>+> main :: IO ()+> main = do putStrLn (show (appointmentsAt "09:00" sampleApps))+>           putStrLn (show (appointmentsDuring "09:30" "10:30" sampleApps))