direct_map.h

Go to the documentation of this file.

/* *****************************************************************************
 * kblib is a general utility library for C++14 and C++17, intended to provide
 * performant high-level abstractions and more expressive ways to do simple
 * things.
 *
 * Copyright (c) 2021 killerbee
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 * ****************************************************************************/
 
#ifndef DIRECT_MAP_H
#define DIRECT_MAP_H
 
#include <kblib/fakestd.h>
#include <kblib/iterators.h>
#include <kblib/tdecl.h>
 
#include <array>
#include <bitset>
#include <cinttypes>
#include <climits>
#include <limits>
#include <new>
#include <optional>
 
namespace KBLIB_NS {
 
namespace detail_direct_map {
 
   template <typename T>
   KBLIB_CONSTANT auto range_of
       = (std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed
          < std::numeric_limits<std::uintmax_t>::digits)
             ? static_cast<std::uintmax_t>(1)
                   << to_unsigned(std::numeric_limits<T>::digits
                                  + std::numeric_limits<T>::is_signed)
             : 0;
   static_assert(range_of<unsigned char> == 1u << to_unsigned(CHAR_BIT), "");
   static_assert(range_of<signed char> == 1u << to_unsigned(CHAR_BIT), "");
 
   template <typename T, bool
                         = std::is_trivially_default_constructible<T>::value and
                             std::is_trivially_destructible<T>::value>
   struct alignas(T) storage_for : private std::array<byte, sizeof(T)> {
      template <
          typename... Args,
          enable_if_t<std::is_constructible<T, Args&&...>::value, int> = 0>
      constexpr auto construct(Args&&... args) noexcept(
          std::is_nothrow_constructible<T, Args&&...>::value) -> T& {
         return *new (this->data()) T(std::forward<Args>(args)...);
      }
      storage_for() = default;
      storage_for(const storage_for&) = delete;
      storage_for(storage_for&&) = delete;
 
      auto operator=(const storage_for&) -> storage_for& = delete;
      auto operator=(storage_for&&) -> storage_for& = delete;
 
      ~storage_for() = default;
 
      constexpr auto destroy() noexcept -> void { get()->~T(); }
 
#if __cpp_lib_launder
#  define LAUNDER(x) std::launder(x)
#else
#  define LAUNDER(x) (x)
#endif
      KBLIB_NODISCARD constexpr auto get() & noexcept -> T* {
         return LAUNDER(reinterpret_cast<T*>(this->data()));
      }
      KBLIB_NODISCARD constexpr auto get() const& noexcept -> const T* {
         return LAUNDER(reinterpret_cast<const T*>(this->data()));
      }
#undef LAUNDER
   };
   template <typename T>
   struct alignas(T) storage_for<T, true> {
    private:
      T t;
 
    public:
      template <
          typename... Args,
          enable_if_t<std::is_constructible<T, Args&&...>::value, int> = 0>
      constexpr auto construct(Args&&... args) noexcept(
          std::is_nothrow_constructible<T, Args&&...>::value) -> T& {
         return *new (&t) T(std::forward<Args>(args)...);
      }
 
      constexpr auto destroy() noexcept -> void {}
 
      KBLIB_NODISCARD constexpr auto get() & noexcept -> T* { return &t; }
      KBLIB_NODISCARD constexpr auto get() const& noexcept -> const T* {
         return &t;
      }
   };
 
} // namespace detail_direct_map
 
template <typename Key, typename T, typename allocator = void>
class direct_map {
   // Allocating direct_map
 public:
   using key_type = Key;
   using mapped_type = T;
   using value_type = std::pair<const Key, T>;
   using size_type = std::size_t;
   using difference_type = std::ptrdiff_t;
 
   using reference = value_type&;
   using const_reference = const value_type&;
   using pointer = value_type*;
   using const_pointer = const value_type*;
 
 private:
   constexpr static std::ptrdiff_t key_range{detail_direct_map::range_of<Key>};
   using storage_type = detail_direct_map::storage_for<value_type>;
 
   using held_type
       = std::pair<std::bitset<key_range>, std::array<storage_type, key_range>>;
 
   template <typename V>
   class iter {
    public:
      copy_const_t<V, held_type>* storage;
      std::ptrdiff_t pos;
 
      constexpr iter(decltype(storage) s, std::ptrdiff_t p)
          : storage(s)
          , pos(p) {
         if (not storage) {
            pos = max();
         }
      }
      constexpr iter()
          : iter(nullptr, max()) {}
 
      using value_type = typename direct_map::value_type;
      using difference_type = typename direct_map::difference_type;
      using reference = copy_const_t<V, value_type>&;
      using pointer = copy_const_t<V, value_type>*;
      using iterator_category = std::bidirectional_iterator_tag;
 
      KBLIB_NODISCARD constexpr auto operator*() const noexcept -> reference {
         return *storage->second[uindex(pos)].get();
      }
      KBLIB_NODISCARD constexpr auto operator->() const noexcept -> pointer {
         return storage->second[uindex(pos)].get();
      }
 
