Hi Breal > I have a list that looks like the following > [(100000, 100010), (100005, 100007), (100009, 100015)] > > I would like to be able to determine which of these overlap each > other. So, in this case, tuple 1 overlaps with tuples 2 and 3. Tuple > 2 overlaps with 1. Tuple 3 overlaps with tuple 1. > > In my scenario I would have hundreds, if not thousands of these > ranges. Any nice pythonic way to do this?
This may be of no help, but.... In 1995 I wrote a C library to do some stuff like this. You're welcome to the code. It might give you some ideas, or you might want to wrap it for Python. If you did that, and had additional energy, you could release the result to the Python community. As someone said, how/what to do depends what you want to do with the resulting data structure once you've processed the inputs. In my case I wanted to be able to read in a large number of ranges and be able to answer questions like "is X in the range?". I'm pretty sure I made it possible to add ranges to ignore (i.e., that punch holes in an existing range). I'm also pretty sure I'd have made this run in n log n time, by first sorting all the lower bounds (and maybe sorting the upper ones too) and then walking that list. One use case is e.g., for a printer program command line: print --inc-pages 40-70 --exc-pages 51-52 --inc-pages 100-120 which could use the library to step through the range of pages in a doc and easily check which ones should be printed. There are lots of other uses. Lookup time on those queries was probably log n where n is the resulting number of range fragments once the processing (merging/splitting) of the command line was done. I don't remember, but it took me several days to write the code, so it wasn't completely trivial. I can't offer help beyond the code I'm afraid - I have too much other stuff going on. Terry -- http://mail.python.org/mailman/listinfo/python-list
