Comparing three C++ data structures for discrete sampling with probability distributions

Question

Introduction

A probability distribution data structures receives pairs \$\langle e_i, w_i \rangle_{i = 1}^n\$, (\$e_i\$ is an element and \$w_i\$ is its respective positive weight) and provides a method for sampling random elements taking weights into account. If the data structure contains \$\langle A, 1.0 \rangle\$, \$\langle B, 1.0 \rangle\$ and \$\langle C, 3.0 \rangle\$, whenever we sample a random element, \$A\$ may be returned with probability \$0.2\$, \$B\$ may be returned with probability \$0.2\$, and \$C\$ may be returned with probability \$0.6\$. Formally, the sampling probability of \$e_i\$ is $$P(e_i | w_1, w_2, \dots, w_n) = \frac{w_i}{\sum_{j = 1}^n w_j}.$$

Code

ProbabilityDistribution.hpp

#ifndef NET_CODERODDE_UTIL_PROBABILITY_DISTRIBUTION_HPP
#define NET_CODERODDE_UTIL_PROBABILITY_DISTRIBUTION_HPP

#include <cmath>
#include <random>
#include <sstream>
#include <stdexcept>

namespace net {
namespace coderodde {
namespace util {

    template<typename T>
    class ProbabilityDistribution {
    public:
        ProbabilityDistribution(std::random_device::result_type seed)
        :
        m_size{0},
        m_total_weight{0.0},
        m_generator{seed},
        m_real_distribution{0.0, 1.0}
        {}

        ProbabilityDistribution()
        :
        m_size{0},
        m_total_weight{0.0},
        m_generator{},
        m_real_distribution{0.0, 1.0}
        {}

        virtual bool is_empty() const {
            return m_size == 0;
        }

        virtual size_t size() const {
            return m_size;
        }

        virtual bool add_element     (T const& element, double weight) = 0;
        virtual T    sample_element  ()                                = 0;
        virtual bool contains_element(T const& element)          const = 0;
        virtual bool remove_element  (T const& element)                = 0;
        virtual void clear           ()                                = 0;

    protected:

        size_t                                 m_size;
        double                                 m_total_weight;
        std::uniform_real_distribution<double> m_real_distribution;
        std::mt19937                           m_generator;

        void check_weight(double weight) {
            if (std::isnan(weight)) {
                throw std::invalid_argument("The input weight is NaN.");
            }

            if (weight <= 0.0) {
                std::stringstream ss;
                ss << "The input weight is non-positive: " << weight << ".";
                throw std::invalid_argument(ss.str());
            }

            if (std::isinf(weight)) {
                throw std::invalid_argument(
                                    "The input weight is positive infinity.");
            }
        }

        void check_not_empty() const {
            if (is_empty()) {
                throw std::length_error{
                    "This probability distribution is empty."
                };
            }
        }
    };

} // End of namespace net::coderodde::util.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_UTIL_PROBABILITY_DISTRIBUTION_HPP

ArrayProbabilityDistribution.hpp

#ifndef NET_CODERODDE_UTIL_ARRAY_PROBABILITY_DISTRIBUTION_HPP
#define NET_CODERODDE_UTIL_ARRAY_PROBABILITY_DISTRIBUTION_HPP

#include "ProbabilityDistribution.hpp"
#include <iterator>
#include <random>
#include <unordered_set>
#include <utility>
#include <vector>

namespace net {
namespace coderodde {
namespace util {

    template<typename T>
    class ArrayProbabilityDistribution : public ProbabilityDistribution<T> {

    public:
        ArrayProbabilityDistribution() : ProbabilityDistribution<T>() {}
        ArrayProbabilityDistribution(std::random_device::result_type seed) :
        ProbabilityDistribution<T>(seed) {}

        ArrayProbabilityDistribution(
            const ArrayProbabilityDistribution<T>& other) {
            this->m_size             = other.m_size;
            this->m_total_weight     = other.m_total_weight;
            m_element_storage_vector = other.m_element_storage_vector;
            m_weight_storage_vector  = other.m_weight_storage_vector;
            m_filter_set             = other.m_filter_set;
        }

        ArrayProbabilityDistribution(
            ArrayProbabilityDistribution<T>&& other) {
            this->m_size             = other.m_size;
            this->m_total_weight     = other.m_total_weight;
            m_element_storage_vector =
                std::move(other.m_element_storage_vector);

            m_weight_storage_vector  = std::move(other.m_weight_storage_vector);
            m_filter_set             = std::move(other.m_filter_set);

            other.m_size         = 0;
            other.m_total_weight = 0.0;
        }

        ArrayProbabilityDistribution& operator=(
            const ArrayProbabilityDistribution<T>& other) {
            this->m_size             = other.m_size;
            this->m_total_weight     = other.m_total_weight;
            m_element_storage_vector = other.m_element_storage_vector;
            m_weight_storage_vector  = other.m_weight_storage_vector;
            m_filter_set             = other.m_filter_set;
            return *this;
        }

        ArrayProbabilityDistribution& operator=(
            ArrayProbabilityDistribution<T>&& other) {
            if (this == &other) {
                return *this;
            }

            this->m_size         = other.m_size;
            this->m_total_weight = other.m_total_weight;

            m_element_storage_vector =
                std::move(other.m_element_storage_vector);

            m_weight_storage_vector = std::move(other.m_weight_storage_vector);
            m_filter_set            = std::move(other.m_filter_set);

            other.m_size         = 0;
            other.m_total_weight = 0.0;

            return *this;
        }

        bool is_empty() const {
            return this->m_size == 0;
        }

        virtual size_t size() const {
            return this->m_size;
        }

