1 #ifndef OSMIUM_INDEX_ID_SET_HPP
2 #define OSMIUM_INDEX_ID_SET_HPP
40 #include <type_traits>
41 #include <unordered_set>
66 virtual void set(T
id) = 0;
71 virtual bool get(T id)
const noexcept = 0;
76 virtual bool empty()
const = 0;
81 virtual void clear() = 0;
100 while (m_value != m_last && !m_set->
get(m_value)) {
102 assert(cid < m_set->m_data.size());
103 if (!m_set->
m_data[cid]) {
132 if (m_value != m_last) {
146 return m_set == rhs.m_set && m_value == rhs.m_value;
150 return ! (*
this == rhs);
154 assert(m_value < m_last);
167 template <
typename T>
168 class IdSetDense :
public IdSet<T> {
180 std::vector<std::unique_ptr<unsigned char[]>>
m_data;
184 return id >> (chunk_bits + 3);
192 return 1 << (
id & 0x7);
196 return static_cast<T
>(m_data.size()) * chunk_size * 8;
201 if (cid >= m_data.size()) {
202 m_data.resize(cid + 1);
205 auto& chunk = m_data[cid];
207 chunk.reset(
new unsigned char[chunk_size]);
229 if ((element &
bitmask(
id)) == 0) {
243 void set(T
id)
override final {
255 if ((element &
bitmask(
id)) != 0) {
266 bool get(T id)
const noexcept
override final {
267 if (
chunk_id(
id) >= m_data.size()) {
270 auto* r = m_data[
chunk_id(
id)].get();
280 bool empty() const noexcept override final {
313 template <
typename T>
323 void set(T
id)
override final {
324 m_data.push_back(
id);
332 bool get(T id)
const noexcept
override final {
333 const auto it = std::find(m_data.cbegin(), m_data.cend(), id);
334 return it != m_data.cend();
348 return std::binary_search(m_data.cbegin(), m_data.cend(), id);
354 bool empty() const noexcept override final {
355 return m_data.empty();
370 std::sort(m_data.begin(), m_data.end());
371 const auto last = std::unique(m_data.begin(), m_data.end());
372 m_data.erase(last, m_data.end());
383 return m_data.size();
390 return m_data.cbegin();
394 return m_data.cend();
398 return m_data.cbegin();
402 return m_data.cend();
407 template <
template<
typename>
class IdSetType>
430 #endif // OSMIUM_INDEX_ID_SET_HPP
bool empty() const noexceptoverridefinal
Definition: id_set.hpp:280
T m_last
Definition: id_set.hpp:97
type
Definition: entity_bits.hpp:63
IdSetType< osmium::unsigned_object_id_type > id_set_type
Definition: id_set.hpp:410
void clear() overridefinal
Definition: id_set.hpp:294
Definition: id_set.hpp:408
std::forward_iterator_tag iterator_category
Definition: id_set.hpp:119
Definition: id_set.hpp:56
virtual ~IdSet()
Definition: id_set.hpp:60
T size() const noexcept
Definition: id_set.hpp:287
item_type
Definition: item_type.hpp:43
value_type * pointer
Definition: id_set.hpp:121
std::vector< T > m_data
Definition: id_set.hpp:316
T m_size
Definition: id_set.hpp:181
IdSetDenseIterator< T > begin() const
Definition: id_set.hpp:299
unsigned int item_type_to_nwr_index(item_type type) noexcept
Definition: item_type.hpp:82
void clear() overridefinal
Definition: id_set.hpp:361
const_iterator cend() const noexcept
Definition: id_set.hpp:401
bool get_binary_search(T id) const noexcept
Definition: id_set.hpp:347
static constexpr const size_t chunk_bits
Definition: id_set.hpp:177
bool get(T id) const noexceptoverridefinal
Definition: id_set.hpp:266
const_iterator end() const noexcept
Definition: id_set.hpp:393
unsigned char & get_element(T id)
Definition: id_set.hpp:199
void set(T id) overridefinal
Definition: id_set.hpp:243
static unsigned char bitmask(T id) noexcept
Definition: id_set.hpp:191
bool operator==(const IdSetDenseIterator< T > &rhs) const noexcept
Definition: id_set.hpp:145
Definition: id_set.hpp:92
Namespace for everything in the Osmium library.
Definition: assembler.hpp:73
static size_t offset(T id) noexcept
Definition: id_set.hpp:187
const_iterator begin() const noexcept
Definition: id_set.hpp:389
bool empty() const noexceptoverridefinal
Definition: id_set.hpp:354
const IdSetDense< T > * m_set
Definition: id_set.hpp:95
static size_t chunk_id(T id) noexcept
Definition: id_set.hpp:183
static constexpr const size_t chunk_size
Definition: id_set.hpp:178
id_set_type & operator()(osmium::item_type type) noexcept
Definition: id_set.hpp:416
id_set_type m_sets[3]
Definition: id_set.hpp:412
bool check_and_set(T id)
Definition: id_set.hpp:226
IdSetDenseIterator(const IdSetDense< T > *set, T value, T last) noexcept
Definition: id_set.hpp:124
T operator*() const noexcept
Definition: id_set.hpp:153
T m_value
Definition: id_set.hpp:96
const id_set_type & operator()(osmium::item_type type) const noexcept
Definition: id_set.hpp:420
size_t size() const noexcept
Definition: id_set.hpp:382
IdSetDenseIterator< T > operator++(int) noexcept
Definition: id_set.hpp:139
IdSetDenseIterator< T > & operator++() noexcept
Definition: id_set.hpp:131
T value_type
Definition: id_set.hpp:120
value_type & reference
Definition: id_set.hpp:122
std::vector< std::unique_ptr< unsigned char[]> > m_data
Definition: id_set.hpp:180
void set(T id) overridefinal
Definition: id_set.hpp:323
Definition: id_set.hpp:314
bool operator!=(const IdSetDenseIterator< T > &rhs) const noexcept
Definition: id_set.hpp:149
void unset(T id)
Definition: id_set.hpp:252
const_iterator cbegin() const noexcept
Definition: id_set.hpp:397
typename std::vector< T >::const_iterator const_iterator
Iterator type. There is no non-const iterator.
Definition: id_set.hpp:387
void next() noexcept
Definition: id_set.hpp:99
IdSetDenseIterator< T > end() const
Definition: id_set.hpp:303
virtual bool empty() const =0
void sort_unique()
Definition: id_set.hpp:369
Definition: id_set.hpp:86
T last() const noexcept
Definition: id_set.hpp:195