FlatMap.h

Go to the documentation of this file.

#pragma once
 
 
#include "objects/containers/Array.h"
#include "objects/wrappers/Optional.h"
#include <algorithm>
 
NAMESPACE_SPH_BEGIN
 
template <typename TKey, typename TValue, typename TLess = std::less<TKey>>
class FlatMap : TLess, Noncopyable {
public:
    struct Element {
        TKey key;
        TValue value;
    };
 
private:
    Array<Element> data;
 
public:
    FlatMap() = default;
 
    FlatMap(std::initializer_list<Element> list)
        : data(list) {
        std::sort(data.begin(), data.end(), [this](const Element& e1, const Element& e2) {
            return less(e1.key, e2.key);
        });
    }
 
    INLINE TValue& operator[](const TKey& key) {
        Element* element = this->find(key);
        SPH_ASSERT(element);
        return element->value;
    }
 
    INLINE const TValue& operator[](const TKey& key) const {
        const Element* element = this->find(key);
        SPH_ASSERT(element);
        return element->value;
    }
 
    INLINE TValue& insert(const TKey& key, const TValue& value) {
        Element* element = this->find(key);
        if (!element) {
            return this->add(key, value);
        } else {
            element->value = value;
            return element->value;
        }
    }
 
    INLINE TValue& insert(const TKey& key, TValue&& value) {
        Element* element = this->find(key);
        if (!element) {
            return this->add(key, std::move(value));
        } else {
            element->value = std::move(value);
            return element->value;
        }
    }
 
    INLINE void remove(const TKey& key) {
        Element* element = this->find(key);
        SPH_ASSERT(element);
        const Size index = element - &data[0];
        data.remove(index);
    }
 
    INLINE bool tryRemove(const TKey& key) {
        Element* element = this->find(key);
        if (!element) {
            return false;
        } else {
            const Size index = element - &data[0];
            data.remove(index);
            return true;
        }
    }
 
    INLINE void clear() {
        data.clear();
    }
 
    INLINE Optional<TValue&> tryGet(const TKey& key) {
        Element* element = this->find(key);
        if (!element) {
            return NOTHING;
        } else {
            return element->value;
        }
    }
 
    INLINE Optional<const TValue&> tryGet(const TKey& key) const {
        const Element* element = this->find(key);
        if (!element) {
            return NOTHING;
        } else {
            return element->value;
        }
    }
 
    INLINE bool contains(const TKey& key) const {
        return this->find(key) != nullptr;
    }
 
    INLINE Size size() const {
        return data.size();
    }
 
    INLINE Size empty() const {
        return data.empty();
    }
 
    INLINE Iterator<Element> begin() {
        return data.begin();
    }
 
    INLINE Iterator<const Element> begin() const {
        return data.begin();
    }
 
    INLINE Iterator<Element> end() {
        return data.end();
    }
 
    INLINE Iterator<const Element> end() const {
        return data.end();
    }
 
    INLINE operator ArrayView<Element>() {
        return data;
    }
 
    INLINE operator ArrayView<const Element>() const {
        return data;
    }
 
    FlatMap clone() const {
        FlatMap cloned;
        cloned.data = data.clone();
        return cloned;
    }
 
private:
    INLINE bool less(const TKey& key1, const TKey& key2) const {
        return TLess::operator()(key1, key2);
    }
 
    INLINE Element* find(const TKey& key) {
        auto compare = [this](const Element& element, const TKey& key) { return less(element.key, key); };
        auto iter = std::lower_bound(data.begin(), data.end(), key, compare);
        if (iter != data.end() && iter->key == key) {
            return &*iter;
        } else {
            return nullptr;
        }
    }
 
    INLINE const Element* find(const TKey& key) const {
        return const_cast<FlatMap*>(this)->find(key);
    }
 
    template <typename T>
    INLINE TValue& add(const TKey& key, T&& value) {
        Size from = 0;
        Size to = data.size();
        Size mid = Size(-1);
 
        while (from < to && from != mid) {
            mid = (from + to) / 2;
            SPH_ASSERT(less(data[mid].key, key) || less(key, data[mid].key));
            if (less(data[mid].key, key)) {
                from = mid + 1;
            } else {
                to = mid;
            }
        }
        data.insert(from, Element{ key, std::forward<T>(value) });
        return data[from].value;
    }
};
 
 
NAMESPACE_SPH_END