        virtual bool add_element(T const& element, double weight) {
            if (m_filter_set.find(element) != m_filter_set.cend()) {
                return false;
            }

            this->check_weight(weight);
            m_element_storage_vector.push_back(element);
            m_weight_storage_vector.push_back(weight);
            m_filter_set.insert(element);
            this->m_total_weight += weight;
            this->m_size++;
            return true;
        }

        virtual T sample_element() {
            this->check_not_empty();
            double value = this->m_real_distribution(this->m_generator) *
                           this->m_total_weight;

            for (size_t i = 0; i < this->m_size; ++i) {
                if (value < m_weight_storage_vector[i]) {
                    return m_element_storage_vector[i];
                }

                value -= m_weight_storage_vector[i];
            }

            throw std::logic_error{"Should not get here."};
        }

        virtual bool contains_element(T const& element) const {
            return m_filter_set.find(element) != m_filter_set.cend();
        }

        virtual bool remove_element(T const& element) {
            if (!contains_element(element)) {
                return false;
            }

            auto target_element_iterator =
            std::find(m_element_storage_vector.begin(),
                      m_element_storage_vector.end(),
                      element);

            size_t target_index =
            std::distance(m_element_storage_vector.begin(),
                          target_element_iterator);

            m_element_storage_vector.erase(target_element_iterator);

            auto target_weight_iterator = m_weight_storage_vector.begin();
            std::advance(target_weight_iterator, target_index);

            double weight = m_weight_storage_vector[target_index];
            m_weight_storage_vector.erase(target_weight_iterator);
            m_filter_set.erase(element);

            this->m_size--;
            this->m_total_weight -= weight;
            return true;
        }

        virtual void clear() {
            this->m_size = 0;
            this->m_total_weight = 0.0;
            m_element_storage_vector.clear();
            m_weight_storage_vector.clear();
            m_filter_set.clear();
        }

    private:
        std::vector<T>        m_element_storage_vector;
        std::vector<double>   m_weight_storage_vector;
        std::unordered_set<T> m_filter_set;
    };

} // End of namespace net::coderodde::util.
} // End of namespace net::coderodde.
} // End of namespace net.


#endif // NET_CODERODDE_UTIL_ARRAY_PROBABILITY_DISTRIBUTION_HPP

LinkedListProbabilityDistribution.hpp

#ifndef NET_CODERODDE_UTIL_LINKED_LIST_PROBABILITY_DISTRIBUTION_HPP
#define NET_CODERODDE_UTIL_LINKED_LIST_PROBABILITY_DISTRIBUTION_HPP

#include "ProbabilityDistribution.hpp"
#include <iterator>
#include <random>
#include <unordered_map>
#include <vector>

namespace net {
namespace coderodde {
namespace util {

