diff options
Diffstat (limited to 'third_party/immer/immer/map.hpp')
| -rw-r--r-- | third_party/immer/immer/map.hpp | 342 |
1 files changed, 0 insertions, 342 deletions
diff --git a/third_party/immer/immer/map.hpp b/third_party/immer/immer/map.hpp deleted file mode 100644 index 58a84d2de9..0000000000 --- a/third_party/immer/immer/map.hpp +++ /dev/null @@ -1,342 +0,0 @@ -// -// immer: immutable data structures for C++ -// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente -// -// This software is distributed under the Boost Software License, Version 1.0. -// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt -// - -#pragma once - -#include <immer/detail/hamts/champ.hpp> -#include <immer/detail/hamts/champ_iterator.hpp> -#include <immer/memory_policy.hpp> - -#include <functional> - -namespace immer { - -template <typename K, - typename T, - typename Hash, - typename Equal, - typename MemoryPolicy, - detail::hamts::bits_t B> -class map_transient; - -/*! - * Immutable unordered mapping of values from type `K` to type `T`. - * - * @tparam K The type of the keys. - * @tparam T The type of the values to be stored in the container. - * @tparam Hash The type of a function object capable of hashing - * values of type `T`. - * @tparam Equal The type of a function object capable of comparing - * values of type `T`. - * @tparam MemoryPolicy Memory management policy. See @ref - * memory_policy. - * - * @rst - * - * This cotainer provides a good trade-off between cache locality, - * search, update performance and structural sharing. It does so by - * storing the data in contiguous chunks of :math:`2^{B}` elements. - * When storing big objects, the size of these contiguous chunks can - * become too big, damaging performance. If this is measured to be - * problematic for a specific use-case, it can be solved by using a - * `immer::box` to wrap the type `T`. - * - * **Example** - * .. literalinclude:: ../example/map/intro.cpp - * :language: c++ - * :start-after: intro/start - * :end-before: intro/end - * - * @endrst - * - */ -template <typename K, - typename T, - typename Hash = std::hash<K>, - typename Equal = std::equal_to<K>, - typename MemoryPolicy = default_memory_policy, - detail::hamts::bits_t B = default_bits> -class map -{ - using value_t = std::pair<K, T>; - - struct project_value - { - const T& operator()(const value_t& v) const noexcept - { - return v.second; - } - }; - - struct project_value_ptr - { - const T* operator()(const value_t& v) const noexcept - { - return &v.second; - } - }; - - struct combine_value - { - template <typename Kf, typename Tf> - value_t operator()(Kf&& k, Tf&& v) const - { - return {std::forward<Kf>(k), std::forward<Tf>(v)}; - } - }; - - struct default_value - { - const T& operator()() const - { - static T v{}; - return v; - } - }; - - struct error_value - { - const T& operator()() const - { - throw std::out_of_range{"key not found"}; - } - }; - - struct hash_key - { - auto operator()(const value_t& v) { return Hash{}(v.first); } - - auto operator()(const K& v) { return Hash{}(v); } - }; - - struct equal_key - { - auto operator()(const value_t& a, const value_t& b) - { - return Equal{}(a.first, b.first); - } - - auto operator()(const value_t& a, const K& b) - { - return Equal{}(a.first, b); - } - }; - - struct equal_value - { - auto operator()(const value_t& a, const value_t& b) - { - return Equal{}(a.first, b.first) && a.second == b.second; - } - }; - - using impl_t = - detail::hamts::champ<value_t, hash_key, equal_key, MemoryPolicy, B>; - -public: - using key_type = K; - using mapped_type = T; - using value_type = std::pair<K, T>; - using size_type = detail::hamts::size_t; - using diference_type = std::ptrdiff_t; - using hasher = Hash; - using key_equal = Equal; - using reference = const value_type&; - using const_reference = const value_type&; - - using iterator = detail::hamts:: - champ_iterator<value_t, hash_key, equal_key, MemoryPolicy, B>; - using const_iterator = iterator; - - using transient_type = map_transient<K, T, Hash, Equal, MemoryPolicy, B>; - - /*! - * Default constructor. It creates a set of `size() == 0`. It - * does not allocate memory and its complexity is @f$ O(1) @f$. - */ - map() = default; - - /*! - * Returns an iterator pointing at the first element of the - * collection. It does not allocate memory and its complexity is - * @f$ O(1) @f$. - */ - IMMER_NODISCARD iterator begin() const { return {impl_}; } - - /*! - * Returns an iterator pointing just after the last element of the - * collection. It does not allocate and its complexity is @f$ O(1) @f$. - */ - IMMER_NODISCARD iterator end() const - { - return {impl_, typename iterator::end_t{}}; - } - - /*! - * Returns the number of elements in the container. It does - * not allocate memory and its complexity is @f$ O(1) @f$. - */ - IMMER_NODISCARD size_type size() const { return impl_.size; } - - /*! - * Returns `true` if there are no elements in the container. It - * does not allocate memory and its complexity is @f$ O(1) @f$. - */ - IMMER_NODISCARD bool empty() const { return impl_.size == 0; } - - /*! - * Returns `1` when the key `k` is contained in the map or `0` - * otherwise. It won't allocate memory and its complexity is - * *effectively* @f$ O(1) @f$. - */ - IMMER_NODISCARD size_type count(const K& k) const - { - return impl_.template get<detail::constantly<size_type, 1>, - detail::constantly<size_type, 0>>(k); - } - - /*! - * Returns a `const` reference to the values associated to the key - * `k`. If the key is not contained in the map, it returns a - * default constructed value. It does not allocate memory and its - * complexity is *effectively* @f$ O(1) @f$. - */ - IMMER_NODISCARD const T& operator[](const K& k) const - { - return impl_.template get<project_value, default_value>(k); - } - - /*! - * Returns a `const` reference to the values associated to the key - * `k`. If the key is not contained in the map, throws an - * `std::out_of_range` error. It does not allocate memory and its - * complexity is *effectively* @f$ O(1) @f$. - */ - const T& at(const K& k) const - { - return impl_.template get<project_value, error_value>(k); - } - - /*! - * Returns a pointer to the value associated with the key `k`. If - * the key is not contained in the map, a `nullptr` is returned. - * It does not allocate memory and its complexity is *effectively* - * @f$ O(1) @f$. - * - * @rst - * - * .. admonition:: Why doesn't this function return an iterator? - * - * Associative containers from the C++ standard library provide a - * ``find`` method that returns an iterator pointing to the - * element in the container or ``end()`` when the key is missing. - * In the case of an unordered container, the only meaningful - * thing one may do with it is to compare it with the end, to - * test if the find was succesfull, and dereference it. This - * comparison is cumbersome compared to testing for a non-empty - * optional value. Furthermore, for an immutable container, - * returning an iterator would have some additional performance - * cost, with no benefits otherwise. - * - * In our opinion, this function should return a - * ``std::optional<const T&>`` but this construction is not valid - * in any current standard. As a compromise we return a - * pointer, which has similar syntactic properties yet it is - * unfortunatelly unnecessarily unrestricted. - * - * @endrst - */ - IMMER_NODISCARD const T* find(const K& k) const - { - return impl_.template get<project_value_ptr, - detail::constantly<const T*, nullptr>>(k); - } - - /*! - * Returns whether the sets are equal. - */ - IMMER_NODISCARD bool operator==(const map& other) const - { - return impl_.template equals<equal_value>(other.impl_); - } - IMMER_NODISCARD bool operator!=(const map& other) const - { - return !(*this == other); - } - - /*! - * Returns a map containing the association `value`. If the key is - * already in the map, it replaces its association in the map. - * It may allocate memory and its complexity is *effectively* @f$ - * O(1) @f$. - */ - IMMER_NODISCARD map insert(value_type value) const - { - return impl_.add(std::move(value)); - } - - /*! - * Returns a map containing the association `(k, v)`. If the key - * is already in the map, it replaces its association in the map. - * It may allocate memory and its complexity is *effectively* @f$ - * O(1) @f$. - */ - IMMER_NODISCARD map set(key_type k, mapped_type v) const - { - return impl_.add({std::move(k), std::move(v)}); - } - - /*! - * Returns a map replacing the association `(k, v)` by the - * association new association `(k, fn(v))`, where `v` is the - * currently associated value for `k` in the map or a default - * constructed value otherwise. It may allocate memory - * and its complexity is *effectively* @f$ O(1) @f$. - */ - template <typename Fn> - IMMER_NODISCARD map update(key_type k, Fn&& fn) const - { - return impl_ - .template update<project_value, default_value, combine_value>( - std::move(k), std::forward<Fn>(fn)); - } - - /*! - * Returns a map without the key `k`. If the key is not - * associated in the map it returns the same map. It may allocate - * memory and its complexity is *effectively* @f$ O(1) @f$. - */ - IMMER_NODISCARD map erase(const K& k) const { return impl_.sub(k); } - - /*! - * Returns an @a transient form of this container, a - * `immer::map_transient`. - */ - IMMER_NODISCARD transient_type transient() const& - { - return transient_type{impl_}; - } - IMMER_NODISCARD transient_type transient() && - { - return transient_type{std::move(impl_)}; - } - - // Semi-private - const impl_t& impl() const { return impl_; } - -private: - friend transient_type; - - map(impl_t impl) - : impl_(std::move(impl)) - {} - - impl_t impl_ = impl_t::empty(); -}; - -} // namespace immer |