map.hpp

Go to the documentation of this file.

//
// 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/memory_policy.hpp>
#include <immer/detail/hamts/champ.hpp>
#include <immer/detail/hamts/champ_iterator.hpp>

#include <functional>

namespace immer {

template <typename K,
          typename T,
          typename Hash,
          typename Equal,
          typename MemoryPolicy,
          detail::hamts::bits_t B>
class map_transient;

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>;

    map() = default;

    iterator begin() const { return {impl_}; }

    iterator end() const { return {impl_, typename iterator::end_t{}}; }

    size_type size() const { return impl_.size; }

    size_type count(const K& k) const
    { return impl_.template get<detail::constantly<size_type, 1>,
                                detail::constantly<size_type, 0>>(k); }

    const T& operator[] (const K& k) const
    { return impl_.template get<project_value, default_value>(k); }

    const T& at(const K& k) const
    { return impl_.template get<project_value, error_value>(k); }


    const T* find(const K& k) const
    { return impl_.template get<project_value_ptr,
                                detail::constantly<const T*, nullptr>>(k); }

    bool operator==(const map& other) const
    { return impl_.template equals<equal_value>(other.impl_); }
    bool operator!=(const map& other) const
    { return !(*this == other); }

    map insert(value_type value) const
    { return impl_.add(std::move(value)); }

    map set(key_type k, mapped_type v) const
    { return impl_.add({std::move(k), std::move(v)}); }

    template <typename Fn>
    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));
    }

    map erase(const K& k) const
    { return impl_.sub(k); }

    transient_type transient() const&
    { return transient_type{ impl_ }; }
    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