    template<typename T>
    class LinkedListProbabilityDistribution :
    public ProbabilityDistribution<T> {

        class LinkedListNode {
        private:

            T               m_element;
            double          m_weight;
            LinkedListNode* m_prev_node;
            LinkedListNode* m_next_node;

        public:

            LinkedListNode(T element, double weight) {
                m_element = element;
                m_weight  = weight;
            }

            T get_element() const {
                return m_element;
            }

            double get_weight() const {
                return m_weight;
            }

            LinkedListNode* get_prev_linked_list_node() const {
                return m_prev_node;
            }

            LinkedListNode* get_next_linked_list_node() const {
                return m_next_node;
            }

            void set_prev_linked_list_node(LinkedListNode* node) {
                m_prev_node = node;
            }

            void set_next_linked_list_node(LinkedListNode* node) {
                m_next_node = node;
            }
        };

    public:
        LinkedListProbabilityDistribution()
        :
        ProbabilityDistribution<T>{},
        m_head{nullptr},
        m_tail{nullptr}
        {}

        LinkedListProbabilityDistribution(std::random_device::result_type seed)
        :
        ProbabilityDistribution<T>{seed},
        m_head{nullptr},
        m_tail{nullptr}
        {}

        LinkedListProbabilityDistribution(
            const LinkedListProbabilityDistribution<T>& other) {
            this->m_size             = other.m_size;
            this->m_total_weight     = other.m_total_weight;

            // Copy the internal linked list:
            copy_linked_list(other.m_head);
        }

        LinkedListProbabilityDistribution(
            LinkedListProbabilityDistribution<T>&& other) {
            this->m_size             = other.m_size;
            this->m_total_weight     = other.m_total_weight;
            m_map                    = std::move(other.m_map);
            m_head                   = other.m_head;
            m_tail                   = other.m_tail;

            other.m_size         = 0;
            other.m_total_weight = 0.0;
            other.m_head         = nullptr;
            other.m_tail         = nullptr;
        }

        LinkedListProbabilityDistribution& operator=(
            const LinkedListProbabilityDistribution<T>& other) {
            delete_linked_list();
            copy_linked_list(other.m_head);

            this->m_size         = other.m_size;
            this->m_total_weight = other.m_total_weight;
            return *this;
        }

        LinkedListProbabilityDistribution& operator=(
            LinkedListProbabilityDistribution<T>&& other) {
            if (this == &other) {
                return *this;
            }

            delete_linked_list();

            this->m_size         = other.m_size;
            this->m_total_weight = other.m_total_weight;
            this->m_head         = other.m_head;
            this->m_tail         = other.m_tail;
            this->m_map          = std::move(other.m_map);

            other.m_size         = 0;
            other.m_total_weight = 0.0;
            other.m_head         = nullptr;
            other.m_tail         = nullptr;

            return *this;
        }

        ~LinkedListProbabilityDistribution() {
            delete_linked_list();
        }

        virtual bool add_element(T const& element, double weight) {
            if (m_map.find(element) != m_map.end()) {
                return false;
            }

            this->check_weight(weight);
            LinkedListNode* new_node = new LinkedListNode{element, weight};

            if (m_head == nullptr) {
                m_head = new_node;
                m_tail = new_node;
                new_node->set_prev_linked_list_node(nullptr);
                new_node->set_next_linked_list_node(nullptr);
            } else {
                new_node->set_prev_linked_list_node(m_tail);
                new_node->set_next_linked_list_node(nullptr);
                m_tail->set_next_linked_list_node(new_node);
                m_tail = new_node;
            }

            m_map[element] = new_node;
            this->m_size++;
            this->m_total_weight += weight;
            return true;
        }

        virtual T sample_element() {
            this->check_not_empty();
            double value = this->m_real_distribution(this->m_generator) *
                           this->m_total_weight;

            for (LinkedListNode* node = m_head;
                 ;
                 node = node->get_next_linked_list_node()) {
                if (value < node->get_weight()) {
                    return node->get_element();
                }

                value -= node->get_weight();
            }

            throw std::logic_error{"Should not get here."};
        }

        virtual bool contains_element(T const& element) const {
            return m_map.find(element) != m_map.end();
        }

        virtual bool remove_element(T const& element) {
            if (!contains_element(element)) {
                return false;
            }

            LinkedListNode* node = m_map[element];

            m_map.erase(element);
            this->m_size--;
            this->m_total_weight -= node->get_weight();
            unlink(node);
            delete node;
            return true;
        }

        virtual void clear() {
            this->m_size = 0;
            this->m_total_weight = 0.0;
            m_map.clear();
            delete_linked_list();
            m_head = nullptr;
            m_tail = nullptr;
        }

    private:
        std::unordered_map<T, LinkedListNode*> m_map;
        LinkedListNode* m_head;
        LinkedListNode* m_tail;

        void unlink(LinkedListNode* node) {
            LinkedListNode* prev_node = node->get_prev_linked_list_node();
            LinkedListNode* next_node = node->get_next_linked_list_node();

            if (prev_node != nullptr) {
                prev_node->set_next_linked_list_node(
                     node->get_next_linked_list_node());
            } else {
                m_head = node->get_next_linked_list_node();

                if (m_head != nullptr) {
                    m_head->set_prev_linked_list_node(nullptr);
                }
            }

            if (next_node != nullptr) {
                next_node->set_prev_linked_list_node(
                     node->get_prev_linked_list_node());
            } else {
                m_tail = node->get_prev_linked_list_node();

                if (m_tail != nullptr) {
                    m_tail->set_next_linked_list_node(nullptr);
                }
            }
        }

        void delete_linked_list() {
            for (LinkedListNode* node = m_head, *next; node != nullptr;) {
                next = node->get_next_linked_list_node();
                delete node;
                node = next;
            }
        }

        void copy_linked_list(LinkedListNode* source_head) {
            if (source_head == nullptr) {
                m_head = nullptr;
                m_tail = nullptr;
                return;
            }

            m_head = m_tail = new LinkedListNode{source_head->get_element(),
                                                 source_head->get_weight()};

            m_head->set_prev_linked_list_node(nullptr);
            m_map[m_head->get_element()] = m_head;

            for (LinkedListNode* node =
                    source_head->get_next_linked_list_node();
                 node != nullptr;
                 node = node->get_next_linked_list_node()) {
                LinkedListNode* new_node =
                    new LinkedListNode(node->get_element(),
                                          node->get_weight());

                m_tail->set_next_linked_list_node(new_node);
                new_node->set_prev_linked_list_node(m_tail);
                m_tail = new_node;

                m_map[new_node->get_element()] = new_node;
            }

            m_tail->set_next_linked_list_node(nullptr);
        }
    };

} // End of namespace net::coderodde::util.
} // End of namespace net::coderodde.
} // End of namespace net.


#endif // NET_CODERODDE_UTIL_LINKED_LIST_PROBABILITY_DISTRIBUTION_HPP

BinaryTreeProbabilityDistribution.hpp

#ifndef NET_CODERODDE_UTIL_BINARY_TREE_PROBABILITY_DISTRIBUTION_HPP
#define NET_CODERODDE_UTIL_BINARY_TREE_PROBABILITY_DISTRIBUTION_HPP

#include "ProbabilityDistribution.hpp"
#include <unordered_map>
#include <utility>

namespace net {
namespace coderodde {
namespace util {

