RegisteredArray.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Math.h>
#include <ogdf/basic/Observer.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/internal/config_autogen.h>
#include <ogdf/basic/memory.h>
 
#include <algorithm>
#include <cstddef>
#include <iterator>
#include <list>
#include <memory> // IWYU pragma: keep
#include <type_traits>
#include <utility>
#include <vector>
 
#ifndef OGDF_MEMORY_POOL_NTS
 
#   include <mutex>
 
#endif
 
namespace ogdf {
namespace internal {
template<typename Registry>
class RegisteredArrayBase;
}
template<typename Key, typename Registry, typename Iterator = void>
class RegistryBase; // IWYU pragma: keep
 
static constexpr int MIN_TABLE_SIZE = (1 << 4);
 
 
inline int calculateTableSize(int actualCount) {
    return Math::nextPower2(MIN_TABLE_SIZE, actualCount);
}
 
template<typename Registry>
class RegisteredObserver : public Observer<Registry, RegisteredObserver<Registry>> {
    using Obs = Observer<Registry, RegisteredObserver<Registry>>;
 
public:
    RegisteredObserver() = default;
 
    OGDF_DEPRECATED("calls registrationChanged with only partially-constructed child classes, "
                    "see copy constructor of Observer for fix")
 
    explicit RegisteredObserver(const Registry* R) { Obs::reregister(R); }
 
    virtual void keyRemoved(typename Registry::key_type v) = 0;
 
    virtual void keyAdded(typename Registry::key_type v) = 0;
 
    virtual void keysSwapped(int index1, int index2) = 0;
 
    virtual void keysCopied(int toIndex, int fromIndex) = 0;
 
    virtual void keysCleared() = 0;
 
    const Registry* getRegistry() const { return Obs::getObserved(); }
};
 
 
template<typename Key, typename Registry, typename Iterator> // default Iterator=void defined above
class RegistryBase : public Observable<RegisteredObserver<Registry>, Registry> {
public:
    using registered_array_type = internal::RegisteredArrayBase<Registry>;
    using key_type = Key;
    using registry_type = Registry;
    using iterator_type = Iterator;
    using registration_list_type =
            std::list<registered_array_type*, OGDFAllocator<registered_array_type*>>;
    using registration_iterator_type = typename registration_list_type::iterator;
 
private:
    using Obs = Observable<RegisteredObserver<Registry>, Registry>;
 
    mutable registration_list_type m_registeredArrays;
    bool m_autoShrink = false;
    int m_size = 0;
 
#ifndef OGDF_MEMORY_POOL_NTS
    mutable std::mutex m_mutexRegArrays;
#endif
 
protected:
    RegistryBase() = default;
 
public:
    virtual ~RegistryBase() noexcept {
        Obs::clearObservers();
        unregisterArrays();
    }
 
 
    OGDF_NODISCARD registration_iterator_type registerArray(registered_array_type* pArray) const {
#ifndef OGDF_MEMORY_POOL_NTS
        std::lock_guard<std::mutex> guard(m_mutexRegArrays);
#endif
        return m_registeredArrays.emplace(m_registeredArrays.end(), pArray);
    }
 
 
    void unregisterArray(registration_iterator_type it) const noexcept {
#ifndef OGDF_MEMORY_POOL_NTS
        std::lock_guard<std::mutex> guard(m_mutexRegArrays);
#endif
        m_registeredArrays.erase(it);
    }
 
    void moveRegisterArray(registration_iterator_type it, registered_array_type* pArray) const {
#ifndef OGDF_MEMORY_POOL_NTS
        std::lock_guard<std::mutex> guard(m_mutexRegArrays);
#endif
        *it = pArray;
    }
 
    void keyAdded(Key key) {
        if (static_cast<Registry*>(this)->keyToIndex(key) >= m_size) {
            resizeArrays();
        }
        for (auto& ob : getObservers()) {
            ob->keyAdded(key);
        }
    }
 
