about summary refs log tree commit diff
path: root/immer/map.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'immer/map.hpp')
-rw-r--r--immer/map.hpp342
1 files changed, 342 insertions, 0 deletions
diff --git a/immer/map.hpp b/immer/map.hpp
new file mode 100644
index 000000000000..58a84d2de939
--- /dev/null
+++ b/immer/map.hpp
@@ -0,0 +1,342 @@
+//
+// 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