    template<typename T>
    class BinaryTreeProbabilityDistribution :
    public ProbabilityDistribution<T> {
    private:

        class TreeNode {
        private:

            T         m_element;
            double    m_weight;
            bool      m_is_relay_node;
            TreeNode* m_left_child;
            TreeNode* m_right_child;
            TreeNode* m_parent;
            size_t    m_leaf_node_count;

        public:

            TreeNode(T element, double weight)
            :
            m_element{element},
            m_weight{weight},
            m_is_relay_node{false},
            m_leaf_node_count{1},
            m_left_child{nullptr},
            m_right_child{nullptr},
            m_parent{nullptr}
            {}

            TreeNode()
            :
            m_element{},
            m_weight{},
            m_is_relay_node{true},
            m_leaf_node_count{},
            m_left_child{nullptr},
            m_right_child{nullptr},
            m_parent{nullptr}
            {}

            T get_element() const {
                return m_element;
            }

            double get_weight() const {
                return m_weight;
            }

            void set_weight(double weight) {
                m_weight = weight;
            }

            size_t get_number_of_leaves() const {
                return m_leaf_node_count;
            }

            void set_number_of_leaves(size_t leaf_node_count) {
                m_leaf_node_count = leaf_node_count;
            }

            TreeNode* get_left_child() const {
                return m_left_child;
            }

            void set_left_child(TreeNode* node) {
                m_left_child = node;
            }

            TreeNode* get_right_child() const {
                return m_right_child;
            }

            void set_right_child(TreeNode* node) {
                m_right_child = node;
            }

            TreeNode* get_parent() const {
                return m_parent;
            }

            void set_parent(TreeNode* node) {
                m_parent = node;
            }

            bool is_relay_node() const {
                return m_is_relay_node;
            }

            bool is_leaf_node() const {
                return !m_is_relay_node;
            }
        };

    public:

        BinaryTreeProbabilityDistribution()
        :
        BinaryTreeProbabilityDistribution(std::random_device::result_type{})
        {}

        BinaryTreeProbabilityDistribution(std::random_device::result_type seed)
        :
        ProbabilityDistribution<T>{seed},
        m_root{nullptr}
        {}

        BinaryTreeProbabilityDistribution(
            const BinaryTreeProbabilityDistribution<T>& other) {
            this->m_size         = other.m_size;
            this->m_total_weight = other.m_total_weight;

            // Copy the internal tree:
            copy_tree(other.m_root);
        }

        BinaryTreeProbabilityDistribution(
            BinaryTreeProbabilityDistribution<T>&& other) {
            this->m_size         = other.m_size;
            this->m_total_weight = other.m_total_weight;

            m_map  = std::move(other.m_map);
            m_root = other.m_root;

            other.m_size         = 0;
            other.m_total_weight = 0.0;
            other.m_root         = nullptr;
        }

        BinaryTreeProbabilityDistribution& operator=(
            const BinaryTreeProbabilityDistribution<T>& other) {
            if (this == &other) {
                return *this;
            }

            delete_tree();
            copy_tree(other.m_root);

            this->m_size         = other.m_size;
            this->m_total_weight = other.m_total_weight;
            return *this;
        }

        BinaryTreeProbabilityDistribution& operator=(
            BinaryTreeProbabilityDistribution<T>&& other) {
            if (this == &other) {
                return *this;
            }

            delete_tree();

            this->m_size         = other.m_size;
            this->m_total_weight = other.m_total_weight;
            this->m_root         = other.m_root;
            this->m_map          = std::move(other.m_map);

            other.m_size         = 0;
            other.m_total_weight = 0.0;
            other.m_root         = nullptr;

            return *this;
        }

        virtual bool add_element(T const& element, double weight) {
            if (m_map.find(element) != m_map.end()) {
                return false;
            }

            this->check_weight(weight);
            TreeNode* new_node = new TreeNode{element, weight};
            insert(new_node);
            this->m_size++;
            this->m_total_weight += weight;
            m_map[element] = new_node;
            return true;
        }

        virtual bool contains_element(T const& element) const {
            return m_map.find(element) != m_map.end();
        }

        virtual T sample_element() {
            this->check_not_empty();
            double value = this->m_real_distribution(this->m_generator) *
                           this->m_total_weight;

            TreeNode* node = m_root;

            while (node->is_relay_node()) {
                if (value < node->get_left_child()->get_weight()) {
                    node = node->get_left_child();
                } else {
                    value -= node->get_left_child()->get_weight();
                    node = node->get_right_child();
                }
            }

            return node->get_element();
        }

        virtual bool remove_element(T const& element) {
            if (!contains_element(element)) {
                return false;
            }

            TreeNode* node = m_map[element];
            delete_node(node);
            m_map.erase(element);
            update_metadata(node->get_parent(), -node->get_weight(), -1);
            this->m_size--;
            this->m_total_weight -= node->get_weight();
            return true;
        }

        virtual void clear() {
            delete_tree();
            m_map.clear();

            m_root               = nullptr;
            this->m_size         = 0;
            this->m_total_weight = 0.0;
        }

    private:

        void delete_node(TreeNode* node) {
            TreeNode* relay_node = node->get_parent();

            if (relay_node == nullptr) {
                m_root = nullptr;
                return;
            }

            TreeNode* parent_of_relay_node = relay_node->get_parent();
            TreeNode* sibling_leaf = relay_node->get_left_child() == node ?
                                     relay_node->get_right_child() :
                                     relay_node->get_left_child();

            if (parent_of_relay_node == nullptr) {
                m_root = sibling_leaf;
                sibling_leaf->set_parent(nullptr);
                return;
            }

            if (parent_of_relay_node->get_left_child() == relay_node) {
                parent_of_relay_node->set_left_child(sibling_leaf);
            } else {
                parent_of_relay_node->set_right_child(sibling_leaf);
            }

            sibling_leaf->set_parent(parent_of_relay_node);
        }

        void update_metadata(TreeNode* node,
                             double weight_delta,
                             size_t node_count_delta) {
            while (node != nullptr) {
                node->set_number_of_leaves(
                            node->get_number_of_leaves() + node_count_delta);
                node->set_weight(node->get_weight() + weight_delta);
                node = node->get_parent();
            }
        }

        void bypass_leaf_node(TreeNode* bypass_node, TreeNode* new_node) {
            TreeNode* relay_node = new TreeNode{};
            TreeNode* parent_of_current_node = bypass_node->get_parent();

            relay_node->set_number_of_leaves(1);
            relay_node->set_weight(bypass_node->get_weight());
            relay_node->set_left_child(bypass_node);
            relay_node->set_right_child(new_node);

            bypass_node->set_parent(relay_node);
            new_node->set_parent(relay_node);

            if (parent_of_current_node == nullptr) {
                m_root = relay_node;
            } else if (parent_of_current_node->get_left_child()
                       == bypass_node) {
                relay_node->set_parent(parent_of_current_node);
                parent_of_current_node->set_left_child(relay_node);
            } else {
                relay_node->set_parent(parent_of_current_node);
                parent_of_current_node->set_right_child(relay_node);
            }

            update_metadata(relay_node, new_node->get_weight(), 1);
        }

        void insert(TreeNode* new_node) {
            if (m_root == nullptr) {
                m_root = new_node;
                new_node->set_parent(nullptr);
                new_node->set_left_child(nullptr);
                new_node->set_right_child(nullptr);
                return;
            }

            TreeNode* current_node = m_root;

            while (current_node->is_relay_node()) {
                if (current_node->get_left_child()->get_number_of_leaves() <
                    current_node->get_right_child()->get_number_of_leaves()) {
                    current_node = current_node->get_left_child();
                } else {
                    current_node = current_node->get_right_child();
                }
            }

            bypass_leaf_node(current_node, new_node);
        }

        void delete_tree(TreeNode* node) {
            if (node == nullptr) {
                return;
            }

            delete_tree(node->get_left_child());
            delete_tree(node->get_right_child());
            delete node;
        }

        void delete_tree() {
            delete_tree(m_root);
            m_root = nullptr;
        }

        TreeNode* copy_tree_impl(TreeNode* node) {
            if (node == nullptr) {
                return nullptr;
            }

            TreeNode* new_node = new TreeNode{node->get_element(),
                                              node->get_weight()};

            m_map[new_node->get_element()] = new_node;

            new_node->set_left_child (copy_tree_impl(node->get_left_child()));
            new_node->set_right_child(copy_tree_impl(node->get_right_child()));
            return new_node;
        }

        void copy_tree(TreeNode* copy_root) {
            m_root = copy_tree_impl(copy_root);
        }

        std::unordered_map<T, TreeNode*> m_map;
        TreeNode* m_root;
    };

} // End of namespace net::coderodde::util.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_UTIL_BINARY_TREE_PROBABILITY_DISTRIBUTION_HPP

assert.hpp

#ifndef ASSERT_HPP
#define ASSERT_HPP

#include <iostream>

#define ASSERT(CONDITION) assert(CONDITION, #CONDITION, __FILE__, __LINE__);
#define REPORT            assert.report();
#define TOTAL_ASSERTIONS  assert.get_total_number_of_assertions()
#define FAILED_ASSERTIONS assert.get_number_of_failed_assertions()
#define FAIL(MSG)         assert.fail(MSG)

class Assert {
public:
    bool operator()(const bool condition,
                    const char *const condition_text,
                    const char *const file_name,
                    const int line_number);