    void keyRemoved(Key key) {
        if (m_autoShrink) {
            resizeArrays();
        }
        for (auto& ob : getObservers()) {
            ob->keyRemoved(key);
        }
    }
 
    void keysCleared() {
        resizeArrays(0);
        for (auto& ob : getObservers()) {
            ob->keysCleared();
        }
    }
 
    void resizeArrays() { resizeArrays(static_cast<Registry*>(this)->calculateArraySize(0)); }
 
    void resizeArrays(int size) { resizeArrays(size, m_autoShrink); }
 
    void resizeArrays(int size, bool shrink) {
        if (size == m_size) {
            return;
        }
        m_size = size = max(size, 0);
        for (registered_array_type* ab : m_registeredArrays) {
            ab->resize(size, shrink);
        }
    }
 
    void reserveSpace(int new_keys) {
        resizeArrays(static_cast<Registry*>(this)->calculateArraySize(new_keys));
    }
 
    void swapArrayEntries(int index1, int index2) {
        for (registered_array_type* ab : m_registeredArrays) {
            ab->swapEntries(index1, index2);
        }
        for (auto& ob : getObservers()) {
            ob->keysSwapped(index1, index2);
        }
    }
 
    void copyArrayEntries(int toIndex, int fromIndex) {
        for (registered_array_type* ab : m_registeredArrays) {
            ab->copyEntry(toIndex, fromIndex);
        }
        for (auto& ob : getObservers()) {
            ob->keysCopied(fromIndex, toIndex);
        }
    }
 
    void unregisterArrays() noexcept {
        while (!m_registeredArrays.empty()) {
#ifdef OGDF_DEBUG
            auto size = m_registeredArrays.size();
#endif
            m_registeredArrays.front()->unregister();
            OGDF_ASSERT(m_registeredArrays.size() < size);
        }
    }
 
    const registration_list_type& getRegisteredArrays() const { return m_registeredArrays; }
 
    bool isAutoShrink() const { return m_autoShrink; }
 
    void setAutoShrink(bool mAutoShrink) { m_autoShrink = mAutoShrink; }
 
    int getArraySize() const { return m_size; }
 
    using Obs::getObservers;
};
 
namespace internal {
 
template<class Registry>
class RegisteredArrayBase {
    using registry_type = Registry;
    using registration_iterator_type = typename Registry::registration_iterator_type;
 
    registration_iterator_type m_registration;
    const Registry* m_pRegistry = nullptr;
 
public:
    RegisteredArrayBase() = default;
 
    RegisteredArrayBase(const RegisteredArrayBase<Registry>& copy) { reregister(copy.m_pRegistry); }
 
    RegisteredArrayBase(RegisteredArrayBase<Registry>&& move_from) noexcept {
        moveRegister(move_from);
    }
 
    RegisteredArrayBase& operator=(const RegisteredArrayBase<Registry>& copy) {
        reregister(copy.m_pRegistry);
        return *this;
    }
 
    RegisteredArrayBase& operator=(RegisteredArrayBase<Registry>&& move_from) noexcept {
        moveRegister(move_from);
        return *this;
    }
 
    virtual ~RegisteredArrayBase() noexcept {
        if (m_pRegistry) {
            m_pRegistry->unregisterArray(m_registration);
        }
    }
 
    virtual void resize(int size, bool shrink) = 0;
 
    virtual void swapEntries(int index1, int index2) = 0;
 
    virtual void copyEntry(int newIndex, int oldIndex) = 0;
 
    void unregister() noexcept {
        resize(0, true);
        reregister(nullptr);
    }
 
protected:
    void reregister(const Registry* registry) {
        if (m_pRegistry) {
            m_pRegistry->unregisterArray(m_registration);
        }
        m_pRegistry = registry;
        if (m_pRegistry != nullptr) {
            m_registration = m_pRegistry->registerArray(this);
        } else {
            m_registration = registration_iterator_type();
        }
    }
 
