Returns a set of all intervals overlapping the given range. Completes in O(m + k*log n) time, where: * n = size of the tree * m = number of matches * k = size of the search range :rtype: set of Interval
(self, begin, end=None)
| 911 | return result |
| 912 | |
| 913 | def overlap(self, begin, end=None): |
| 914 | """ |
| 915 | Returns a set of all intervals overlapping the given range. |
| 916 | |
| 917 | Completes in O(m + k*log n) time, where: |
| 918 | * n = size of the tree |
| 919 | * m = number of matches |
| 920 | * k = size of the search range |
| 921 | :rtype: set of Interval |
| 922 | """ |
| 923 | root = self.top_node |
| 924 | if not root: |
| 925 | return set() |
| 926 | if end is None: |
| 927 | iv = begin |
| 928 | return self.overlap(iv.begin, iv.end) |
| 929 | elif begin >= end: |
| 930 | return set() |
| 931 | result = root.search_point(begin, set()) # bound_begin might be greater |
| 932 | boundary_table = self.boundary_table |
| 933 | bound_begin = boundary_table.bisect_left(begin) |
| 934 | bound_end = boundary_table.bisect_left(end) # up to, but not including end |
| 935 | result.update(root.search_overlap( |
| 936 | # slice notation is slightly slower |
| 937 | boundary_table.keys()[index] for index in xrange(bound_begin, bound_end) |
| 938 | )) |
| 939 | return result |
| 940 | |
| 941 | def begin(self): |
| 942 | """ |