      constexpr auto operator++() noexcept -> iter& {
         if (pos == max()) {
            // not required in general, but direct_map::iterator guarantees that
            // ++end() == end() because it simplifies the implementation and is
            // unlikely to be a significant performance impact
            return *this;
         }
         for (auto i : range(++pos, index(max()))) {
            if (storage->first.test(uindex(i))) {
               pos = i;
               return *this;
            }
         }
         pos = index(max());
         return *this;
      }
      constexpr auto operator++(int) noexcept -> iter {
         iter it = *this;
         ++*this;
         return it;
      }
 
      constexpr auto operator--() noexcept -> iter& {
         for (auto i : range(pos - 1, index(min()), -1)) {
            if (storage->first.test(uindex(i))) {
               pos = i;
               return *this;
            }
         }
         pos = index(min());
         return *this;
      }
      constexpr auto operator--(int) noexcept -> iter {
         iter it = *this;
         --*this;
         return it;
      }
 
      KBLIB_NODISCARD friend constexpr auto operator==(iter l, iter r) noexcept
          -> bool {
         return l.storage == r.storage and l.pos == r.pos;
      }
      KBLIB_NODISCARD friend constexpr auto operator!=(iter l, iter r) noexcept
          -> bool {
         return not (l == r);
      }
#define DECL_OP(op)                                                           \
   KBLIB_NODISCARD friend constexpr auto operator op(iter l,                  \
                                                     iter r) noexcept->bool { \
      assert(l.storage == r.storage);                                         \
      return l.pos op r.pos;                                                  \
   }
      DECL_OP(<)
      DECL_OP(>)
      DECL_OP(>=)
      DECL_OP(<=)
#undef DECL_OP
 
      constexpr auto swap(iter& other) noexcept -> void {
         kblib::swap(storage, other.storage);
         kblib::swap(pos, other.pos);
      }
   };
 
 public:
   using iterator = iter<value_type>;
   using const_iterator = iter<const value_type>;
   using reverse_iterator = std::reverse_iterator<iterator>;
   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
   constexpr direct_map() noexcept = default;
 
   template <typename InputIt>
   constexpr direct_map(InputIt first, InputIt last)
       : storage() {
      if (first != last) {
         allocate();
         for (auto v : indirect(first, last)) {
            construct(v.first, v.second);
         }
      }
   }
   // TODO(killerbee13): copy construction for allocating direct_map
   constexpr direct_map(const direct_map& other)
       : storage()
       , _size(other._size) {
      if (not other.empty()) {
         allocate();
         storage->first = other.storage->first;
         for (auto k : range(+min(), max() + 1)) {
            if (contains(k)) { // the bitmap is already copied from other
               do_construct(k, other.at(k));
            }
         }
      }
   }
 
   constexpr direct_map(direct_map&& other) noexcept
       : storage(std::move(other.storage))
       , _size(std::exchange(other._size, 0)) {}
 
   constexpr direct_map(std::initializer_list<value_type> init)
       : direct_map(init.begin(), init.end()) {}
 
   KBLIB_CXX20(constexpr) ~direct_map() { clear(); }
 
   constexpr auto operator=(const direct_map& other) -> direct_map& {
      if (this == &other) {
         return *this;
      }
      clear();
      storage.assign(in_place_agg, other.storage->first);
      _size = other._size;
      for (auto k : range(+min(), max() + 1)) {
         if (contains(k)) { // the bitmap is already copied from other
            do_construct(k, other.at(k));
            bitmap().set(index(k));
         }
      }
      return *this;
   }
   constexpr auto operator=(direct_map&& other) noexcept
       -> direct_map& = default;
   constexpr auto operator=(std::initializer_list<value_type> init)
       -> direct_map& {
      clear();
      for (auto it : init) {
         construct(it->first, it->second);
      }
      return *this;
   }
 
   KBLIB_NODISCARD constexpr auto at(Key key) & -> T& {
      if (contains(key)) {
         return unsafe_at(key).get()->second;
      } else {
         throw std::out_of_range("direct_map: key out of range");
      }
   }
   KBLIB_NODISCARD constexpr auto at(Key key) && -> T&& {
      if (contains(key)) {
         return std::move(unsafe_at(key).get()->second);
      } else {
         throw std::out_of_range("direct_map: key out of range");
      }
   }
   KBLIB_NODISCARD constexpr auto at(Key key) const& -> const T& {
      if (contains(key)) {
         return unsafe_at(key).get()->second;
      } else {
         throw std::out_of_range("direct_map: key out of range");
      }
   }
   KBLIB_NODISCARD constexpr auto at(Key key) const&& -> const T&& {
      if (contains(key)) {
         return std::move(unsafe_at(key).get()->second);
      } else {
         throw std::out_of_range("direct_map: key out of range");
      }
   }
 
   KBLIB_NODISCARD constexpr T& operator[](Key key) noexcept(
       std::is_nothrow_default_constructible<T>::value) {
      return try_emplace(key).first->second;
   }
 
   KBLIB_NODISCARD constexpr auto begin() & noexcept -> iterator {
      return {storage.get(), cbegin().pos};
   }
   KBLIB_NODISCARD constexpr auto begin() const& noexcept -> const_iterator {
      return {storage.get(), cbegin().pos};
   }
   KBLIB_NODISCARD constexpr auto cbegin() const& noexcept -> const_iterator {
      if (not empty()) {
         if (contains(to_key(min()))) {
            return {storage.get(), min()};
         } else {
            return ++const_iterator{storage.get(), min()};
         }
      } else {
         return end();
      }
   }
 
