BaseSetDelta.h

Go to the documentation of this file.

 
#pragma once
#include "BaseSetDefaultTraits.h"
#include "BaseSetFindIterator.h"
#include "DeltaElements.h"
#include "catapult/utils/NonCopyable.h"
#include "catapult/exceptions.h"
#include <memory>
#include <type_traits>
#include <unordered_map>
 
namespace catapult { namespace deltaset {
 
    enum class InsertResult {
        Unremoved,
 
        Updated,
 
        Redundant,
 
        Inserted
    };
 
    enum class RemoveResult {
        None,
 
        Unmodified_And_Removed,
 
        Uninserted,
 
        Redundant,
 
        Removed
    };
 
    template<typename TSetTraits>
    class BaseSetDeltaIterationView;
 
    template<typename TElementTraits, typename TSetTraits>
    class BaseSetDelta : public utils::NonCopyable {
    public:
        using ElementType = typename TElementTraits::ElementType;
        using ElementMutabilityTag = typename TElementTraits::MutabilityTag;
 
        using SetType = typename TSetTraits::SetType;
        using MemorySetType = typename TSetTraits::MemorySetType;
 
        using KeyType = typename TSetTraits::KeyType;
        using FindTraits = FindTraitsT<ElementType, TSetTraits::AllowsNativeValueModification>;
        using SetTraits = TSetTraits;
 
        using FindIterator = std::conditional_t<
            std::is_same_v<ElementMutabilityTag, ImmutableTypeTag>,
            BaseSetDeltaFindConstIterator<FindTraits, TSetTraits>,
            BaseSetDeltaFindIterator<FindTraits, TSetTraits>
        >;
        using FindConstIterator = BaseSetDeltaFindConstIterator<FindTraits, TSetTraits>;
 
    public:
        explicit BaseSetDelta(const SetType& originalElements)
                : m_originalElements(originalElements)
                , m_generationId(1)
        {}
 
    public:
        bool empty() const {
            return 0 == size();
        }
 
        size_t size() const {
            return m_originalElements.size() - m_removedElements.size() + m_addedElements.size();
        }
 
    public:
        FindConstIterator find(const KeyType& key) const {
            return Find<FindConstIterator>(*this, key);
        }
 
        FindIterator find(const KeyType& key) {
            auto iter = Find<FindIterator>(*this, key);
            if (!!iter.get())
                markFoundElement(key, ElementMutabilityTag());
 
            return iter;
        }
 
    private:
        template<typename TResultIterator, typename TBaseSetDelta>
        static TResultIterator Find(TBaseSetDelta& set, const KeyType& key) {
            if (Contains(set.m_removedElements, key))
                return TResultIterator();
 
            auto originalIter = set.find(key, ElementMutabilityTag());
            if (originalIter.get())
                return originalIter;
 
            auto addedIter = set.m_addedElements.find(key);
            return set.m_addedElements.cend() != addedIter ? TResultIterator(std::move(addedIter)) : TResultIterator();
        }
 
        FindIterator find(const KeyType& key, MutableTypeTag) {
            auto copiedIter = m_copiedElements.find(key);
            if (m_copiedElements.cend() != copiedIter)
                return FindIterator(std::move(copiedIter));
 
            auto originalIter = find(key, ImmutableTypeTag());
            if (!originalIter.get())
                return FindIterator();
 
            auto copy = TElementTraits::Copy(originalIter.get());
            auto result = m_copiedElements.insert(SetTraits::ToStorage(copy));
            return FindIterator(std::move(result.first));
        }
 
        FindConstIterator find(const KeyType& key, MutableTypeTag) const {
            auto copiedIter = m_copiedElements.find(key);
            return m_copiedElements.cend() != copiedIter
                    ? FindConstIterator(std::move(copiedIter))
                    : find(key, ImmutableTypeTag());
        }
 
        FindConstIterator find(const KeyType& key, ImmutableTypeTag) const {
            auto originalIter = m_originalElements.find(key);
            return m_originalElements.cend() != originalIter ? FindConstIterator(std::move(originalIter)) : FindConstIterator();
        }
 
        void markFoundElement(const KeyType& key, MutableTypeTag) {
            markKey(key);
        }
 
        void markFoundElement(const KeyType&, ImmutableTypeTag) {
            // find can never modify an immutable element
        }
 
    public:
        bool contains(const KeyType& key) const {
            return !Contains(m_removedElements, key) && (Contains(m_addedElements, key) || Contains(m_originalElements, key));
        }
 
    private:
        template<typename TSet> // SetType or MemorySetType
        static constexpr bool Contains(const TSet& set, const KeyType& key) {
            return set.cend() != set.find(key);
        }
 
    public:
        InsertResult insert(const ElementType& element) {
            return insert(element, ElementMutabilityTag());
        }
 
        template<typename... TArgs>
        InsertResult emplace(TArgs&&... args) {
            return insert(ElementType(std::forward<TArgs>(args)...));
        }
 
