Code Review: AnyValueSet

_description.md

Code review: AnyValueSet

I am posting this to allow anyone to review this code which is part of one of my projects. As I am developping this massive thing alone, I am looking for people to help reviewing these kind of code that are fundations and I can easily isolate and publish.

The project use C++11/14 as provided by VS2013 (no CTP) and Boost. I didn't try to compile it in other compilers yet (lack of time and resources). The tests are provided in another other file, it compiles and run for me but the tests themselves might require review too. Tests are using GTest. I use custom assert macros which I will not explain here as they are obvious to understand.

AnyValueSet: I use this container more or less as a message board, the values being the messages. Sometime, I use types which are compared using only part of their value and contain more data that are not used in comparison, which is why there are overwritting functions.

anyvalueset.hpp

#ifndef HGUARD_NETRUSH_INPUT_ANYVALUESET_HPP__
#define HGUARD_NETRUSH_INPUT_ANYVALUESET_HPP__

#include <memory>
#include <typeindex>
#include <vector>

#include <boost/container/flat_map.hpp>
#include <boost/container/flat_set.hpp>
#include <boost/optional.hpp>

#include <utilcxx/assert.hpp>

namespace netrush {
namespace input {
    
    /** Set that can contain multiple value types.
        The contained types must be Comparable, Copyable and CopyConstructible.
        The identity of values is determined by comparison (operator< and operator==), 
        which allows for the type to have a different identity than it's value, 
        in which case overwriting can be used to change the non-observable state while keeping the identity.
    */
    class AnyValueSet
    {
    public:

        AnyValueSet() = default;

        AnyValueSet( const AnyValueSet& other ) 
        { 
            insert( other );    
        }

        AnyValueSet& operator=( const AnyValueSet& other ) 
        { 
            clear();
            insert( other );
            return *this;
        }

        AnyValueSet( AnyValueSet&& other )
            : m_size_changed( std::move(other.m_size_changed) )
            , m_size( std::move(other.m_size) )
            , m_set_index( std::move(other.m_set_index) )
        {}

        AnyValueSet& operator=( AnyValueSet&& other )
        {
            m_size_changed = std::move(other.m_size_changed);
            m_size = std::move(other.m_size);
            m_set_index = std::move(other.m_set_index);
            return *this;
        }

           
        /** Add a new value if not already stored.
            @return True if the value have been added, false otherwise.
        */
        template< class ValueType >
        bool add( ValueType&& value )
        {
            auto& value_set = find_or_create_set<ValueType>();
            bool was_added = value_set.add( std::forward<ValueType>(value) );
            if( was_added )
                size_changed();
            return was_added;
        }

        /** Add a new value and overwrite the previous one even if it was already stored. 
            @return True if the value have been added, false if the value was overwritten.
        */
        template< class ValueType >
        bool overwrite( ValueType&& value )
        {
            auto& value_set = find_or_create_set<ValueType>();
            bool was_added = value_set.overwrite( std::forward<ValueType>( value ) );
            if( was_added )
                size_changed();
            return was_added;
        }

        /** Remove a value if it was stored. */
        template< class ValueType >
        void remove( const ValueType& value )
        {
            if( auto* value_set = find_set<ValueType>() )
            {
                value_set->remove( value );
                size_changed();
            }
        }

        /** Remove all values contained in the provided set which are stored in this one. */
        void remove( const AnyValueSet& other )
        {
            if( other.empty() || this->empty() )
                return;

            auto current_slot = begin( m_set_index );
            const auto end_current = end( m_set_index );

            auto other_slot = begin( other.m_set_index );
            const auto end_other = end( other.m_set_index );

            while( current_slot != end_current
                && other_slot != end_other )
            {
                if( current_slot->first == other_slot->first )
                {
                    auto& current_set_ptr = current_slot->second;
                    auto& other_set_ptr = other_slot->second;
                    UCX_ASSERT_NOT_NULL( current_set_ptr );
                    UCX_ASSERT_NOT_NULL( other_set_ptr );
                    current_set_ptr->remove( *other_set_ptr );
                    size_changed();
                    ++other_slot;
                }               
                ++current_slot;
            }
        }