   KBLIB_NODISCARD constexpr auto end() & noexcept -> iterator {
      return {storage.get(), max()};
   }
   KBLIB_NODISCARD constexpr auto end() const& noexcept -> const_iterator {
      return {storage.get(), max()};
   }
   KBLIB_NODISCARD constexpr auto cend() const& noexcept -> const_iterator {
      return {storage.get(), max()};
   }
 
   KBLIB_NODISCARD constexpr auto rbegin() & noexcept -> auto {
      return std::make_reverse_iterator(end());
   }
   KBLIB_NODISCARD constexpr auto rbegin() const& noexcept -> auto {
      return std::make_reverse_iterator(end());
   }
   KBLIB_NODISCARD constexpr auto crbegin() const& noexcept -> auto {
      return std::make_reverse_iterator(cend());
   }
 
   KBLIB_NODISCARD constexpr auto rend() & noexcept -> auto {
      return std::make_reverse_iterator(begin());
   }
   KBLIB_NODISCARD constexpr auto rend() const& noexcept -> auto {
      return std::make_reverse_iterator(begin());
   }
   KBLIB_NODISCARD constexpr auto crend() const& noexcept -> auto {
      return std::make_reverse_iterator(cbegin());
   }
 
   KBLIB_NODISCARD constexpr auto empty() const& noexcept -> bool {
      return _size == 0;
   }
 
   KBLIB_NODISCARD constexpr auto size() const& noexcept -> std::size_t {
      return _size;
   }
   KBLIB_NODISCARD constexpr auto ssize() const& noexcept -> std::ptrdiff_t {
      return _size;
   }
 
   KBLIB_NODISCARD constexpr static auto max_size() noexcept -> std::size_t {
      return key_range;
   }
 
   constexpr auto clear() noexcept -> void {
      if (_size == 0) {
         return;
      }
      for (auto i : range(+min(), max() + 1)) {
         auto j = static_cast<Key>(i);
         if (contains(j)) {
            unsafe_at(j).destroy();
         }
      }
      storage.reset();
      _size = 0;
   }
 
   constexpr auto insert(const value_type& value) -> std::pair<iterator, bool> {
      if (not contains(value.first)) {
         construct(value.first, value.second);
         return {{storage.get(), index(value.first)}, true};
      } else {
         return {{storage.get(), index(value.first)}, false};
      }
   }
   template <typename U>
   constexpr auto insert(U&& value)
       -> enable_if_t<std::is_constructible<value_type, U&&>::value,
                      std::pair<iterator, bool>> {
      if (not contains(value.first)) {
         construct(value.first, std::forward<U>(value.second));
         return {{storage.get(), index(value.first)}, true};
      } else {
         return {{storage.get(), index(value.first)}, false};
      }
   }
   constexpr auto insert(value_type&& value) -> std::pair<iterator, bool> {
      if (not contains(value.first)) {
         construct(value.first, std::move(value.second));
         return {{storage.get(), index(value.first)}, true};
      } else {
         return {{storage.get(), index(value.first)}, false};
      }
   }
 
   template <typename U>
   constexpr auto insert_or_assign(Key key, U&& value)
       -> std::pair<iterator, bool> {
      if (not contains(key)) {
         construct(key, std::forward<U>(value));
         return {{storage.get(), index(key)}, true};
      } else {
         *unsafe_at(key).get() = std::forward<U>(value);
         return {{storage.get(), index(key)}, false};
      }
   }
   template <typename... Args>
   constexpr auto try_emplace(Key key, Args&&... args)
       -> std::pair<iterator, bool> {
      if (not contains(key)) {
         construct(key, std::forward<Args>(args)...);
         return {{storage.get(), index(key)}, true};
      } else {
         return {{storage.get(), index(key)}, false};
      }
   }
 
   constexpr auto erase(iterator pos) noexcept -> iterator {
      assert(contains(to_key(pos.pos)));
      bitmap().reset(pos.pos);
      unsafe_at(to_key(pos.pos)).destroy();
      --_size;
      return ++pos;
   }
   constexpr auto erase(const_iterator pos) noexcept -> iterator {
      assert(contains(to_key(pos.pos)));
      bitmap().reset(pos.pos);
      unsafe_at(to_key(pos.pos)).destroy();
      --_size;
      return ++pos;
   }
 
   constexpr auto erase(iterator first, iterator last) noexcept -> iterator {
      for (auto i : range(first.pos, last.pos)) {
         if (contains(to_key(i))) {
            bitmap().reset(i);
            unsafe_at(to_key(i)).destroy();
            --_size;
         }
      }
      return ++last;
   }
 
   constexpr auto erase(Key key) noexcept -> std::size_t {
      if (contains(key)) {
         bitmap().reset(index(key));
         unsafe_at(key).destroy();
         --_size;
         return 1;
      } else {
         return 0;
      }
   }
 
   constexpr auto swap(direct_map& other) noexcept -> void {
      using std::swap;
      swap(storage, other.storage);
      swap(_size, other._size);
   }
 
   KBLIB_NODISCARD constexpr auto contains(Key key) const noexcept -> bool {
      return storage and bitmap().test(uindex(key));
   }
   KBLIB_NODISCARD constexpr auto count(Key key) const noexcept -> std::size_t {
      return contains(key);
   }
 
