Feature: Ancestor search

[holke]

Closes #1715

Describe your changes here:

Currently waiting for https://github.com/DLR-AMR/t8code/pull/1640 to merge. Will add a description afterwards.

All these boxes must be checked by the AUTHOR before requesting review:

• [x] The PR is small enough to be reviewed easily. If not, consider splitting up the changes in multiple PRs.
• [x] The title starts with one of the following prefixes: Documentation:, Bugfix:, Feature:, Improvement: or Other:.
• [x] If the PR is related to an issue, make sure to link it.
• [x] The author made sure that, as a reviewer, he/she would check all boxes below.

All these boxes must be checked by the REVIEWERS before merging the pull request:

As a reviewer please read through all the code lines and make sure that the code is fully understood, bug free, well-documented and well-structured.

General

• [ ] The reviewer executed the new code features at least once and checked the results manually.
• [ ] The code follows the t8code coding guidelines.
• [ ] New source/header files are properly added to the CMake files.
• [ ] The code is well documented. In particular, all function declarations, structs/classes and their members have a proper doxygen documentation.
• [ ] All new algorithms and data structures are sufficiently optimal in terms of memory and runtime (If this should be merged, but there is still potential for optimization, create a new issue).

Tests

• [ ] The code is covered in an existing or new test case using Google Test.
• [ ] The code coverage of the project (reported in the CI) should not decrease. If coverage is decreased, make sure that this is reasonable and acceptable.
• [ ] Valgrind doesn't find any bugs in the new code. This script can be used to check for errors; see also this wiki article.

If the Pull request introduces code that is not covered by the github action (for example coupling with a new library):

• [ ] Should this use case be added to the github action?
• [ ] If not, does the specific use case compile and all tests pass (check manually).

Scripts and Wiki

• [ ] If a new directory with source files is added, it must be covered by the script/find_all_source_files.scp to check the indentation of these files.
• [ ] If this PR introduces a new feature, it must be covered in an example or tutorial and a Wiki article.

License

• [ ] The author added a BSD statement to doc/ (or already has one).

[codecov[bot]]

Codecov Report

:x: Patch coverage is 42.42424% with 38 lines in your changes missing coverage. Please review. :white_check_mark: Project coverage is 74.00%. Comparing base (d06d4ee) to head (9361571). :warning: Report is 705 commits behind head on main.

Files with missing lines	Patch %	Lines
src/t8_forest/t8_forest_private.cxx	0.00%	36 Missing :warning:
...t8_default/t8_default_common/t8_default_common.hxx	90.00%	1 Missing :warning:
...mes/t8_standalone/t8_standalone_implementation.hxx	92.85%	1 Missing :warning:

Additional details and impacted files

@@            Coverage Diff             @@
##             main    #1714      +/-   ##
==========================================
- Coverage   74.13%   74.00%   -0.13%     
==========================================
  Files          99       99              
  Lines       18682    18749      +67     
==========================================
+ Hits        13849    13876      +27     
- Misses       4833     4873      +40     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

:rocket: New features to boost your workflow:

• :snowflake: Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[holke]

i now moved the implementation of is_ancestor into the scheme interface. However, due to the current structure i needed to add the "default" version to the common scheme. But this only applies to the default scheme now, the standalone scheme does not use the common scheme.

I currently added a non-implementation, i.e. SC_ABORT to the standalone scheme. I do not think we should merge it like this, but discuss whether we either

a) want to use the same implementation for standalone, this would require a construction like an intermediate "generalized" scheme from which the common and the standalone inherit b) implement an optimized version in the standalone scheme

We should discuss this in our next dev meeting with @lukasdreyer

imho there is no urgency in merging this yet.

[lukasdreyer]

i now moved the implementation of is_ancestor into the scheme interface. However, due to the current structure i needed to add the "default" version to the common scheme. But this only applies to the default scheme now, the standalone scheme does not use the common scheme.

I currently added a non-implementation, i.e. SC_ABORT to the standalone scheme. I do not think we should merge it like this, but discuss whether we either

a) want to use the same implementation for standalone, this would require a construction like an intermediate "generalized" scheme from which the common and the standalone inherit b) implement an optimized version in the standalone scheme

We should discuss this in our next dev meeting with @lukasdreyer

imho there is no urgency in merging this yet.

As the standalone scheme already has an implementation for ancestor, that is just not put through to the general interface, I would prefer for the standalone scheme to use a combination of get_ancestor and is_equal. (Or even better adjusting the functionality from the ancestor computation and checking early.)

[holke]

TODO: @lukasdreyer suggested an is_equal(get_ancestor) implementation for the standalone scheme.

[holke]

I added an implementation for the standalone scheme and a test. @Davknapp you could check with @lukasdreyer whether he wants to have a look at this implementation before merging.

[holke]

@Davknapp please have a look at this again.