How do I partition datetime intervals which overlap (Org Mode clocked time)?

Question

I have related tasks from two Org files/subtrees where some of the clocked time overlaps. These are a manual worklog and a generated git commit log, see below.

One subtree's CLOCK: entries needs to be adjusted to remove overlapping time. The other subtree is considered complete, and it's CLOCK: entries should not be adjusted.

EDIT: This question is about calculating new time intervals to remove any overlaps. Any suggestions don't need to parse the Org mode file format. Python datetime.datetime algorithms are helpful, as are Emacs Lisp with or without the use of Org mode functions.

In Python (more familiar) or Emacs Lisp (Org functions could help) I would like to:

1. Identify time overlaps where they occur. file1.org will be mutable, file2.org time intervals should be considered fixed/correct.

2. Calculate new time intervals for the CLOCK: lines in file1.org to remove any overlap with file2.org CLOCK: lines.

3. write resulting new CLOCK: lines out, or at least the pertinent datetimes.

The python convenience function tsparse converts an Org Mode timestamp to a python datetime.datetime object:

>>> from datetime import datetime, timedelta
>>> def tsparse(timestring): return datetime.strptime(timestring,'%Y-%m-%d %a %H:%M')
>>> tsparse('2008-10-15 Wed 00:45')
datetime.datetime(2008, 10, 15, 0, 45)

Test cases can be found below. Thanks for any algorithm or implementation suggestions for Python or Emacs Lisp.

Jeff

---

file1.org, prior to adjustments:

* Manually Edited Worklog

** DONE Onsite
   CLOSED: [2009-09-09 Wed 15:00]
   :LOGBOOK:
   CLOCK: [2009-09-09 Wed 07:00]--[2009-09-09 Wed 15:00] =>  8:00
   :END:

** DONE Onsite
   CLOSED: [2009-09-10 Wed 15:00]
   :LOGBOOK:
   CLOCK: [2009-09-10 Thu 08:00]--[2009-09-10 Thu 15:00] =>  7:00
   :END:

---

file2.org:

* Generated commit log

** DONE Commit 1                          :partial:overlap:leading:contained:
   CLOSED: [2009-09-09 Tue 10:18]
   :LOGBOOK:
   CLOCK: [2009-09-09 Wed 06:40]--[2009-09-09 Wed 07:18] =>  0:38
   CLOCK: [2009-09-09 Wed 10:12]--[2009-09-09 Wed 10:18] =>  0:06
   :END:

** DONE Commit 2                               :contained:overlap:contiguous:
   CLOSED: [2009-09-09 Wed 10:20]
   :LOGBOOK:
   CLOCK: [2009-09-09 Wed 10:18]--[2009-09-09 Wed 10:20] =>  0:02
   :END:

** DONE Commit 4                                          :contained:overlap:
   CLOSED: [2009-09-10 Wed 09:53]
   :LOGBOOK:
   CLOCK: [2009-09-10 Wed 09:49]--[2009-09-10 Wed 09:53] =>  0:04
   :END:

** DONE Commit 5                                   :partial:overlap:trailing:
   CLOSED: [2009-09-10 Wed 15:12]
   :LOGBOOK:
   CLOCK: [2009-09-10 Wed 14:45]--[2009-09-10 Wed 15:12] =>  0:27
   :END:

** DONE Commit 6                                    :partial:overlap:leading:
   CLOSED: [2009-09-11 Fri 08:05]
   :LOGBOOK:
   CLOCK: [2009-09-11 Fri 07:50]--[2009-09-11 Fri 08:05] =>  0:15
   :END:

** DONE Commit 7                                                 :nonoverlap:
   CLOSED: [2009-09-11 Fri 15:55]
   :LOGBOOK:
   CLOCK: [2009-09-11 Fri 15:25]--[2009-09-11 Fri 15:55] =>  0:30
   :END:

---

file1.org, after adjustments:

* Manually Edited Worklog

** DONE Onsite
   CLOSED: [2009-09-09 Wed 15:00]
   :LOGBOOK:
   CLOCK: [2009-09-09 Wed 10:20]--[2009-09-09 Wed 14:45] =>  4:25
   CLOCK: [2009-09-09 Wed 07:18]--[2009-09-09 Wed 10:12] =>  2:54
   :END:

** DONE Onsite
   CLOSED: [2009-09-10 Wed 15:00]
   :LOGBOOK:
   CLOCK: [2009-09-10 Thu 08:05]--[2009-09-10 Thu 15:00] =>  6:55
   :END:

Answer 1

Do you want help parsing the file format? Or just on figuring out the overlapping times?

datetime objects are comparable in Python, so you can do something like this:

>>> (a,b) = (datetime(2009, 9, 15, 8, 30), datetime(2009, 9, 15, 8, 45))
>>> (c,d) = (datetime(2009, 9, 15, 8, 40), datetime(2009, 9, 15, 8, 50))
>>> a <= b
True
>>> if c <= b <= d:
...     print "overlap, merge these two ranges"
... else:
...     print "separate ranges, leave them alone"
...
overlap, merge these two ranges

If the end of the first range (b) is within the second range (c and d), then there is an overlap and you can merge those two pairs into one range (a,d).

Since your set of data looks pretty small you can probably just do this comparison and merge between all time ranges (N**2) and get an acceptable result.