#include <iostream>
#include <utility>
#include <cassert>
#include <stdexcept>
#include <type_traits>
#include <array>
#include <experimental/string_view>
// #define USE_TEMPLATES
namespace {
////////////////////////////////////////////////////////////////////////////////
/// I used this class in place of `std::runtime_error` because GCC has
/// trouble inlining/evaluating constexpr code that uses `std::runtime_error`.
////////////////////////////////////////////////////////////////////////////////
struct key_not_found_error : std::exception {
auto what() const noexcept -> char const* override
{
return "Key not found.";
}
};
template < class _Pair
, class _Key
, std::size_t _N
, class _Pred
>
__attribute__((always_inline))
inline
constexpr
auto ls_at_impl( _Pair const (&values) [_N]
, _Key&& key
, _Pred&& equal )
{
std::size_t i = 0;
while (i < _N and not equal(values[i].first, key)) {
++i;
}
return i;
}
////////////////////////////////////////////////////////////////////////////////
/// LINEAR SEARCH.
////////////////////////////////////////////////////////////////////////////////
template < class _Pair
, class _Key
, std::size_t _N
, class _Pred
>
__attribute__((always_inline))
inline
constexpr
// Notice the decltype(auto) -- we want to return a by reference rather than
// by value.
decltype(auto) ls_at( _Pair (&values) [_N]
, _Key&& key
, _Pred&& equal )
{
auto const i = ls_at_impl( values
, std::forward<_Key>(key)
, std::forward<_Pred>(equal) );
return i != _N
? values[i].second
: (throw key_not_found_error{}, values[0].second);
}
////////////////////////////////////////////////////////////////////////////////
/// ITERATORS
////////////////////////////////////////////////////////////////////////////////
template < class _Key, class _Tp
, std::size_t _N
, bool _is_const // allows us to write a single struct for both
// const and non-const iterators
>
struct map_iterator {
using difference_type = std::ptrdiff_t;
using value_type =
std::conditional_t< _is_const
, std::pair<_Key const, _Tp> const
, std::pair<_Key const, _Tp> >;
using pointer = std::add_pointer_t<value_type>;
using reference = std::add_lvalue_reference_t<value_type>;
using iterator_category = std::random_access_iterator_tag;
private:
using _iterator = map_iterator<_Key, _Tp, _N, _is_const>;
using _const_iterator = map_iterator<_Key, _Tp, _N, /*is_const = */ true>;
static constexpr std::size_t _size = _N;
// We store a pointer rather than a reference, because we need
// map_iterator to be default constructible.
value_type (*_vs)[_size];
std::size_t _i;
public:
constexpr
map_iterator() noexcept
: _vs{ nullptr }
, _i{ 0 }
{}
constexpr
map_iterator( value_type (&values)[_size]
, std::size_t const pos ) noexcept
: _vs{ &values }
, _i{ pos }
{}
constexpr map_iterator(_iterator const& other) noexcept = default;
constexpr _iterator& operator=(_iterator const& other) noexcept = default;
__attribute__((always_inline))
constexpr auto operator*() const -> reference
{
return _vs != nullptr
? ( _i < _N
? (*_vs)[_i]
: ( throw std::out_of_range{"Iterator not dereferenceable."}
, (*_vs)[0] )
)
: ( throw std::invalid_argument{"Iterator not dereferenceable."}
, (*_vs)[0] );
}
constexpr auto operator->() const -> pointer
{ return &(*(*this)); }
__attribute__((always_inline))
constexpr auto operator++() noexcept -> _iterator&
{ ++_i; return *this; }
__attribute__((always_inline))
constexpr auto operator++(int) noexcept -> _iterator
{
_iterator saved{ *this };
++(*this);
return saved;
}
__attribute__((always_inline))
constexpr
auto operator-(_iterator const& other) const
-> difference_type
{
return _vs == other._vs
? (_i - other._i)
: ( throw std::invalid_argument{"Iterators not comparable."}
, 0 );
}
__attribute__((always_inline))
constexpr auto operator==(_iterator const& other) const -> bool
{ return (_vs == other._vs) and (_i == other._i); }
__attribute__((always_inline))
constexpr auto operator!=(_iterator const& other) const -> bool
{ return not (*this == other); }
__attribute__((always_inline))
constexpr auto operator< (_iterator const& other) const -> bool
{ return (*this - other) < 0; }
__attribute__((always_inline))
constexpr auto operator<=(_iterator const& other) const -> bool
{ return (*this - other) <= 0; }
__attribute__((always_inline))
constexpr auto operator> (_iterator const& other) const -> bool
{ return (*this - other) > 0; }
__attribute__((always_inline))
constexpr auto operator>=(_iterator const& other) const -> bool
{ return (*this - other) >= 0; }
constexpr auto operator[](difference_type const n) const -> reference
{ return *(*this + n); }
constexpr
operator _const_iterator() const noexcept
{ return {_vs, _i}; }
friend
constexpr auto swap(_iterator& lhs, _iterator& rhs) noexcept -> void
{
auto const _temp_idx = lhs._i;
lhs._i = rhs._i;
rhs._i = _temp_idx;
auto& _temp_values = lhs._vs;
lhs._vs = rhs._vs;
rhs._vs = _temp_values;
}
friend
constexpr auto operator+ ( _iterator const& x
, difference_type const n ) noexcept -> _iterator
{ return _iterator{*(x._vs), x._i + n}; }
friend
constexpr auto operator+ ( difference_type const n
, _iterator const& x ) noexcept -> _iterator
{ return x + n; }
friend
constexpr auto operator- ( _iterator const& x
, difference_type const n ) noexcept -> _iterator
{ return _iterator{*(x._vs), x._i - n}; }
friend
constexpr auto operator+=( _iterator & x
, difference_type const n ) noexcept -> _iterator&
{ return x = x + n; }
friend
constexpr auto operator-=( _iterator & x
, difference_type const n ) noexcept -> _iterator&
{ return x = x - n; }
};
template <class _Key, class _Tp, std::size_t _N, bool _is_const>
constexpr std::size_t map_iterator<_Key, _Tp, _N, _is_const>::_size;
template <class _T, std::size_t _N, class = void>
struct hash_c;
template < class _T
, std::size_t _N
>
struct hash_c<_T, _N, std::enable_if_t<std::is_integral<_T>::value>> {
constexpr auto operator()(_T const x) const noexcept
{
return static_cast<std::size_t>(x) % _N;
}
};
template < class _RAIterator
, class _Pred
>
__attribute__((always_inline))
inline
constexpr
auto find_if_c( _RAIterator&& first, _RAIterator&& last
, _Pred&& p ) noexcept
{
auto const _count = last - first;
auto i = first;
typename std::iterator_traits<_RAIterator>::difference_type n = 0;
while (n < _count and not p(*i)) {
++n; ++i;
}
return n == _count ? last : i;
}
} // unnamed namespace
////////////////////////////////////////////////////////////////////////////////
/// That is the actual static_map
////////////////////////////////////////////////////////////////////////////////
template < class _Key
, class _Tp
, size_t _N
, class _Pred = std::equal_to<_Key>
, class _Hash = hash_c<_Key, _N>
>
class static_map {
public:
using key_type = _Key;
using mapped_type = _Tp;
using key_equal = _Pred;
using hasher = _Hash;
using value_type = std::pair<key_type const, mapped_type>;
using reference = value_type &;
using const_reference = value_type const&;
using iterator = map_iterator< key_type
, mapped_type
, _N
, /*is_const =*/ false >;
using const_iterator = map_iterator< key_type
, mapped_type
, _N
, /*is_const =*/ true >;
using difference_type = typename std::iterator_traits<iterator>
::difference_type;
using size_type = std::size_t;
private:
key_equal const _eq;
hasher const _hf;
public:
value_type _vs[_N];
private:
__attribute__((always_inline))
constexpr
auto _lookup(key_type const& k) const noexcept
{
auto const guess = _hf(k);
auto i = guess;
while (i < _N and not _eq(_vs[i].first, k)) { ++i; }
if (i == _N) {
i = 0;
while (i < guess and not _eq(_vs[i].first, k)) { ++i; }
if (i == guess) return _N;
}
return i;
}
public:
template <class... _K, class... _V>
constexpr
static_map(std::pair<_K, _V> const&... values)
: _eq{}
, _hf{}
, _vs{ values... }
{
// bool initialised[_N] = {false};
// _init_impl(initialised, values...);
}
/*
template <class... _K, class... _V>
constexpr
static_map( key_equal equal, hasher hash_function
, std::pair<_K, _V> const&... values )
: _vs{ values... }
, _eq{ std::move(equal) }
, _hf{ std::move(hash_function) }
{
}
*/
constexpr auto size() const noexcept -> size_type
{ return _N; }
constexpr auto begin() noexcept -> iterator
{ return {_vs, 0}; }
constexpr auto end() noexcept -> iterator
{ return {_vs, size()}; }
constexpr auto cbegin() const noexcept -> const_iterator
{ return {_vs, 0}; }
constexpr auto cend() const noexcept -> const_iterator
{ return {_vs, size()}; }
__attribute__((always_inline))
constexpr
auto find(key_type const& k) const noexcept -> const_iterator
{
auto i = _lookup(k);
return i == _N
? cend()
: const_iterator{_vs, i};
/*
struct local_equal {
key_type const& _key;
key_equal const& _eq;
constexpr
local_equal( key_type const& key
, key_equal const& equal )
: _key{ key }
, _eq{ equal }
{}
__attribute__((always_inline))
constexpr auto operator()(value_type const& i) const noexcept
{ return _eq(_key, i.first); }
};
return find_if( cbegin(), cend()
, local_equal{k, _equal} );
*/
}
constexpr
auto count(key_type const& k) const noexcept -> size_type
{ return find(k) == cend() ? 0 : 1; }
__attribute__((always_inline))
constexpr
auto at(key_type const& k) const -> mapped_type const&
{
auto i = _lookup(k);
return i != _N
? _vs[i].second
: (throw key_not_found_error{}, _vs[0].second);
// return ls_at(_vs, k, _eq);
}
__attribute__((always_inline))
constexpr
auto at(key_type const& k) -> mapped_type&
{
auto i = _lookup(k);
return i != _N
? _vs[i].second
: (throw key_not_found_error{}, _vs[0].second);
// return ls_at(_vs, k, _eq);
}
__attribute__((always_inline))
constexpr
auto operator[](key_type const& k) const -> mapped_type const&
{ return at(k); }
};
namespace {
template < class _Key
, class _Tp
, size_t _N
, size_t... _Is
>
inline
constexpr auto static_map_from_array
( std::pair<const _Key, _Tp> const (&il)[_N]
, std::index_sequence<_Is...> )
{
return static_map<_Key, _Tp, _N>{ il[_Is]...};
}
/*
template < class _Key
, class _Tp
, size_t _N
, size_t... _Is
, class _Pred
>
inline
constexpr auto static_map_from_array
( std::pair<const _Key, _Tp> const (&il)[_N]
, std::index_sequence<_Is...>
, _Pred&& equal )
{
return static_map<_Key, _Tp, _N, _Pred>
{ std::forward<_Pred>(equal)
, il[_Is]... };
}
*/
} // unnamed namespace
template < class _Key
, class _Tp
, size_t _N
>
__attribute__((always_inline))
inline
constexpr auto make_static_map(std::pair<const _Key, _Tp> const (&il)[_N])
-> static_map<_Key, _Tp, _N>
{
return static_map_from_array<_Key, _Tp, _N>
(il, std::make_index_sequence<_N>{});
}
/*
template < class _Key
, class _Tp
, size_t _N
, class _Pred
>
__attribute__((always_inline))
inline
constexpr auto make_static_map( std::pair<const _Key, _Tp> const (&il)[_N]
, _Pred&& equal )
-> static_map<_Key, _Tp, _N, _Pred>
{
return static_map_from_array
( il
, std::make_index_sequence<_N>{}
, std::forward<_Pred>(equal) );
}
*/
template <std::size_t _N>
__attribute__((always_inline))
inline
constexpr
auto _insert( std::size_t const index
, std::size_t const guess
, std::size_t (&indices)[_N] )
{
auto i = guess;
while (i < _N and indices[i] != _N) {
++i;
}
if (i == _N) {
i = 0;
while (i < guess and indices[i] != _N) {
++i;
}
}
indices[i] = index;
}
template <std::size_t _N>
__attribute__((always_inline))
inline
constexpr
auto _init_impl( std::size_t (&indices)[_N]
, std::pair<std::size_t, std::size_t> const& x )
{
_insert(x.first, x.second, indices);
}
template <std::size_t _N, class... _I>
__attribute__((always_inline))
inline
constexpr
auto _init_impl( std::size_t (&indices)[_N]
, std::pair<std::size_t, std::size_t> const& x
, std::pair<_I, _I> const&... xs )
{
_insert(x.first, x.second, indices);
_init_impl(indices, xs...);
}
template < class _K
, class _V
, std::size_t _N
, std::size_t... _Is
>
__attribute__((always_inline))
inline
constexpr
auto _initialise( std::pair<_K const, _V> const (&il)[_N]
, std::index_sequence<_Is...> )
{
std::size_t indices[_N] = {((void)_Is, _N)...};
hash_c<_K, _N> const hf;
_init_impl(indices, std::make_pair(_Is, hf(il[_Is].first))...);
return static_map<_K, _V, _N>{ il[indices[_Is]]...};
}
template < class _K
, class _V
, std::size_t _N
, std::size_t... _Is
>
__attribute__((always_inline))
inline
constexpr
auto initialise(std::pair<_K const, _V> const (&il)[_N])
{
return _initialise(il, std::make_index_sequence<_N>{});
}
enum class weekday { sunday, monday, tuesday, wednesday, thursday, friday, saturday };
#define STRING_VIEW(str) std::experimental::string_view{ str, sizeof(str)-1 }
constexpr std::pair<const std::experimental::string_view, weekday>
string_to_weekday[]
{ { STRING_VIEW("sunday"), weekday::sunday }
, { STRING_VIEW("monday"), weekday::monday }
, { STRING_VIEW("tuesday"), weekday::tuesday }
, { STRING_VIEW("wednesday"), weekday::wednesday }
, { STRING_VIEW("thursday"), weekday::thursday }
, { STRING_VIEW("friday"), weekday::friday }
, { STRING_VIEW("saturday"), weekday::saturday }
};
namespace {
__attribute__((always_inline))
inline
constexpr
auto cstrcmp(char const* a, char const* b) noexcept -> int
{
std::size_t i = 0;
for (; a[i] != '\0' and b[i] != '\0'; ++i)
{
if (a[i] < b[i]) return -1;
if (a[i] > b[i]) return 1;
}
if (a[i] == '\0' and b[i] != '\0') return -1;
if (a[i] != '\0' and b[i] == '\0') return 1;
return 0;
}
}
struct equal_string_view {
constexpr
auto operator()( std::experimental::string_view const& a
, std::experimental::string_view const& b ) const noexcept
-> bool
{
return !cstrcmp(a.data(), b.data());
}
};
// constexpr
// static
// auto cmap2 = cmap;
// make_static_map(map_data);
// constexpr auto to_weekday = make_static_map(string_to_weekday, equal_string_view{});
int main(void)
{
{
// Compile-time stuff
constexpr std::pair<int const, const char *> map_data[] =
{ { 5, "apple" }
, { 8, "pear" }
, { 0, "banana" }
};
constexpr auto cmap = initialise(map_data);
static_assert(cmap._vs[0].first == 8);
static_assert(cmap._vs[1].first == 0);
static_assert(cmap._vs[2].first == 5);
// Easy
// No abort call in assembly
if (!cmap.count(8)) abort();
// These operations use hashing
static_assert(!cstrcmp(cmap[5], "apple"));
static_assert(!cstrcmp(cmap[8], "pear"));
static_assert(!cstrcmp(cmap[0], "banana"));
// This fails to compile -- as expected.
// auto foo = cmap[-1];
// We need this because GCC does not support constexpr lambdas, yet.
struct is_eight {
constexpr auto operator()(std::pair<int, char const*> const& x)
const noexcept
{ return x.first == 8; }
};
// Iterators
static_assert( find_if_c(cmap.cbegin(), cmap.cend(), is_eight{})
!= cmap.cend() );
}
{
// Run-time stuff
constexpr std::pair<int const, const char *> map_data[] =
{ { 5, "apple" }
, { 8, "pear" }
, { 0, "banana" }
};
auto cmap = initialise(map_data);
// No abort in assembly
if (!cmap[8]) abort();
if (!cmap.count(5)) abort();
// Values are mutable !!
auto& i = cmap.at(8);
i = "orange";
// This one is nice!
assert(!cstrcmp(cmap[8], "orange"));
// Iterators
auto const it1 = cmap.find(8);
assert(it1->first == 8);
}
// auto& bar = cmap2.at(5);
// bar = "orange";
// std::cout << foo << '\n';
// The following does not compile
// constexpr auto b = cmap[-2];
// cmap.at(5) = "orange";
// constexpr auto
// i = find_if( cmap.cbegin()
// , cmap.cend()
// , is_eight) + 1;
// static_assert( !cstrcmp(((-1) + i)->second, "pear"), "" );
// std::cout << find_if( cmap.cbegin()
// , cmap.cend()
// , [](auto p) { return p.first == 8; } )->second
// << '\n';
// std::cout << cmap.find(0)->second << '\n';
// static_assert(to_weekday[STRING_VIEW("thursday")] == weekday::thursday, "");
// auto tuesday = to_weekday[STRING_VIEW("tuesday")];
// std::cout << static_cast<int>(tuesday) << '\n';
// return 0;
}