   KBLIB_NODISCARD constexpr auto find(Key key) & noexcept -> iterator {
      return contains(key) ? iterator{storage.get(), index(key)} : end();
   }
   KBLIB_NODISCARD constexpr auto find(Key key) const& noexcept
       -> const_iterator {
      return contains(key) ? iterator{storage.get(), index(key)} : end();
   }
 
   KBLIB_NODISCARD constexpr auto equal_range(Key key) & noexcept
       -> std::pair<iterator, iterator> {
      return {lower_bound(key), upper_bound(key)};
   }
   KBLIB_NODISCARD constexpr auto equal_range(Key key) const& noexcept
       -> std::pair<const_iterator, const_iterator> {
      return {lower_bound(key), upper_bound(key)};
   }
 
   KBLIB_NODISCARD constexpr auto lower_bound(Key key) & noexcept -> iterator {
      if (contains(key)) {
         return find(key);
      } else {
         return ++iterator{storage.get(), index(key)};
      }
   }
   KBLIB_NODISCARD constexpr auto lower_bound(Key key) const& noexcept
       -> const_iterator {
      if (contains(key)) {
         return find(key);
      } else {
         return ++iterator{storage.get(), index(key)};
      }
   }
 
   KBLIB_NODISCARD constexpr auto upper_bound(Key key) & noexcept -> iterator {
      // if the key exists, upper_bound is the next one
      auto l = lower_bound(key);
      if (l.pos == index(key)) {
         return ++l;
         // otherwise upper_bound == lower_bound
      } else {
         return l;
      }
   }
   KBLIB_NODISCARD constexpr auto upper_bound(Key key) const& noexcept
       -> const_iterator {
      // if the key exists, upper_bound is the next one
      auto l = lower_bound(key);
      if (l.pos == index(key)) {
         return ++l;
         // otherwise upper_bound == lower_bound
      } else {
         return l;
      }
   }
 
   KBLIB_NODISCARD constexpr static auto min() noexcept -> Key {
      return std::numeric_limits<Key>::min();
   }
   KBLIB_NODISCARD constexpr static auto max() noexcept -> Key {
      return std::numeric_limits<Key>::max();
   }
 
   KBLIB_NODISCARD friend constexpr auto operator==(
       const direct_map& l,
       const direct_map& r) noexcept(noexcept(std::declval<T&>()
                                              == std::declval<T&>())) -> bool {
      if (l.size() != r.size()) {
         return false;
      }
      for (auto i : kblib::range(+min(), max() + 1)) {
         if (l.contains(i) != r.contains(i)) {
            return false;
         } else if (l.contains(i)) {
            if (l.at(i) != r.at(i)) {
               return false;
            }
         }
      }
      return true;
   }
 
   KBLIB_NODISCARD friend constexpr auto operator!=(
       const direct_map& l,
       const direct_map& r) noexcept(noexcept(std::declval<T&>()
                                              == std::declval<T&>())) -> bool {
      return not (l == r);
   }
 
   KBLIB_NODISCARD friend constexpr auto operator<(
       const direct_map& l,
       const direct_map& r) noexcept(noexcept(std::declval<T&>(),
                                              std::declval<T&>())) -> bool {
      return kblib::lexicographical_compare(l.begin(), l.end(), r.begin(),
                                            r.end());
   }
   KBLIB_NODISCARD friend constexpr auto operator>(
       const direct_map& l,
       const direct_map& r) noexcept(noexcept(std::declval<T&>(),
                                              std::declval<T&>())) -> bool {
      return r < l;
   }
   KBLIB_NODISCARD friend constexpr auto operator<=(
       const direct_map& l,
       const direct_map& r) noexcept(noexcept(std::declval<T&>(),
                                              std::declval<T&>())) -> bool {
      return not (r < l);
   }
   KBLIB_NODISCARD friend constexpr auto operator>=(
       const direct_map& l,
       const direct_map& r) noexcept(noexcept(std::declval<T&>(),
                                              std::declval<T&>())) -> bool {
      return not (l < r);
   }
 
   KBLIB_NODISCARD constexpr static auto index(Key key) noexcept
       -> std::ptrdiff_t {
      return to_signed(key);
   }
   KBLIB_NODISCARD constexpr static auto uindex(Key key) noexcept
       -> std::size_t {
      return to_unsigned(key);
   }
   KBLIB_NODISCARD constexpr static auto to_key(std::ptrdiff_t i) noexcept
       -> Key {
      return Key(i);
   }
 
 private:
   KBLIB_NODISCARD constexpr auto bitmap() noexcept -> std::bitset<key_range>& {
      return storage->first;
   }
   KBLIB_NODISCARD constexpr const std::bitset<key_range>& bitmap()
       const noexcept {
      return storage->first;
   }
 
   KBLIB_NODISCARD constexpr auto unsafe_at(Key key) & -> storage_type& {
      return storage->second[uindex(key)];
   }
   KBLIB_NODISCARD constexpr auto unsafe_at(Key key) && -> storage_type&& {
      return storage->second[uindex(key)];
   }
   KBLIB_NODISCARD constexpr auto unsafe_at(Key key) const& -> const
       storage_type& {
      return storage->second[uindex(key)];
   }
   KBLIB_NODISCARD constexpr auto unsafe_at(Key key) const&& -> const
       storage_type&& {
      return storage->second[uindex(key)];
   }
 