        /** Search for the value comparable to the provided key.
            The key can have a different type than the value or the same type.
            If the value type is specified, the 
            @return Either a copy of the stored value or none if not found.
        */
        template< class ValueType, class KeyType >
        boost::optional<ValueType> find( const KeyType& key ) const
        {
            if( auto* value_set = find_set<ValueType>() )
            {
                return value_set->find( key );
            }
            return {};
        }

        /** Specializatoin of find() in case the value type is not specified. */
        template< class ValueType >
        boost::optional<ValueType> find( const ValueType& value ) const
        {
            return find<ValueType, ValueType>( value );
        }

        /** @return true if the specified key is comparable to a stored value of the specified value type, false otherwise. */
        template< class ValueType, class KeyType >
        bool contains( const KeyType& key ) const
        {
            if( auto* value_set = find_set<ValueType>() )
            {
                return value_set->contains( key );
            }
            return false;
        }

        /** @return true if the value is comparable to a stored value of the same type. */
        template< class ValueType >
        bool contains( const ValueType& value ) const
        {
            return contains<ValueType, ValueType>( value );
        }

        /** Insert all the values from the provided set which are not already stored into this one. */
        void insert( const AnyValueSet& other )
        {
            for( const auto& set_pair : other.m_set_index )
            {
                auto& set_ptr = set_pair.second;
                UCX_ASSERT_NOT_NULL( set_ptr );

                if( auto value_set = find_set( set_pair.first ) )
                {
                    value_set->insert( *set_ptr );
                }
                else
                {
                    m_set_index.emplace( set_pair.first, set_ptr->clone() );
                }
                size_changed();
            }
            
        }

        /** Insert all the values from the provided set which are not already stored into this one. */
        void insert_overwrite( const AnyValueSet& other )
        {
            for( const auto& set_pair : other.m_set_index )
            {
                auto& set_ptr = set_pair.second;
                UCX_ASSERT_NOT_NULL( set_ptr );

                if( auto value_set = find_set( set_pair.first ) )
                {
                    value_set->insert_overwrite( *set_ptr );
                }
                else
                {
                    m_set_index.emplace( set_pair.first, set_ptr->clone() );
                }
                size_changed();
            }

        }

        /** Copy and return all the values of the specified type. */
        template< class ValueType >
        std::vector<ValueType> all() const
        {
            if( auto* value_set = find_set<ValueType>() )
            {
                return value_set->values();
            }
            return {};
        }
        
        /** @return How many values are currently stored for all types. */
        size_t size() const 
        { 
            if( m_size_changed )
            {
                m_size_changed = false;
                compute_size();
            }
                
            return m_size; 
        }

        /** @return true if there is at least one value stored of any type, false otherwise. */
        bool empty() const
        {
            return m_set_index.empty()
                || size() == 0;
        }

        /** Destroy all values of the provided type. */
        template< class ValueType >
        void clear()
        {
            if( auto* value_set = find_set<ValueType>() )
            {
                value_set->clear();
                size_changed();
            }
        }

        /** Destroy all values of all types. */
        void clear()
        {
            for( const auto& set_slot : m_set_index )
            {
                auto& set_ptr = set_slot.second;
                UCX_ASSERT_NOT_NULL( set_ptr );
                set_ptr->clear();
            }
            size_changed();
        }

        

    private:

        struct Set
        {
            virtual void insert( const Set& other ) = 0;
            virtual void insert_overwrite( const Set& other ) = 0;
            virtual void remove( const Set& other ) = 0;
            virtual std::unique_ptr<Set> clone() = 0;
            virtual size_t size() const = 0;
            virtual void clear() = 0;
            virtual ~Set() = default;
        };

        template< class T >
        class SetOf : public Set
        {
            boost::container::flat_set<T> m_values;
        public:
            SetOf() = default;

            template< class Iterator >
            SetOf( Iterator&& it_begin, Iterator&& it_end )
                : m_values( std::forward<Iterator>( it_begin ), std::forward<Iterator>( it_end ) )
            {}

            /** Add a new value if not already stored.
                @return True if the value have been added, false otherwise.
            */
            bool add( T value ) 
            {
                auto result = m_values.emplace( std::move( value ) );
                return result.second;
            }

