1#ifndef OSMIUM_INDEX_ID_SET_HPP
2#define OSMIUM_INDEX_ID_SET_HPP
70 virtual ~
IdSet() noexcept = default;
75 virtual
void set(T
id) = 0;
80 virtual
bool get(T
id) const noexcept = 0;
106 default_chunk_bits = 22U
111 template <
typename T, std::
size_t chunk_bits = detail::default_chunk_bits>
117 template <
typename T, std::
size_t chunk_bits>
130 assert(cid < m_set->m_data.size());
131 if (!
m_set->m_data[cid]) {
132 m_value = (cid + 1) << (chunk_bits + 3);
178 return !(*
this == rhs);
181 T operator*() const noexcept {
182 assert(m_value < m_last);
195 template <
typename T, std::
size_t chunk_bits>
205 std::vector<std::unique_ptr<unsigned char[]>>
m_data;
209 return id >> (chunk_bits + 3U);
212 static std::size_t
offset(T
id)
noexcept {
213 return (
id >> 3U) & ((1U << chunk_bits) - 1U);
217 return 1U << (
id & 0x7U);
226 if (cid >=
m_data.size()) {
230 auto& chunk =
m_data[cid];
245 swap(first.m_data, second.m_data);
246 swap(first.m_size, second.m_size);
255 for (
const auto& ptr : other.
m_data) {
257 m_data.emplace_back(new unsigned char[chunk_size]);
258 ::memcpy(m_data.back().get(), ptr.get(), chunk_size);
260 m_data.emplace_back();
287 if ((element &
bitmask(
id)) == 0) {
313 if ((element &
bitmask(
id)) != 0) {
324 bool get(T
id)
const noexcept final {
362 return {
this, 0,
last()};
375 template <
typename T>
397 m_data.push_back(id);
406 bool get(T
id)
const noexcept final {
407 const auto it = std::find(
m_data.cbegin(),
m_data.cend(),
id);
408 return it !=
m_data.cend();
422 return std::binary_search(
m_data.cbegin(),
m_data.cend(),
id);
446 const auto last = std::unique(
m_data.begin(),
m_data.end());
457 std::size_t
size() const noexcept {
462 return m_data.capacity() *
sizeof(T);
472 std::vector<T> new_data;
476 std::back_inserter(new_data));
Definition id_set.hpp:118
IdSetDense< T, chunk_bits > id_set
Definition id_set.hpp:121
value_type & reference
Definition id_set.hpp:150
T m_last
Definition id_set.hpp:125
void next() noexcept
Definition id_set.hpp:127
IdSetDenseIterator operator++(int) noexcept
Definition id_set.hpp:167
IdSetDenseIterator & operator++() noexcept
Definition id_set.hpp:159
T m_value
Definition id_set.hpp:124
IdSetDenseIterator(const id_set *set, T value, T last) noexcept
Definition id_set.hpp:152
const id_set * m_set
Definition id_set.hpp:123
bool operator!=(const IdSetDenseIterator &rhs) const noexcept
Definition id_set.hpp:177
bool operator==(const IdSetDenseIterator &rhs) const noexcept
Definition id_set.hpp:173
T value_type
Definition id_set.hpp:148
std::forward_iterator_tag iterator_category
Definition id_set.hpp:147
value_type * pointer
Definition id_set.hpp:149
Definition id_set.hpp:196
@ chunk_size
Definition id_set.hpp:202
IdSetDense & operator=(IdSetDense other)
Definition id_set.hpp:265
const_iterator begin() const
Definition id_set.hpp:361
IdSetDense(const IdSetDense &other)
Definition id_set.hpp:251
void set(T id) final
Definition id_set.hpp:301
bool check_and_set(T id)
Definition id_set.hpp:284
std::vector< std::unique_ptr< unsigned char[]> > m_data
Definition id_set.hpp:205
IdSetDense(IdSetDense &&) noexcept=default
static std::size_t chunk_id(T id) noexcept
Definition id_set.hpp:208
T last() const noexcept
Definition id_set.hpp:220
friend void swap(IdSetDense &first, IdSetDense &second) noexcept
Definition id_set.hpp:243
T size() const noexcept
Definition id_set.hpp:345
void clear() final
Definition id_set.hpp:352
const_iterator end() const
Definition id_set.hpp:365
static std::size_t offset(T id) noexcept
Definition id_set.hpp:212
static unsigned int bitmask(T id) noexcept
Definition id_set.hpp:216
IdSetDenseIterator< T, chunk_bits > const_iterator
Definition id_set.hpp:241
unsigned char & get_element(T id)
Definition id_set.hpp:224
void unset(T id)
Definition id_set.hpp:310
T m_size
Definition id_set.hpp:206
std::size_t used_memory() const noexcept final
Definition id_set.hpp:357
bool get(T id) const noexcept final
Definition id_set.hpp:324
bool empty() const noexcept final
Definition id_set.hpp:338
std::size_t used_memory() const noexcept final
Definition id_set.hpp:461
typename std::vector< T >::const_iterator const_iterator
Iterator type. There is no non-const iterator.
Definition id_set.hpp:482
void merge_sorted(const IdSetSmall< T > &other)
Definition id_set.hpp:471
const_iterator cend() const noexcept
Definition id_set.hpp:496
const_iterator begin() const noexcept
Definition id_set.hpp:484
void set(T id) final
Definition id_set.hpp:395
IdSetSmall(const IdSetSmall &)=default
const_iterator end() const noexcept
Definition id_set.hpp:488
const_iterator cbegin() const noexcept
Definition id_set.hpp:492
std::vector< T > m_data
Definition id_set.hpp:378
bool get_binary_search(T id) const noexcept
Definition id_set.hpp:421
bool empty() const noexcept final
Definition id_set.hpp:428
bool get(T id) const noexcept final
Definition id_set.hpp:406
void clear() final
Definition id_set.hpp:435
IdSetSmall & operator=(const IdSetSmall &)=default
void sort_unique()
Definition id_set.hpp:444
IdSetSmall(IdSetSmall &&) noexcept=default
std::size_t size() const noexcept
Definition id_set.hpp:457
virtual bool empty() const =0
virtual std::size_t used_memory() const noexcept=0
IdSet(const IdSet &)=default
IdSet & operator=(const IdSet &)=default
virtual bool get(T id) const noexcept=0
IdSet(IdSet &&) noexcept=default
Indexing of OSM data, Locations, etc.
Definition id_set.hpp:51
Namespace for everything in the Osmium library.
Definition assembler.hpp:53
Definition location.hpp:555