    private:
        InsertResult insert(const ElementType& element, MutableTypeTag) {
            // copy the storage before erasing in case element is sourced from the same container being updated
            const auto& key = TSetTraits::ToKey(element);
            auto storage = TSetTraits::ToStorage(element);
            markKey(key);
 
            auto insertResult = InsertResult::Inserted;
            decltype(m_copiedElements)* pTargetElements;
            auto removedIter = m_removedElements.find(key);
            if (m_removedElements.cend() != removedIter) {
                m_removedElements.erase(removedIter);
                pTargetElements = Contains(m_addedElements, key) ? &m_addedElements : &m_copiedElements;
                insertResult = InsertResult::Unremoved;
            } else if (Contains(m_originalElements, key)) {
                pTargetElements = &m_copiedElements; // original element, possibly modified
                insertResult = InsertResult::Updated;
            } else {
                pTargetElements = &m_addedElements; // not an original element
                if (Contains(m_addedElements, key))
                    insertResult = InsertResult::Updated;
            }
 
            pTargetElements->erase(key);
            pTargetElements->insert(std::move(storage));
            return insertResult;
        }
 
        InsertResult insert(const ElementType& element, ImmutableTypeTag) {
            const auto& key = TSetTraits::ToKey(element);
            auto removedIter = m_removedElements.find(key);
            if (m_removedElements.cend() != removedIter) {
                // since element is immutable, always preserve the first seen element
                if (Contains(m_addedElements, key))
                    markKey(key);
                else
                    clearKey(key);
 
                m_removedElements.erase(removedIter);
                return InsertResult::Unremoved;
            }
 
            if (Contains(m_originalElements, key) || Contains(m_addedElements, key))
                return InsertResult::Redundant;
 
            markKey(key);
            m_addedElements.insert(TSetTraits::ToStorage(element));
            return InsertResult::Inserted;
        }
 
    public:
        RemoveResult remove(const KeyType& key) {
            if (Contains(m_removedElements, key))
                return RemoveResult::Redundant;
 
            return remove(key, ElementMutabilityTag());
        }
 
    private:
        RemoveResult remove(const KeyType& key, MutableTypeTag) {
            auto copiedIter = m_copiedElements.find(key);
            if (m_copiedElements.cend() != copiedIter) {
                markKey(key);
                m_removedElements.insert(*copiedIter);
                m_copiedElements.erase(copiedIter);
                return RemoveResult::Unmodified_And_Removed;
            }
 
            return remove(key, ImmutableTypeTag());
        }
 
        RemoveResult remove(const KeyType& key, ImmutableTypeTag) {
            auto addedIter = m_addedElements.find(key);
            if (m_addedElements.cend() != addedIter) {
                // in order for generations to work correctly, deltas must reflect removal of temporarily added elements
                // so that subsequent generation processing can process their removal
                //
                // consider:
                // 1. add(x) at generation y
                // 2. remove(x) at generation y+1
                //
                // processing at generation y+1 must be able to detect removal of x
                // chosen solution is to include x in both Added and Removed at generation y+1
                markKey(key);
                m_removedElements.insert(*addedIter);
                return RemoveResult::Uninserted;
            }
 
            auto originalIter = m_originalElements.find(key);
            if (m_originalElements.cend() != originalIter) {
                markKey(key);
                m_removedElements.insert(TSetTraits::ToStorage(key, std::move(originalIter)));
                return RemoveResult::Removed;
            }
 
            return RemoveResult::None;
        }
 
    public:
        DeltaElements<MemorySetType> deltas() const {
            return DeltaElements<MemorySetType>(m_addedElements, m_removedElements, m_copiedElements);
        }
 
        void reset() {
            m_addedElements.clear();
            m_removedElements.clear();
            m_copiedElements.clear();
 
            m_generationId = 1;
            m_keyGenerationIdMap.clear();
        }
 
    public:
        uint32_t generationId() const {
            return m_generationId;
        }
 
        uint32_t generationId(const KeyType& key) const {
            auto iter = m_keyGenerationIdMap.find(key);
            return m_keyGenerationIdMap.cend() == iter ? 0 : iter->second;
        }
 
        void incrementGenerationId() {
            ++m_generationId;
        }
 
    private:
        void markKey(const KeyType& key) {
            // latest generation id should always be stored
            m_keyGenerationIdMap[key] = m_generationId;
        }
 
        void clearKey(const KeyType& key) {
            m_keyGenerationIdMap.erase(key);
        }
 
    private:
        // for sorted containers, use map because no hasher is specified
        template<typename T, typename = void>
        struct KeyGenerationIdMap {
            using Type = std::map<KeyType, uint32_t, typename T::key_compare>;
        };
 
        // for hashed containers, use unordered_map because hasher is specified
        template<typename T>
        struct KeyGenerationIdMap<T, utils::traits::is_type_expression_t<typename T::hasher>> {
            using Type = std::unordered_map<KeyType, uint32_t, typename T::hasher, typename T::key_equal>;
        };
 
    private:
        const SetType& m_originalElements;
        MemorySetType m_addedElements;
        MemorySetType m_removedElements;
        MemorySetType m_copiedElements;
 
        uint32_t m_generationId;
        typename KeyGenerationIdMap<SetType>::Type m_keyGenerationIdMap;
 
    private:
        template<typename TElementTraits2, typename TSetTraits2>
        friend BaseSetDeltaIterationView<TSetTraits2> MakeIterableView(const BaseSetDelta<TElementTraits2, TSetTraits2>& set);
    };
}}