   auto allocate() -> void {
      if (not storage) {
         storage.assign();
      }
   }
 
   template <typename... Args>
   constexpr void construct(Key key, Args&&... args) noexcept(
       std::is_nothrow_constructible<value_type, Args&&...>::value) {
      allocate();
      if (not storage->first.test(uindex(key))) {
         do_construct(key, std::forward<Args>(args)...);
         // doing these after construction maintains exception safety.
         storage->first.set(uindex(key));
         ++_size;
      }
   }
 
   template <typename... Args>
   constexpr void do_construct(Key key, Args&&... args) noexcept(
       std::is_nothrow_constructible<value_type, Args&&...>::value) {
      storage->second[uindex(key)].construct(
          std::piecewise_construct, std::forward_as_tuple(key),
          std::forward_as_tuple(std::forward<Args>(args)...));
   }
 
   // TODO(killerbee13): Implement, test, and document direct_map
   // TODO(killerbee13): allocator support for direct_map
   kblib::heap_value<held_type> storage;
   std::size_t _size{};
};
 
template <typename Key, typename T>
class direct_map<Key, T, void> {
   // Non-allocating direct_map
 public:
   using key_type = Key;
   using mapped_type = T;
   using value_type = std::pair<const Key, T>;
   using size_type = std::size_t;
   using difference_type = std::ptrdiff_t;
 
   using reference = value_type&;
   using const_reference = const value_type&;
   using pointer = value_type*;
   using const_pointer = const value_type*;
 
 private:
   constexpr static std::ptrdiff_t key_range{detail_direct_map::range_of<Key>};
   using storage_type = detail_direct_map::storage_for<value_type>;
 
   template <typename V>
   class iter {
    public:
      copy_const_t<V, direct_map>* map;
      std::ptrdiff_t pos;
 
      constexpr iter(decltype(map) s, std::ptrdiff_t p)
          : map(s)
          , pos(p) {
         if (not map) {
            pos = max();
         }
      }
      constexpr iter()
          : iter(nullptr, max()) {}
 
      using value_type = typename direct_map::value_type;
      using difference_type = typename direct_map::difference_type;
      using reference = copy_const_t<V, value_type>&;
      using pointer = copy_const_t<V, value_type>*;
      using iterator_category = std::bidirectional_iterator_tag;
 
      KBLIB_NODISCARD constexpr auto operator*() const -> reference {
         return *map->elems[uindex(pos)].get();
      }
      KBLIB_NODISCARD constexpr auto operator->() const -> pointer {
         return map->elems[uindex(pos)].get();
      }
 
      constexpr auto operator++() -> iter& {
         if (pos == max()) {
            // not required in general, but direct_map::iterator guarantees that
            // ++end() == end() because it simplifies the implementation and is
            // unlikely to be a significant performance impact
            return *this;
         }
         for (auto i : range(++pos, index(max()))) {
            if (map->active_elems.test(uindex(i))) {
               pos = i;
               return *this;
            }
         }
         pos = index(max());
         return *this;
      }
      constexpr auto operator++(int) -> iter {
         iter it = *this;
         ++*this;
         return it;
      }
 
      constexpr auto operator--() -> iter& {
         for (auto i : range(pos - 1, index(min()), -1)) {
            if (map->active_elems.test(uindex(i))) {
               pos = i;
               return *this;
            }
         }
         pos = index(min());
         return *this;
      }
      constexpr auto operator--(int) -> iter {
         iter it = *this;
         --*this;
         return it;
      }
 
      KBLIB_NODISCARD friend constexpr auto operator==(iter l, iter r) noexcept
          -> bool {
         return l.map == r.map and l.pos == r.pos;
      }
      KBLIB_NODISCARD friend constexpr auto operator!=(iter l, iter r) noexcept
          -> bool {
         return not (l == r);
      }
 
#define DECL_OP(op)                                                           \
   KBLIB_NODISCARD friend constexpr auto operator op(iter l,                  \
                                                     iter r) noexcept->bool { \
      assert(l.map == r.map);                                                 \
      return l.pos op r.pos;                                                  \
   }
      DECL_OP(<)
      DECL_OP(>)
      DECL_OP(>=)
      DECL_OP(<=)
#undef DECL_OP
 
      constexpr auto swap(iter& other) noexcept -> void {
         kblib::swap(map, other.map);
         kblib::swap(pos, other.pos);
      }
   };
 
 public:
   using iterator = iter<value_type>;
   using const_iterator = iter<const value_type>;
   using reverse_iterator = std::reverse_iterator<iterator>;
   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
   constexpr direct_map() noexcept = default;
 
   template <typename InputIt>
   constexpr direct_map(InputIt first, InputIt last) {
      for (auto&& v : indirect(first, last)) {
         construct(std::forward<decltype(v)>(v).first,
                   std::forward<decltype(v)>(v).second);
      }
   }
 
   constexpr direct_map(const direct_map& other)
       : active_elems{other.active_elems}
       , _size(other._size) {
      for (const key_type k : range(+min(), max() + 1)) {
         if (contains(k)) { // the bitmap is already copied from other
            do_construct(k, other.unsafe_at(k).get()->second);
            bitmap().set(uindex(k));
         }
      }
   }
 
