From 4bd8f1dba316dca308c1c9282ea36bfaa498357d Mon Sep 17 00:00:00 2001 From: Scott Gasch 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.45.2