cpp-snippets

binarytree.cpp

#include <stdio.h>
#include <QString>

/**
 * @brief The BinaryTree class
 */
template <class K, class V>
class BinaryTree
{
   public:
      /**
       * @brief BinaryTree
       */
      BinaryTree()
      {
         _root = NULL;
      }

      /**
       *
       */
      ~BinaryTree()
      {
         if (_root != NULL)
         {
            delete _root;
            _root = NULL;
         }
      }

      /**
       * @brief add
       * @param key
       * @param value
       */
      void add(K key, V value)
      {
         if (_root == NULL)
         {
            _root = new Node(key, value);
         }
         else
         {
            _add(_root, key, value);
         }
      }

      /**
       * @brief get
       * @param key
       * @return
       */
      V find(K key)
      {
         Node* node = _root;

         while (node != NULL)
         {
            if (key == node->key)
            {
               return node->value;
            }
            else if (key < node)
            {
               node = node->left;
            }
            else
            {
               node = node->right;
            }
         }

         return NULL;
      }

      /**
       * @brief printInOrder
       */
      void printInOrder()
      {
         _printInOrder(_root);
      }

   private:
      /**
       * @brief The Node class
       */
      class Node
      {
         public:
            /**
             * @brief key
             */
            K key;

            /**
             * @brief _eft
             */
            Node* left;

            /**
             * @brief right
             */
            Node* right;

            /**
             * @brief value
             */
            V value;

            /**
             * @brief Node
             * @param newKey
             * @param newValue
             */
            Node(K newKey, V newValue)
            {
               key = newKey;
               left = NULL;
               right = NULL;
               value = newValue;
            }

            /**
             * @brief ~Node
             */
            ~Node()
            {
               if (left != NULL)
               {
                  delete left;
                  left = NULL;
               }

               if (right != NULL)
               {
                  delete right;
                  right = NULL;
               }
            }
      };

      /**
       * @brief _root
       */
      Node* _root;

      /**
       * @brief _add
       * @param node
       * @param key
       * @param value
       */
      void _add(Node* node, K key, V value)
      {
         if (key < node->key)
         {
            if (node->left == NULL)
            {
               node->left = new Node(key, value);
            }
            else
            {
               _add(node->left, key, value);
            }
         }
         else
         {
            if (node->right == NULL)
            {
               node->right = new Node(key, value);
            }
            else
            {
               _add(node->right, key, value);
            }
         }
      }

      /**
       * @brief _printInOrder
       * @param node
       */
      void _printInOrder(Node* node)
      {
         if (node->left != NULL)
         {
            _printInOrder(node->left);
         }

         qDebug("%s", qPrintable(QString("%1").arg(node->value)));

         if (node->right != NULL)
         {
            _printInOrder(node->right);
         }
      }

};

/**
 * @brief main
 * @return
 */
int main()
{
   BinaryTree<int, QString> tree = BinaryTree<int, QString>();

   tree.add(10, "Second");
   tree.add(5,  "First");
   tree.add(15, "Third");

   tree.printInOrder();

   return 0;
}

hashtable.cpp

#include <stdio.h>
#include <QList>
#include <QString>

/**
 * @brief The IHashFunction abstract class
 */
class IHashFunction
{
   public:
      /**
       * @brief IHashFunction
       * @param max
       */
      IHashFunction(int max = 100)
      {
         _max = max;
      }

      /**
       * @brief ~IHashFunction
       */
      virtual ~IHashFunction() { }

      /**
       * @brief hash
       * @param key
       * @return
       */
      virtual int hash(void* key) = 0;

      /**
       * @brief getMax
       * @return
       */
      int getMax()
      {
         return _max;
      }

   protected:
      /**
       * @brief _max
       */
      int _max;
};

/**
 * @brief The QStringHashFunction class
 */
class QStringHashFunction : public IHashFunction
{
   public:
      /**
       * @brief hash
       * @param key
       * @return
       */
      int hash(void* key)
      {
         QString* str = static_cast<QString*>(key);

         int sum = 0;

         foreach(int c, str->toUtf8())
         {
            sum += c;
         }

         return sum % _max;
      }
};

/**
 * @brief The HashTable class
 */