   constexpr direct_map(direct_map&& other) noexcept(
       std::is_nothrow_move_constructible<value_type>::value)
       : active_elems{other.active_elems}
       , _size(other._size) {
      for (const key_type k : range(+min(), max() + 1)) {
         if (contains(k)) { // the bitmap is already copied from other
            do_construct(k, std::move(other.unsafe_at(k).get()->second));
            bitmap().set(uindex(k));
         }
      }
   }
 
   constexpr direct_map(std::initializer_list<value_type> init)
       : direct_map(init.begin(), init.end()) {}
 
   // TODO(killerbee13): Remove this and allow it to be trivially destructible
   // for trivial Key and T
   KBLIB_CXX20(constexpr) ~direct_map() { clear(); }
 
   constexpr auto operator=(const direct_map& other) -> direct_map& {
      if (this == &other) {
         return *this;
      }
      clear();
      active_elems = other.active_elems;
      _size = other._size;
      for (const key_type k : range(+min(), max() + 1)) {
         if (contains(k)) { // the bitmap is already copied from other
            do_construct(k, other.unsafe_at(k).get()->second);
            bitmap().set(uindex(k));
         }
      }
      return *this;
   }
   constexpr auto operator=(direct_map&& other) noexcept(
       std::is_nothrow_move_constructible<T>::value) -> direct_map& {
      if (this == &other) {
         return *this;
      }
      active_elems = other.active_elems;
      _size = other._size;
      for (const key_type k : range(+min(), max() + 1)) {
         if (contains(k)) { // the bitmap is already copied from other
            do_construct(k, std::move(other.unsafe_at(k).get()->second));
            bitmap().set(uindex(k));
         }
      }
      return *this;
   }
   constexpr auto operator=(std::initializer_list<value_type> init)
       -> direct_map& {
      clear();
      for (auto it : init) {
         construct(it->first, it->second);
      }
      return *this;
   }
 
   KBLIB_NODISCARD constexpr auto at(Key key) & -> T& {
      if (contains(key)) {
         return unsafe_at(key).get()->second;
      } else {
         throw std::out_of_range("direct_map: key out of range");
      }
   }
   KBLIB_NODISCARD constexpr auto at(Key key) && -> T&& {
      if (contains(key)) {
         return std::move(unsafe_at(key).get()->second);
      } else {
         throw std::out_of_range("direct_map: key out of range");
      }
   }
   KBLIB_NODISCARD constexpr auto at(Key key) const& -> const T& {
      if (contains(key)) {
         return unsafe_at(key).get()->second;
      } else {
         throw std::out_of_range("direct_map: key out of range");
      }
   }
   KBLIB_NODISCARD constexpr auto at(Key key) const&& -> const T&& {
      if (contains(key)) {
         return std::move(unsafe_at(key).get()->second);
      } else {
         throw std::out_of_range("direct_map: key out of range");
      }
   }
 
   KBLIB_NODISCARD constexpr T& operator[](Key key) noexcept(
       std::is_nothrow_default_constructible<T>::value) {
      return try_emplace(key).first->second;
   }
 
   KBLIB_NODISCARD constexpr auto begin() & noexcept -> iterator {
      return {this, cbegin().pos};
   }
   KBLIB_NODISCARD constexpr auto begin() const& noexcept -> const_iterator {
      return {this, cbegin().pos};
   }
   KBLIB_NODISCARD constexpr auto cbegin() const& noexcept -> const_iterator {
      if (not empty()) {
         if (contains(to_key(min()))) {
            return {this, min()};
         } else {
            return ++const_iterator{this, min()};
         }
      } else {
         return end();
      }
   }
 
   KBLIB_NODISCARD constexpr auto end() & noexcept -> iterator {
      return {this, max()};
   }
   KBLIB_NODISCARD constexpr auto end() const& noexcept -> const_iterator {
      return {this, max()};
   }
   KBLIB_NODISCARD constexpr auto cend() const& noexcept -> const_iterator {
      return {this, max()};
   }
 
   KBLIB_NODISCARD constexpr auto rbegin() & noexcept -> reverse_iterator {
      return std::make_reverse_iterator(end());
   }
   KBLIB_NODISCARD constexpr auto rbegin() const& noexcept
       -> const_reverse_iterator {
      return std::make_reverse_iterator(end());
   }
   KBLIB_NODISCARD constexpr auto crbegin() const& noexcept
       -> const_reverse_iterator {
      return std::make_reverse_iterator(crend());
   }
 
   KBLIB_NODISCARD constexpr auto rend() & noexcept -> reverse_iterator {
      return std::make_reverse_iterator(begin());
   }
   KBLIB_NODISCARD constexpr auto rend() const& noexcept
       -> const_reverse_iterator {
      return std::make_reverse_iterator(begin());
   }
   KBLIB_NODISCARD constexpr auto crend() const& noexcept
       -> const_reverse_iterator {
      return std::make_reverse_iterator(cbegin());
   }
 
   KBLIB_NODISCARD constexpr auto empty() const& noexcept -> bool {
      return _size == 0;
   }
 
