Template Magic

All remember compile-time factorial example

#include <iostream>

template<const int N> 
struct factorial {
    int num;
    factorial() {
        num = N * factorial<N-1>().num;
    }
};

template<>
struct factorial<0> 
{
    const int num = 1;
};

int main()
{
    factorial<5> t;
    std::cout << t.num << "\n";
    return 0;
}

Now we can use variadic template args like this

#include <iostream>

template<const int ...Args> struct factorial;

struct base { int num = 1; };

template<const int N, const int ...Args>
struct factorial<N, Args...> : base {
    factorial() {
        num = N * factorial<Args...>().num;
    }
};

template<> struct factorial<>  : base { };

int main()
{
    factorial<1,2,3,4,5> t;
    std::cout << t.num << "\n";
    return 0;
}

Moreover we could do better with inheritance

#include <iostream>

template<const int ...Args> 
struct factorial {
    const int num = 1;
};

template<const int N, const int ...Args>
struct factorial<N, Args...> : factorial<Args...> {
    typedef factorial<Args...> base_t;
    const int num = N * base_t::num;
};

template<> 
struct factorial<> {
    const int num = 1;
};

int main()
{
    factorial<1,2,3,4> t;
    std::cout << t.num << "\n";
    return 0;
}

Recursion via method run(). Conclusion in class with one template argument

#include <iostream>
#include <string>

template< typename ...ARGS > struct record;

template <typename FIELD, typename ...ARGS>
struct record< FIELD, ARGS... > : record<ARGS...> {
    typedef record<ARGS...> base_record_t;
    enum { index = base_record_t::index + 1 };
    
    void run() {
        base_record_t::run();
        std::cout << FIELD::name() << " " << index << "\n";
    }
};

template <typename FIELD>
struct record<FIELD> {
    enum { index = 0 };
    void run() {
        std::cout << FIELD::name() << " " << index << "\n";
    }    
};

struct f1 { static const char * name() { return "f1"; } };
struct f2 { static const char * name() { return "f2"; } };
struct f3 { static const char * name() { return "f3"; } };

int main()
{
    record<f1,f2,f3> r;
    r.run();
    return 0;
}

Find node in a binary search tree

template<typename T>
treenode<T> * find_node_by_data(treenode<T> * root, const T& value) {
 treenode<T> * node = root;
 while (node) {
  if (node->data == value)
   return node;
  if (value > node->data)
   node = node->right;
  else
   node = node->left;
 }
 return nullptr;
}

Create binary search tree from sorted array (asc order)

/* call example */
std::vector v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
treenode * root = generate_bst_tree(v);

/* implementation */
template<typename T>
treenode<T> * generate_bst_tree(const std::vector<T>& v, 
treenode<T> * node = nullptr, 
size_t from = 0, 
size_t to = 0) {
 
 treenode<T> * root = nullptr;

 if (!node) {
  if (v.size() == 0)
   return nullptr;

  root = node = new treenode();
  if (v.size() == 1) {
   root->data = v[0];
   return root;
  }
  to = v.size() - 1;
 }

 const size_t mid = (to - from) / 2 + from;
 node->data = v[mid];
 
 if ((mid - from) > 1) {
  node->left = new treenode<T>();
  generate_bst_tree(v, node->left, from, mid);
 }
 else {
  if ( from == 0 )
   node->left = new treenode<T>(v[from]);
 }

 if ((to - mid) > 1 ) {
  node->right = new treenode<T>();
  generate_bst_tree(v, node->right, mid, to);
 }
 else {
  if (to == v.size() - 1)
   node->right = new treenode<T>(v[to]);
 }

 return root;
}

Print binary tree by levels (breadth first)

template<typename T>
struct treenode {
 treenode<T> * left, *right, *parent;
 T data;
 treenode() : left(nullptr), right(nullptr), parent(nullptr) {}
 treenode(const T& param) 
: left(nullptr), right(nullptr), parent(nullptr), data(param) {}
};

template<typename T>
void print_tree(const treenode * root) {
 if (!root) {
  std::cout << "EMPTY\r\n";
  return;
 }
 
 std::queue<const treenode<T> * > q;
 q.push(root);

 const treenode<T>* node;
 size_t sz = 0; 
 
 while ((sz = q.size()) > 0) {
  for (size_t i = 0; i < sz; ++i) {
   node = q.front();
   std::cout  << node->data  << " ";
   q.pop();
   if (node->left)
    q.push(node->left);
   if (node->right)
    q.push(node->right);
  }
  std::cout  << std::endl;
 }
}

Check if the binary tree is balanced

template<typename T>
struct treenode {
 treenode<T> * left, * right;
 T data;
 treenode(const T& param) 
: left(NULL), right(NULL), data(param) {}
};

template<typename T>
bool is_balanced(treenode<T> * node, int& height) {
 if (!node)
  return true;
 ++height;

 if (!is_balanced(node->left, height))
  return false;

 const int lh = height;
 height = 0;

 if (!is_balanced(node->right, height))
  return false;

 const int rh = height;
 return abs(lh - rh) <= 2;
}

Binary search

Finds an index to put a element to if it's absent. Return true if it's there. Helps to find an index to insert an element. Not content with this one. Must be somehow redone. Looks like shit actually. Requires size_t slot be initialized by '0'

bool find_slot(const char * buffer, 
const size_t size, 
const char elem, 
size_t * slot) {

    const size_t m = (size_t)(size / 2);

    if ( m == 0 )
        return false;

    if ( elem > buffer[m - 1] ) {
        *slot += m;
        if ( elem < buffer[m] )
            return false;
        return find_slot(buffer + m, size - m, elem, slot);
    }

    if ( elem < buffer[m - 1] ) {
        if ( elem > buffer[m - 2] )
            return false;
        return find_slot(buffer, size - m, elem, slot);
    }
    return true;
}

Reverse string

void reverse(char * str) {

    char temp;

    for ( int i = strlen(str) - 1, j = 0; 
              j < (int)(strlen(str) / 2); --i, ++j) {

        temp = str[i];
        str[i] = str[j];
        str[j] = temp;

    }
}

Permutations

void permute(permtype * p, const char * expr) {
    p->perms[0][0] = expr[0];

    for (size_t i = 1; i < p->LEN; ++i)
        merge(p, i, expr[i]);

}

void merge(permtype * p, const size_t index, const char elem) {

    const size_t Nprev = index > 0 ? factorial(index) : 0;
    assert(p->N > Nprev);
    size_t j = Nprev;

    for (size_t i = 0; i < Nprev; ++i) {
        for ( size_t k = 0; k < index; ++k )
            splice(&(p->perms[j++]), p->perms[i], elem, k, index);

        p->perms[i][index] = elem;
    }

}

The quick magic of reversing a linked list in these two lines

     node->next = prev;
     prev = node;

This brilliant code snippet takes a node offset by the index from the head and swaps its value with the node offset by the index from the tail.

void swapAt(Node *head, int index) {

    Node * node = head;
    Node * begin, trailer;

    for (int i = 0; node != NULL; node = node->next, ++i ) {

         if ( i == index ) {
            begin = node;
            trailer = head;
         }

         if ( i > index)
             trailer = trailer->next;

    }

    int temp = begin.val;
    begin.val = trailer.val;
    trailer.val = temp;
}