Returns the set of all intervals fully contained in the range [begin, end). 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)
| 876 | return root.search_point(p, set()) |
| 877 | |
| 878 | def envelop(self, begin, end=None): |
| 879 | """ |
| 880 | Returns the set of all intervals fully contained in the range |
| 881 | [begin, end). |
| 882 | |
| 883 | Completes in O(m + k*log n) time, where: |
| 884 | * n = size of the tree |
| 885 | * m = number of matches |
| 886 | * k = size of the search range |
| 887 | :rtype: set of Interval |
| 888 | """ |
| 889 | root = self.top_node |
| 890 | if not root: |
| 891 | return set() |
| 892 | if end is None: |
| 893 | iv = begin |
| 894 | return self.envelop(iv.begin, iv.end) |
| 895 | elif begin >= end: |
| 896 | return set() |
| 897 | result = root.search_point(begin, set()) # bound_begin might be greater |
| 898 | boundary_table = self.boundary_table |
| 899 | bound_begin = boundary_table.bisect_left(begin) |
| 900 | bound_end = boundary_table.bisect_left(end) # up to, but not including end |
| 901 | result.update(root.search_overlap( |
| 902 | # slice notation is slightly slower |
| 903 | boundary_table.keys()[index] for index in xrange(bound_begin, bound_end) |
| 904 | )) |
| 905 | |
| 906 | # TODO: improve envelop() to use node info instead of less-efficient filtering |
| 907 | result = set( |
| 908 | iv for iv in result |
| 909 | if iv.begin >= begin and iv.end <= end |
| 910 | ) |
| 911 | return result |
| 912 | |
| 913 | def overlap(self, begin, end=None): |
| 914 | """ |