    size_t get_total_number_of_assertions() const;
    size_t get_number_of_failed_assertions() const;
    void fail(const char* msg);
    void report() const;

private:
    size_t m_total_assertions;
    size_t m_failed_assertions;
};

// Can't think of anything better than a global.
extern Assert assert;

#endif  // ASSERT_HPP

assert.cpp

#include "assert.hpp"
#include <iostream>

bool Assert::operator()(const bool condition,
                        const char *const condition_text,
                        const char *const file_name,
                        const int line_number) {
    if (!condition) {
        m_failed_assertions++;
        std::cerr << "'" << condition_text << "' is not true in file "
        << "'" << file_name << "' at line " << line_number << "."
        << std::endl;
    }

    m_total_assertions++;
    return condition;
}

size_t Assert::get_number_of_failed_assertions() const {
    return m_failed_assertions;
}

size_t Assert::get_total_number_of_assertions() const {
    return m_total_assertions;
}

void Assert::fail(const char *msg) {
    std::cerr << "FAILURE: " << msg << '\n';
    m_failed_assertions++;
}

void Assert::report() const {
    std::cout << "[TOTAL ASSERTIONS: "
    << m_total_assertions
    << ", FAILED ASSERTIONS: "
    << m_failed_assertions
    << ", PASS RATIO: ";

    if (m_total_assertions == 0)
    {
        std::cout << "N/A";
    }
    else
    {
        std::cout << ((float)
                      (m_total_assertions - m_failed_assertions)) / m_total_assertions;
    }

    std::cout << "]";

    if (m_failed_assertions == 0) {
        std::cout << " Test success!\n";
    } else {
        std::cout << " Some tests failed.\n";
    }
}

Assert assert;

main.cpp

#include "ArrayProbabilityDistribution.hpp"
#include "BinaryTreeProbabilityDistribution.hpp"
#include "LinkedListProbabilityDistribution.hpp"
#include "ProbabilityDistribution.hpp"
#include "assert.hpp"
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <iostream>

using net::coderodde::util::ProbabilityDistribution;
using net::coderodde::util::ArrayProbabilityDistribution;
using net::coderodde::util::BinaryTreeProbabilityDistribution;
using net::coderodde::util::LinkedListProbabilityDistribution;

static void test_all();
static void demo();
static void benchmark();

int main() {
    demo();
    benchmark();
    test_all();
    REPORT
}

static void test_array();
static void test_linked_list();
static void test_tree();

static void test_all() {
    test_array();
    test_linked_list();
    test_tree();
}

static void test_impl(ProbabilityDistribution<int>* dist) {
    ASSERT(dist->is_empty());

    for (int i = 0; i < 4; ++i) {
        ASSERT(dist->size() == i);
        dist->add_element(i, 1.0);
        ASSERT(dist->size() == i + 1);
    }

    ASSERT(dist->is_empty() == false);

    for (int i = 0; i < 4; ++i) {
        ASSERT(dist->contains_element(i));
    }

    ASSERT(dist->contains_element(-1) == false);

    for (int i = 4; i < 10; ++i) {
        ASSERT(dist->contains_element(i) == false);
    }

    for (int i = 0; i < 4; ++i) {
        ASSERT(dist->add_element(i, 2.0) == false);
    }

    for (int i = 0; i < 4; ++i) {
        ASSERT(dist->remove_element(i));
    }

    for (int i = 0; i < 4; ++i) {
        ASSERT(dist->remove_element(i) == false);
    }

    try {
        dist->sample_element();
        FAIL("std::length_error expected.");
    } catch (std::length_error err) {}

    for (int i = 0; i < 4; ++i) {
        dist->add_element(i, 2.0);
    }

    ASSERT(dist->size() == 4);
    dist->clear();
    ASSERT(dist->size() == 0);
}

static void test_array() {
    test_impl(new ArrayProbabilityDistribution<int>);

    ArrayProbabilityDistribution<int> dist1;
    ArrayProbabilityDistribution<int> dist2;

    for (int i = 0; i < 3; ++i) {
        dist2.add_element(i, 1.0);
    }

    ASSERT(dist1.size() == 0);
    ASSERT(dist2.size() == 3);

    dist1 = dist2;

    ASSERT(dist1.size() == 3);
    ASSERT(dist2.size() == 3);

    ArrayProbabilityDistribution<int> dist3(dist1);

    ASSERT(dist1.size() == 3);
    ASSERT(dist2.size() == 3);
    ASSERT(dist3.size() == 3);

    ArrayProbabilityDistribution<int> dist4;
    dist4 = std::move(dist1);

    ASSERT(dist1.size() == 0);
    ASSERT(dist4.size() == 3);

    ArrayProbabilityDistribution<int> dist5(std::move(dist2));

    ASSERT(dist5.size() == 3);
    ASSERT(dist2.size() == 0);

    dist1.clear();
    dist2.clear();

    ASSERT(dist1.is_empty());
    ASSERT(dist2.is_empty());

    for (int i = 10; i < 15; ++i) {
        dist1.add_element(i, 1.5);
    }

    // Test move assignment:
    dist2 = std::move(dist1);

    for (int i = 10; i < 15; ++i) {
        ASSERT(dist2.contains_element(i));
        ASSERT(dist1.contains_element(i) == false);
    }

    // Test move constructor:
    ArrayProbabilityDistribution<int> dist6(std::move(dist2));

    for (int i = 10; i < 15; ++i) {
        ASSERT(dist6.contains_element(i));
        ASSERT(dist2.contains_element(i) == false);
    }

    // Test copy constructor:
    ArrayProbabilityDistribution<int> dist7(dist6);
    dist7.remove_element(14);

    for (int i = 10; i < 14; ++i) {
        ASSERT(dist6.contains_element(i));
        ASSERT(dist7.contains_element(i));
    }

    ASSERT(dist6.contains_element(14));
    ASSERT(dist7.contains_element(14) == false);

    ASSERT(dist6.size() == 5);
    ASSERT(dist7.size() == 4);

    // Test copy assignment:
    dist1.clear();
    dist1 = dist6;

    ASSERT(dist6.size() == 5);
    ASSERT(dist1.size() == 5);

    ASSERT(dist1.remove_element(11));
    ASSERT(dist1.remove_element(13));

    ASSERT(dist6.size() == 5);
    ASSERT(dist1.size() == 3);
}

static void test_linked_list() {
    test_impl(new LinkedListProbabilityDistribution<int>);

    LinkedListProbabilityDistribution<int> dist1;
    LinkedListProbabilityDistribution<int> dist2;

    for (int i = 0; i < 3; ++i) {
        dist2.add_element(i, 1.0);
    }

    ASSERT(dist1.size() == 0);
    ASSERT(dist2.size() == 3);

    dist1 = dist2;

    ASSERT(dist1.size() == 3);
    ASSERT(dist2.size() == 3);

    LinkedListProbabilityDistribution<int> dist3(dist1);

    ASSERT(dist1.size() == 3);
    ASSERT(dist2.size() == 3);
    ASSERT(dist3.size() == 3);

    LinkedListProbabilityDistribution<int> dist4;
    dist4 = std::move(dist1);

    ASSERT(dist1.size() == 0);
    ASSERT(dist4.size() == 3);

    LinkedListProbabilityDistribution<int> dist5(std::move(dist2));

    ASSERT(dist5.size() == 3);
    ASSERT(dist2.size() == 0);

    dist1.clear();
    dist2.clear();

    ASSERT(dist1.is_empty());
    ASSERT(dist2.is_empty());

    for (int i = 10; i < 15; ++i) {
        dist1.add_element(i, 1.5);
    }

    // Test move assignment:
    dist2 = std::move(dist1);

    for (int i = 10; i < 15; ++i) {
        ASSERT(dist2.contains_element(i));
        ASSERT(dist1.contains_element(i) == false);
    }

    // Test move constructor:
    LinkedListProbabilityDistribution<int> dist6(std::move(dist2));

    for (int i = 10; i < 15; ++i) {
        ASSERT(dist6.contains_element(i));
        ASSERT(dist2.contains_element(i) == false);
    }

    // Test copy constructor:
    LinkedListProbabilityDistribution<int> dist7(dist6);
    dist7.remove_element(14);

    for (int i = 10; i < 14; ++i) {
        ASSERT(dist6.contains_element(i));
        ASSERT(dist7.contains_element(i));
    }

    ASSERT(dist6.contains_element(14));
    ASSERT(dist7.contains_element(14) == false);

    ASSERT(dist6.size() == 5);
    ASSERT(dist7.size() == 4);

    // Test copy assignment:
    dist1.clear();
    dist1 = dist6;

    ASSERT(dist6.size() == 5);
    ASSERT(dist1.size() == 5);

    ASSERT(dist1.remove_element(11));
    ASSERT(dist1.remove_element(13));

    ASSERT(dist6.size() == 5);
    ASSERT(dist1.size() == 3);

}

static void test_tree() {
    test_impl(new BinaryTreeProbabilityDistribution<int>);


    BinaryTreeProbabilityDistribution<int> dist1;
    BinaryTreeProbabilityDistribution<int> dist2;

    for (int i = 0; i < 3; ++i) {
        dist2.add_element(i, 1.0);
    }

    ASSERT(dist1.size() == 0);
    ASSERT(dist2.size() == 3);

    dist1 = dist2;

    ASSERT(dist1.size() == 3);
    ASSERT(dist2.size() == 3);

    BinaryTreeProbabilityDistribution<int> dist3(dist1);

    ASSERT(dist1.size() == 3);
    ASSERT(dist2.size() == 3);
    ASSERT(dist3.size() == 3);

    BinaryTreeProbabilityDistribution<int> dist4;
    dist4 = std::move(dist1);

    ASSERT(dist1.size() == 0);
    ASSERT(dist4.size() == 3);

    BinaryTreeProbabilityDistribution<int> dist5(std::move(dist2));

    ASSERT(dist5.size() == 3);
    ASSERT(dist2.size() == 0);

    dist1.clear();
    dist2.clear();

    ASSERT(dist1.is_empty());
    ASSERT(dist2.is_empty());

    for (int i = 10; i < 15; ++i) {
        dist1.add_element(i, 1.5);
    }

    // Test move assignment:
    dist2 = std::move(dist1);

    for (int i = 10; i < 15; ++i) {
        ASSERT(dist2.contains_element(i));
        ASSERT(dist1.contains_element(i) == false);
    }

    // Test move constructor:
    BinaryTreeProbabilityDistribution<int> dist6(std::move(dist2));

    for (int i = 10; i < 15; ++i) {
        ASSERT(dist6.contains_element(i));
        ASSERT(dist2.contains_element(i) == false);
    }

    // Test copy constructor:
    BinaryTreeProbabilityDistribution<int> dist7(dist6);
    dist7.remove_element(14);

    for (int i = 10; i < 14; ++i) {
        ASSERT(dist6.contains_element(i));
        ASSERT(dist7.contains_element(i));
    }

    ASSERT(dist6.contains_element(14));
    ASSERT(dist7.contains_element(14) == false);

    ASSERT(dist6.size() == 5);
    ASSERT(dist7.size() == 4);

    // Test copy assignment:
    dist1.clear();
    dist1 = dist6;

    ASSERT(dist6.size() == 5);
    ASSERT(dist1.size() == 5);

    ASSERT(dist1.remove_element(11));
    ASSERT(dist1.remove_element(13));

    ASSERT(dist6.size() == 5);
    ASSERT(dist1.size() == 3);
}

static void demo() {
    std::cout << "--- Sanity demo ---\n";

    using net::coderodde::util::ArrayProbabilityDistribution;
    using net::coderodde::util::LinkedListProbabilityDistribution;
    using net::coderodde::util::BinaryTreeProbabilityDistribution;

    std::random_device rd{};
    std::random_device::result_type seed = rd();

    ArrayProbabilityDistribution<int> prob_dist1{seed};
    LinkedListProbabilityDistribution<int> prob_dist2{seed};
    BinaryTreeProbabilityDistribution<int> prob_dist3{seed};

    prob_dist1.add_element(1, 1.0);
    prob_dist1.add_element(2, 1.0);
    prob_dist1.add_element(3, 3.0);

    prob_dist2.add_element(1, 1.0);
    prob_dist2.add_element(2, 1.0);
    prob_dist2.add_element(3, 3.0);

    prob_dist3.add_element(1, 1.0);
    prob_dist3.add_element(2, 1.0);
    prob_dist3.add_element(3, 3.0);

    int arr1[4] = {};
    int arr2[4] = {};
    int arr3[4] = {};

    for (int i = 0; i < 1000; ++i) {
        arr1[prob_dist1.sample_element()]++;
        arr2[prob_dist2.sample_element()]++;
        arr3[prob_dist3.sample_element()]++;
    }

    for (int i = 1; i < 4; ++i) {
        std::cout << arr1[i] << " ";
    }

    std::cout << "\n";

    for (int i = 1; i < 4; ++i) {
        std::cout << arr2[i] << " ";
    }

    std::cout << "\n";

    for (int i = 1; i < 4; ++i) {
        std::cout << arr3[i] << " ";
    }

    std::cout << "\n-------------------\n";
}

static size_t LOAD = 40 * 1000;
static size_t SAMPLES = 40 * 1000;

static void benchmark() {

    class CurrentTime {
        std::chrono::high_resolution_clock m_clock;

    public:
        uint64_t milliseconds() {
            return std::chrono::duration_cast<std::chrono::milliseconds>
            (m_clock.now().time_since_epoch()).count();
        }
    };

    ArrayProbabilityDistribution<int>      prob_dist1;
    LinkedListProbabilityDistribution<int> prob_dist2;
    BinaryTreeProbabilityDistribution<int> prob_dist3;

    std::vector<int> remove_order_vector;

    for (int i = 0; i < LOAD; ++i) {
        remove_order_vector.push_back(i);
    }
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(remove_order_vector.begin(),
                 remove_order_vector.end(),
                 g);

    CurrentTime ct;

    //// ARRAY BASED BENCHMARK ////
    std::cout << "ArrayProbabilityDistribution:\n";

    uint64_t add_time = 0;
    uint64_t sample_time = 0;
    uint64_t remove_time = 0;

    uint64_t start = ct.milliseconds();

    for (size_t i = 0; i < LOAD; ++i) {
        prob_dist1.add_element(i, 1.0);
    }

    uint64_t end = ct.milliseconds();

    add_time = end - start;
    std::cout << "  add_element: " << add_time << " milliseconds.\n";

    start = ct.milliseconds();

    for (size_t i = 0; i < SAMPLES; ++i) {
        prob_dist1.sample_element();
    }

    end = ct.milliseconds();

    sample_time = end - start;
    std::cout << "  sample_element: " << sample_time << " milliseconds.\n";

    start = ct.milliseconds();

    for (int element : remove_order_vector) {
        prob_dist1.remove_element(element);
    }

    end = ct.milliseconds();

    remove_time = end - start;
    std::cout << "  remove_element: " << remove_time << " milliseconds.\n";
    std::cout << "  Total: " << (add_time + sample_time + remove_time)
              << " milliseconds.\n";


    //// LINKED LIST BASED BENCHMARK ////
    std::cout << "LinkedListProbabilityDistribution:\n";

    add_time = 0;
    sample_time = 0;
    remove_time = 0;

    start = ct.milliseconds();

    for (size_t i = 0; i < LOAD; ++i) {
        prob_dist2.add_element(i, 1.0);
    }

    end = ct.milliseconds();

    add_time = end - start;
    std::cout << "  add_element: " << add_time << " milliseconds.\n";

    start = ct.milliseconds();

    for (size_t i = 0; i < SAMPLES; ++i) {
        prob_dist2.sample_element();
    }

    end = ct.milliseconds();

    sample_time = end - start;
    std::cout << "  sample_element: " << sample_time << " milliseconds.\n";

    start = ct.milliseconds();

    for (int element : remove_order_vector) {
        prob_dist2.remove_element(element);
    }

    end = ct.milliseconds();

    remove_time = end - start;
    std::cout << "  remove_element: " << remove_time << " milliseconds.\n";
    std::cout << "  Total: " << (add_time + sample_time + remove_time)
    << " milliseconds.\n";

    //// TREE BASED BENCHMARK ////
    std::cout << "BinaryTreeProbabilityDistribution:\n";

    add_time = 0;
    sample_time = 0;
    remove_time = 0;

    start = ct.milliseconds();

    for (size_t i = 0; i < LOAD; ++i) {
        prob_dist3.add_element(i, 1.0);
    }

    end = ct.milliseconds();

    add_time = end - start;
    std::cout << "  add_element: " << add_time << " milliseconds.\n";

    start = ct.milliseconds();

    for (size_t i = 0; i < SAMPLES; ++i) {
        prob_dist3.sample_element();
    }

    end = ct.milliseconds();

    sample_time = end - start;
    std::cout << "  sample_element: " << sample_time << " milliseconds.\n";

    start = ct.milliseconds();

    for (int element : remove_order_vector) {
        prob_dist3.remove_element(element);
    }

    end = ct.milliseconds();

    remove_time = end - start;
    std::cout << "  remove_element: " << remove_time << " milliseconds.\n";
    std::cout << "  Total: " << (add_time + sample_time + remove_time)
    << " milliseconds.\n";
}

Benchmark

My benchmark prints this:

--- Sanity demo ---
192 223 585 
192 223 585 
192 223 585 
-------------------
ArrayProbabilityDistribution:
  add_element: 9 milliseconds.
  sample_element: 1365 milliseconds.
  remove_element: 707 milliseconds.
  Total: 2081 milliseconds.
LinkedListProbabilityDistribution:
  add_element: 8 milliseconds.
  sample_element: 3758 milliseconds.
  remove_element: 16 milliseconds.
  Total: 3782 milliseconds.
BinaryTreeProbabilityDistribution:
  add_element: 29 milliseconds.
  sample_element: 27 milliseconds.
  remove_element: 36 milliseconds.
  Total: 92 milliseconds.
[TOTAL ASSERTIONS: 258, FAILED ASSERTIONS: 0, PASS RATIO: 1] Test success!
Program ended with exit code: 0

Critique request

Please tell me anything that comes to mind. However, I am most concerned with adherence to C++ programming idioms.

Answer 1

Concept review

I had some controversial thoughts, but now it is all clear, after @Edward have provided the link to the std::discrete_distribution. So I'll mostly compare the code in the post with the distribution.

Multiple concerns

Current code does lifetime management and discrete distribution logic. I guess one could use something like this:

template <typename Container, typename PredefinedGenerator>
class discrete_select // ?
{
    //other members
    //insert check for difference type here
    std::discrete_distribution<typename Container::const_iterator::difference_type> distribution;
public:
    template <typename GeneratorArgs>
    discrete_select(const Container& container, 
                    std::initializer_list<double> weights, 
                    GeneratorArgs&& ... args): 
    //initialize container and forward args to generator
    {} 

