// we all (or a lot of us) know the bubble sort algotithm // but what of it at compile time ? /* implemented algorithm: a[n + 1] i=0..n j=i..n-1 if a[j] > a[j+1] swap a[j] and a[j+1] */ #include using std::cout; using std::endl; // Array class, helper that "store" our integers template struct Array{}; // --- If class // 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; }; // --- Min and Max classes // Get the minimum value between two integer using If template struct Min{ const static int value = If<(I < J), I, J>::value; }; // Get the maximum value between two integer using If template struct Max{ const static int value = If<(I < J), J, I>::value; }; // --- 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; } }; // --- --- Bubble sort class true implementation // declaration template struct BubbleSortImpl; // --- Starting point: only Array<...> // Case with only one value template struct BubbleSortImpl> : Result{}; // Case with only two value template struct BubbleSortImpl> : Result::value, Max::value>{}; // Case with only one value, starting point of the recursion template struct BubbleSortImpl> : BubbleSortImpl< Array::value>, Array::value, K...> > {}; // --- First iteration through the list, the result list is empty // Case with a second array with. only two values, we add the maximum of those two to the result and add back the minimum of those two values to the first array template struct BubbleSortImpl, Array> : BubbleSortImpl< Result::value>, Array::value> > {}; // Case where the second array still has mote than two values, we add the minimum value between the two first values of the second array to the end of the first one, then keep iterating template struct BubbleSortImpl, Array> : BubbleSortImpl< Array::value>, Array::value, L...> > {}; // --- All iterations through the list but the first, the result list has at least one value // case were the second array only has two values, we store the max at the beginning of the result array and the minimum at the end of the first array and go on template struct BubbleSortImpl, Array, Array> : BubbleSortImpl< Result::value, I...>, Array::value> > {}; // Case where the second array has more than two values, we store the minimum of the two first values at the end of the first array and go on template struct BubbleSortImpl, Array, Array> : BubbleSortImpl< Result, Array::value>, Array::value, M...> > {}; // Case where the second arrays is empty and the first array has more than two values, we only keep the minimum value of those two in the first array and add all the others to the second array template struct BubbleSortImpl, Array> : BubbleSortImpl< Result, Array::value>, Array::value, L...> > {}; // Case where the second arrays is empty and the first array has two values, we add the minimum and the maximum of those two values in the right order at the beginning of the result array and end the recursion template struct BubbleSortImpl, Array> : Result::value, Max::value, I...> {}; // --- Bubble sort class used by the user // it simplifies the call to BubbleSortImpl for the user template struct BubbleSort : BubbleSortImpl>{}; // --- Test Display class template struct TestDisplay{ static void run(){ cout << "Unsorted array:" << endl << " "; Result().show(); cout << "Sorted:" << endl << " "; BubbleSort().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 bubble sort