dictionary.hpp

Go to the documentation of this file.

// -----------------------------------------------------------------------------------------------------
// Copyright (c) 2022 deCODE Genetics
// Copyright (c) 2006-2020, Knut Reinert & Freie Universität Berlin
// Copyright (c) 2016-2020, Knut Reinert & MPI für molekulare Genetik
// This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
// shipped with this file and also available at: https://github.com/biocpp/biocpp-core/blob/main/LICENSE.md
// -----------------------------------------------------------------------------------------------------
 
#pragma once
 
#include <array>
#include <concepts>
#include <initializer_list>
#include <ranges>
#include <type_traits>
#include <unordered_map>
 
#if __has_include(<cereal/types/vector.hpp>)
#    include <cereal/types/vector.hpp>
#endif
#if __has_include(<cereal/types/unordered_map.hpp>)
#    include <cereal/types/unordered_map.hpp>
#endif
 
#include <bio/meta/concept/core_language.hpp>
#include <bio/meta/detail/int_types.hpp>
#include <bio/meta/tag/vtag.hpp>
#include <bio/ranges/detail/random_access_iterator.hpp>
 
namespace bio::ranges
{
 
template <typename key_t, typename mapped_t, bool mapped_t_is_context_aware = false>
class dictionary
{
public:
    static_assert(std::is_object_v<key_t>, "The key type may not be a reference or have const.");
    static_assert(std::convertible_to<key_t, std::string_view>,
                  "The key type must be std::convertible_to<std::string_view>.");
    static_assert(std::is_object_v<mapped_t>, "The mapped type may not be a reference or have const.");
 
    using mapped_ref_t =
      std::conditional_t<mapped_t_is_context_aware, mapped_t const &, mapped_t &>; 
    using value_type      = std::tuple<key_t, mapped_t>;                           
    using reference       = std::tuple<key_t const &, mapped_ref_t>;               
    using const_reference = std::tuple<key_t const &, mapped_t const &>;           
    using difference_type = ptrdiff_t;                                             
    using size_type       = size_t;                                                
    using const_iterator  = detail::random_access_iterator<dictionary const>;      
    using iterator        = std::conditional_t<mapped_t_is_context_aware,
                                        const_iterator,
                                        detail::random_access_iterator<dictionary>>; 
 
    // this signals to range-v3 that something is a container :|
    using allocator_type = void;
 
    dictionary()                                   = default; 
    dictionary(dictionary const &)                 = default; 
    dictionary(dictionary &&) noexcept             = default; 
    dictionary & operator=(dictionary const &)     = default; 
    dictionary & operator=(dictionary &&) noexcept = default; 
    ~dictionary()                                  = default; 
 
    template <typename... value_type_>
        requires((std::convertible_to<value_type_, value_type> && ...) && sizeof...(value_type_) > 0)
    explicit dictionary(value_type_ &&... args)
    {
        assign(std::forward<value_type_>(args)...);
    }
 
    template <meta::different_from<iterator> begin_it_type, typename end_it_type>
        requires(meta::different_from<const_iterator, begin_it_type> && std::forward_iterator<begin_it_type> &&
                 std::sentinel_for<end_it_type, begin_it_type> &&
                 std::convertible_to<std::iter_reference_t<begin_it_type>, value_type>)
    dictionary(begin_it_type const begin_it, end_it_type const end_it) : dictionary{}
    {
        assign(begin_it, end_it);
    }
 
    dictionary(iterator const begin_it, iterator const end_it) : dictionary{} { assign(begin_it, end_it); }
 
    dictionary(const_iterator const begin_it, const_iterator const end_it)
        requires(!std::same_as<iterator, const_iterator>)
      : dictionary{}
    {
        assign(begin_it, end_it);
    }
 
    template <meta::different_from<dictionary> other_range_t>
        requires(std::ranges::input_range<other_range_t>)
    explicit dictionary(other_range_t && range) : dictionary{std::ranges::begin(range), std::ranges::end(range)}
    {}
 
    template <typename... value_type_>
        requires((meta::different_from<dictionary, value_type_> && ...) &&
                 (meta::different_from<iterator, value_type_> && ...) &&
                 (meta::different_from<const_iterator, value_type_> && ...) &&
                 (std::convertible_to<value_type_, value_type> && ...) && (sizeof...(value_type_) > 0))
    void assign(value_type_ &&... args)
    {
        storage.clear();
        storage.reserve(sizeof...(args));
        (storage.push_back(std::forward<value_type_>(args)), ...);
        recompute_hashes(); // this validates uniqueness of keys
    }
 