    void moveRegister(RegisteredArrayBase<Registry>& move_from) {
        if (m_pRegistry) {
            m_pRegistry->unregisterArray(m_registration);
        }
        m_pRegistry = move_from.m_pRegistry;
        m_registration = move_from.m_registration;
        move_from.m_pRegistry = nullptr;
        move_from.m_registration = registration_iterator_type();
        if (m_pRegistry != nullptr) {
            m_pRegistry->moveRegisterArray(m_registration, this);
        }
    }
 
public:
    const Registry* registeredAt() const { return m_pRegistry; }
};
}
 
 
template<class ArrayType, class KeyIterator, bool isConst = false>
class RegisteredArrayIterator {
public:
    using registry_type = typename ArrayType::registry_type;
    using key_type = typename ArrayType::key_type;
    using value_type = typename std::conditional<isConst, const typename ArrayType::value_type,
            typename ArrayType::value_type>::type;
    using array_pointer_type = typename std::conditional<isConst, const ArrayType*, ArrayType*>::type;
 
private:
    KeyIterator m_it;
    array_pointer_type m_array;
 
public:
    RegisteredArrayIterator() : m_it(), m_array(nullptr) { }
 
 
    RegisteredArrayIterator(KeyIterator mIt, array_pointer_type mArray)
        : m_it(mIt), m_array(mArray) { }
 
    key_type key() const { return *m_it; }
 
    value_type& value() const { return (*m_array)[*m_it]; }
 
    value_type& operator*() const { return (*m_array)[*m_it]; }
 
    bool operator==(const RegisteredArrayIterator<ArrayType, KeyIterator, isConst>& iter) const {
        return m_it == iter.m_it && m_array == iter.m_array;
    }
 
    bool operator!=(const RegisteredArrayIterator<ArrayType, KeyIterator, isConst>& iter) const {
        return !operator==(iter);
    }
 
    RegisteredArrayIterator<ArrayType, KeyIterator, isConst>& operator++() {
        ++m_it;
        return *this;
    }
 
    RegisteredArrayIterator<ArrayType, KeyIterator, isConst> operator++(int) {
        RegisteredArrayIterator<ArrayType, KeyIterator, isConst> iter = *this;
        ++m_it;
        return iter;
    }
 
    RegisteredArrayIterator<ArrayType, KeyIterator, isConst>& operator--() {
        --m_it;
        return *this;
    }
 
    RegisteredArrayIterator<ArrayType, KeyIterator, isConst> operator--(int) {
        RegisteredArrayIterator<ArrayType, KeyIterator, isConst> iter = *this;
        --m_it;
        return iter;
    }
};
 
namespace internal {
 
template<class Registry, class Value>
class RegisteredArrayWithoutDefaultOrIndexAccess : protected RegisteredArrayBase<Registry> {
protected:
    using key_iterator = typename Registry::iterator_type;
    using registered_array = RegisteredArrayWithoutDefaultOrIndexAccess<Registry, Value>;
    using registered_array_base = RegisteredArrayBase<Registry>;
 
public:
    using registry_type = Registry;
    using key_type = typename Registry::key_type;
    using vector_type = std::vector<Value, OGDFAllocator<Value>>;
    using value_type = typename vector_type::value_type;
    using value_ref_type = typename vector_type::reference;
    using value_const_ref_type = typename vector_type::const_reference;
 
    using iterator = RegisteredArrayIterator<registered_array, key_iterator, false>;
    using const_iterator = RegisteredArrayIterator<registered_array, key_iterator, true>;
 
protected:
    vector_type m_data;
 
public:
    RegisteredArrayWithoutDefaultOrIndexAccess() = default;
 
    explicit RegisteredArrayWithoutDefaultOrIndexAccess(const Registry* registry) {
        // during base class initialization, no part of the derived class exists, so this will always call our base init
        // so base classes should call their own init themselves
        registered_array::init(registry);
    }
 