            /** Add a new value and overwrite the previous one even if it was already there. 
                @return True if the value have been added, false if the value was overwritten.
            */
            bool overwrite( T value )
            {
                auto result = m_values.insert( value );
                if( !result.second )
                {
                    *result.first = value;
                    return false;
                }
                return true;                    
            }

            void remove( const T& value ) { m_values.erase( value ); }

            template< class KeyType >
            boost::optional<T> find( const KeyType& key ) const
            {
                for( const auto& value : m_values )
                {
                    if( value == key ) 
                        return value;
                }

                return {};
            }

            template< class KeyType >
            bool contains( const KeyType& key ) const 
            { 
                for( const auto& value : m_values )
                {
                    if( value == key )
                        return true;
                }
                
                return false;
            }
            
            void insert( const Set& other ) override
            {
                const auto& specific_set = static_cast<const SetOf<T>&>( other );
                m_values.insert( begin(specific_set.m_values), end(specific_set.m_values) );
            }
            
            void insert_overwrite( const Set& other ) override
            {
                const auto& specific_set = static_cast<const SetOf<T>&>( other );
                for( auto&& value : specific_set.m_values )
                {
                    overwrite( value );
                }
            }

            void remove( const Set& other ) override
            {
                const auto& specific_set = static_cast<const SetOf<T>&>( other );
                m_values.erase( std::remove_if( begin( m_values ), end( m_values )
                    , [&]( const T& value ) { return specific_set.contains( value ); } )
                    , end( m_values ) );
            }

            std::unique_ptr<Set> clone() override
            {
                return std::make_unique<SetOf<T>>( begin( m_values ), end( m_values ) );
            }

            size_t size() const override { return m_values.size(); }

            std::vector<T> values() const
            {
                return { begin( m_values ), end( m_values ) };
            }

            void clear() override { m_values.clear(); }
        };
        
        Set* find_set( std::type_index type_id ) const
        {
            auto find_it = m_set_index.find( type_id );
            if( find_it != end( m_set_index ) )
            {
                auto& set_ptr = find_it->second;
                auto& specific_set = *set_ptr;
                return &specific_set;
            }
            return nullptr;
        }


        template< class T, typename ValueType = std::decay<T>::type >
        SetOf<ValueType>* find_set() const 
        { 
            return static_cast<SetOf<ValueType>*>( find_set( typeid( ValueType ) ) ); 
        }

        template< class T, typename ValueType = std::decay<T>::type >
        SetOf<ValueType>& find_or_create_set()
        {
            if( auto* specific_set = find_set<ValueType>() )
            {
                return *specific_set;
            }

            auto new_set = std::make_unique<SetOf<ValueType>>();
            auto position = m_set_index.emplace( typeid( ValueType ), std::move(new_set) ).first;
            auto& set_ptr = position->second;
            return static_cast<SetOf<ValueType>&>( *set_ptr );
        }

        inline void size_changed() const { m_size_changed = true; }

        void compute_size() const
        {
            m_size = 0;
            for( const auto& set_pair : m_set_index )
            {
                auto& set_ptr = set_pair.second;
                m_size += set_ptr->size();
            }
        }
    

        boost::container::flat_map<std::type_index, std::unique_ptr<Set>> m_set_index;
        mutable bool m_size_changed = false;
        mutable size_t m_size = 0;

    };



}}


#endif

test_anyvalueset.cpp

#include <gtest/gtest.h>

#include <utility>
#include <string>

#include <netrush/system/input/anyvalueset.hpp>

using namespace netrush::input;

struct Foo
{
    int k;
    long l;
};

bool operator==( const Foo& a, const Foo& b )
{
    return a.k == b.k
        && a.l == b.l
        ;
}

bool operator< ( const Foo& a, const Foo& b )
{
    return a.k < b.k
        && a.l < b.l
        ;
}

struct Id
{
    int value;
};

bool operator==( const Id& a, const Id& b )
{
    return a.value == b.value;
}

bool operator< ( const Id& a, const Id& b )
{
    return a.value < b.value;
}


struct Entity // The id is the identity, comparisons use only the id.
{
    Id id;
    std::string name;
};

