Bubble sort with CPP template metaprogramming — Part 4

Photo by Drew Beamer on Unsplash

So, in previous parts, we started with a complete bubble sort in template metaprogramming and then I made two reworks. First explaining in detail how I approached the for loop issue and than actually doing it, covering a pitfall of the template syntax. In this last (?) part I will first do another quick rework and then present the entire solution again, in it’s new form.

Second refactoring — the if statement

As this is our second time, I’ll do it briefly. So first, analyzing the if statement

if (condition)
  state = if_true_operation(state);
else
  state = if_false_operation(state);

In the bubble sort implementation shown, there’s an if statement — the items in adjacent locations are swapped, given the former is greater than the latter. The original code is this (not showing the swap itself)

template <int index1, int index2, bool gt, class T>
struct IntVec_ConditionalSwap;

template <int index1, int index2, class T>
struct IntVec_ConditionalSwap<index1, index2, true, T>
{
 typedef typename IntVec_Swap<index1, index2, T>::type type;
};

template <int index1, int index2, class T>
struct IntVec_ConditionalSwap<index1, index2, false, T>
{
 typedef T type;
};

The “else” is empty, nothing is done. More specifically, the state is preserved. So a more generic (get it?) construct would be

template <bool condition, class current_state, template<class> class IfTrue, template<class> class IfFalse>
struct IfElseStatement;

template <class current_state, template<class> class IfTrue, template<class> class IfFalse>
struct IfElseStatement<true, current_state, IfTrue, IfFalse>
{
 typedef typename IfTrue<current_state>::state state;
};

template <class current_state, template<class> class IfTrue, template<class> class IfFalse>
struct IfElseStatement<false, current_state, IfTrue, IfFalse>
{
 typedef typename IfFalse<current_state>::state state;
};

// Theis will serve use when it's just an if, and no else.
template <class current_state>
struct IdentityOperator
{
 typedef typename current_state state;
};

Just as in the for loop case, the state type is the one subject to change, and template template parameters are used. We’re now ready to go to the reworked solution.

Conventions

Before the dive, let’s agree on notation

• template types — CamelCase
• template parameters and public members— lower_case
• template template parameters (a.k.a operators) — CamelCase
• free choice when it comes to local types, but mostly — _lower_case

Basic types

Not a must but just makes smoother code later

template<int i>
struct Int
{
 static constexpr int value = i;
};

template<bool b>
struct Bool
{
 static constexpr bool value = b;
};

Flow control statements

• IfElse
• ForLoop
• IdentityOperator — to be used as a default when no operation is needed. For example, for the else part of an IfElse statement, when it’s empty.

So, here’s the IfElse

template <bool condition, class current_state, template<class> class IfTrue, template<class> class IfFalse>
struct IfElseStatement;

template <class current_state, template<class> class IfTrue, template<class> class IfFalse>
struct IfElseStatement<true, current_state, IfTrue, IfFalse>
{
 typedef typename IfTrue<current_state>::state state;
};

template <class current_state, template<class> class IfTrue, template<class> class IfFalse>
struct IfElseStatement<false, current_state, IfTrue, IfFalse>
{
 typedef typename IfFalse<current_state>::state state;
};

template <class current_state>
struct IdentityOperator
{
 typedef typename current_state state;
};

and the ForLoop

template <int current_index, int max_index, class current_state, template<int, class> class Iteration>
struct ForLoop
{
 typedef typename Iteration<current_index, current_state>::state next_state;
 typedef typename ForLoop<current_index + 1, max_index, next_state, Iteration>::state state;
};

template <int max_index, class current_state, template<int, class> class Iteration>
struct ForLoop<max_index, max_index, current_state, Iteration>
{
 typedef typename current_state state;
};

The vector of integer values

IntVec represents the vector of integers. It holds the values in recursive way. The first member holds the first value, while the rest member holds another IntVec has some basic API

• IntVec_Size — returning the size
• IntVec_ToString — for debug, this is actually running in runtime, and generates an std::string showing the values in the vector
• IntVec_Set, IntVec_Get — obvious utilities
• IntVec_Swap — actually swapping two elements in the vector. Implemented in terms of the get and set utilities

template <int i, class int_vec = nullptr_t>
struct IntVec
{
 using first = Int<i>;
 using rest  = int_vec;
};

template <class int_vec>
class IntVec_Size
{
 typedef typename int_vec::rest _rest;

public:
 static constexpr int value = 1 + IntVec_Size<_rest>::value;
};