    void init(const Registry* registry = nullptr) {
        if (registry == nullptr) {
            resize(0, true);
        } else {
            OGDF_ASSERT(registry->maxKeyIndex() < registry->getArraySize());
            resize(0, false);
            resize(registry->getArraySize(), true);
        }
        registered_array::reregister(registry);
    }
 
    void fill(value_const_ref_type x) { m_data.assign(m_data.size(), x); }
 
    value_const_ref_type operator[](key_type key) const {
        OGDF_ASSERT(getRegistry().isKeyAssociated(key));
#ifdef OGDF_DEBUG
        return m_data.at(registeredAt()->keyToIndex(key));
#else
        return m_data[registeredAt()->keyToIndex(key)];
#endif
    }
 
    value_ref_type operator[](key_type key) {
        OGDF_ASSERT(getRegistry().isKeyAssociated(key));
#ifdef OGDF_DEBUG
        return m_data.at(registeredAt()->keyToIndex(key));
#else
        return m_data[registeredAt()->keyToIndex(key)];
#endif
    }
 
    value_const_ref_type operator()(key_type key) const {
        OGDF_ASSERT(getRegistry().isKeyAssociated(key));
#ifdef OGDF_DEBUG
        return m_data.at(registeredAt()->keyToIndex(key));
#else
        return m_data[registeredAt()->keyToIndex(key)];
#endif
    }
 
    value_ref_type operator()(key_type key) {
        OGDF_ASSERT(getRegistry().isKeyAssociated(key));
#ifdef OGDF_DEBUG
        return m_data.at(registeredAt()->keyToIndex(key));
#else
        return m_data[registeredAt()->keyToIndex(key)];
#endif
    }
 
    iterator begin() {
        using std::begin;
        return iterator(begin(getRegistry()), this);
    }
 
    const_iterator begin() const {
        using std::begin;
        return const_iterator(begin(getRegistry()), this);
    }
 
    const_iterator cbegin() const {
        using std::begin;
        return const_iterator(begin(getRegistry()), this);
    }
 
    iterator end() {
        using std::end;
        return iterator(end(getRegistry()), this);
    }
 
    const_iterator end() const {
        using std::end;
        return const_iterator(end(getRegistry()), this);
    }
 
    const_iterator cend() const {
        using std::end;
        return const_iterator(end(getRegistry()), this);
    }
 
    using registered_array_base::registeredAt;
 
    bool valid() const {
        OGDF_ASSERT(registeredAt() == nullptr || registeredAt()->maxKeyIndex() < 0
                || ((size_t)registeredAt()->maxKeyIndex()) < m_data.size());
        return registeredAt();
    }
 
protected:
    inline const Registry& getRegistry() const {
        OGDF_ASSERT(registeredAt());
        OGDF_ASSERT(valid());
        return *registeredAt();
    }
 
    void resize(int size, bool shrink) override {
        m_data.resize(size);
        if (shrink) {
            m_data.shrink_to_fit();
        }
    }
 
    void swapEntries(int index1, int index2) override {
        using std::swap;
        swap(m_data.at(index1), m_data.at(index2));
    }
 