   KBLIB_NODISCARD constexpr auto size() const& noexcept -> std::size_t {
      return _size;
   }
   KBLIB_NODISCARD constexpr auto ssize() const& noexcept -> std::ptrdiff_t {
      return _size;
   }
 
   KBLIB_NODISCARD constexpr static auto max_size() noexcept -> std::size_t {
      return key_range;
   }
 
   constexpr auto clear() noexcept -> void {
      for (auto i : range(+min(), max() + 1)) {
         auto j = static_cast<Key>(i);
         if (contains(j)) {
            unsafe_at(j).destroy();
         }
      }
      _size = 0;
   }
 
   constexpr auto insert(const value_type& value) -> std::pair<iterator, bool> {
      if (not contains(value.first)) {
         construct(value.first, value.second);
         return {{this, index(value.first)}, true};
      } else {
         return {{this, index(value.first)}, false};
      }
   }
   template <typename U>
   constexpr auto insert(U&& value)
       -> return_assert_t<std::is_constructible<value_type, U&&>::value,
                          std::pair<iterator, bool>> {
      if (not contains(value.first)) {
         construct(value.first, std::forward<U>(value.second));
         return {{this, index(value.first)}, true};
      } else {
         return {{this, index(value.first)}, false};
      }
   }
   constexpr auto insert(value_type&& value) -> std::pair<iterator, bool> {
      if (not contains(value.first)) {
         construct(value.first, std::move(value.second));
         return {{this, index(value.first)}, true};
      } else {
         return {{this, index(value.first)}, false};
      }
   }
 
   template <typename U>
   constexpr auto insert_or_assign(Key key, U&& value)
       -> std::pair<iterator, bool> {
      if (not contains(key)) {
         construct(key, std::forward<U>(value));
         return {{this, index(key)}, true};
      } else {
         *unsafe_at(key).get() = std::forward<U>(value);
         return {{this, index(key)}, false};
      }
   }
   template <typename... Args>
   constexpr auto try_emplace(Key key, Args&&... args)
       -> std::pair<iterator, bool> {
      if (not contains(key)) {
         construct(key, std::forward<Args>(args)...);
         return {{this, index(key)}, true};
      } else {
         return {{this, index(key)}, false};
      }
   }
 
   constexpr auto erase(iterator pos) noexcept -> iterator {
      assert(contains(to_key(pos.pos)));
      destroy(to_key(pos.pos));
      return ++pos;
   }
   constexpr auto erase(const_iterator pos) noexcept -> iterator {
      assert(contains(to_key(pos.pos)));
      destroy(to_key(pos.pos));
      return ++pos;
   }
 
   constexpr auto erase(iterator first, iterator last) noexcept -> iterator {
      for (auto i : range(first.pos, last.pos)) {
         if (contains(to_key(i))) {
            destroy(to_key(i));
         }
      }
      return ++last;
   }
 
   constexpr auto erase(Key key) noexcept -> std::size_t {
      if (contains(key)) {
         destroy(key);
         return 1;
      } else {
         return 0;
      }
   }
 
   constexpr auto swap(direct_map& other) noexcept(
       std::is_nothrow_move_constructible<value_type>::value and
           fakestd::is_nothrow_swappable<T>::value) -> void {
      using std::swap;
      for (const key_type k : range(+min(), max() + 1)) {
         if (contains(k)) {
            if (other.contains(k)) {
               kblib::swap(unsafe_at(k).get()->second,
                           other.unsafe_at(k).get()->second);
            } else {
               other.construct(k, std::move(unsafe_at(k).get()->second));
               destroy(k);
            }
         } else if (other.contains(k)) {
            construct(k, std::move(other.unsafe_at(k).get()->second));
            other.destroy(k);
         } else {
            // do nothing
         }
      }
 
      swap(active_elems, other.active_elems);
      swap(_size, other._size);
   }
 
   KBLIB_NODISCARD constexpr auto contains(Key key) const noexcept -> bool {
      return bitmap().test(uindex(key));
   }
   KBLIB_NODISCARD constexpr auto count(Key key) const noexcept -> std::size_t {
      return contains(key);
   }
 
   KBLIB_NODISCARD constexpr auto find(Key key) & noexcept -> iterator {
      return contains(key) ? iterator{this, index(key)} : end();
   }
   KBLIB_NODISCARD constexpr auto find(Key key) const& noexcept
       -> const_iterator {
      return contains(key) ? iterator{this, index(key)} : end();
   }
 
   KBLIB_NODISCARD constexpr auto equal_range(Key key) & noexcept
       -> std::pair<iterator, iterator> {
      return {lower_bound(key), upper_bound(key)};
   }
   KBLIB_NODISCARD constexpr auto equal_range(Key key) const& noexcept
       -> std::pair<const_iterator, const_iterator> {
      return {lower_bound(key), upper_bound(key)};
   }
 
   KBLIB_NODISCARD constexpr auto lower_bound(Key key) & noexcept -> iterator {
      if (contains(key)) {
         return find(key);
      } else {
         return ++iterator{this, index(key)};
      }
   }
   KBLIB_NODISCARD constexpr auto lower_bound(Key key) const& noexcept
       -> const_iterator {
      if (contains(key)) {
         return find(key);
      } else {
         return ++iterator{this, index(key)};
      }
   }
 
