一组非重叠整数范围的Python表示

Question

我想用Python表示一组整数范围,其中可以动态修改集合并测试包含.具体来说,我想将其应用于地址范围或文件中的行号.

我可以定义我关心的地址范围:

200 - 400  
450 - 470  
700 - 900  

然后我希望能够为集合添加一个可能重叠的范围,以便在我添加460 - 490集合时变为:

200 - 400  
450 - 490  
700 - 900  

但是然后能够从我可以排除范围的集合中删除,300 - 350集合变为:

200 - 300
350 - 400  
450 - 490  
700 - 900  

最后,我希望能够遍历集合中包含的所有整数,或者测试集合是否包含特定值.

我想知道最好的方法是什么(特别是如果有内置的Python).

Answer 1

您正在描述间隔树.

pip install intervaltree

用法:

from intervaltree import IntervalTree, Interval
tree = IntervalTree()
tree[200:400] = True  # or you can use ranges as the "values"
tree[450:470] = True
tree[700-900] = True

查询:

>>> tree
IntervalTree([Interval(200, 400, True), Interval(450, 470, True), Interval(700, 900, True)])
>>> tree[250]
{Interval(200, 400, True)}
>>> tree[150]
set()

添加重叠范围:

>>> tree[450:490] = True
>>> tree
IntervalTree([Interval(200, 400, True), Interval(450, 470, True), Interval(450, 490, True), Interval(700, 900, True)])
>>> tree.merge_overlaps()
>>> tree
IntervalTree([Interval(200, 400, True), Interval(450, 490), Interval(700, 900, True)])

丢弃:

>>> tree.chop(300, 350)
>>> tree
IntervalTree([Interval(200, 300, True), Interval(350, 400, True), Interval(450, 490), Interval(700, 900, True)])