From 4bd8f1dba316dca308c1c9282ea36bfaa498357d Mon Sep 17 00:00:00 2001
From: Scott Gasch <scott@gasch.org>
Date: Thu, 15 Dec 2022 15:40:08 -0800
Subject: [PATCH] Update docs again.
---
src/pyutils/collectionz/interval_tree.py | 29 ++++++++++++++++++++----
1 file changed, 24 insertions(+), 5 deletions(-)
diff --git a/src/pyutils/collectionz/interval_tree.py b/src/pyutils/collectionz/interval_tree.py
index 92c975d..d4b33cb 100644
--- a/src/pyutils/collectionz/interval_tree.py
+++ b/src/pyutils/collectionz/interval_tree.py
@@ -73,9 +73,16 @@ class AugmentedIntervalTree(bst.BinarySearchTree):
new_highest_candidates.append(parent.right.value.highest_in_subtree)
parent.value.highest_in_subtree = max(new_highest_candidates)
- def find_one_overlap(self, x: NumericRange):
+ def find_one_overlap(self, to_find: NumericRange) -> Optional[NumericRange]:
"""Identify and return one overlapping node from the tree.
+ Args:
+ to_find: the interval with which to find an overlap.
+
+ Returns:
+ An overlapping range from the tree or None if no such
+ ranges exist in the tree at present.
+
>>> tree = AugmentedIntervalTree()
>>> tree.insert(NumericRange(20, 24))
>>> tree.insert(NumericRange(18, 22))
@@ -90,8 +97,9 @@ class AugmentedIntervalTree(bst.BinarySearchTree):
>>> tree.insert(NumericRange(21, 27))
>>> tree.find_one_overlap(NumericRange(6, 7))
1..30
+
"""
- return self._find_one_overlap(self.root, x)
+ return self._find_one_overlap(self.root, to_find)
def _find_one_overlap(
self, root: bst.Node, x: NumericRange
@@ -110,8 +118,18 @@ class AugmentedIntervalTree(bst.BinarySearchTree):
return self._find_one_overlap(root.right, x)
return None
- def find_all_overlaps(self, x: NumericRange):
- """Yields ranges previously added to the tree that x overlaps with.
+ def find_all_overlaps(
+ self, to_find: NumericRange
+ ) -> Generator[NumericRange, None, None]:
+ """Yields ranges previously added to the tree that overlaps with
+ to_find argument.
+
+ Args:
+ to_find: the interval with which to find all overlaps.
+
+ Returns:
+ A (potentially empty) sequence of all ranges in the tree
+ that overlap with the argument.
>>> tree = AugmentedIntervalTree()
>>> tree.insert(NumericRange(20, 24))
@@ -140,10 +158,11 @@ class AugmentedIntervalTree(bst.BinarySearchTree):
18..22
16..28
21..27
+
"""
if self.root is None:
return
- yield from self._find_all_overlaps(self.root, x)
+ yield from self._find_all_overlaps(self.root, to_find)
def _find_all_overlaps(
self, root: bst.Node, x: NumericRange
--
2.49.0