association_map.hpp

Go to the documentation of this file.

 
#pragma once
 
#include "xstl/internal/map_interface.hpp"
#include <iostream>
#include <memory>
#include <vector>
#include <utility>
 
namespace xstd {

  template <typename T>
  class association_map : public internal::map_interface<association_map<T>> {
  public:
    using key_type = int32_t;
    using mapped_type = T;
    using value_type = T;
    using size_type = std::size_t;
    using iterator = value_type*;
    using const_iterator = const value_type*;
    using key_container_type = std::vector<key_type>;
    using mapped_container_type = std::vector<mapped_type>;
 
    struct containers {
      mapped_container_type values;
      key_container_type keys;
      key_container_type& keys_host;
 
      explicit containers(size_type values_size, size_type keys_size)
          : values(values_size), keys(keys_size + 1), keys_host{keys} {}
    };
 
    struct Extents {
      size_type values;
      size_type keys;
    };
 
    struct View {
      value_type* values;
      key_type* keys;
 
      constexpr std::span<value_type> operator[](key_type key) const {
        const auto offset = keys[key];
        const auto size = keys[key + 1] - offset;
        return std::span<const value_type>(values + offset, size);
      }
 
      constexpr std::span<value_type> operator[](key_type key) {
        const auto offset = keys[key];
        const auto size = keys[key + 1] - offset;
        return std::span<value_type>(values + offset, size);
      }
    };

    explicit association_map(size_type values, size_type keys)
        : m_data(values, keys),
          m_view{m_data.values.data(), m_data.keys.data()},
          m_values{values},
          m_keys{keys} {}
 
#ifdef XSTL_BUILD_DOXYGEN
    auto empty() const;
    auto size() const;
    auto extents() const;

    iterator begin();
    const_iterator begin() const;
    const_iterator cbegin() const;

    iterator end();
    const_iterator end() const;
    const_iterator cend() const;

    iterator find(key_type key);
    const_iterator find(key_type key) const;

    size_type count(key_type key) const;

    bool contains(key_type key) const;

    iterator lower_bound(key_type key);
    const_iterator lower_bound(key_type key) const;

    iterator upper_bound(key_type key);
    const_iterator upper_bound(key_type key) const;

    std::pair<iterator, iterator> equal_range(key_type key);
    std::pair<const_iterator, const_iterator> equal_range(key_type key) const;

    void fill(std::span<key_type> keys, std::span<mapped_type> values);

    View view();
#endif
 
  private:
    containers m_data;
    View m_view;
    size_type m_values;
    size_type m_keys;
 
  private:
    Extents extents_impl() const;
 
    void fill_impl(std::span<key_type> keys, std::span<mapped_type> values);
 
    friend struct internal::map_interface<association_map<T>>;
  };
 
}  // namespace xstd
 
#include "xstl/cpu/detail/association_map.hpp"