template <>
class IntVec_Size<nullptr_t>
{
public:
 static constexpr int value = 0;
};

template <class int_vec>
class IntVec_ToString
{
 typedef typename int_vec::first TFirst;
 typedef typename int_vec::rest TRest;

public:
 static std::string to_string() { return std::to_string(TFirst::value) + ", " + IntVec_ToString<TRest>::to_string(); }
};

template <>
class IntVec_ToString<nullptr_t>
{
public:
 static std::string to_string() { return ""; }
};

template <int index, class int_vec>
class IntVec_Get
{
 typedef typename int_vec::rest _rest;

public:
 typedef typename IntVec_Get<index - 1, _rest>::type type;
};

template <class int_vec>
class IntVec_Get<0, int_vec>
{
public:
 typedef typename int_vec::first type;
};

template <int index, int i, class int_vec>
class IntVec_Set
{
 typedef typename int_vec::first _first;
 typedef typename int_vec::rest _rest;
 typedef typename IntVec_Set<index - 1, i, _rest>::type _restSet;
 
public:
 typedef IntVec<_first::value, _restSet> type;
};

template <int i, class int_vec>
class IntVec_Set<0, i, int_vec>
{
 typedef typename int_vec::rest _rest;

public:
 typedef IntVec<i, _rest> type;
};

template <int index1, int index2, class int_vec>
class IntVec_Swap
{
 typedef typename IntVec_Get<index1, int_vec>::type _int1_type;
 typedef typename IntVec_Get<index2, int_vec>::type _int2_type;
 typedef typename IntVec_Set<index1, _int2_type::value, int_vec>::type _int_vec_set1;

public:
 typedef typename IntVec_Set<index2, _int1_type::value, _int_vec_set1>::type type;
};

Now, for the main course — the algorithm

The internal iteration operator — BubbleIterator

1. Getting the two elements at two adjacent locations
2. Comparing them to compute the condition
3. The _iteration_state defines the iterator state — both the index to work at, and the current IntVec vector
4. _IfTrue — what to do when the condition holds
5. An IfElse statement. In case the condition doesn’t hold, the IdentityOperator is given, preserving the state as it is.
6. Extract the IntVec from the iterator state, thus the external context is satisfied with the IntVec alone.

template <int index, class int_vec>
class BubbleIterator
{
 typedef typename IntVec_Get<index,   int_vec>::type _int1_type;
 typedef typename IntVec_Get<index+1, int_vec>::type _int2_type;
 static constexpr bool should_swap = _int1_type::value > _int2_type::value;

 template<int index, class int_vec>
 struct _iteration_state
 {
  typedef Int<index> _index;
  typedef int_vec    _int_vec;
 };
 
 template <class current_state>
 class _IfTrue
 {
  typedef typename current_state::_index _index;
  typedef typename current_state::_int_vec _int_vec;
  typedef typename IntVec_Swap<_index::value, _index::value + 1, _int_vec>::type _new_int_vec;
  
 public:
  typedef typename _iteration_state<_index::value, _new_int_vec> state;
 };

 typedef typename IfElseStatement<
      should_swap,
      _iteration_state<index, int_vec>,
      _IfTrue,
      IdentityOperator>::state _state;

public:
 typedef typename _state::_int_vec state;
};

Note that _iteration_state has an int_vec which “hides” the BubbleIterator int_vec, but the scoping rules are working for us here.

Having done all that, the algorithm writes itself — just run a for loop, running an iteration, that in turn runs the previous iterator in a nested for loop

template <class int_vec>
struct BubbleSort
{
 template <int index, class int_vec>
 struct _iterator
 {
  typedef typename ForLoop<0, IntVec_Size<int_vec>::value - 1, int_vec, BubbleIterator>::state state;
 };

 typedef typename ForLoop<0, IntVec_Size<int_vec>::value - 1, int_vec, _iterator>::state type;
};

For deserts, a function to check if the vector is indeed sorted

1. _iteration_state — containing the maintained boolean sort state and the vector
2. _iterator — iterator to work on the list and update the boolean
3. Call to the for loop with the iterator
4. Extract the value of the computed boolean

template <class int_vec>
class CheckSorted
{
 template<bool b, class int_vec>
 struct _iteration_state
 {
  typedef Bool<b> _is_sorted;
  typedef int_vec _int_vec;
 };

 template<int index, class current_state>
 struct _iterator
 {
  typedef typename current_state::_int_vec   _int_vec;
  typedef typename current_state::_is_sorted _is_sorted;

