-
Notifications
You must be signed in to change notification settings - Fork 52
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Enhancement #1089: Replace the implemented binary search by a binary search from the standard library #1162
base: main
Are you sure you want to change the base?
Conversation
…by a std::upper_bound search with t8_element_array iterators
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
@Niklas997 Always a treat reading your code! I'm learning new quirks of C++ every time from you. I posted some comments/ideas. Let me know what you think.
…dereference operator return a value_type instead of a reference type
Thank you! That is very nice to hear! And thanks for the input. Now it seems to be a nice substitution for the previously implemented binary search in t8_forest_bin_lower |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I got into the mood for code deletions. Let me know what you think about them.
Moreover, it seems that currently std::upper_bound
falls back to linear search with given iterator.
/* A typedef for the value type of the t8_element_array_t iterator. */ | ||
using element_ptr_t = t8_element_t *; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
/* A typedef for the value type of the t8_element_array_t iterator. */ | |
using element_ptr_t = t8_element_t *; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I think you can save this line by simply using t8_element_array_iterator::value_type
. See comment below.
/* A typedef for the value type of the t8_element_array_t iterator. */ | ||
using element_ptr_t = t8_element_t *; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I think you can save this line by simply using t8_element_array_iterator::value_type
. See comment below.
/* We search for the first element in the array that is greater than the given element id. */ | ||
auto elem_iter | ||
= std::upper_bound (t8_element_array_begin (elements), t8_element_array_end (elements), element_id, | ||
[&maxlevel, &ts] (const t8_linearidx_t element_id_, const element_ptr_t &elem_ptr) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
[&maxlevel, &ts] (const t8_linearidx_t element_id_, const element_ptr_t &elem_ptr) { | |
[&maxlevel, &ts] (const t8_linearidx_t element_id_, const t8_element_array_iterator::value_type &elem_ptr) { |
Describe your changes here:
A bidirectional iterator that wraps the serialized content of a
t8_element_array_t
has been implemented as well as functions providing abegin()
and anend()
iterator to at8_element_array_t.
This allows a convenient usage of algorithms from the standard library like std::lower_bound, etc. on
t8_element_array_t
's.The implemented binary search in
t8_forest_bin_lower
has been replaced by astd::upper_bound
search utilizing the before mentioned iterators providing the same output as the initial implementation.The "discussion" and "help wanted" labels result from the fact, that this is more of a pseudo-iterator since the original data is serialized to char-bytes in the internal sc_array_t and I am not sure if this is the best solution. A complete makover of the t8_element_array_t class would be of course a nicer but more complex solution than the presented approch for closing the issue.
Closes #1089
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 Makefiles
The code is well documented
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
Github action
The code compiles without warning in debugging and release mode, with and without MPI (this should be executed automatically in a github action)
All tests pass (in various configurations, this should be executed automatically in a github action)
If the Pull request introduces code that is not covered by the github action (for example coupling with a new library):
Scripts and Wiki
script/find_all_source_files.scp
to check the indentation of these files.Licence
doc/
(or already has one)