mde.hpp

Go to the documentation of this file.

 
#ifndef MDE_HPP
#define MDE_HPP
 
#include "mde_common.hpp"
#include "profiling.hpp"
 
#include <tuple>
#include <utility>
#include <algorithm>
 
namespace mde {
 
struct OperationNode {
    IndexValue left;
    IndexValue right;
 
    std::string to_string() const {
        std::stringstream s;
        s << "(" << left << "," << right << ")";
        return s.str();
    }
 
    bool operator<(const OperationNode &op) const {
        return (left < op.left) || (right < op.right);
    }
 
    bool operator==(const OperationNode &op) const {
        return (left == op.left) && (right == op.right);
    }
};
 
inline std::ostream &operator<<(std::ostream &os, const OperationNode &op) {
    return os << op.to_string();
}
 
} // END namespace mde
 
/************************** START GLOBAL NAMESPACE ****************************/
 
template <>
struct std::hash<mde::OperationNode> {
    mde::Size operator()(const mde::OperationNode& k) const {
        return
            std::hash<mde::IndexValue>()(k.left) ^
            (std::hash<mde::IndexValue>()(k.right) << 1);
    }
};
 
/************************** END GLOBAL NAMESPACE ******************************/
 
namespace mde {
 
template<typename OrderedSetT, typename ElementT, typename PropertyLess>
struct SetLess {
    bool operator()(const OrderedSetT *a, const OrderedSetT *b) const {
        PropertyLess less;
 
        auto cursor_1 = a->begin();
        const auto &cursor_end_1 = a->end();
        auto cursor_2 = b->begin();
        const auto &cursor_end_2 = b->end();
 
        while (cursor_1 != cursor_end_1 && cursor_2 != cursor_end_2) {
            if (less(*cursor_1, *cursor_2)) {
                return true;
            }
 
            if (less(*cursor_2, *cursor_1)) {
                return false;
            }
 
            cursor_1++;
            cursor_2++;
        }
 
        return a->size() < b->size();
    }
};
 
template<
    typename SetT,
    typename ElementT,
    typename ElementHash = DefaultHash<ElementT>>
struct SetHash {
    Size operator()(const SetT *k) const {
        // Adapted from boost::hash_combine
        size_t hash_value = 0;
        for (const auto &value : *k) {
            hash_value = compose_hash<ElementT, ElementHash>(hash_value, value);
        }
 
        return hash_value;
    }
};
 
template<
    typename SetT,
    typename ElementT,
    typename PropertyEqual = DefaultEqual<ElementT>>
struct SetEqual {
    inline bool operator()(const SetT *a, const SetT *b) const {
        PropertyEqual eq;
        if (a->size() != b->size()) {
            return false;
        }
 
        if (a->size() == 0) {
            return true;
        }
 
        auto cursor_1 = a->begin();
        const auto &cursor_end_1 = a->end();
        auto cursor_2 = b->begin();
 
        while (cursor_1 != cursor_end_1) {
            if (!eq(*cursor_1, *cursor_2)) {
                return false;
            }
 
            cursor_1++;
            cursor_2++;
        }
 
        return true;
    }
};
 
#ifdef MDE_ENABLE_TBB
 
template<typename T, typename Hash, typename Equal>
struct TBBHashCompare {
    Size hash(const T v) const {
        return Hash()(v);
    }
 
    bool equal(const T a, const T b) const {
        return Equal()(a, b);
    }
};
 
#endif
 
 
struct AssertError : public std::invalid_argument {
    AssertError(const std::string &message):
        std::invalid_argument(message.c_str()) {}
};
 
struct Unreachable : public std::runtime_error {
    Unreachable(const std::string &message = "Hit a branch marked as unreachable."):
        std::runtime_error(message.c_str()) {}
};
 
#define __MDE_EXCEPT(__msg) AssertError(__msg " [At: " __FILE__ ":" __MDE_STR(__LINE__) "]")
 
#ifdef MDE_DEBUG
#define __MDE_ASSERT(__cond, __msg_arg) \
    { if (!(__cond)) { __MDE_EXCEPT(__msg_arg); } }
#else
#define __MDE_ASSERT(__cond, __msg_arg)
#endif
 
 
template<typename PropertySetT, typename PropertyElementT>
static inline void verify_property_set_integrity(const PropertySetT &cont) {
    if (cont.size() == 1) {
        return;
    }
 
    std::unordered_set<
        PropertyElementT,
        typename PropertyElementT::Hash> k;
    const PropertyElementT *prev_val = nullptr;
 
    for (const PropertyElementT &val : cont) {
        if (prev_val && !(*prev_val < val)) {
            throw AssertError("Supplied property set is not sorted.");
        }
 
        if (k.count(val) > 0) {
            throw AssertError("Found duplicate key in given container.");
        } else {
            k.insert(val);
        }
 
        prev_val = &val;
    }
}
 
#ifndef MDE_DISABLE_INTEGRITY_CHECKS
#define MDE_PROPERTY_SET_INTEGRITY_VALID(__set) \
    verify_property_set_integrity<PropertySet, PropertyElement>(__set);
#else
#define MDE_PROPERTY_SET_INTEGRITY_VALID(__set)
#endif
 
 
#ifdef MDE_ENABLE_DEBUG
 
#define MDE_PROPERTY_SET_INDEX_VALID(__index) { \
    _Pragma("GCC diagnostic push"); \
    _Pragma("GCC diagnostic ignored \"-Wtype-limits\"") \
    if ((__index.value) < 0 || ((__index.value) > property_sets.size() - 1)) { \
        throw __MDE_EXCEPT("Invalid index supplied"); \
    } \
    _Pragma("GCC diagnostic pop") \
}
 
#define MDE_PROPERTY_SET_PAIR_VALID(__index1, __index2) \
    MDE_PROPERTY_SET_INDEX_VALID(__index1); \
    MDE_PROPERTY_SET_INDEX_VALID(__index2);
 
#define MDE_PROPERTY_SET_PAIR_UNEQUAL(__index1, __index2) \
    if ((__index1) == (__index2)) { \
        throw __MDE_EXCEPT("Equal set condition not handled by caller"); \
    }
 
#else
 
#define MDE_PROPERTY_SET_INDEX_VALID(__index)
#define MDE_PROPERTY_SET_PAIR_VALID(__index1, __index2)
#define MDE_PROPERTY_SET_PAIR_UNEQUAL(__index1, __index2)
 
#endif
 
#if defined(MDE_ENABLE_PARALLEL) && !defined(MDE_ENABLE_TBB)
#define MDE_PARALLEL(__x) __x
#else
#define MDE_PARALLEL(__x)
#endif
 
#ifdef MDE_ENABLE_EVICTION
#define MDE_EVICTION(__x) __x
#else
#define MDE_EVICTION(__x)
#endif
 
#define MDE_PUSH_ONE(__cont, __val) (__cont).push_back((__val))
 
#define MDE_PUSH_RANGE(__cont, __start, __end) (__cont).insert((__cont).end(), (__start), (__end))
 
 
#define MDE_REGISTER_SET_INTERNAL(__set, __cold) register_set<MDE_DISABLE_INTERNAL_INTEGRITY_CHECK>((__set), (__cold))
 