    template <std::ranges::input_range other_range_t>
        requires std::convertible_to<std::ranges::range_reference_t<other_range_t>, value_type>
    void assign(other_range_t && range)
    {
        //TODO we could create move-iterators for
        assign(std::ranges::begin(range), std::ranges::end(range));
    }
 
    template <meta::different_from<iterator> begin_it_type, typename end_it_type>
        requires(meta::different_from<const_iterator, begin_it_type> && std::forward_iterator<begin_it_type> &&
                 std::sentinel_for<end_it_type, begin_it_type> &&
                 std::convertible_to<std::iter_reference_t<begin_it_type>, value_type>)
    void assign(begin_it_type begin_it, end_it_type end_it)
    {
        assign_impl(begin_it, end_it);
    }
 
    void assign(iterator begin_it, iterator end_it) { assign_impl(begin_it, end_it); }
 
    void assign(const_iterator begin_it, const_iterator end_it)
        requires(!std::same_as<iterator, const_iterator>)
    {
        assign_impl(begin_it, end_it);
    }
 
    iterator begin() noexcept { return iterator{*this}; }
 
    const_iterator begin() const noexcept { return const_iterator{*this}; }
 
    const_iterator cbegin() const noexcept { return const_iterator{*this}; }
 
    iterator end() noexcept { return iterator{*this, size()}; }
 
    const_iterator end() const noexcept { return const_iterator{*this, size()}; }
 
    const_iterator cend() const noexcept { return const_iterator{*this, size()}; }
 
    reference at(size_type const i)
    {
        if (i >= size())
        {
            throw std::out_of_range{"Trying to access element behind the last in dictionary."};
        }
        return (*this)[i];
    }
 
    const_reference at(size_type const i) const
    {
        if (i >= size())
        {
            throw std::out_of_range{"Trying to access element behind the last in dictionary."};
        }
        return (*this)[i];
    }
 
    reference operator[](size_type const i) noexcept
    {
        assert(i < size());
        return reference{get<0>(storage[i]), get<1>(storage[i])};
    }
 
    const_reference operator[](size_type const i) const noexcept
    {
        assert(i < size());
        return storage[i];
    }
 
    reference front() noexcept
    {
        assert(size() > 0);
        return (*this)[0];
    }
 
    const_reference front() const noexcept
    {
        assert(size() > 0);
        return (*this)[0];
    }
 
    reference back() noexcept
    {
        assert(size() > 0);
        return (*this)[size() - 1];
    }
 
    const_reference back() const noexcept
    {
        assert(size() > 0);
        return (*this)[size() - 1];
    }
 
//TODO(GCC11): always use string_view after deprecating GCC10
#ifdef __cpp_lib_generic_unordered_lookup
    using het_key_t = std::string_view const; 
#else
    using het_key_t = key_t const &; 
#endif
 
    bool contains(het_key_t key) const { return key_to_index.contains(key); }
 
    size_t count(het_key_t key) const { return key_to_index.count(key); }
 
    iterator find(het_key_t key)
    {
        if (auto it = key_to_index.find(key); it == key_to_index.end())
            return end();
        else
            return begin() + get<1>(*it);
    }
 
    const_iterator find(het_key_t key) const
    {
        if (auto it = key_to_index.find(key); it == key_to_index.end())
            return end();
        else
            return begin() + get<1>(*it);
    }
 
    mapped_ref_t at(het_key_t key)
    {
        auto it = key_to_index.find(key);
        if (it == key_to_index.end())
            throw std::out_of_range{"Key not found in dictionary."};
        return get<1>(storage[it->second]);
    }
 
    mapped_t const & at(het_key_t key) const
    {
        auto it = key_to_index.find(key);
        if (it == key_to_index.end())
            throw std::out_of_range{"Key not found in dictionary."};
        return get<1>(storage[it->second]);
    }
 
    mapped_ref_t operator[](het_key_t key) { return at(key); }
 
    mapped_t const & operator[](het_key_t key) const { return at(key); }
 
    template <small_string key>
    friend decltype(auto) get(meta::decays_to<dictionary> auto && dict)
        requires(mapped_t_is_context_aware && requires { get<key>(get<1>(dict.storage[0])); })
    {
#ifdef __cpp_lib_generic_unordered_lookup
        auto it = dict.key_to_index.find(key);
#else //TODO(GCC11): remove special case
        auto it = dict.key_to_index.find(static_cast<key_t>(key));
#endif
        if (it == dict.key_to_index.end())
            throw std::out_of_range{"Key not found in dictionary."};
 
        if constexpr (std::is_rvalue_reference_v<decltype(dict)>)
            return std::move(get<key>(get<1>(dict.storage[it->second])));
        else
            return get<key>(get<1>(dict.storage[it->second]));
    }
 
