区間木

仕事で区間木（interval tree）を使うことになったので，Pythonのモジュールを探したところ，以下のモジュールがあった．

https://github.com/chaimleib/intervaltree

簡単に解説しておく．

インストールはpipで行う．

pip install intervaltree

Python 2.6+ もしくはPython 3.2+で動作する．以下では Python3系を仮定する．

IntervalTreeクラスが準備されているので，以下のように空の区間木インスタンスを生成する．

from intervaltree import Interval, IntervalTree

tree = IntervalTree()

データを挿入は，以下の何れかの形式で行う．

tree[begin:end] = data

tree.add(interval)

tree.addi(begin, end, data)

削除は以下の何れかを用いる．

tree.remove(interval) (raises ValueError if not present)

tree.discard(interval) (quiet if not present)

tree.removei(begin, end, data) (short for tree.remove(Interval(begin, end, data)))

tree.discardi(begin, end, data) (short for tree.discard(Interval(begin, end, data)))

tree.remove_overlap(point)

tree.remove_overlap(begin, end) (removes all overlapping the range)

tree.remove_envelop(begin, end) (removes all enveloped in the range)

区間もしくは点と重なりをもつ区間の列挙は，以下のように行う．

tree[point]

tree[begin:end]

反復は，

for interval_obj in tree:

で行い．要素数は

len(tree)

で確認できる．集合としての操作も union，difference，intersection,

symmetric difference, issubsetなどが準備されている．

要素からなる集合はset(tree)でリストはlist(tree) で得ることができる．