一组非重叠整数范围的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)])