    void copyEntry(int toIndex, int fromIndex) override {
        // silently ignored
    }
};
 
template<class Registry, class Value>
class RegisteredArrayWithoutDefaultWithIndexAccess
    : public RegisteredArrayWithoutDefaultOrIndexAccess<Registry, Value> {
    using RA = RegisteredArrayWithoutDefaultOrIndexAccess<Registry, Value>;
 
public:
    RegisteredArrayWithoutDefaultWithIndexAccess() = default;
 
    explicit RegisteredArrayWithoutDefaultWithIndexAccess(const Registry* registry)
        : RA(registry) { }
 
    using RA::operator[];
 
    typename RA::value_const_ref_type operator[](int idx) const {
#ifdef OGDF_DEBUG
        return RA::m_data.at(idx);
#else
        return RA::m_data[idx];
#endif
    }
 
    typename RA::value_ref_type operator[](int idx) {
#ifdef OGDF_DEBUG
        return RA::m_data.at(idx);
#else
        return RA::m_data[idx];
#endif
    }
};
 
template<class Registry, class Value>
using RegisteredArrayWithoutDefault =
        typename std::conditional_t<std::is_integral_v<typename Registry::key_type>,
                RegisteredArrayWithoutDefaultOrIndexAccess<Registry, Value>,
                RegisteredArrayWithoutDefaultWithIndexAccess<Registry, Value>>;
 
 
template<class Registry, class Value>
class RegisteredArrayWithDefault : public RegisteredArrayWithoutDefault<Registry, Value> {
    using RA = RegisteredArrayWithoutDefault<Registry, Value>;
    Value m_default;
 
    static_assert(std::is_copy_constructible_v<Value>,
            "This RegisteredArrayWithDefault<Value> instantiation (e.g. NodeArray<Graph>) is "
            "invalid because Value is not copy-constructible! "
            "Use, e.g., NodeArrayP<Graph> or NodeArray<unique_ptr<Graph>, false> instead.");
 
public:
    explicit RegisteredArrayWithDefault() : RA(), m_default() {};
 
    explicit RegisteredArrayWithDefault(const Registry* registry) : RA(), m_default() {
        // call init from here, as our virtual override of init is not available during initialization of the base class
        RA::init(registry);
    };
 
    explicit RegisteredArrayWithDefault(const Value& def) : RA(), m_default(def) {};
 
    explicit RegisteredArrayWithDefault(const Registry* registry, const Value& def)
        : RA(), m_default(def) {
        // call init from here, as our virtual override of init is not available during initialization of the base class
        RA::init(registry);
    };
 
    explicit RegisteredArrayWithDefault(Value&& def) : RA(), m_default(std::forward<Value>(def)) {};
 
    explicit RegisteredArrayWithDefault(const Registry* registry, Value&& def)
        : RA(), m_default(std::forward<Value>(def)) {
        // call init from here, as our virtual override of init is not available during initialization of the base class
        RA::init(registry);
    };
 
    void setDefault(Value&& def) { m_default = std::forward<Value>(def); }
 
    void setDefault(const Value& def) { m_default = def; }
 
    const Value& getDefault() const { return m_default; }
 
    Value& getDefault() { return m_default; }
 
    void fillWithDefault() { RA::m_data.assign(RA::getRegistry().getArraySize(), m_default); }
 
protected:
    void copyEntry(int toIndex, int fromIndex) override {
        RA::m_data.at(toIndex) = RA::m_data.at(fromIndex);
    }
 
