blob: b4c2ab537ce270e9a1ae3a9b1e9918afb09d206f [file] [log] [blame]
// Copyright 2020 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
#pragma once
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <type_traits>
namespace pw::containers {
// A simple, fixed-size associative array with lookup by key or value.
//
// FlatMaps are initialized with a std::array of FlatMap::Pair objects:
// FlatMap<int, int> map({{{1, 2}, {3, 4}}});
//
// The keys do not need to be sorted as the constructor will sort the items
// if need be.
template <typename Key, typename Value, size_t kArraySize>
class FlatMap {
public:
// Define and use a custom Pair object. This is because std::pair does not
// support constexpr assignment until C++20. The assignment is needed since
// the array of pairs will be sorted in the constructor (if not already).
template <typename First, typename Second>
struct Pair {
First first;
Second second;
};
using key_type = Key;
using mapped_type = Value;
using value_type = Pair<key_type, mapped_type>;
using size_type = size_t;
using difference_type = ptrdiff_t;
using container_type = typename std::array<value_type, kArraySize>;
using iterator = typename container_type::iterator;
using const_iterator = typename container_type::const_iterator;
constexpr FlatMap(const std::array<value_type, kArraySize>& items)
: items_(items) {
ConstexprSort(items_.data(), kArraySize);
}
FlatMap(FlatMap&) = delete;
FlatMap& operator=(FlatMap&) = delete;
// Capacity.
constexpr size_type size() const { return kArraySize; }
constexpr size_type empty() const { return size() == 0; }
constexpr size_type max_size() const { return kArraySize; }
// Lookup.
constexpr bool contains(const key_type& key) const {
return find(key) != end();
}
constexpr const_iterator find(const key_type& key) const {
if (end() == begin()) {
return end();
}
const_iterator it = lower_bound(key);
return key == it->first ? it : end();
}
constexpr const_iterator lower_bound(const key_type& key) const {
return std::lower_bound(
begin(), end(), key, [](const value_type& item, key_type lkey) {
return item.first < lkey;
});
}
constexpr const_iterator upper_bound(const key_type& key) const {
return std::upper_bound(
begin(), end(), key, [](key_type lkey, const value_type& item) {
return item.first > lkey;
});
}
constexpr std::pair<const_iterator, const_iterator> equal_range(
const key_type& key) const {
if (end() == begin()) {
return std::make_pair(end(), end());
}
return std::make_pair(lower_bound(key), upper_bound(key));
}
// Iterators.
constexpr const_iterator begin() const { return cbegin(); }
constexpr const_iterator cbegin() const { return items_.cbegin(); }
constexpr const_iterator end() const { return cend(); }
constexpr const_iterator cend() const { return items_.cend(); }
private:
// Simple stable insertion sort function for constexpr support.
// std::stable_sort is not constexpr. Should not be a problem with performance
// in regards to the sizes that are typically dealt with.
static constexpr void ConstexprSort(iterator data, size_type size) {
if (size < 2) {
return;
}
for (iterator it = data + 1, end = data + size; it < end; ++it) {
if (it->first < it[-1].first) {
// Rotate the value into place.
value_type temp = std::move(*it);
iterator it2 = it - 1;
while (true) {
*(it2 + 1) = std::move(*it2);
if (it2 == data || !(temp.first < it2[-1].first)) {
break;
}
--it2;
}
*it2 = std::move(temp);
}
}
}
std::array<value_type, kArraySize> items_;
};
} // namespace pw::containers