   KBLIB_NODISCARD constexpr auto upper_bound(Key key) & noexcept -> iterator {
      // if the key exists, upper_bound is the next one
      auto l = lower_bound(key);
      if (l.pos == index(key)) {
         return ++l;
         // otherwise upper_bound == lower_bound
      } else {
         return l;
      }
   }
   KBLIB_NODISCARD constexpr auto upper_bound(Key key) const& noexcept
       -> const_iterator {
      // if the key exists, upper_bound is the next one
      auto l = lower_bound(key);
      if (l.pos == index(key)) {
         return ++l;
         // otherwise upper_bound == lower_bound
      } else {
         return l;
      }
   }
 
   KBLIB_NODISCARD constexpr static auto min() noexcept -> Key {
      return std::numeric_limits<Key>::min();
   }
   KBLIB_NODISCARD constexpr static auto max() noexcept -> Key {
      return std::numeric_limits<Key>::max();
   }
 
   KBLIB_NODISCARD friend constexpr auto operator==(
       const direct_map& l,
       const direct_map& r) noexcept(noexcept(std::declval<T&>()
                                              == std::declval<T&>())) -> bool {
      if (l.size() != r.size()) {
         return false;
      }
      for (const key_type i : kblib::range(+min(), max() + 1)) {
         if (l.contains(i) != r.contains(i)) {
            return false;
         } else if (l.contains(i)) {
            if (l.at(i) != r.at(i)) {
               return false;
            }
         }
      }
      return true;
   }
 
   KBLIB_NODISCARD friend constexpr auto operator!=(
       const direct_map& l,
       const direct_map& r) noexcept(noexcept(std::declval<T&>()
                                              == std::declval<T&>())) -> bool {
      return not (l == r);
   }
 
   KBLIB_NODISCARD friend constexpr auto operator<(
       const direct_map& l,
       const direct_map& r) noexcept(noexcept(std::declval<T&>(),
                                              std::declval<T&>())) -> bool {
      return kblib::lexicographical_compare(l.begin(), l.end(), r.begin(),
                                            r.end());
   }
   KBLIB_NODISCARD friend constexpr auto operator>(
       const direct_map& l,
       const direct_map& r) noexcept(noexcept(std::declval<T&>(),
                                              std::declval<T&>())) -> bool {
      return r < l;
   }
   KBLIB_NODISCARD friend constexpr auto operator<=(
       const direct_map& l,
       const direct_map& r) noexcept(noexcept(std::declval<T&>(),
                                              std::declval<T&>())) -> bool {
      return not (r < l);
   }
   KBLIB_NODISCARD friend constexpr auto operator>=(
       const direct_map& l,
       const direct_map& r) noexcept(noexcept(std::declval<T&>(),
                                              std::declval<T&>())) -> bool {
      return not (l < r);
   }
 
   KBLIB_NODISCARD constexpr static auto index(Key key) noexcept
       -> std::ptrdiff_t {
      return to_signed(key);
   }
   KBLIB_NODISCARD constexpr static auto uindex(Key key) noexcept
       -> std::size_t {
      return to_unsigned(key);
   }
   KBLIB_NODISCARD constexpr static auto to_key(std::ptrdiff_t i) noexcept
       -> Key {
      return Key(i);
   }
 
 private:
   KBLIB_NODISCARD constexpr auto bitmap() noexcept -> std::bitset<key_range>& {
      return active_elems;
   }
   KBLIB_NODISCARD constexpr auto bitmap() const noexcept
       -> const std::bitset<key_range>& {
      return active_elems;
   }
 
   KBLIB_NODISCARD constexpr auto unsafe_at(Key key) & -> storage_type& {
      return elems[uindex(key)];
   }
   KBLIB_NODISCARD constexpr auto unsafe_at(Key key) && -> storage_type&& {
      return elems[uindex(key)];
   }
   KBLIB_NODISCARD constexpr auto unsafe_at(Key key) const& -> const
       storage_type& {
      return elems[uindex(key)];
   }
   KBLIB_NODISCARD constexpr auto unsafe_at(Key key) const&& -> const
       storage_type&& {
      return elems[uindex(key)];
   }
 
   template <typename... Args>
   constexpr auto construct(Key key, Args&&... args) noexcept(
       std::is_nothrow_constructible<value_type, Args&&...>::value) -> void {
      if (not active_elems.test(uindex(key))) {
         do_construct(key, std::forward<Args>(args)...);
         // doing these after construction maintains exception safety.
         active_elems.set(uindex(key));
         ++_size;
      }
   }
 
   template <typename... Args>
   constexpr auto do_construct(Key key, Args&&... args) noexcept(
       std::is_nothrow_constructible<value_type, Args&&...>::value) -> void {
      elems[uindex(key)].construct(
          std::piecewise_construct, std::forward_as_tuple(key),
          std::forward_as_tuple(std::forward<Args>(args)...));
   }
 
   auto destroy(Key key) -> void {
      assert(contains(key));
 
      bitmap().reset(uindex(key));
      unsafe_at(key).destroy();
      --_size;
   }
 
   // TODO(killerbee13): Implement, test, and document direct_map
 
   std::bitset<key_range> active_elems;
   std::array<storage_type, key_range> elems;
 
   std::size_t _size{};
};
 
} // namespace KBLIB_NS
 
#endif // DIRECT_MAP_H