template <class K, class V>
class HashTable
{
   public:
      /**
       * @brief
       */
      HashTable(IHashFunction* hash)
      {
         _hash = hash;

         _buckets = new QList<Node>[_hash->getMax()];
         for (int i = 0; i < _hash->getMax(); i++)
         {
            _buckets[i] = QList<Node>();
         }
      }

      /**
       * @brief ~HashTable
       */
      ~HashTable()
      {
         delete _hash;
         _hash = NULL;

         for (int i = 0; i < _hash->getMax(); i++)
         {
            _buckets[i].clear();
         }

         delete[] _buckets;
      }

      /**
       * @brief add
       * @param key
       * @param value
       */
      void add(K key, V value)
      {
         Node node = Node(key, value);

         int bucket = _hash->hash(&key);

         int index = _buckets[bucket].indexOf(node);
         if (index > -1)
         {
            _buckets[bucket].replace(index, node);
         }
         else
         {
            _buckets[bucket].append(node);
         }
      }

      /**
       * @brief get
       * @param key
       * @return
       */
      V find(K key)
      {
         int bucket = _hash->hash(&key);

         foreach(Node node, _buckets[bucket])
         {
            if (node.key == key)
            {
               return node.value;
            }
         }

         return NULL;
      }

   private:

      /**
       * @brief The Node class
       */
      class Node
      {
         public:
            /**
             * @brief key
             */
            K key;

            /**
             * @brief value
             */
            V value;

            /**
             * @brief Node
             * @param newKey
             * @param newValue
             */
            Node(K newKey, V newValue)
            {
               key = newKey;
               value = newValue;
            }

            /**
             * @brief ~Node
             */
            ~Node()
            {
            }

            /**
             * @brief operator ==
             * @param node
             */
            bool operator==(const Node& node)
            {
               return key == node.key;
            }
      };

      /**
       * @brief _hash
       */
      IHashFunction* _hash;

      /**
       * @brief _buckets
       */
      QList<Node>* _buckets;
};

/**
 * @brief main
 * @return
 */
int main()
{
   HashTable<QString, QString> hashTable = HashTable<QString, QString>(new QStringHashFunction());

   hashTable.add("Key1", "A Value 1");
   hashTable.add("Key2", "A Value 2");
   hashTable.add("Key3", "A Value 3");
   hashTable.add("Key3", "A Value 3-1");

   qDebug("%s", qPrintable(hashTable.find("Key3")));

   return 0;
}

interface.cpp

#include <stdio.h>
#include <QString>

/**
 * @brief The Animal class
 */
class IAnimal
{
   public:
      /**
       * @brief getName
       * @return
       */
      virtual QString getIntroduction() = 0;

   protected:
      /**
       * @brief _name
       */
      QString _name;
};

/**
 * @brief The Dog class
 */
class Dog : public IAnimal
{
   public:
      /**
       * @brief Dog
       * @param name
       */
      Dog(QString name)
      {
         _name = name;
      }

      /**
       * @see Animal.getName()
       */
      QString getIntroduction()
      {
         return QString("My name is %1.").arg(_name);
      }
};

/**
 * @brief main
 * @return
 */
int main()
{
   Dog dog = Dog("Charlie");

   qDebug("%s", qPrintable(dog.getIntroduction()));

   return 0;
}

mergesort.cpp

#include <stdio.h>
#include <QString>

/**
 * @brief merge
 * @param unsorted
 * @param start
 * @param middle
 * @param end
 * @param sorted
 */
void merge(int* unsorted, const int start, const int middle, const int end, int* sorted)
{
   int j = start;
   int k = middle;

   for (int i = start; i < end; i++)
   {
      if (j < middle && (k >= end || unsorted[j] <= unsorted[k]))
      {
         sorted[i] = unsorted[j++];
      }
      else
      {
         sorted[i] = unsorted[k++];
      }
   }
}

/**
 * @brief split
 * @param unsorted
 * @param start
 * @param end
 * @param sorted
 */
void split(int* unsorted, const int start, const int end, int* sorted)
{
   // Can't sort a list with only one number!
   if (end - start < 2)
      return;

   const int middle = (end + start) / 2;

   split(unsorted, start, middle, sorted);
   split(unsorted, middle, end, sorted);

   merge(unsorted, start, middle, end, sorted);

   for (int i = start; i < end; i++)
   {
      unsorted[i] = sorted[i];
   }
}