    const_iterator operator()()
    {
        return std::next(container.cbegin(), distribution());
    }
}

(the ? means that I'm not sure if it is mathematically correct name)

PredefinedGenerator might be unnecessary here.

• It delegates resource management to container, yet it holds ownership of it. I believe this is better because covering all of the container types is impossible. This also provides insane flexibility.

• The decision to use PredefinedGenerator lies in rule of 3 of them. If I'm not mistaken, all of them support rule of 3.

• It will have flexibility to provide range like objects. I believe @Emily have shown a "decorator" range, e.g. it returns an object which has begin() and end(), but does somewhat different behavior than original container. If container is stored by const, the need to call cbegin() is lifted.

• I guess this will cause insane code decrease. I'd bet it will be around 3 to 5 times.

Code Review

        if (std::isnan(weight)) {
            throw std::invalid_argument("The input weight is NaN.");
        }

I'm not sure if it is gonna be useful to check for it. I guess they have much bigger problems if they have NaN, so I guess it would be better to remove the check, and document that NaN is not valid input argument.

Formatting. May be it is subjective, but it is harder to read for me. I need to do more head movement. People with bad vision will probably have bigger problems.

Raw pointers. I know only of two possible cases where smart pointers would lead to stack overflow:

1. Linked list with too many elements.

2. Graph -- easy to cause inifinite loop if implemented wrong. Harder to implement with smart pointers (in my opinion).

I guess the code is not made to handle linked lists with many elements (10^5 and up). The other one is a tree, which has nice top-down ownership semantics.

Subjective, but I think that using std::istringstream is overkill for error generation. std::to_string() could be used and the string could be concatenated. Though I wouldn't be surprised if compiler figured that out. Especially since number of inlinings in one scope is three for clang as of 2016, I believe.