template<typename PropertyT>
struct NestingNone {
    static constexpr bool is_nested = false;
 
    static constexpr Size num_children = 0;
 
 
    using MDEReferenceList =  std::tuple<>;
 
    using ChildValueList = std::tuple<>;
 
    template<
        typename PropertyLess,
        typename PropertyHash,
        typename PropertyEqual,
        typename PropertyPrinter>
    struct PropertyElement {
    public:
        using InterfaceKeyType = PropertyT;
 
        using InterfaceValueType = PropertyT;
 
    protected:
        PropertyT value;
 
    public:
        PropertyElement(const PropertyT &value): value(value) {}
 
        const PropertyT &get_key() const {
            return value;
        }
 
        const PropertyT &get_value() const {
            return value;
        }
 
        PropertyElement apply() const {
            return *this;
        }
 
        bool operator<(const PropertyElement &b) const {
            return PropertyLess()(value, b.value);
        }
 
        bool operator==(const PropertyElement &b) const {
            return PropertyEqual()(value, b.value);
        }
 
        String to_string() const {
            return PropertyPrinter()(value);
        }
 
        friend std::ostream& operator<<(std::ostream& os, const PropertyElement& obj) {
            os << obj.to_string();
            return os;
        }
 
        struct Hash {
            Size operator()(const PropertyElement &p) const {
                return PropertyHash()(p.value);
            }
        };
 
        struct FullEqual {
            bool operator()(const PropertyElement &a, const PropertyElement &b) const {
                return PropertyEqual()(a.value, b.value);
            }
        };
    };
 
};
 
 
#define MDE_BINARY_NESTED_OPERATION(__op_name) \
    struct __NestingOperation_ ## __op_name { \
        template<typename ArgIndex, typename MDE> \
        void operator()(ArgIndex &ret, MDE &mde, const ArgIndex &c, const ArgIndex &d) { \
            ret = mde . __op_name (c, d); \
        } \
    };
 
