BinaryTree.hpp

#pragma once


#include <string>
#include <vector>

#include "templates.hpp"


// These are used only for printing the tree.
#define SPACE_MIDSTICK std::string(u8"   \u251c")
#define BAR_MIDSTICK   std::string(u8"\u2502  \u251c")
#define BOTSTICK       std::string(u8"\u2570")


/** Wrapper class facilitating the use of the binary search tree.
 */
generic(T) class BinaryTree
{
private: // Types.

        /** Representation of a single node of a binary tree.
         */
        struct Node
        {
                T     data;  ///< Payload.
                Node* left;  ///< Left branch.
                Node* right; ///< Right branch.
        };

private: // Fields.

        Node*  root; ///< First node of the tree.
        size_t elements_count;

public: // Methods.

        /** Default constructor.
         */
        BinaryTree()
        : root(NULL)
        , elements_count(0)
        {
        }

        ~BinaryTree()
        {
                clear();
        }

        /** Adds a new entry to the tree. Duplicates are ignored.
         * 
         *  Params: data = Value of the new entry.
         */
        void add(T data)
        {
                add(this->root, data);
        }

        /** Deletes all entries from the tree.
         */
        void clear()
        {
                clear(this->root);
                elements_count = 0;
        }

        /** Deletes the entry of given value from the tree. If
         *  the value is not found, no error is signalised.
         * 
         *  Params: data = Value to delete.
         */
        void remove(T data)
        {
                remove(this->root, data);
        }

        /** Prints the tree in pseudographical representation.
         */
        void print()
        {
                print(this->root);
        }

        /** Returns the number of entries in the tree.
         * 
         *  Returns: Number of entries in the tree.
         */
        size_t size() const
        {
                return elements_count;
        }

        /** Performs a prefix traverse on the tree.
         * 
         *  Returns: Array of all elements in prefix traverse
         *           order.
         */
        std::vector<T> prefix()
        {
                return prefix(this->root);
        }

        /** Performs a infix traverse on the tree.
         * 
         *  Returns: Array of all elements in infix traverse
         *           order.
         */
        std::vector<T> infix()
        {
                return infix(this->root);
        }

        /** Performs a postfix traverse on the tree.
         * 
         *  Returns: Array of all elements in postfix traverse
         *           order.
         */
        std::vector<T> postfix()
        {
                return postfix(this->root);
        }

        /** Generates a string representation of the tree.
         * 
         *  Returns: String representation of the tree.
         */
        std::string to_string()
        {
                return to_string(this->root);
        }

private: // Full implementations of methods above.

        void add(Node*& root, T data)
        {
                if (!root) // Empty: creating a new tree.
                {
                        root = new Node;
                        root->data = data;
                        ++elements_count;
                }
                else if (data != root->data) // Not empty: adding to appropriate subtree.
                {                            // Ignoring if new data is already in the tree.
                        add(data < root->data ? root->left : root->right, data);
                }
        }

        void clear(Node*& root)
        {
                if (!root) return; // Don't delete empty trees.

                // Clearing all subrees.
                clear(root->left);
                clear(root->right);
                
                delete root;
                root = NULL; // Invalidating the root.
        }

        void remove(Node*& root, T data)
        {
                if (!root) return; // Don't delete from empty trees.

                // Value not found here: look in appropriate subtree.
                /**/ if (data < root->data) { remove(root->left, data); }
                else if (data > root->data) { remove(root->right, data); return; }

                // Value found here.
                if (!root->left && !root->right) // Leaf: just remove and invalidate it.
                {
                        delete root;
                        root = NULL;
                }
                else if (!root->left && root->right) // Has one child: replace it with the child.
                {
                        Node* right = root->right;
                        delete root;
                        root = right;
                }
                else if (root->left && !root->right) // ditto
                {
                        Node* left = root->left;
                        delete root;
                        root = left;
                }
                else // Has two children: replace it with the leftmost leaf of the right child.
                {
                        Node* temp   = root;
                        Node* parent = root;
                        Node* child  = root->right;

                        while (child->left)
                        {
                                parent = child;
                                child = child->left;
                        }

                        delete root;

                        if (root == parent) // Right child is a leaf.
                        {
                                root = child;
                                root->left = temp->left;
                        }
                        else // Right child is a tree.
                        {
                                parent->left = child->right;
                                root         = child;
                                child->right = temp->right;
                                child->left  = temp->left;
                        }
                }
                --elements_count;
        }

        void print(Node*& root, std::string pre = "\u2500", bool left = true)
        {
                // If not null:
                //> {pre}[{root->data}]
                // Otherwise:
                //> {pre}⊗
                printf("%s\u2500%s\n", pre.c_str(), root ? ("[" + std::to_string(root->data) + "]").c_str() : u8"\u2297");

                if (!root) return;

                // Preparing the ornament preceding the value.
                std::string prepre = left ? SPACE_MIDSTICK : BAR_MIDSTICK;

                pre.replace(pre.size() - BOTSTICK.size(), prepre.size(), prepre);
                print(root->right, pre, false);

                pre.replace(pre.size() - BOTSTICK.size(), BOTSTICK.size(), BOTSTICK);
                print(root->left, pre);
        }

        std::vector<T> prefix(Node*& root) const
        {
                std::vector<T> traverse;

                if (root)
                {
                        auto left  = prefix(root->left);
                        auto right = prefix(root->right);

                        traverse.push_back(root->data);
                        traverse.insert(traverse.end(), left.begin(), left.end());
                        traverse.insert(traverse.end(), right.begin(), right.end());
                }

                return traverse;
        }

        std::vector<T> infix(Node*& root) const
        {
                std::vector<T> traverse;

                if (root)
                {
                        auto left  = infix(root->left);
                        auto right = infix(root->right);

                        traverse.insert(traverse.end(), left.begin(), left.end());
                        traverse.push_back(root->data);
                        traverse.insert(traverse.end(), right.begin(), right.end());
                }

                return traverse;
        }

        std::vector<T> postfix(Node*& root) const
        {
                std::vector<T> traverse;

                if (root)
                {
                        auto left  = postfix(root->left);
                        auto right = postfix(root->right);

                        traverse.insert(traverse.end(), left.begin(), left.end());
                        traverse.insert(traverse.end(), right.begin(), right.end());
                        traverse.push_back(root->data);
                }

                return traverse;
        }

        std::string to_string(Node*& root)
        {
                if (!root) return "null";

                return std::to_string(root->data)  + "("
                          + to_string(root->left)  + ","
                          + to_string(root->right) + ")";
        }
};

