Finds all intervals with overlapping ranges and splits them along the range boundaries. Completes in worst-case O(n^2*log n) time (many interval boundaries are inside many intervals), best-case O(n*log n) time (small number of overlaps << n per interval).
(self)
| 620 | ) |
| 621 | |
| 622 | def split_overlaps(self): |
| 623 | """ |
| 624 | Finds all intervals with overlapping ranges and splits them |
| 625 | along the range boundaries. |
| 626 | |
| 627 | Completes in worst-case O(n^2*log n) time (many interval |
| 628 | boundaries are inside many intervals), best-case O(n*log n) |
| 629 | time (small number of overlaps << n per interval). |
| 630 | """ |
| 631 | if not self: |
| 632 | return |
| 633 | if len(self.boundary_table) == 2: |
| 634 | return |
| 635 | |
| 636 | bounds = sorted(self.boundary_table) # get bound locations |
| 637 | |
| 638 | new_ivs = set() |
| 639 | for lbound, ubound in zip(bounds[:-1], bounds[1:]): |
| 640 | for iv in self[lbound]: |
| 641 | new_ivs.add(Interval(lbound, ubound, iv.data)) |
| 642 | |
| 643 | self.__init__(new_ivs) |
| 644 | |
| 645 | def merge_overlaps(self, data_reducer=None, data_initializer=None, strict=True): |
| 646 | """ |