bool operator==( const Entity& a, const Entity& b )
{
    return a.id == b.id;
}

bool operator< ( const Entity& a, const Entity& b )
{
    return a.id < b.id;
}

bool operator==( const Id& a, const Entity& b )
{
    return a == b.id;
}
bool operator==( const Entity& a, const Id& b )
{
    return b == a;
}

template< class T >
void test_all_operations( AnyValueSet& value_set, T value )
{
    const auto begin_size = value_set.size();
    value_set.add( value );
    ASSERT_TRUE( value_set.contains( value ) );
    const auto stored_value = value_set.find( value );
    ASSERT_EQ( value, *stored_value );
    ASSERT_EQ( begin_size + 1, value_set.size() );

    auto values = value_set.all<T>();
    auto find_it = std::find( begin( values ), end( values ), value );
    ASSERT_NE( end( values ), find_it );
}

TEST( Test_AnyValueSet, any_kind_of_values )
{
    static const auto BLAH = std::string{ "Blah" };

    AnyValueSet value_set;
    test_all_operations( value_set, 42 );
    test_all_operations( value_set, 3.14 );
    test_all_operations( value_set, 0.5f );
    test_all_operations( value_set, Foo{ 42, 5 } );
    test_all_operations( value_set, Id{ 1234 } );
    test_all_operations( value_set, Entity{ Id{ 5678 }, "A" } );
    test_all_operations( value_set, BLAH );

    ASSERT_FALSE( value_set.empty() );
    ASSERT_EQ( 7, value_set.size() );
    
    AnyValueSet values_to_remove;
    values_to_remove.add( BLAH );
    values_to_remove.add( 0 );
    values_to_remove.add( 2.5 );

    value_set.remove( values_to_remove );
    ASSERT_FALSE( value_set.contains( BLAH ) );
    ASSERT_FALSE( value_set.empty() );
    ASSERT_EQ( 6, value_set.size() );
    
    value_set.clear<int>();
    ASSERT_FALSE( value_set.empty() );
    ASSERT_EQ( 5, value_set.size() );

    value_set.clear();
    ASSERT_TRUE( value_set.empty() );
}

TEST( Test_AnyValueSet, add_unique_simple_values )
{
    AnyValueSet value_set;
    value_set.add( 42 );
    value_set.add( 42 );
    value_set.add( 42 );
    value_set.add( 42 );
    value_set.add( 42 );
    ASSERT_EQ( 1, value_set.size() );

}

TEST( Test_AnyValueSet, overwrite_unique_simple_values )
{
    AnyValueSet value_set;
    value_set.overwrite( 42 );
    value_set.overwrite( 42 );
    value_set.overwrite( 42 );
    value_set.overwrite( 42 );
    value_set.overwrite( 42 );
    ASSERT_EQ( 1, value_set.size() );

}

TEST( Test_AnyValueSet, add_unique_key_values )
{
    AnyValueSet value_set;
    value_set.add( Entity{ Id{ 42 }, "A" } );
    value_set.add( Entity{ Id{ 42 }, "B" } );
    value_set.add( Entity{ Id{ 42 }, "C" } );
    value_set.add( Entity{ Id{ 42 }, "D" } );
    value_set.add( Entity{ Id{ 42 }, "E" } );
    ASSERT_EQ( 1, value_set.size() );
    
    {
        auto entity = value_set.find<Entity>( Id{ 42 } );
        ASSERT_TRUE( entity );
        ASSERT_EQ( "A", entity->name );
    }
    
    AnyValueSet other_set;
    other_set.add( Entity{ Id{ 42 }, "X" } );
    value_set.insert( other_set );
    ASSERT_EQ( 1, value_set.size() );

    {
        auto entity = value_set.find<Entity>( Id{ 42 } );
        ASSERT_TRUE( entity );
        ASSERT_EQ( "A", entity->name );
    }
}