  typedef typename IntVec_Get<index, _int_vec>::type _int1_type;
  typedef typename IntVec_Get<index + 1, _int_vec>::type _int2_type;

  typedef _iteration_state<(_int1_type::value <= _int2_type::value) && _is_sorted::value, _int_vec> state;
 };

 typedef typename ForLoop<0, IntVec_Size<int_vec>::value - 1, _iteration_state<true, int_vec>, _iterator>::state _state;

public:
 static constexpr bool value = _state::_is_sorted::value;
};

The demo program

That has not changed a bit

int main(int argc, char* argv[])
{
#define print_vec(__vec) \
 std::cout << std::setw(10) << #__vec\
  << " (size " << IntVec_Size<__vec>::value << ", "\
  << " sorted " << (CheckSorted<__vec>::value ? "Yes!" : "Nooo") << ") = "\
  << IntVec_ToString<__vec>::to_string() << "\n";

 {
  std::cout << "\n1st sample - random\n";
  using myList = IntVec<1, IntVec<-2, IntVec<13, IntVec <400, IntVec<5>>>>>;
  using mySorted = BubbleSort<myList>::type;
  print_vec(myList);
  print_vec(mySorted);
 }

 {
  std::cout << "\n2nd sample - reverse\n";
  using myList = IntVec<1, IntVec<-2, IntVec<-3, IntVec <-4, IntVec<-5, IntVec<-6>>>>>>;
  using mySorted = BubbleSort<myList>::type;
  print_vec(myList);
  print_vec(mySorted);
 }

 {
  std::cout << "\n3rd sample - reverse but 1\n";
  using myList = IntVec<-1, IntVec<-2, IntVec<-3, IntVec <-4, IntVec<-5, IntVec<6>>>>>>;
  using mySorted = BubbleSort<myList>::type;
  print_vec(myList);
  print_vec(mySorted);
 }

 {
  std::cout << "\n4th sample - already sorted\n";
  using myList = IntVec<1, IntVec<2, IntVec<3, IntVec <4, IntVec<5, IntVec<6>>>>>>;
  using mySorted = BubbleSort<myList>::type;
  print_vec(myList);
  print_vec(mySorted);
 }

 {
  std::cout << "\n5th sample - sorted but 1\n";
  using myList = IntVec<1, IntVec<2, IntVec<3, IntVec <4, IntVec<-6, IntVec<5>>>>>>;
  using mySorted = BubbleSort<myList>::type;
  print_vec(myList);
  print_vec(mySorted);
 }

 {
  std::cout << "\n6th sample - repeats\n";
  using myList = IntVec<1, IntVec<2, IntVec<3, IntVec <3, IntVec<2, IntVec<1>>>>>>;
  using mySorted = BubbleSort<myList>::type;
  print_vec(myList);
  print_vec(mySorted);
 }

 return 0;
}

The output

1st sample - random
    myList (size 5,  sorted Nooo) = 1, -2, 13, 400, 5,
  mySorted (size 5,  sorted Yes!) = -2, 1, 5, 13, 400,

2nd sample - reverse
    myList (size 6,  sorted Nooo) = 1, -2, -3, -4, -5, -6,
  mySorted (size 6,  sorted Yes!) = -6, -5, -4, -3, -2, 1,

3rd sample - reverse but 1
    myList (size 6,  sorted Nooo) = -1, -2, -3, -4, -5, 6,
  mySorted (size 6,  sorted Yes!) = -5, -4, -3, -2, -1, 6,

4th sample - already sorted
    myList (size 6,  sorted Yes!) = 1, 2, 3, 4, 5, 6,
  mySorted (size 6,  sorted Yes!) = 1, 2, 3, 4, 5, 6,

5th sample - sorted but 1
    myList (size 6,  sorted Nooo) = 1, 2, 3, 4, -6, 5,
  mySorted (size 6,  sorted Yes!) = -6, 1, 2, 3, 4, 5,

6th sample - repeats
    myList (size 6,  sorted Nooo) = 1, 2, 3, 3, 2, 1,
  mySorted (size 6,  sorted Yes!) = 1, 1, 2, 2, 3, 3,

Next steps

There’s a few directions this can continue. To name several interesting onse

• Simplifying the vector using the variadic templates
• Enhancing the flow control (can we make a break in the loop? could be a tough one)
• Writing more complex algorithms using the IfElse and ForLoop

LMK if you make some of these, that would be great to see.