// Selection sort algirithm, but at compile time ! /* implemented algorithm: a[n+1] i=0..n-1 min=i j=i+1..n if a[min] > a[j] min=j swap a[min] and a[i] */ #include using std::cout; using std::endl; // Array class, helper that "store" our integers template struct Array{}; // Type class, helper for ::type template struct Type{ using type = T; }; // --- If class on value // declaration template struct If; // specialisation with B == true so value == T template struct If{ const static int value = T; }; // specialisation with B == false so value == V template struct If{ const static int value = V; }; // --- If class on type // declaration template struct IfType; // specialisation with B == true so type == T template struct IfType : Type {}; // specialisation with B == false so type == V template struct IfType : Type {}; // Helper to call IfType<...>::type easily template using If_t = typename IfType::type; // --- EnableIf class, to invalidate a template definition based on a condition // declaration template struct EnableIf; // specialisation with B == true, type is defined template struct EnableIf{ using type = T; }; // helper to call EnableIf<...>::type easily template using EnableIf_t = typename EnableIf::type; // --- Min class // declaration template struct Min; // Single value minimum template struct Min{ const static int value = I; }; // Two value minimum template struct Min : If<(I < J), I, J> {}; // For more than two value minimum, we keep the minimum of the two first and all the other and redo this step until there is only two values template struct Min : Min::value, K...> {}; // --- AllButFirstOccurence class, the first value (or first array) is the value to remove // declaration template struct AllButFirstOccurenceImpl; // - Starting points // Only one value in the list: allowed if it is not the value to remove template struct AllButFirstOccurenceImpl, Array> : EnableIf<(I != J), Array> {}; // More than one value in the list: if the first one is the one to be removed, we remove it then end here, else we go to generic step template struct AllButFirstOccurenceImpl, Array> : If_t< (I == J), Type>, Type, Array, Array>::type> > {}; // - Generic steps // Last value to be checked for: if it is the value to remove, we dump it, else we keep it. In any cases, the recursion ends here template struct AllButFirstOccurenceImpl, Array, Array> : If_t< (I == K), Type>, Type> > {}; // More than one value left to be checked: if the current one is the value to remove, we dump it and ends the recursion here, ekse we keep it and go to the next value template struct AllButFirstOccurenceImpl, Array, Array> : If_t< (I == K), Type>, Type, Array, Array>::type> > {}; // - Helper to make AllButFirstOccurenceImpl calls easier template using AllButFirstOccurence = typename AllButFirstOccurenceImpl, Array>::type; // --- Result class // declaration template struct Result; // "recursion" step, print an integer then call show of the parent class template struct Result : Result{ void show(){ cout << J << ' '; Result::show(); } }; // "recursion stop", print the integer template struct Result{ void show(){ cout << I << endl; } }; // --- Select sort implementation // declaration template struct SelectSortImpl; // - Starting points // Only one element to sort: already sorted template struct SelectSortImpl> : Result {}; // More than one: we select the minimum value and put it in the result, then go to the generic step to store all remaining values template struct SelectSortImpl> : SelectSortImpl< Result::value>, AllButFirstOccurence< Min::value, I... > > {}; // - Generic steps // We sorted all values but one: it is the greatest value so it is sorted template struct SelectSortImpl, Array> : Result {}; // We are currently sorting: we put the minimum of all remaining values, put it in the result and go on with what remains template struct SelectSortImpl, Array> : SelectSortImpl< Result::value>, AllButFirstOccurence< Min::value, J... > > {}; // - Select sort helper so that it is easier for the user to call template struct SelectSort : SelectSortImpl> {}; // --- Test Display class template struct TestDisplay{ static void run(){ cout << "Unsorted array:" << endl << " "; Result().show(); cout << "Sorted:" << endl << " "; SelectSort().show(); cout << endl; } }; int main() { TestDisplay<3, 2, 1>::run(); TestDisplay<1>::run(); TestDisplay<2, 1>::run(); TestDisplay<1, 2, 3, 4>::run(); TestDisplay<1, 3, 2, 5, 7 ,6, -1>::run(); return 0; }

compile time selection sort