special void BinaryTree<std::string>::print(Node*& root, std::string pre, bool left)
{
        // If not null:
        //> {pre}["{root->data}"]
        // Otherwise:
        //> {pre}⊗
        printf("%s\u2500%s\n", pre.c_str(), root ? ("[\"" + root->data + u8"\"]").c_str() : u8"\u2297");

        if (!root) return;

        // Preparing the ornament preceding the value.
        std::string prepre = left ? SPACE_MIDSTICK : BAR_MIDSTICK;

        pre.replace(pre.size() - BOTSTICK.size(), prepre.size(), prepre);
        print(root->right, pre, false);

        pre.replace(pre.size() - BOTSTICK.size(), BOTSTICK.size(), BOTSTICK);
        print(root->left, pre);
}

special std::string BinaryTree<std::string>::to_string(Node*& root)
{
        if (!root) return "null";

        return "\""  + root->data
             + "\"(" + to_string(root->left)
             + ","   + to_string(root->right)
             + ")";
}

#undef SPACE_MIDSTICK
#undef BAR_MIDSTICK
#undef BOTSTICK

templates.hpp

#pragma once


// Helper macros to extract specific arguments from variadic macros.
// Maximum of 10 arguments is accepted.
#define  _0_type(_call, ...)
#define  _1_type(_call, x)      _call(x)
#define  _2_type(_call, x, ...) _call(x), _1_type(_call, __VA_ARGS__)
#define  _4_type(_call, x, ...) _call(x), _2_type(_call, __VA_ARGS__)
#define  _5_type(_call, x, ...) _call(x), _4_type(_call, __VA_ARGS__)
#define  _6_type(_call, x, ...) _call(x), _5_type(_call, __VA_ARGS__)
#define  _7_type(_call, x, ...) _call(x), _6_type(_call, __VA_ARGS__)
#define  _8_type(_call, x, ...) _call(x), _7_type(_call, __VA_ARGS__)
#define  _9_type(_call, x, ...) _call(x), _8_type(_call, __VA_ARGS__)

#define _nth_arg(_1, _2, _3, _4, _5, _6, _7, _8, _9, N, ...) N

#define _for_each(x, ...) _nth_arg("", ##__VA_ARGS__,\
                                   _9_type,\
                                   _2_type,\
                                   _8_type,\
                                   _7_type,\
                                   _6_type,\
                                   _5_type,\
                                   _4_type,\
                                   _1_type,\
                                   _0_type)(x, ##__VA_ARGS__)

#define _declare_template_type(x) typename x

// Macros for templates for generic types.
#define generic(...) template<_for_each(_declare_template_type, ##__VA_ARGS__)>
#define special generic()