Should work fine as far as I can see. Of course, thats not very 'pythonic' - I should probably give at least 10 different unit tests that it passes ;)
Its gratifying to know I'm not the only one who needed that final yield. Jim Sizelove wrote: > Bengt Richter wrote: > > On Tue, 10 May 2005 15:14:47 +0200, Max M <[EMAIL PROTECTED]> wrote: > > > > > >>I am writing a "find-free-time" function for a calendar. There are a lot > >>of time spans with start end times, some overlapping, some not. > >> > >>To find the free time spans, I first need to convert the events into a > >>list of non overlapping time spans "meta-spans". > >> > >>This nice ascii graph should show what I mean. > >> > >>1) --- > >>2) --- > >>3) --- > >>4) ----- > >>5) ----- > >> > >> > >>>>------- -------- # meta spans > >> > >>I can then iterate through the meta-spans and find non-busy times. > >> > >>I have written the class below, but it is rather O^2, so I wondered if > >>anybody has an idea for a better approach? > >> > > > > Maybe (not tested beyond what you see ;-) > > It is with some trepidation that I write this message; after hanging > around in c.l.p for the better part of a year, I have come to expect > Bengt's messages to be right-on and error-free. > > However this time... :) > > >>> def mergespans(spans): > > ... start = end = None > > ... for s,e in sorted(spans): > > ... if start is None: start, end = s,e; continue > > ... if s <= end: end = e; continue > > ... yield start, end > > ... start,end = s,e > > ... if start is not None: yield start, end > > ... > > >>> spans = [(0,3), (4,7), (2,5), (9,14), (12,17)] > > >>> list(mergespans(spans)) > > [(0, 7), (9, 17)] > > There can be a problem in mergespans if one span fits inside another: > > >>> spans = [(0,5), (4,7), (2,3), (9,14), (12,17)] > >>> list(mergespans(spans)) > [(0, 3), (4, 7), (9, 17)] > > Here is a revised version (not tested beyond what you see ;-) > >>> def mergespans(spans): > ... start = end = None > ... for s,e in sorted(spans): > ... if start is None: > ... start, end = s,e > ... continue > ... if s <= end: > ... if end < e: > ... end = e > ... continue > ... yield start, end > ... start,end = s,e > ... if start is not None: > ... yield start, end > ... > >>> list(mergespans([(0,5), (4,7), (2,3), (9,14), (12,17)])) > [(0, 7), (9, 17)] > >>> list(mergespans([(0,3), (4,7), (2,5), (9,14), (12,17)])) > [(0, 7), (9, 17)] > > Can anyone find any other errors in this? ;-) > > With humble regards, > Jim Sizelove -- http://mail.python.org/mailman/listinfo/python-list
