import typing
NodeType = typing.Union[None, 'FileTree']
[docs]
class FileTree:
"""
Construct a FileTree node
Parameters
----------
low
First frame contained in this file
high
First index of the next file
value
The corresponding file object
idx
The index of the file object in the fileset
left
Nodes with a lower low
right
Nodes with a higher low
"""
def __init__(self, low: int, high: int, value: typing.Any, idx: int,
left: NodeType, right: NodeType):
if low >= high:
raise ValueError("low should be < high")
self.low = low
self.high = high
self.value = value
self.idx = idx
self.left = left
self.right = right
[docs]
@classmethod
def make(cls, files):
"""
build a balanced binary tree by bisecting the files list
"""
def _make(files):
if len(files) == 0:
return None
mid = len(files) // 2
idx, value = files[mid]
return FileTree(
low=value.start_idx,
high=value.end_idx,
value=value,
idx=idx,
left=_make(files[:mid]),
right=_make(files[mid + 1:]),
)
return _make(list(enumerate(files)))
[docs]
def search_start(self, value):
"""
search a node that has start_idx <= value && end_idx > value
"""
if self.low <= value and self.high > value:
return self.idx, self.value
elif self.low > value:
return self.left.search_start(value)
else:
return self.right.search_start(value)
def __str__(self):
return self.to_string()
[docs]
def to_string(self, depth=0):
padsingle = 4 * ' '
pad = (depth * padsingle)
str_left = (self.left is not None and self.left.to_string(depth + 1) or 'None')
str_right = (self.right is not None and self.right.to_string(depth + 1) or 'None')
str_self = f"(d={depth} l={self.low}, i={self.idx}, h={self.high})"
return f"{pad}{str_left}\n{pad}{str_self}\n{pad}{str_right}"