persistent_map.hpp

Go to the documentation of this file.

// @file include/datastructures/persistent_map.hpp
 
#pragma once
 
#include "_persistent_avl.hpp"
 
namespace datastructures {
 
template <class TKey, class TValue, class TKeyComp = std::less<TKey>,
          class TAlloc = std::allocator<std::pair<const TKey, const TValue>>>
class persistent_map {
    // TODO: implement iterators that store the parent path so that you can
    // iterate in amortized O(1)
 
  public:
    // ==== Keys and values types ====
    using key_type = TKey;
    using mapped_type = TValue;
    using value_type = std::pair<const key_type, const mapped_type>;
 
    using reference = value_type &;
    using const_reference = const value_type &;
 
    // ==== Comparisons types ====
 
    using key_compare = TKeyComp;
 
    struct value_compare {
      protected:
        friend class map;
        [[no_unique_address]] key_compare comp;
 
      public:
        value_compare(key_compare c) : comp(c) {}
 
        inline bool operator()(const value_type &a,
                               const value_type &b) const noexcept {
            return comp(a.first, b.first);
        }
 
        inline bool operator()(const key_type &a,
                               const value_type &b) const noexcept {
            return comp(a, b.first);
        }
 
        inline bool operator()(const value_type &a,
                               const key_type &b) const noexcept {
            return comp(a.first, b);
        }
 
        inline bool operator()(const key_type &a,
                               const key_type &b) const noexcept {
            return comp(a, b);
        }
    };
 
    // ==== Allocator and memory types ====
    using allocator_type = TAlloc;
    using alloc_traits = std::allocator_traits<allocator_type>;
    using size_type = typename alloc_traits::size_type;
    using difference_type = typename alloc_traits::difference_type;
 
    using pointer = typename alloc_traits::pointer;
    using const_pointer = typename alloc_traits::const_pointer;
 
  private:
    // ==== The Tree Type ====
 
    using tree_type =
        detail::persistent_avl_tree<key_type, value_type, value_compare,
                                    allocator_type>;
 
    [[no_unique_address]] key_compare comparator;
    [[no_unique_address]] value_compare value_comparator;
 
    tree_type tree;
 
  public:
    using version_type = typename tree_type::version_type;
 
    // ==== Constructors & Assigments ====
    persistent_map();
 
    explicit persistent_map(const key_compare &comparator,
                            const allocator_type &allocator = allocator_type{});
 
    explicit persistent_map(const allocator_type &allocator);
 
    persistent_map(const persistent_map &other);
    persistent_map &operator=(const persistent_map &other);
 
    persistent_map(persistent_map &&other) noexcept;
    persistent_map &operator=(persistent_map &&other) noexcept;
 
    ~persistent_map() noexcept;
 
    // ==== Observers & Allocator getter ====
 
    [[nodiscard]] allocator_type get_allocator() const noexcept;
 
    [[nodiscard]] key_compare key_comp() const noexcept;
 
    [[nodiscard]] value_compare value_comp() const noexcept;
 
    // ==== Access Functions ====
 
    [[nodiscard]] std::vector<const mapped_type *>
    list_in_order(version_type version) const noexcept;
 
    [[nodiscard]] const mapped_type *find(const key_type &key,
                                          version_type version) const noexcept;
 
    [[nodiscard]] bool contains(const key_type &key,
                                version_type version) const noexcept;
 
    // ==== Size Queries ====
 
    [[nodiscard]] bool empty(version_type version) const noexcept;
 
    [[nodiscard]] size_type size(version_type version) const noexcept;
 
    [[nodiscard]] int get_height(version_type version) const noexcept;
 
    // ==== Update Operations ====
 
    void clear() noexcept;
 
    std::pair<bool, version_type> insert(const value_type &item,
                                         version_type version);
 
    std::pair<bool, version_type> insert(value_type &&item,
                                         version_type version);
 
    template <class TMapped>
    std::pair<bool, version_type> insert_or_assign(const key_type &key,
                                                   TMapped &&value,
                                                   version_type version);
 
    template <class TMapped>
    std::pair<bool, version_type>
    insert_or_assign(key_type &&key, TMapped &&value, version_type version);
 
    template <class... Args>
    std::pair<bool, version_type>
    try_emplace(const key_type &key, version_type version, Args &&...args);
 
    template <class... Args>
    std::pair<bool, version_type>
    try_emplace(key_type &&key, version_type version, Args &&...args);
 
    std::pair<bool, version_type> erase(const key_type &key,
                                        version_type version) noexcept;
 
    // ==== Swap ====
 
    void swap(persistent_map &other) noexcept;
 
    // ==== Version ====
 
    [[nodiscard]] version_type get_current_version() const noexcept {
        return tree.get_current_version();
    }
 
    [[nodiscard]] version_type
    get_preceding_version(version_type version) const {
        return tree.get_preceding_version(version);
    }
};
 
} // namespace datastructures
 
// ==== Implementation ====
 
#include "persistent_map.ipp"