Repository navigation
Redundant branch checks #56
Description
Looks like there are some redundant subtree checks. Consider this part of overlap_find_all_i() for instance:
interval-tree/include/interval-tree/interval_tree.hpp
Lines 1885 to 1903 in 9870f34
| if (ptr->left_ && ptr->left_->max() >= ival.low()) | |
| { | |
| // no right? can only continue left | |
| // or interval low is bigger than max of right branch. | |
| if (!ptr->right_ || ival.low() > ptr->right_->max()) | |
| return overlap_find_all_i<ThisType, Exclusive, IteratorT>(self, ptr->left_, ival, on_find); | |
| if (!overlap_find_all_i<ThisType, Exclusive, IteratorT>(self, ptr->left_, ival, on_find)) | |
| return false; | |
| } | |
| if (ptr->right_ && ptr->right_->max() >= ival.low()) | |
| { | |
| if (!ptr->left_ || ival.low() > ptr->right_->max()) | |
| return overlap_find_all_i<ThisType, Exclusive, IteratorT>(self, ptr->right_, ival, on_find); | |
| if (!overlap_find_all_i<ThisType, Exclusive, IteratorT>(self, ptr->right_, ival, on_find)) | |
| return false; | |
| } | |
| return true; |
First, the last 4 lines are just
if (!someFunc())
return false;
return true;which is the same as return someFunc().
Then right subtree check becomes
if (ptr->right_ && ptr->right_->max() >= ival.low())
{
if (!ptr->left_ || ival.low() > ptr->right_->max())
return overlap_find_all_i<ThisType, Exclusive, IteratorT>(self, ptr->right_, ival, on_find);
return overlap_find_all_i<ThisType, Exclusive, IteratorT>(self, ptr->right_, ival, on_find);
}Notice that both branches of the inner if are the same. Regardless of whether the condition is true or false, the function call will be exactly the same. By the way, that's why copy-paste mistake in its condition (the left node is checked for nullptr, but max() of the right subtree is used after ||) doesn't affect the logic. So the right branch check becomes just
if (ptr->right_ && ptr->right_->max() >= ival.low())
{
return overlap_find_all_i<ThisType, Exclusive, IteratorT>(self, ptr->right_, ival, on_find);
}Finally, the left branch check has exactly the same condition for the right one (in line 1889), so if the right node is present, the same condition is checked twice. In the end, this whole fragment becomes
if (ptr->left_ && ptr->left_->max() >= ival.low())
{
if (!overlap_find_all_i<ThisType, Exclusive, IteratorT>(self, ptr->left_, ival, on_find))
return false;
}
if (ptr->right_ && ptr->right_->max() >= ival.low())
{
return overlap_find_all_i<ThisType, Exclusive, IteratorT>(self, ptr->right_, ival, on_find);
}
return true;This version is more readable and expresses the intention more clearly:
- Check the left subtree (if present and eligible).
- If found/should stop, return.
- Check the right subtree (if present and eligible).
Same applies to a few other places.
Activity
odorovskoy commentedon Aug 27, 2025
Corresponding PR is #57.
Ran the tests, all pass.
5cript commentedon Aug 27, 2025
Thank you very much for this improvement, I will review this at a later date within this week.
EDIT: My eyes almost fell out when I saw this. I wonder if this was copy paste or an all nighter result :O . I want to be thorough with this.
5cript commentedon Aug 29, 2025
I have reviewed the changes and tested them, I will also add 2 more tests in a subsequent PR.