    void resize(int size, bool shrink) override {
        RA::m_data.resize(size, m_default);
        if (shrink) {
            RA::m_data.shrink_to_fit();
        }
    }
};
}
 
 
template<class Registry, class Value, bool WithDefault = true, class Base = Registry>
class RegisteredArray
    : public std::conditional<WithDefault, internal::RegisteredArrayWithDefault<Registry, Value>,
              internal::RegisteredArrayWithoutDefault<Registry, Value>>::type {
    using RA =
            typename std::conditional<WithDefault, internal::RegisteredArrayWithDefault<Registry, Value>,
                    internal::RegisteredArrayWithoutDefault<Registry, Value>>::type;
 
    static inline const Registry* cast(const Base* base) {
        if (base != nullptr) {
            // unpack the pointer to invoke the conversion operator
            return &((const Registry&)*base);
        } else {
            return nullptr;
        }
    }
 
public:
    RegisteredArray() : RA() {};
 
    explicit RegisteredArray(const Base& base) : RA(cast(&base)) {};
 
    RegisteredArray(const Base& base, const Value& def) : RA(cast(&base), def) {};
 
    explicit RegisteredArray(const Base* base) : RA(cast(base)) {};
 
    RegisteredArray(const Base* base, const Value& def) : RA(cast(base), def) {};
 
    void init(const Base* base = nullptr) { RA::init(cast(base)); }
 
    void init(const Base& base) { RA::init(cast(&base)); }
 
    void init(const Base& base, const Value& new_default) {
        RA::setDefault(new_default);
        RA::init(cast(&base));
    }
 
    void init(const Base* base, const Value& new_default) {
        RA::setDefault(new_default);
        RA::init(cast(base));
    }
};
 
template<class Registry, bool WithDefault, class Base>
class RegisteredArray<Registry, bool, WithDefault, Base>
    : public RegisteredArray<Registry, unsigned char, WithDefault, Base> {
    using RA = RegisteredArray<Registry, unsigned char, WithDefault, Base>;
    using BRA = RegisteredArray<Registry, bool, WithDefault, Base>;
 
public:
    using RA::RA;
 
    using key_type = typename RA::key_type;
    using value_type = bool;
    using value_const_ref_type = const bool&;
    using value_ref_type = bool&;
    using iterator = RegisteredArrayIterator<BRA, typename RA::key_iterator, false>;
    using const_iterator = RegisteredArrayIterator<BRA, typename RA::key_iterator, true>;
 
    value_const_ref_type operator[](key_type key) const {
        return reinterpret_cast<value_const_ref_type>(RA::operator[](key));
    }
 
    value_ref_type operator[](key_type key) {
        return reinterpret_cast<value_ref_type>(RA::operator[](key));
    }
 
    value_const_ref_type operator()(key_type key) const {
        return reinterpret_cast<value_const_ref_type>(RA::operator()(key));
    }
 
    value_ref_type operator()(key_type key) {
        return reinterpret_cast<value_ref_type>(RA::operator()(key));
    }
 
    value_const_ref_type operator[](int idx) const {
        return reinterpret_cast<value_const_ref_type>(RA::operator[](idx));
    }
 
    value_ref_type operator[](int idx) {
        return reinterpret_cast<value_ref_type>(RA::operator[](idx));
    }
 
    value_ref_type getDefault() { return reinterpret_cast<value_ref_type>(RA::getDefault()); }
 
    value_const_ref_type getDefault() const {
        return reinterpret_cast<value_const_ref_type>(RA::getDefault());
    }
 
    iterator begin() {
        using std::begin;
        return iterator(begin(RA::getRegistry()), this);
    }
 
    const_iterator begin() const {
        using std::begin;
        return const_iterator(begin(RA::getRegistry()), this);
    }
 
    const_iterator cbegin() const {
        using std::begin;
        return const_iterator(begin(RA::getRegistry()), this);
    }
 
    iterator end() {
        using std::end;
        return iterator(end(RA::getRegistry()), this);
    }
 
    const_iterator end() const {
        using std::end;
        return const_iterator(end(RA::getRegistry()), this);
    }
 
    const_iterator cend() const {
        using std::end;
        return const_iterator(end(RA::getRegistry()), this);
    }
};
}
 
template<typename RA1, typename RA2>
inline void invertRegisteredArray(const RA1& from, RA2& to) {
    OGDF_ASSERT(from.registeredAt() != nullptr);
    for (const auto& key : *from.registeredAt()) {
        to[from[key]] = key;
    }
}
 
/* The following macro will be expanded in the docs, see doc/ogdf-doxygen.cfg:EXPAND_AS_DEFINED */
 
#define OGDF_DECL_REG_ARRAY(NAME)                                  \
    template<typename Value, bool WithDefault = true>              \
    using NAME = OGDF_DECL_REG_ARRAY_TYPE(Value, WithDefault);     \
 \
    template<typename Value>                                       \
    using NAME##P = NAME<std::unique_ptr<Value>, false>;