// quick sort algorithm at compilation time /* implemented algorithm: a[n] if n <= 1 return a else b=[] c=[] i=1..n-1 if a[i] > a[0] c += [a[i]] else b += [a[i]] return quicksort(b[i]) + [a[0]] + quicksort(c[i]) */ #include using std::cout; using std::endl; // Type class, helper for ::type template struct Type{ using type = T; }; // --- 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; // --- boolean value to store a boolean in a class at compile time template struct BoolValue{ static const bool value = V; }; // --- Result class // declaration template struct Result; // "recursion" step, print an integer then call show of the parent class template struct Result : Result{ static void show(){ cout << J << ' '; Result::show(); } }; // "recursion stop", print the integer template struct Result{ static void show(){ cout << I << endl; } }; // Array class, helper that "store" our integers template struct Array{}; // --- Array cast to result // declaration template struct ArrayToResult; // definition with a single array as template parameter template struct ArrayToResult> : Result {}; // --- merge class //declaration template struct Merge; // Case with two arrays template struct Merge, Array> : Type> {}; // Case with three arrays template struct Merge, Array, Array> : Type> {}; // Helper to simplify call to Merge<...>::type template using Merge_t = typename Merge::type; // --- Has strictly lower (first array contains the value to be checked and the second is the array to be processed) // declaration template struct HasStrictlyLower; // case when second array has only one value: end point of the search template struct HasStrictlyLower, Array> : BoolValue<(I > J)> {}; // case where the second array has more than one value: if the comparison between the value of the first array and the first value of the second array is true, we end the search here, else we go on template struct HasStrictlyLower, Array> : If_t< (I > J), BoolValue, HasStrictlyLower, Array> > {}; // --- Has greater or equal (first array contains the value to be checked and the second is the array to be processed) // declaration template struct HasGreaterOrEqual; // case when second array has only one value: end point of the search template struct HasGreaterOrEqual, Array> : BoolValue<(I <= J)> {}; // case where the second array has more than one value: if the comparison between the value of the first array and the first value of the second array is true, we end the search here, else we go on template struct HasGreaterOrEqual, Array> : If_t< (I <= J), BoolValue, HasGreaterOrEqual, Array> > {}; // --- All strictly lower (first array contains the value to be checked and the second is the array to be processed) // declaration template struct AllStrictlyLower; // helper to call AllStrictlyLower<...>::type template using AllStrictlyLower_t = typename AllStrictlyLower::type; // start and end step when there is only one value left to compare, we keep it anyway template struct AllStrictlyLower, Array> : Type> {}; // step when we still didn't find a correct value, if the current value match the comparison, we keep it and go to the next step, else we leave it and redo this step without it template struct AllStrictlyLower, Array> : If_t< (I > J), AllStrictlyLower, Array, Array>, AllStrictlyLower, Array> > {}; // end step where we already have values. If the last value match the comparison, we keep it else we leave it template struct AllStrictlyLower, Array, Array> : IfType< (I > K), Array, Array > {}; // generic step where we already have values. If the last value match the comparison, we keep it else we leave it. In both case, we do this step again template struct AllStrictlyLower, Array, Array> : If_t< (I > K), AllStrictlyLower, Array, Array>, AllStrictlyLower, Array, Array> > {}; // --- All greater or equal (first array contains the value to be checked and the second is the array to be processed) // declaration template struct AllGreaterOrEqual; // helper to call AllGreaterOrEqual<...>::type template using AllGreaterOrEqual_t = typename AllGreaterOrEqual::type; // start and end step when there is only one value left to compare, we keep it anyway template struct AllGreaterOrEqual, Array> : Type> {}; // step when we still didn't find a correct value, if the current value match the comparison, we keep it and go to the next step, else we leave it and redo this step without it template struct AllGreaterOrEqual, Array> : If_t< (I <= J), AllGreaterOrEqual, Array, Array>, AllGreaterOrEqual, Array> > {}; // end step where we already have values. If the last value match the comparison, we keep it else we leave it template struct AllGreaterOrEqual, Array, Array> : IfType< (I <= K), Array, Array > {}; // generic step where we already have values. If the last value match the comparison, we keep it else we leave it. In both case, we do this step again template struct AllGreaterOrEqual, Array, Array> : If_t< (I <= K), AllGreaterOrEqual, Array, Array>, AllGreaterOrEqual, Array, Array> > {}; // --- QuickSort implementation // declaration template struct QuickSortImpl; // helper to call QuickSortImpl<...>::type template using QuickSortImpl_t = typename QuickSortImpl::type; // helper to call <1, 2, ...> instead of > template using QuickSort = ArrayToResult>>; // end step with an array of size 1: already sorted template struct QuickSortImpl> : Type> {}; /* generic step We do: QuickSort => Array< quick sort of AllStrictlyLower than I from ... if any I quick sort of AllGreaterOrEqual than I from ... if any > */ template struct QuickSortImpl> : If_t< HasStrictlyLower, Array>::value, If_t< HasGreaterOrEqual, Array>::value, Merge< QuickSortImpl_t< AllStrictlyLower_t< Array, Array > >, Array, QuickSortImpl_t< AllGreaterOrEqual_t< Array, Array > > >, Merge< QuickSortImpl_t< AllStrictlyLower_t< Array, Array > >, Array > >, If_t< HasGreaterOrEqual, Array>::value, Merge< Array, QuickSortImpl_t< AllGreaterOrEqual_t< Array, Array > > >, Type> > > {}; // --- Test Display class template struct TestDisplay{ static void run(){ cout << "Unsorted array:" << endl << " "; Result::show(); cout << "Sorted:" << endl << " "; QuickSort::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 quick sort