/**
 * @brief merge_sort
 * @param unsorted
 * @param size
 * @return
 */
int* merge_sort(int* unsorted, const int size)
{
   int* sorted = new int[size];

   split(unsorted, 0, size, sorted);

   return sorted;
}

/**
 * @brief main
 * @return
 */
int main()
{
   const int size = 10;
   int numbers[size] = {4, 1, 2, 7, 8, 5, 6, 10, 9, 3};

   int* sorted = merge_sort(numbers, size);

   QString str = QString();
   for (int i = 0; i < size; i++)
   {
      str.append(QString::number(sorted[i])).append(", ");
   }

   qDebug("%s", qPrintable(str));

   delete[] sorted;

   return 0;
}

spinlock.cpp

#include <thread>
#include <vector>
#include <iostream>
#include <atomic>

std::atomic_flag lock = ATOMIC_FLAG_INIT;

/**
 * @brief f
 * @param n
 */
void f(int n)
{
   for (int cnt = 0; cnt < 100; ++cnt) {
      while (lock.test_and_set(std::memory_order_acquire))  // acquire lock
         ; // spin
      std::cout << "Output from thread " << n << '\n';
      lock.clear(std::memory_order_release);               // release lock
   }
}

/**
 * @brief main
 * @return
 */
int main()
{
   std::vector<std::thread> v;

   for (int n = 0; n < 10; ++n) {
      v.emplace_back(f, n);
   }

   for (auto& t : v) {
      t.join();
   }
}

templates.cpp

#include <stdio.h>
#include <QString>

/**
 *
 */
template <class T>
class LinkedList
{
   public:
      /**
       * @brief LinkedList
       */
      LinkedList()
      {
         _root = NULL;
         _size = 0;
      }

      /**
       *
       */
      ~LinkedList()
      {
         if (_root != NULL)
         {
            delete _root;
         }
      }

      /**
       * @brief add
       */
      void add(T value)
      {
         if (_root == NULL)
         {
            _root = new Node(value);
         }
         else
         {
            Node* node = _root;
            while (node->getNext() != NULL)
            {
               node = node->getNext();
            }

            node->setNext(new Node(value));
         }

         _size++;
      }

      /**
       * @brief get
       * @param index
       * @return
       */
      T get(int index)
      {
         if (index < _size)
         {
            Node* node = _root;
            for (int i = 0; i < index; i++)
            {
               node = node->getNext();
            }

            return node->getValue();
         }

         return NULL;
      }

      /**
       * @brief remove
       */
      void remove(int index)
      {
         if (index < _size)
         {
            Node* previous = NULL;
            Node* node = _root;
            for (int i = 0; i < index; i++)
            {
               previous = node;
               node = node->getNext();
            }

            Node* next = node->getNext();
            if (previous != NULL)
            {
               previous->setNext(next);
            }

            node->setNext(NULL);
            delete node;

            _size--;
         }
      }

   private:
      /**
       * @brief The Node class
       */
      class Node
      {
         public:
            /**
             * @brief Node
             * @param value
             */
            Node(T value)
            {
               _next = NULL;
               _value = value;
            }

            /**
             * @brief ~Node
             */
            ~Node()
            {
               if (_next != NULL)
               {
                  delete _next;
                  _next = NULL;
               }
            }

            /**
             * @brief getNext
             * @return
             */
            Node* getNext()
            {
               return _next;
            }

            /**
             * @brief getValue
             * @return
             */
            T getValue()
            {
               return _value;
            }

            /**
             * @brief setNext
             * @param node
             */
            void setNext(Node* node)
            {
               _next = node;
            }

         private:
            /**
             * @brief _next
             */
            Node* _next;

            /**
             * @brief _value
             */
            T _value;
      };

      /**
       * @brief _root
       */
      Node* _root;

      /**
       * @brief _size
       */
      int _size;
};

/**
 * @brief main
 * @return
 */
int main()
{
   LinkedList<QString> list = LinkedList<QString>();

   list.add("Value1");
   list.add("Value2");
   list.add("Value3");

   qDebug("%s", qPrintable(list.get(2)));

   list.remove(1);
   qDebug("%s", qPrintable(list.get(1)));

   return 0;
}