[OT] Lower and upper median of 4

[Timon Gehr via Digitalmars-d]

On 26.11.2016 23:16, Timon Gehr wrote:
> On 26.11.2016 22:36, Timon Gehr wrote:
>>>>
>>>
>>> Thanks! Sorry, I forgot to mention partitioning around the lower/upper
>>> median is also needed. It seems that changes the tradeoff space. --
>>> Andrei
>>
>> Did you see the suggestion to make the leanLeft/leanRight cases
>> symmetric, such that both use at most 4 branches?
>
> Code:
>
> void medianOf(bool leanRight,T)(ref T[4] r, size_t a, size_t b, size_t
> c, size_t d){
>     assert(a!=b&&a!=c&&a!=d&&b!=c&&b!=d&&c!=d);
>     if(r[c]<r[a]) swap(r[a],r[c]);
>     if(r[d]<r[b]) swap(r[b],r[d]);
>     if(leanRight?r[d]<r[c]:r[b]<r[a]){
>         swap(r[c],r[d]);
>         swap(r[a],r[b]);
>     }
>     if(r[c]<r[b]) swap(r[b],r[c]);
>     if(leanRight) assert(r[a]<=r[c]&&r[b]<=r[c]&&r[c]<=r[d]);
>     else assert(r[a]<=r[b]&&r[b]<=r[c]&&r[b]<=r[d]);
> }
>

Slightly larger code, but uses fewer swaps:

void medianOf(bool leanRight,T)(ref T[4] r, size_t a, size_t b, size_t 
c, size_t d){
     assert(a!=b&&a!=c&&a!=d&&b!=c&&b!=d&&c!=d);
     if(r[c]<r[a]) swap(r[a],r[c]);
     if(r[d]<r[b]) swap(r[b],r[d]);
     static if(leanRight){
         if(r[d]<r[c]){
             swap(r[c],r[d]);
             if(r[c]<r[a]) swap(r[a],r[c]);
         }else if(r[c]<r[b]) swap(r[b],r[c]);
         assert(r[a]<=r[c]&&r[b]<=r[c]&&r[c]<=r[d]);
     }else{
         if(r[b]<r[a]){
             swap(r[a],r[b]);
             if(r[d]<r[b]) swap(r[b],r[d]);
         }else if(r[c]<r[b]) swap(r[b],r[c]);
         assert(r[a]<=r[b]&&r[b]<=r[c]&&r[b]<=r[d]);
     }
}

The best strategy is probably to exhaustively enumerate all 
Pareto-optimal algorithms and to benchmark them automatically within the 
larger algorithm.