TEST( Test_AnyValueSet, overwrite_unique_key_values )
{
    AnyValueSet value_set;
    value_set.overwrite( Entity{ Id{ 42 }, "A" } );
    value_set.overwrite( Entity{ Id{ 42 }, "B" } );
    value_set.overwrite( Entity{ Id{ 42 }, "C" } );
    value_set.overwrite( Entity{ Id{ 42 }, "D" } );
    value_set.overwrite( Entity{ Id{ 42 }, "E" } );
    ASSERT_EQ( 1, value_set.size() );

    {
        auto entity = value_set.find<Entity>( Id{ 42 } );
        ASSERT_TRUE( entity );
        ASSERT_EQ( "E", entity->name );
    }

    AnyValueSet other_set;
    other_set.add( Entity{ Id{ 42 }, "A" } );
    value_set.insert_overwrite( other_set );
    ASSERT_EQ( 1, value_set.size() );

    {
        auto entity = value_set.find<Entity>( Id{ 42 } );
        ASSERT_TRUE( entity );
        ASSERT_EQ( "A", entity->name );
    }

}


TEST( Test_AnyValueSet, merge_sets_same_type )
{
    AnyValueSet set_a, set_b;
    
    set_a.add( 1 );
    set_a.add( 2 );
    set_a.add( 3 );
    set_a.add( 4 );
    
    set_b.add( 1 );
    set_b.add( 2 );
    set_b.add( 3 );
    set_b.add( 4 );
    set_b.add( 5 );
    set_b.add( 6 );
    set_b.add( 7 );
    set_b.add( 8 );

    set_a.insert( set_b );
    ASSERT_EQ( set_a.size(), set_b.size() );
    auto b_values = set_b.all<int>();
    for( const auto i : b_values )
    {
        ASSERT_TRUE( set_a.contains( i ) );
    }

    AnyValueSet set_c;
    set_c.insert( set_a );
    auto c_values = set_c.all<int>();
    for( const auto i : c_values )
    {
        ASSERT_TRUE( set_a.contains( i ) );
    }
    for( const auto i : b_values )
    {
        ASSERT_TRUE( set_c.contains( i ) );
    }

}

TEST( Test_AnyValueSet, merge_sets_different_types )
{
    AnyValueSet set_a, set_b;

    set_a.add( 1 );
    set_a.add( 2 );
    set_a.add( 3 );
    set_a.add( 4 );

    set_b.add( 1.f );
    set_b.add( 2.f );
    set_b.add( 3.f );
    set_b.add( 4.f );
    set_b.add( 5.f );
    set_b.add( 6.f );
    set_b.add( 7.f );
    set_b.add( 8.f );

    set_a.insert( set_b );
    AnyValueSet set_c;
    set_c.insert( set_a );

    {

        auto b_values = set_b.all<int>();
        for( const auto i : b_values )
        {
            ASSERT_TRUE( set_a.contains( i ) );
        }
        auto c_values = set_c.all<int>();
        for( const auto i : c_values )
        {
            ASSERT_TRUE( set_a.contains( i ) );
        }
        for( const auto i : b_values )
        {
            ASSERT_TRUE( set_c.contains( i ) );
        }
    }
    {
        
        auto b_values = set_b.all<float>();
        for( const auto i : b_values )
        {
            ASSERT_TRUE( set_a.contains( i ) );
        }
        auto c_values = set_c.all<float>();
        for( const auto i : c_values )
        {
            ASSERT_TRUE( set_a.contains( i ) );
        }
        for( const auto i : b_values )
        {
            ASSERT_TRUE( set_c.contains( i ) );
        }
    }
    
}

TEST( Test_AnyValueSet, copy_and_move )
{
    AnyValueSet set_a;
    set_a.add( 42 );

    AnyValueSet set_b = set_a;
    ASSERT_TRUE( set_a.contains( 42 ) );
    ASSERT_TRUE( set_b.contains( 42 ) );

    set_a.add( 33 );
    ASSERT_TRUE( set_a.contains( 33 ) );
    ASSERT_FALSE( set_b.contains( 33 ) );

    AnyValueSet set_c = std::move(set_a);
    ASSERT_FALSE( set_a.contains( 42 ) );
    ASSERT_FALSE( set_a.contains( 33 ) );
    ASSERT_TRUE( set_a.empty() );
    ASSERT_TRUE( set_c.contains( 42 ) );
    ASSERT_TRUE( set_c.contains( 33 ) );
    ASSERT_FALSE( set_c.empty() );

}