#define MDE_PERFORM_BINARY_NESTED_OPERATION(__op_name, __reflist, __arg1, __arg2) \
    ((__arg1) . template apply<__NestingOperation_ ## __op_name>((__reflist), (__arg2)))
 
template<typename PropertyT, typename ...ChildT>
struct NestingBase {
    static constexpr bool is_nested = true;
 
    static constexpr Size num_children = sizeof...(ChildT);
 
    using MDEReferenceList = std::tuple<ChildT&...>;
 
    using ChildValueList = std::tuple<typename ChildT::Index...>;
 
    template<std::size_t ListIndex>
    using ChildValueListIndexType =
        typename std::tuple_element<ListIndex, ChildValueList>::type;
 
    template<
        typename PropertyLess,
        typename PropertyHash,
        typename PropertyEqual,
        typename PropertyPrinter>
    struct PropertyElement {
    public:
        using InterfaceKeyType = PropertyT;
 
        using InterfaceValueType = PropertyT;
 
    private:
        PropertyT _key;
        ChildValueList _value;
 
    public:
        PropertyElement(
            const PropertyT &key,
            const ChildValueList &value):
            _key(key),
            _value(value) {}
 
        const PropertyT &get_key() const {
            return _key;
        }
 
        const PropertyT &key() const {
            return _key;
        }
 
        const ChildValueList &get_value() const {
            return _value;
        }
 
        template<int ListIndex>
        const ChildValueListIndexType<ListIndex> &value() const {
            return std::get<ListIndex>(_value);
        }
 
        const ChildValueListIndexType<0> &value0() const {
            return std::get<0>(_value);
        }
 
        template <typename Operation, Size... Indices>
        void apply_internal(
            ChildValueList &ret,
            const MDEReferenceList &mde,
            const ChildValueList &arg_value,
            std::index_sequence<Indices...>) const {
            ((Operation()(std::get<Indices>(ret),
                std::get<Indices>(mde),
                std::get<Indices>(_value),
                std::get<Indices>(arg_value)
                )), ...);
        }
 
        template<typename Operation>
        PropertyElement apply(
            const MDEReferenceList &mde,
            const PropertyElement &arg) const {
            ChildValueList ret;
            apply_internal<Operation>(
                ret,
                mde,
                arg._value,
                std::make_index_sequence<num_children>{});
            return PropertyElement(_key, ret);
        }
 
        bool operator<(const PropertyElement &b) const {
            return PropertyLess()(_key, b._key);
        }
 
        bool operator==(const PropertyElement &b) const {
            return PropertyEqual()(_key, b._key);
        }
 
        String to_string() const {
            std::stringstream s;
            s << PropertyPrinter()(_key);
            s << " -> [ ";
            std::apply(
                [&s](auto&&... args) {
                    ((s << args.value << ' '), ...);
                }, _value);
            s << "]";
            return s.str();
        }
 
        friend std::ostream& operator<<(std::ostream& os, const PropertyElement& obj) {
            os << obj.to_string();
            return os;
        }
 
        struct Hash {
            Size operator()(const PropertyElement &p) const {
                return PropertyHash()(p._key);
            }
        };
 
        struct FullEqual {
            bool operator()(const PropertyElement &a, const PropertyElement &b) const {
                return PropertyEqual()(a._key, b._key) && (a._value == b._value);
            }
        };
    };
};
 
 
#ifdef MDE_ENABLE_TBB
 
template<typename MapClass>
class MapAdapter {
public:
    using Map = MapClass;
    using Key = typename Map::key_type;
    using MappedType = typename Map::mapped_type;
    using KeyValuePair = typename Map::value_type;
 
protected:
    using Accessor = typename Map::const_accessor;
    Map data;
 
public:
    Optional<MappedType> find(const Key &key) const {
        Accessor acc;
        bool found = data.find(acc, key);
        if (!found) {
            return Optional<MappedType>::absent();
        } else {
            return acc->second;
        }
    }
 
    void insert(KeyValuePair &&v) {
        data.insert(std::move(v));
    }
 
    void clear() {
        data.clear();
    }
 
    Size size() const {
        return data.size();
    }
 
    typename Map::const_iterator begin() const {
        return data.begin();
    }
 
    typename Map::const_iterator end() const {
        return data.end();
    }
 
    String to_string() const {
        std::stringstream s;
 
        for (auto i : data) {
            s << "      {" << i.first << " -> " << i.second << "} \n";
        }
 
        return s.str();
    }
 
};
 
#else
 
template<typename MapClass>
class MapAdapter {
public:
    using Map = MapClass;
    using Key = typename Map::key_type;
    using MappedType = typename Map::mapped_type;
    using KeyValuePair = typename Map::value_type;
 
protected:
    Map data;
    MDE_PARALLEL(mutable RWMutex mutex;)
 
public:
    Optional<MappedType> find(const Key &key) const {
        MDE_PARALLEL(ReadLock m(mutex);)
        auto value = data.find(key);
        if (value == data.end()) {
            return Optional<MappedType>::absent();
        } else {
            return value->second;
        }
    }
 
    void insert(KeyValuePair &&v) {
        MDE_PARALLEL(WriteLock m(mutex);)
        data.insert(std::move(v));
    }
 
    void clear() {
        MDE_PARALLEL(WriteLock m(mutex);)
        data.clear();
    }
 
    Size size() const {
        MDE_PARALLEL(ReadLock m(mutex);)
        return data.size();
    }
 
    typename Map::const_iterator begin() const {
        return data.begin();
    }
 
    typename Map::const_iterator end() const {
        return data.end();
    }
 
    String to_string() const {
        MDE_PARALLEL(ReadLock m(mutex);)
        std::stringstream s;
 
        for (auto i : data) {
            s << "      {" << i.first << " -> " << i.second << "} \n";
        }
 
        return s.str();
    }
 
};
 
#endif
 
 
#ifdef MDE_ENABLE_TBB
 
template<typename K, typename V>
using InternalMap = MapAdapter<tbb::concurrent_hash_map<K, V>>;
 
#else
 
template<typename K, typename V>
using InternalMap = MapAdapter<HashMap<K, V>>;
 
#endif
 
template<typename T>
using OperationMap =  InternalMap<T, IndexValue>;
 
struct OperationPerf {
    size_t hits = 0;
 
    size_t equal_hits = 0;
 
    size_t subset_hits = 0;
 
    size_t empty_hits = 0;
 
    size_t cold_misses = 0;
 
    size_t edge_misses = 0;
 
    String to_string() const {
        std::stringstream s;
        s << "      " << "Hits       : " << hits << "\n"
          << "      " << "Equal Hits : " << equal_hits << "\n"
          << "      " << "Subset Hits: " << subset_hits << "\n"
          << "      " << "Empty Hits : " << empty_hits << "\n"
          << "      " << "Cold Misses: " << cold_misses << "\n"
          << "      " << "Edge Misses: " << edge_misses << "\n";
        return s.str();
    }
};
 
#ifdef MDE_ENABLE_PERFORMANCE_METRICS
#define MDE_PERF_INC(__oper, __category) (perf[__MDE_STR(__oper)] . __category ++)
#else
#define MDE_PERF_INC(__oper, __category)
#endif
 
template <typename T>
struct MDEConfig {
    static constexpr const char* name = "";
 
    using PropertyT          = T;
    using PropertyLess       = DefaultLess<PropertyT>;
    using PropertyHash       = DefaultHash<PropertyT>;
    using PropertyEqual      = DefaultEqual<PropertyT>;
    using PropertyPrinter    = DefaultPrinter<PropertyT>;
 
    static constexpr Size BLOCK_SHIFT = MDE_DEFAULT_BLOCK_SHIFT;
    static constexpr Size BLOCK_SIZE  = MDE_DEFAULT_BLOCK_SIZE;
    static constexpr Size BLOCK_MASK  = MDE_DEFAULT_BLOCK_MASK;
};
 
template <
    typename Config,
    typename NestingT = NestingNone<typename Config::PropertyT>>
class MDENode {
public:
    using PropertyT          = typename Config::PropertyT;
    using PropertyLess       = typename Config::PropertyLess;
    using PropertyHash       = typename Config::PropertyHash;
    using PropertyEqual      = typename Config::PropertyEqual;
    using PropertyPrinter    = typename Config::PropertyPrinter;
    using Nesting            = NestingT;
 
    static constexpr const char *name = Config::name;
    static constexpr Size BLOCK_SIZE = Config::BLOCK_SIZE;
    static constexpr Size BLOCK_MASK = Config::BLOCK_MASK;
    static constexpr Size BLOCK_SHIFT = Config::BLOCK_SHIFT;
 
    struct Index {
        IndexValue value;
 
        Index(IndexValue idx = EMPTY_SET_VALUE): value(idx) {}
 
        bool is_empty() const {
            return value == EMPTY_SET_VALUE;
        }
 
        bool operator==(const Index &b) const {
            return value == b.value;
        }
 
        bool operator!=(const Index &b) const {
            return value != b.value;
        }
 
        bool operator<(const Index &b) const {
            return value < b.value;
        }
 
        bool operator>(const Index &b) const {
            return value > b.value;
        }
 
        String to_string() const {
            return std::to_string(value);
        }
 
        friend std::ostream& operator<<(std::ostream& os, const Index& obj) {
            os << obj.to_string();
            return os;
        }
 
        struct Hash {
            Size operator()(const Index &idx) const {
                return DefaultHash<IndexValue>()(idx.value);
            }
        };
    };
 
    using PropertyElement =
        typename Nesting::template PropertyElement<
            PropertyLess,
            PropertyHash,
            PropertyEqual,
            PropertyPrinter>;
 
    using PropertySet = std::vector<PropertyElement>;
 
    using PropertySetHash =
        SetHash<
            PropertySet,
            PropertyElement,
            typename PropertyElement::Hash>;
 
    using PropertySetFullEqual =
        SetEqual<
            PropertySet,
            PropertyElement,
            typename PropertyElement::FullEqual>;
 
#ifdef MDE_ENABLE_TBB
    using PropertySetMap =
        MapAdapter<tbb::concurrent_hash_map<
            const PropertySet *, IndexValue,
            TBBHashCompare<
                const PropertySet *,
                PropertySetHash,
                PropertySetFullEqual>>>;
#else
    using PropertySetMap =
        MapAdapter<std::unordered_map<
            const PropertySet *, IndexValue,
            PropertySetHash,
            PropertySetFullEqual>>;
#endif
 
    using UnaryOperationMap = OperationMap<IndexValue>;
    using BinaryOperationMap = OperationMap<OperationNode>;
    using RefList = typename Nesting::MDEReferenceList;
 
protected:
    RefList reflist;
 
#ifdef MDE_ENABLE_PERFORMANCE_METRICS
    PerformanceStatistics stat;
    HashMap<String, OperationPerf> perf;
#endif
 
    struct PropertySetHolder {
        using PtrContainer = UniquePointer<PropertySet>;
        using Ptr = typename PtrContainer::pointer;
 
        mutable PtrContainer ptr;
 
        PropertySetHolder(Ptr &&p): ptr(p) {}
 
        Ptr get() const {
            return ptr.get();
        }
 
        bool is_evicted() const {
#ifdef MDE_ENABLE_EVICTION
            return ptr.get() == nullptr;
#else
            return false;
#endif
        }
 
#ifdef MDE_ENABLE_EVICTION
 
        void evict() {
            __MDE_ASSERT(is_present(),
                "Tried to evict an already absent property set")
            ptr.release();
        }
 
        void reassign(Ptr &&p) {
            __MDE_ASSERT(!is_present(),
                "Tried to reassign when a property set is already present");
            ptr.reset(p);
        }
 
        void swap(PropertySetHolder &p) {
            __MDE_ASSERT(!is_present(),
                "Tried to reassign when a property set is already present");
            __MDE_ASSERT(p.is_present(),
                "Attempted to swap to a null pointer");
            ptr.swap(p.ptr);
        }
 
#endif
    };
 
#if defined(MDE_ENABLE_TBB)
 
    class PropertySetStorage {
    protected:
        //        is important for eviction to work.
        mutable tbb::concurrent_vector<PropertySetHolder> data = {};
 
    public:
        PropertySetHolder &at_mutable(const Index &idx) const {
            return data.at(idx.value);
        }
 
        const PropertySetHolder &at(const Index &idx) const {
            return data.at(idx.value);
        }
 
        Index push_back(PropertySetHolder &&p) {
            auto it = data.push_back(std::move(p));
            return it - data.begin();
        }
 
        void clear() {
            data.clear();
        }
 
        Size size() const {
            return data.size();
        }
 
 
    };
 
#elif defined(MDE_ENABLE_PARALLEL)
 
    class PropertySetStorage {
    protected:
        //        is important for eviction to work.
        mutable Vector<Vector<PropertySetHolder>> data = {};
 
        mutable RWMutex mutex;
        mutable RWMutex realloc_mutex;
 
        std::atomic<Size> total_elems = 0;
        std::atomic<Size> block_base = 0;
 
    public:
        PropertySetStorage() {
            data.push_back({});
            data.back().reserve(BLOCK_SIZE);
        }
 
        PropertySetHolder &at_mutable(const Index &idx) const {
            ReadLock m(realloc_mutex);
            if (idx.value >= block_base) {
                return data.back().at(idx.value & BLOCK_MASK);
            } else {
                return
                    data
                        .at((idx.value & (~BLOCK_MASK)) >> BLOCK_SHIFT)
                        .at(idx.value & BLOCK_MASK);
            }
        }
 
        const PropertySetHolder &at(const Index &idx) const {
            ReadLock m(realloc_mutex);
            if (idx.value >= block_base) {
                return data.back().at(idx.value & BLOCK_MASK);
            } else {
                return
                    data
                        .at((idx.value & (~BLOCK_MASK)) >> BLOCK_SHIFT)
                        .at(idx.value & BLOCK_MASK);
            }
        }
 
        Index push_back(PropertySetHolder &&p) {
            WriteLock m(mutex);
            __MDE_ASSERT(!data.empty(), "Internal error: no storage blocks avaialable.");
            if (data.back().size() >= BLOCK_SIZE) {
                WriteLock r(realloc_mutex);
                data.push_back({});
                data.back().reserve(BLOCK_SIZE);
                block_base += BLOCK_SIZE;
            }
            data.back().push_back(std::move(p));
            total_elems++;
            return Index(total_elems - 1);
        }
 
        void clear() {
            WriteLock m(mutex);
            data.clear();
            data.push_back({});
            total_elems = 0;
            block_base = 0;
        }
 
        Size size() const {
            return total_elems;
        }
    };
 
#else
 
    class PropertySetStorage {
    protected:
        //        is important for eviction to work.
        mutable Vector<PropertySetHolder> data = {};
 
    public:
        PropertySetHolder &at_mutable(const Index &idx) const {
            return data.at(idx.value);
        }
 
        const PropertySetHolder &at(const Index &idx) const {
            return data.at(idx.value);
        }
 
        Index push_back(PropertySetHolder &&p) {
            data.push_back(std::move(p));
            return data.size() - 1;
        }
 
        void clear() {
            data.clear();
        }
 
        Size size() const {
            return data.size();
        }
    };
 
#endif
 
    // The property set storage array.
    PropertySetStorage property_sets = {};
 
    // The property set -> Index in storage array mapping.
    PropertySetMap property_set_map = {};
 
    BinaryOperationMap unions = {};
    BinaryOperationMap intersections = {};
    BinaryOperationMap differences = {};
 
    InternalMap<OperationNode, SubsetRelation> subsets = {};
 
    void store_subset(const Index &a, const Index &b) {
        MDE_PROPERTY_SET_PAIR_VALID(a, b)
        MDE_PROPERTY_SET_PAIR_UNEQUAL(a, b)
        __mde_calc_functime(stat);
 
        // We need to maintain the operation pair in index-order here as well.
        if (a > b) {
            subsets.insert({{b.value, a.value}, SUPERSET});
        } else {
            subsets.insert({{a.value, b.value}, SUBSET});
        }
    }
 
    virtual void clear() {
        property_sets.clear();
        property_set_map.clear();
        unions.clear();
        intersections.clear();
        differences.clear();
        subsets.clear();
    }
 
public:
    explicit MDENode(RefList reflist = {}): reflist(reflist) {
        // INSERT EMPTY SET AT INDEX 0
        register_set({ });
    }
 
    inline bool is_empty(const Index &i) const {
        return i.is_empty();
    }
 
    void clear_and_initialize() {
        clear();
        register_set({ });
    }
 
    SubsetRelation is_subset(const Index &a, const Index &b) const {
        MDE_PROPERTY_SET_PAIR_VALID(a, b)
 
        auto i = subsets.find({a.value, b.value});
 
        if (!i.is_present()) {
            return UNKNOWN;
        } else {
            return i.get();
        }
    }
 
    Index register_set_single(const PropertyElement &c) {
        __mde_calc_functime(stat);
 
        PropertySetHolder new_set = PropertySetHolder(new PropertySet{c});
 
        auto result = property_set_map.find(new_set.get());
 
        if (!result.is_present()) {
            MDE_PERF_INC(property_sets, cold_misses);
 
            Index ret = property_sets.push_back(std::move(new_set));
            property_set_map.insert(std::make_pair(property_sets.at(ret).get(), ret.value));
 
            return ret;
        }
        MDE_EVICTION(else if (is_evicted(result.get())) {
            property_sets.at_mutable(result.get()).swap(new_set);
            return Index(result.get());
        })
        else {
            MDE_PERF_INC(property_sets, hits);
            return Index(result.get());
        }
    }
 
    Index register_set_single(const PropertyElement &c, bool &cold) {
        __mde_calc_functime(stat);
 
        PropertySetHolder new_set = PropertySetHolder(new PropertySet{c});
        auto result = property_set_map.find(new_set.get());
 
        if (!result.is_present()) {
            MDE_PERF_INC(property_sets, cold_misses);
 
            Index ret = property_sets.push_back(std::move(new_set));
            property_set_map.insert(std::make_pair(property_sets.at(ret).get(), ret.value));
 
            cold = true;
            return ret;
        }
        MDE_EVICTION(else if (is_evicted(result.get())) {
            property_sets.at_mutable(result.get()).swap(new_set);
            cold = false;
            return Index(result.get());
        })
        else {
            MDE_PERF_INC(property_sets, hits);
            cold = false;
            return Index(result.get());
        }
    }
 
    void prepare_vector_set(PropertySet &c) {
        std::unordered_set<
            PropertyElement,
            typename PropertyElement::Hash,
            typename PropertyElement::FullEqual> deduplicator;
 
        for (auto &i : c) {
            deduplicator.insert(i);
        }
 
        c.assign(deduplicator.begin(), deduplicator.end());
        std::sort(c.begin(), c.end());
    }
 
    template <bool disable_integrity_check = false>
    Index register_set(const PropertySet &c) {
        __mde_calc_functime(stat);
 
        if (!disable_integrity_check) {
            MDE_PROPERTY_SET_INTEGRITY_VALID(c);
        }
 
        auto result = property_set_map.find(&c);
 
        if (!result.is_present()) {
            MDE_PERF_INC(property_sets, cold_misses);
 
            PropertySetHolder new_set(new PropertySet(c));
            Index ret = property_sets.push_back(std::move(new_set));
            property_set_map.insert(std::make_pair(property_sets.at(ret).get(), ret.value));
            return ret;
        }
        MDE_EVICTION(else if (is_evicted(result.get())) {
            property_sets.at_mutable(result.get()).reassign(new PropertySet(c));
            return Index(result.get());
        })
        else {
            MDE_PERF_INC(property_sets, hits);
            return Index(result.get());
        }
    }
 
    template <bool disable_integrity_check = false>
    Index register_set(const PropertySet &c, bool &cold) {
        __mde_calc_functime(stat);
 
        if (!disable_integrity_check) {
            MDE_PROPERTY_SET_INTEGRITY_VALID(c);
        }
 
        auto result = property_set_map.find(&c);
 
        if (!result.is_present()) {
            MDE_PERF_INC(property_sets, cold_misses);
 
            PropertySetHolder new_set(new PropertySet(c));
            Index ret = property_sets.push_back(std::move(new_set));
            property_set_map.insert(std::make_pair(property_sets.at(ret).get(), ret.value));
 
            cold = true;
            return ret;
        }
        MDE_EVICTION(else if (is_evicted(result.get())) {
            property_sets.at_mutable(result.get()).reassign(new PropertySet(c));
            cold = false;
            return Index(result.get());
        })
        else {
            MDE_PERF_INC(property_sets, hits);
            cold = false;
            return Index(result.get());
        }
    }
 
    template <bool disable_integrity_check = false>
    Index register_set(PropertySet &&c) {
        __mde_calc_functime(stat);
 
        if (!disable_integrity_check) {
            MDE_PROPERTY_SET_INTEGRITY_VALID(c);
        }
 
        auto result = property_set_map.find(&c);
 
        if (!result.is_present()) {
            MDE_PERF_INC(property_sets, cold_misses);
 
            PropertySetHolder new_set(new PropertySet(std::move(c)));
            Index ret = property_sets.push_back(std::move(new_set));
            property_set_map.insert(std::make_pair(property_sets.at(ret).get(), ret.value));
            return ret;
        }
        MDE_EVICTION(else if (is_evicted(result.get())) {
            property_sets.at_mutable(result.get()).reassign(new PropertySet(c));
            return Index(result.get());
        })
        else {
            MDE_PERF_INC(property_sets, hits);
            return Index(result.get());
        }
    }
 
    template <bool disable_integrity_check = false>
    Index register_set(PropertySet &&c, bool &cold) {
        __mde_calc_functime(stat);
 
        if (!disable_integrity_check) {
            MDE_PROPERTY_SET_INTEGRITY_VALID(c);
        }
 
        auto result = property_set_map.find(&c);
 
        if (!result.is_present()) {
            MDE_PERF_INC(property_sets, cold_misses);
 
            PropertySetHolder new_set(new PropertySet(std::move(c)));
            Index ret = property_sets.push_back(std::move(new_set));
            property_set_map.insert(std::make_pair(property_sets.at(ret).get(), ret.value));
 
            cold = true;
            return ret;
        }
        MDE_EVICTION(else if (is_evicted(result.get())) {
            property_sets.at_mutable(result.get()).reassign(new PropertySet(c));
            cold = false;
            return Index(result.get());
        })
        else {
            MDE_PERF_INC(property_sets, hits);
            cold = false;
            return Index(result.get());
        }
    }
 
    template<typename Iterator, bool disable_integrity_check = false>
    Index register_set(Iterator begin, Iterator end) {
        __mde_calc_functime(stat);
 
        PropertySetHolder new_set(new PropertySet(begin, end));
 
        if (!disable_integrity_check) {
            MDE_PROPERTY_SET_INTEGRITY_VALID(*new_set.get());
        }
 
        auto result = property_set_map.find(new_set.get());
 
        if (!result.is_present()) {
            MDE_PERF_INC(property_sets, cold_misses);
 
            Index ret = property_sets.push_back(std::move(new_set));
            property_set_map.insert(std::make_pair(property_sets.at(ret).get(), ret.value));
            return ret;
        }
        MDE_EVICTION(else if (is_evicted(result.get())) {
            property_sets.at_mutable(result.get()).reassign(std::move(new_set));
            return Index(result.get());
        })
        else {
            MDE_PERF_INC(property_sets, hits);
            return Index(result.get());
        }
    }
 
    template<typename Iterator, bool disable_integrity_check = false>
    Index register_set(Iterator begin, Iterator end, bool &cold) {
        __mde_calc_functime(stat);
 
        PropertySetHolder new_set(new PropertySet(begin, end));
 
        if (!disable_integrity_check) {
            MDE_PROPERTY_SET_INTEGRITY_VALID(*new_set.get());
        }
 
        auto result = property_set_map.find(new_set.get());
 
        if (!result.is_present()) {
            MDE_PERF_INC(property_sets, cold_misses);
 
            Index ret = property_sets.push_back(std::move(new_set));
            property_set_map.insert(std::make_pair(property_sets.at(ret).get(), ret.value));
            cold = true;
            return ret;
        }
        MDE_EVICTION(else if (is_evicted(result.get())) {
            property_sets.at_mutable(result.get()).reassign(std::move(new_set));
            cold = false;
            return Index(result.get());
        })
        else {
            MDE_PERF_INC(property_sets, hits);
            cold = false;
            return Index(result.get());
        }
    }
 
#ifdef MDE_ENABLE_EVICTION
    bool is_evicted(const Index &index) const {
        return property_sets.at(index.value).is_evicted();
    }
#endif
 
#ifdef MDE_ENABLE_EVICTION
    void evict_set(const Index &index) {
        __MDE_ASSERT(!index.is_empty(),
            "Tried to evict the empty set");
        property_sets.at_mutable(index.value).evict();
    }
#endif
 
    inline const PropertySet &get_value(const Index &index) const {
        MDE_PROPERTY_SET_INDEX_VALID(index);
#if defined(MDE_DEBUG) && defined(MDE_ENABLE_EVICTION)
        __MDE_ASSERT(!is_evicted(index),
            "Tried to access an evicted set");
#endif
        return *property_sets.at(index.value).get();
    }
 
    inline Size property_set_count() const {
        return property_sets.size();
    }
 
    inline Size size_of(const Index &index) const {
        if (index == EMPTY_SET_VALUE) {
            return 0;
        } else {
            return get_value(index).size();
        }
    }
 
    static inline bool less(const PropertyElement &a, const PropertyElement &b) {
        return a < b;
    }
 
    static inline bool less_key(const PropertyElement &a, const PropertyT &b) {
        return PropertyLess()(a.get_key(), b);
    }
 
    static inline bool less_key(const PropertyElement &a, const PropertyElement &b) {
        return PropertyLess()(a.get_key(), b.get_key());
    }
 
    static inline bool equal(const PropertyElement &a, const PropertyElement &b) {
        return a == b;
    }
 
    static inline bool equal_key(const PropertyElement &a, const PropertyT &b) {
        return PropertyEqual()(a.get_key(), b);
    }
 
    static inline bool equal_key(const PropertyElement &a, const PropertyElement &b) {
        return PropertyEqual()(a.get_key(), b.get_key());
    }
 
    inline OptionalRef<PropertyElement> find_key(const Index &index, const PropertyT &p) const {
        if (is_empty(index)) {
            return OptionalRef<PropertyElement>::absent();
        }
 
        const PropertySet &s = get_value(index);
 
        if (s.size() <= MDE_SORTED_VECTOR_BINARY_SEARCH_THRESHOLD) {
            for (const PropertyElement &i : s) {
                if (equal_key(i, p)) {
                    return OptionalRef<PropertyElement>(i);
                }
            }
        } else {
            // Binary search implementation
            long int low = 0;
            long int high = s.size() - 1;
 
            while (low <= high) {
                long int mid = low + (high - low) / 2;
 
                if (equal_key(s[mid], p)) {
                    return OptionalRef<PropertyElement>(s[mid]);
                } else if (less_key(s[mid], p)) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
 
        return OptionalRef<PropertyElement>::absent();
    }
 
    inline bool contains(const Index &index, const PropertyElement &prop) const {
        if (is_empty(index)) {
            return false;
        }
 
        const PropertySet &s = get_value(index);
 
        if (s.size() <= MDE_SORTED_VECTOR_BINARY_SEARCH_THRESHOLD) {
            for (PropertyElement i : s) {
                if (equal_key(i, prop)) {
                    return true;
                }
            }
        } else {
            // Binary search implementation
            std::int64_t low = 0;
            std::int64_t high = s.size() - 1;
 
            while (low <= high) {
                long int mid = low + (high - low) / 2;
                if (equal_key(s[mid], prop)) {
                    return true;
                } else if (less_key(s[mid], prop)) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
 
        return false;
    }
 
    MDE_BINARY_NESTED_OPERATION(set_union)
    Index set_union(const Index &_a, const Index &_b) {
        MDE_PROPERTY_SET_PAIR_VALID(_a, _b);
        __mde_calc_functime(stat);
 
        if (_a == _b) {
            MDE_PERF_INC(unions, equal_hits);
            return Index(_a);
        }
 
        if (is_empty(_a)) {
            MDE_PERF_INC(unions, empty_hits);
            return Index(_b);
        } else if (is_empty(_b)) {
            MDE_PERF_INC(unions,empty_hits);
            return Index(_a);
        }
 
        const Index &a = std::min(_a, _b);
        const Index &b = std::max(_a, _b);
 
        SubsetRelation r = is_subset(a, b);
 
        if (r == SUBSET) {
            MDE_PERF_INC(unions, subset_hits);
            return Index(b);
        } else if (r == SUPERSET) {
            MDE_PERF_INC(unions, subset_hits);
            return Index(a);
        }
 
        auto result = unions.find({a.value, b.value});
 
        if (!result.is_present() MDE_EVICTION(|| is_evicted(result.get()))) {
            PropertySet new_set;
            const PropertySet &first = get_value(a);
            const PropertySet &second = get_value(b);
 
            // The union implementation here is adapted from the example
            // suggested implementation provided of std::set_union from
            // cppreference.com
            auto cursor_1 = first.begin();
            const auto &cursor_end_1 = first.end();
            auto cursor_2 = second.begin();
            const auto &cursor_end_2 = second.end();
 
            while (cursor_1 != cursor_end_1) {
                if (cursor_2 == cursor_end_2) {
                    MDE_PUSH_RANGE(new_set, cursor_1, cursor_end_1);
                    break;
                }
 
                if (less(*cursor_2, *cursor_1)) {
                    MDE_PUSH_ONE(new_set, *cursor_2);
                    cursor_2++;
                } else {
                    if (!(less(*cursor_1, *cursor_2))) {
                        if constexpr (Nesting::is_nested) {
                            PropertyElement new_elem =
                                MDE_PERFORM_BINARY_NESTED_OPERATION(
                                    set_union, reflist, *cursor_1, *cursor_2);
                            MDE_PUSH_ONE(new_set, new_elem);
                        } else {
                            MDE_PUSH_ONE(new_set, *cursor_1);
                        }
                        cursor_2++;
                    } else {
                        MDE_PUSH_ONE(new_set, *cursor_1);
                    }
                    cursor_1++;
                }
            }
 
            MDE_PUSH_RANGE(new_set, cursor_2, cursor_end_2);
 
            bool cold = false;
            Index ret;
 
            MDE_EVICTION(if (result.is_present() && is_evicted(result.get())) {
                ret = result.get();
                property_sets.at_mutable(ret).reassign(new PropertySet(std::move(new_set)));
            } else) {
                ret = MDE_REGISTER_SET_INTERNAL(std::move(new_set), cold);
 
                unions.insert({{a.value, b.value}, ret.value});
 
                if (ret == a) {
                    store_subset(b, ret);
                } else if (ret == b) {
                    store_subset(a, ret);
                } else {
                    store_subset(a, ret);
                    store_subset(b, ret);
                }
            }
 
            if (cold) {
                MDE_PERF_INC(unions, cold_misses);
            } else {
                MDE_PERF_INC(unions, edge_misses);
            }
 
            return Index(ret);
        } else {
            MDE_PERF_INC(unions, hits);
            return Index(result.get());
        }
    }
 
    Index set_insert_single(const Index &a, const PropertyElement &b) {
        return set_union(a, register_set_single(b));
    }
 
    MDE_BINARY_NESTED_OPERATION(set_difference)
    Index set_difference(const Index &a, const Index &b) {
        MDE_PROPERTY_SET_PAIR_VALID(a, b);
        __mde_calc_functime(stat);
 
        if (a == b) {
            MDE_PERF_INC(differences, equal_hits);
            return Index(EMPTY_SET_VALUE);
        }
 
        if (is_empty(a)) {
            MDE_PERF_INC(differences, empty_hits);
            return Index(EMPTY_SET_VALUE);
        } else if (is_empty(b)) {
            MDE_PERF_INC(differences, empty_hits);
            return Index(a);
        }
 
        auto result = differences.find({a.value, b.value});
 
        if (!result.is_present() MDE_EVICTION(|| is_evicted(result.get()))) {
            PropertySet new_set;
            const PropertySet &first = get_value(a);
            const PropertySet &second = get_value(b);
 
            // The difference implementation here is adapted from the example
            // suggested implementation provided of std::set_difference from
            // cppreference.com
            auto cursor_1 = first.begin();
            const auto &cursor_end_1 = first.end();
            auto cursor_2 = second.begin();
            const auto &cursor_end_2 = second.end();
 
            while (cursor_1 != cursor_end_1) {
                if (cursor_2 == cursor_end_2) {
                    MDE_PUSH_RANGE(new_set, cursor_1, cursor_end_1);
                    break;
                }
 
                if (less(*cursor_1, *cursor_2)) {
                    MDE_PUSH_ONE(new_set, *cursor_1);
                    cursor_1++;
                } else {
                    if (!(less(*cursor_2, *cursor_1))) {
                        if constexpr (Nesting::is_nested) {
                            PropertyElement new_elem =
                                MDE_PERFORM_BINARY_NESTED_OPERATION(
                                    set_difference, reflist, *cursor_1, *cursor_2);
                            MDE_PUSH_ONE(new_set, new_elem);
                        }
                        cursor_1++;
                    }
                    cursor_2++;
                }
            }
 
            bool cold = false;
            Index ret;
 
            MDE_EVICTION(if (result.is_present() && is_evicted(result.get())) {
                ret = result.get();
                property_sets.at_mutable(ret).reassign(new PropertySet(std::move(new_set)));
            } else) {
                ret = MDE_REGISTER_SET_INTERNAL(std::move(new_set), cold);
                differences.insert({{a.value, b.value}, ret.value});
 
                if (ret != a) {
                    store_subset(ret, a);
                } else {
                    intersections.insert({
                        {
                            std::min(a.value, b.value),
                            std::max(a.value, b.value)
                        }, EMPTY_SET_VALUE});
                }
            }
 
            if (cold) {
                MDE_PERF_INC(differences, cold_misses);
            } else {
                MDE_PERF_INC(differences, edge_misses);
            }
 
            return Index(ret);
        } else {
            MDE_PERF_INC(differences, hits);
            return Index(result.get());
        }
    }
 
    Index set_remove_single(const Index &a, const PropertyElement &b) {
        return set_difference(a, register_set_single(b));
    }
 
    Index set_remove_single_key(const Index &a, const PropertyT &p) {
        PropertySet new_set;
        const PropertySet &first = get_value(a);
 
        auto cursor_1 = first.begin();
        const auto &cursor_end_1 = first.end();
 
        for (;cursor_1 != cursor_end_1; cursor_1++) {
            if (!PropertyEqual()(cursor_1->get_key(), p)) {
                MDE_PUSH_ONE(new_set, *cursor_1);
            }
        }
        return register_set<true>(std::move(new_set));
    }
 
    MDE_BINARY_NESTED_OPERATION(set_intersection)
    Index set_intersection(const Index &_a, const Index &_b) {
        MDE_PROPERTY_SET_PAIR_VALID(_a, _b);
        __mde_calc_functime(stat);
 
        if (_a == _b) {
            MDE_PERF_INC(intersections, equal_hits);
            return Index(_a);
        }
 
        if (is_empty(_a) || is_empty(_b)) {
            MDE_PERF_INC(intersections, empty_hits);
            return Index(EMPTY_SET_VALUE);
        }
 
        const Index &a = std::min(_a, _b);
        const Index &b = std::max(_a, _b);
 
        SubsetRelation r = is_subset(a, b);
 
        if (r == SUBSET) {
            MDE_PERF_INC(intersections, subset_hits);
            return Index(a);
        } else if (r == SUPERSET) {
            MDE_PERF_INC(intersections, subset_hits);
            return Index(b);
        }
 
        auto result = intersections.find({a.value, b.value});
 
        if (!result.is_present() MDE_EVICTION(|| is_evicted(result.get()))) {
            PropertySet new_set;
            const PropertySet &first = get_value(a);
            const PropertySet &second = get_value(b);
 
            // The intersection implementation here is adapted from the example
            // suggested implementation provided for std::set_intersection from
            // cppreference.com
            auto cursor_1 = first.begin();
            const auto &cursor_end_1 = first.end();
            auto cursor_2 = second.begin();
            const auto &cursor_end_2 = second.end();
 
            while (cursor_1 != cursor_end_1 && cursor_2 != cursor_end_2)
            {
                if (less(*cursor_1,*cursor_2)) {
                    cursor_1++;
                } else {
                    if (!(less(*cursor_2, *cursor_1))) {
                        if constexpr (Nesting::is_nested) {
                            PropertyElement new_elem =
                                MDE_PERFORM_BINARY_NESTED_OPERATION(set_intersection, reflist, *cursor_1, *cursor_2);
                            MDE_PUSH_ONE(new_set, new_elem);
                        } else {
                            MDE_PUSH_ONE(new_set, *cursor_1);
                        }
                        cursor_1++;
                    }
                    cursor_2++;
                }
            }
 
            bool cold = false;
            Index ret;
 
            MDE_EVICTION(if (result.is_present() && is_evicted(result.get())) {
                ret = result.get();
                property_sets.at_mutable(ret).reassign(new PropertySet(std::move(new_set)));
            } else){
                ret = MDE_REGISTER_SET_INTERNAL(std::move(new_set), cold);
                intersections.insert({{a.value, b.value}, ret.value});
 
                if (ret != a) {
                    store_subset(ret, a);
                } else if (ret != b) {
                    store_subset(ret, b);
                } else {
                    store_subset(ret, a);
                    store_subset(ret, b);
                }
            }
 
            if (cold) {
                MDE_PERF_INC(intersections, cold_misses);
            } else {
                MDE_PERF_INC(intersections, edge_misses);
            }
            return Index(ret);
        }
 
        MDE_PERF_INC(intersections, hits);
        return Index(result.get());
    }
 
 
    Index set_filter(
        Index s,
        std::function<bool(const PropertyElement &)> filter_func,
        UnaryOperationMap &cache) {
        MDE_PROPERTY_SET_INDEX_VALID(s);
        __mde_calc_functime(stat);
 
        if (is_empty(s)) {
            return s;
        }
 
        auto result = cache.find(s.value);
 
        if (!result.is_present() MDE_EVICTION(|| is_evicted(result.get()))) {
            PropertySet new_set;
            for (const PropertyElement &value : get_value(s)) {
                if (filter_func(value)) {
                    MDE_PUSH_ONE(new_set, value);
                }
            }
 
            bool cold;
            Index ret;
 
            MDE_EVICTION(if (result.is_present() && is_evicted(result.get())) {
                ret = result.get();
                property_sets.at_mutable(ret).reassign(new PropertySet(std::move(new_set)));
            } else) {
                ret = MDE_REGISTER_SET_INTERNAL(std::move(new_set), cold);
                cache.insert(std::make_pair(s.value, ret.value));
            }
 
            if (cold) {
                MDE_PERF_INC(filter, cold_misses);
            } else {
                MDE_PERF_INC(filter, edge_misses);
            }
 
            return Index(ret);
        } else {
            MDE_PERF_INC(filter, hits);
            return Index(result.get());
        }
    }
 
    static String property_set_to_string(const PropertySet &set) {
        std::stringstream s;
        s << "{ ";
        for (const PropertyElement &p : set) {
            s << p.to_string() << " ";
        }
        s << "}";
 
        return s.str();
    }
 
    String property_set_to_string(const Index &idx) const {
        return property_set_to_string(get_value(idx));
    }
 
#ifdef MDE_ENABLE_SERIALIZATION
 
    const RefList &get_reflist() const {
        return reflist;
    }
 
    virtual slz::JSON operations_to_json() const {
        slz::JSON ret = slz::JSON::object();
        ret["unions"]        = slz::binary_operation_map_to_json(unions);
        ret["intersections"] = slz::binary_operation_map_to_json(intersections);
        ret["differences"]   = slz::binary_operation_map_to_json(differences);
        ret["subsets"]       = slz::binary_operation_map_to_json(subsets);
        return ret;
    }
 
    virtual void operations_from_json(const slz::JSON &obj) {
        std::cout << obj.dump() << std::endl;
        slz::binary_operation_map_from_json(unions, obj["unions"]);
        slz::binary_operation_map_from_json(intersections, obj["intersections"]);
        slz::binary_operation_map_from_json(differences, obj["differences"]);
        slz::binary_operation_map_from_json(subsets, obj["subsets"]);
    }
 
    template<typename Serializer =
        slz::DefaultValueSerializer<PropertyT>>
    slz::JSON to_json(Serializer &s) const {
        slz::JSON ret = slz::JSON::object();
 
        if constexpr (Nesting::is_nested) {
            ret["property_sets"] =
                slz::storage_array_to_json_nested(property_sets, s);
        } else {
            ret["property_sets"] =
                slz::storage_array_to_json(property_sets, s);
        }
 
        ret["operations"] = operations_to_json();
 
        return ret;
    }
 
    template<typename Serializer =
        slz::DefaultValueSerializer<PropertyT>>
    slz::JSON to_json() const {
        auto s = Serializer();
        return to_json(s);
    }
 
    template<typename Serializer =
        slz::DefaultValueSerializer<PropertyT>>
    void load_from_json(const slz::JSON &obj, Serializer &s) {
        clear();
        operations_from_json(obj["operations"]);
        if constexpr (Nesting::is_nested) {
            slz::register_storage_from_json_nested(*this, obj["property_sets"], s);
        } else {
            slz::register_storage_from_json(*this, obj["property_sets"], s);
        }
    }
 
    template<typename Serializer =
        slz::DefaultValueSerializer<PropertyT>>
    void load_from_json(const slz::JSON &obj) {
        auto s = Serializer();
        load_from_json(obj, s);
    }
 
#endif
 
    String dump() const {
        std::stringstream s;
 
        s << "{\n";
 
        s << "    " << "Unions: " << "(Count: " << unions.size() << ")\n";
        s << unions.to_string();
        s << "\n";
 
        s << "    " << "Differences:" << "(Count: " << differences.size() << ")\n";
        s << differences.to_string();
        s << "\n";
 
        s << "    " << "Intersections: " << "(Count: " << intersections.size() << ")\n";
        s << intersections.to_string();
        s << "\n";
 
        s << "    " << "Subsets: " << "(Count: " << subsets.size() << ")\n";
        for (auto i : subsets) {
            s << "      " << i.first << " -> " << (i.second == SUBSET ? "sub" : "sup") << "\n";
        }
        s << "\n";
 
        s << "    " << "PropertySets: " << "(Count: " << property_sets.size() << ")\n";
        for (size_t i = 0; i < property_sets.size(); i++) {
            s << "      "
                << i << " : " << property_set_to_string(*property_sets.at(i).get()) << "\n";
        }
        s << "}\n";
 
        return s.str();
    }
 
    friend std::ostream& operator<<(std::ostream& os, const MDENode& obj) {
        os << obj.dump();
        return os;
    }
 
#ifdef MDE_ENABLE_PERFORMANCE_METRICS
    String dump_perf() const {
        std::stringstream s;
        s << "Performance Profile: \n";
        for (auto &p : perf) {
            s << p.first << "\n"
              << p.second.to_string() << "\n";
        }
        s << stat.dump();
        return s.str();
    }
#endif
 
}; // END MDENode
 
 
#define MDE_PROPERTY_INDEX_VALID(__index) { \
    _Pragma("GCC diagnostic push"); \
    _Pragma("GCC diagnostic ignored \"-Wtype-limits\"") \
    if ((__index.value) < 0 || ((__index.value) > property_list.size() - 1)) { \
        throw __MDE_EXCEPT("Invalid index supplied"); \
    } \
    _Pragma("GCC diagnostic pop") \
}
 
template <
    typename PropertyT,
    typename PropertyHash = DefaultHash<PropertyT>,
    typename PropertyEqual = DefaultEqual<PropertyT>,
    typename PropertyPrinter = DefaultPrinter<PropertyT>>
struct Deduplicator {
    struct Index {
        IndexValue value;
 
        Index(IndexValue idx = EMPTY_SET_VALUE): value(idx) {}
 
        bool is_empty() const {
            return value == EMPTY_SET_VALUE;
        }
 
        bool operator==(const Index &b) const {
            return value == b.value;
        }
 
        bool operator!=(const Index &b) const {
            return value != b.value;
        }
 
        bool operator<(const Index &b) const {
            return value < b.value;
        }
 
        bool operator>(const Index &b) const {
            return value > b.value;
        }
 
        String to_string() const {
            return std::to_string(value);
        }
 
        friend std::ostream& operator<<(std::ostream& os, const Index& obj) {
            os << obj.to_string();
            return os;
        }
 
        struct Hash {
            Size operator()(const Index &idx) const {
                return DefaultHash<IndexValue>()(idx.value);
            }
        };
    };
 
    struct PropertyPtrHash {
        Size operator()(const PropertyT *p) const {
            return PropertyHash()(*p);
        }
    };
 
    struct PropertyPtrEqual {
        Size operator()(const PropertyT *a, const PropertyT *b) const {
            return PropertyEqual()(*a, *b);
        }
    };
 
    using PropertyMap =
        std::unordered_map<
            PropertyT *, IndexValue,
            PropertyPtrHash,
            PropertyPtrEqual>;
 
    // The property storage array.
    Vector<UniquePointer<PropertyT>> property_list = {};
 
    // The property -> Index in storage array mapping.
    PropertyMap property_map = {};
 
    Index register_value(PropertyT &c) {
        auto cursor = property_map.find(&c);
 
        if (cursor == property_map.end()) {
            UniquePointer<PropertyT> new_value =
                UniquePointer<PropertyT>(new PropertyT(c));
            property_list.push_back(std::move(new_value));
            IndexValue ret = property_list.size() - 1;
            property_map.insert(std::make_pair(property_list[ret].get(), ret));
            return Index(ret);
        }
        return Index(cursor->second);
    }
 
    Index register_value(PropertyT &&c) {
        auto cursor = property_map.find(&c);
 
        if (cursor == property_map.end()) {
            UniquePointer<PropertyT> new_value =
                UniquePointer<PropertyT>(new PropertyT(std::move(c)));
            property_list.push_back(std::move(new_value));
            IndexValue ret = property_list.size() - 1;
            property_map.insert(std::make_pair(property_list[ret].get(), ret));
            return Index(ret);
        }
        return Index(cursor->second);
    }
 
    Index register_ptr(PropertyT *c) {
        auto cursor = property_map.find(c);
 
        if (cursor == property_map.end()) {
            UniquePointer<PropertyT> new_value = UniquePointer<PropertyT>(c);
            property_list.push_back(std::move(new_value));
            IndexValue ret = property_list.size() - 1;
            property_map.insert(std::make_pair(property_list[ret].get(), ret));
            return Index(ret);
        }
        delete c;
        return Index(cursor->second);
    }
 
    Size get_property_count() const {
        return property_list.size();
    }
 
    const PropertyT &get_value(Index id) const {
        MDE_PROPERTY_INDEX_VALID(id);
        return *property_list[id.value].get();
    }
 
    const PropertyT *get_value_ptr(Index id) const {
        MDE_PROPERTY_INDEX_VALID(id);
        return property_list[id.value].get();
    }
 
    std::string dump() const {
        std::stringstream s;
        s << "Deduplicator Stored Data: "
          << "(Size = " << property_list.size() <<") {" << std::endl;
        for (Size i = 0; i < get_property_count(); i++) {
            s << "   " << i << ": "
              << PropertyPrinter()(get_value(i)) << std::endl;
        }
        s << "}" << std::endl;
 
        return s.str();
    }
 
};
 
}; // END NAMESPACE
 
#endif