    template <small_string key>
    decltype(auto) at(meta::vtag_t<key> BIOCPP_DOXYGEN_ONLY(key_tag))
        requires(requires(dictionary d) { get<key>(d); })
    {
        return get<key>(*this);
    }
 
    template <small_string key>
    decltype(auto) at(meta::vtag_t<key> BIOCPP_DOXYGEN_ONLY(key_tag)) const
        requires(requires(dictionary const d) { get<key>(d); })
    {
        return get<key>(*this);
    }
 
    template <small_string key>
    decltype(auto) operator[](meta::vtag_t<key> BIOCPP_DOXYGEN_ONLY(key_tag))
        requires(requires(dictionary d) { get<key>(d); })
    {
        return get<key>(*this);
    }
 
    template <small_string key>
    decltype(auto) operator[](meta::vtag_t<key> BIOCPP_DOXYGEN_ONLY(key_tag)) const
        requires(requires(dictionary const d) { get<key>(d); })
    {
        return get<key>(*this);
    }
 
    bool empty() const noexcept { return size() == 0; }
 
    size_type size() const noexcept { return storage.size(); }
 
    size_type max_size() const noexcept { return storage.max_size(); }
 
    size_type capacity() const noexcept { return storage.capacity(); }
 
    void reserve(size_type const new_cap)
    {
        storage.reserve(new_cap);
        key_to_index.reserve(new_cap);
    }
 
    void shrink_to_fit() { storage.shrink_to_fit(); }
 
    void clear() noexcept
    {
        storage.clear();
        key_to_index.clear();
    }
 
    template <std::convertible_to<value_type> value_type_ = value_type>
    void push_back(value_type_ && value)
    {
        if (key_to_index.contains(get<0>(value)))
            throw std::runtime_error{"An element with this key already exists."};
        storage.push_back(std::forward<value_type_>(value));
        key_to_index[get<0>(storage.back())] = storage.size() - 1;
    }
 
    void emplace_back(auto &&... args)
        requires(std::constructible_from<value_type, decltype(args)...>)
    {
        storage.emplace_back(std::forward<decltype(args)>(args)...);
        if (key_to_index.contains(get<0>(storage.back())))
            throw std::runtime_error{"An element with this key already exists."};
        key_to_index[get<0>(storage.back())] = storage.size() - 1;
    }
 
    void pop_back()
    {
        assert(!empty());
        key_to_index.erase(get<0>(storage.back()));
        storage.pop_back();
    }
 
    value_type extract_back()
    {
        assert(!empty());
        value_type tmp = std::move(storage.back());
        pop_back();
        return tmp;
    }
 
 
    friend bool operator==(dictionary const & lhs, dictionary const & rhs) noexcept
    {
        return lhs.storage == rhs.storage;
    }
 
    friend bool operator<=>(dictionary const & lhs, dictionary const & rhs) noexcept
    {
        return lhs.storage <=> rhs.storage;
    }
 
private:
 
    struct hash_string
    {
        using is_transparent = void;
 
        std::size_t operator()(std::string_view const v) const { return std::hash<std::string_view>{}(v); }
    };
 
    struct eq_string
    {
        using is_transparent = void;
 
        bool operator()(std::string_view const lhs, std::string_view const rhs) const
        {
            return std::ranges::equal(lhs, rhs);
        }
    };
 
    std::vector<value_type>                                   storage;
    std::unordered_map<key_t, size_t, hash_string, eq_string> key_to_index;
 
    void recompute_hashes()
    {
        key_to_index.clear();
        key_to_index.reserve(storage.size());
        size_t i = 0;
        for (auto && [key, value] : storage)
            key_to_index[key] = i++;
        if (key_to_index.size() != storage.size())
            throw std::runtime_error{"When creating/assigning bio::ranges::dictionary, keys where not unique."};
    }
 
    void assign_impl(auto begin_it, auto end_it)
    {
        if constexpr (requires { storage.assign(begin_it, end_it); })
        {
            storage.assign(begin_it, end_it);
        }
        else
        {
            storage.clear();
 
            if constexpr (std::sized_sentinel_for<decltype(end_it), decltype(begin_it)>)
                storage.reserve(end_it - begin_it);
 
            for (; begin_it != end_it; ++begin_it)
                storage.push_back(*begin_it);
        }
    }
 
public:
 
    template <typename archive_t>
    void serialize(archive_t & archive)
    {
        archive(storage);
        archive(key_to_index);
    }
};
 
} // namespace bio::ranges