t8_element_array_sort

[lukasdreyer]

Feature request

t8_element_array_sort functionality (ideally based on standard library)

Is your feature request related to a problem? Please describe.
I'd like to implement a version of the balance algorithm based on global sort (https://ieeexplore.ieee.org/abstract/document/9355233).
For this, i need a local balance extension, for which in one step I need to create all neighbors of my current elements, and finally want to have them ordered without duplicates.

To this end, it would be really nice to have t8_element_array_sort functionality, so I could just throw all neighbors in an array, and sort and remove duplicates later.

I tried to implement this myself, but both C qsort (from sc_array_sort) as well as C++ std::sort lead to problems.
For std::sort, we do not have the type of the elements available. For qsort, only a function depending on both elements is passed, and we do not have the context scheme available needed to actually compare elements.

Describe the solution or feature you'd like
An implementation of t8_element_array_sort, ideally not written manually, but using standard library implementations.

Describe alternatives you've considered
There seems to be a qsort_r variant not in the standard supporting context, but as it is not in the standard, i am not sure if it is the right approach, especially as different operating systems seem to use different parameter orders.

All my other alternatives were based on more complicated c++ standard library constructs, so if sort does not work, these will neither.

Estimated priority
"Priority: medium" Should be solved within half a year

[Davknapp]

Have you tried using a t8_element_array_iterator? It is a random access iterator which should be enough to use it.

[Davknapp]

Ok, I have looked more into your problem and I think I understand it now. You are right, the problem is that the type of the element is not known, as we return a raw pointer coming from the sc_array when we use the * operator.

A "standart" approach to the problem is to return a "Proxy Object", that is a struct that pretends to be a pointer but internally handles the writing of the data. If we use that as the reference for the iterator we should be able to solve your problem.

The major drawback will be that C++-type reductions will return surprising results:
auto ptr = *element_iterator will be a proxy object instead of a t8_element_t*.
An implicit conversion will work though.

The implementations that I have seen so far all rely on a memcpy, instead of swapping pointers, resulting in a performance overhead.
Maybe further research will show a way around this performance overhead.

We will discuss it internally how we will progress.