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;
99 while (m_value != m_last && !m_set->
get(m_value)) {
101 assert(cid < m_set->m_data.size());
102 if (!m_set->
m_data[cid]) {
131 if (m_value != m_last) {
145 return m_set == rhs.m_set && m_value == rhs.m_value;
149 return ! (*
this == rhs);
153 assert(m_value < m_last);
166 template <
typename T>
176 constexpr
static const size_t chunk_bits = 22;
177 constexpr
static const size_t chunk_size = 1 << chunk_bits;
179 std::vector<std::unique_ptr<unsigned char[]>>
m_data;
183 return id >> (chunk_bits + 3);
187 return (
id >> 3) & ((1 << chunk_bits) - 1);
191 return 1 << (
id & 0x7);
195 return m_data.size() * chunk_size * 8;
199 const auto cid = chunk_id(
id);
200 if (cid >= m_data.size()) {
201 m_data.resize(cid + 1);
204 auto& chunk = m_data[cid];
206 chunk.reset(
new unsigned char[chunk_size]);
207 ::memset(chunk.get(), 0, chunk_size);
210 return chunk[offset(
id)];
226 auto& element = get_element(
id);
228 if ((element & bitmask(
id)) == 0) {
229 element |= bitmask(
id);
242 void set(T id)
override final {
243 (void)check_and_set(
id);
252 auto& element = get_element(
id);
254 if ((element & bitmask(
id)) != 0) {
255 element &= ~bitmask(
id);
265 bool get(T id)
const noexcept
override final {
266 if (chunk_id(
id) >= m_data.size()) {
269 auto* r = m_data[chunk_id(
id)].get();
273 return (r[offset(
id)] & bitmask(
id)) != 0;
279 bool empty() const noexcept override final {
312 template <
typename T>
322 void set(T id)
override final {
323 m_data.push_back(
id);
331 bool get(T id)
const noexcept
override final {
332 const auto it = std::find(m_data.cbegin(), m_data.cend(), id);
333 return it != m_data.cend();
347 return std::binary_search(m_data.cbegin(), m_data.cend(), id);
353 bool empty() const noexcept override final {
354 return m_data.empty();
369 std::sort(m_data.begin(), m_data.end());
370 const auto last = std::unique(m_data.begin(), m_data.end());
371 m_data.erase(last, m_data.end());
382 return m_data.size();
389 return m_data.cbegin();
393 return m_data.cend();
397 return m_data.cbegin();
401 return m_data.cend();
406 template <
template<
typename>
class IdSetType>
429 #endif // OSMIUM_INDEX_ID_SET_HPP void unset(T id)
Definition: id_set.hpp:251
void clear() override final
Definition: id_set.hpp:360
T m_last
Definition: id_set.hpp:96
static size_t offset(T id) noexcept
Definition: id_set.hpp:186
type
Definition: entity_bits.hpp:63
IdSetType< osmium::unsigned_object_id_type > id_set_type
Definition: id_set.hpp:409
Definition: id_set.hpp:407
std::forward_iterator_tag iterator_category
Definition: id_set.hpp:118
Definition: id_set.hpp:56
virtual ~IdSet()
Definition: id_set.hpp:60
item_type
Definition: item_type.hpp:43
T last() const noexcept
Definition: id_set.hpp:194
value_type * pointer
Definition: id_set.hpp:120
std::vector< T > m_data
Definition: id_set.hpp:315
Definition: id_set.hpp:86
unsigned int item_type_to_nwr_index(item_type type) noexcept
Definition: item_type.hpp:82
const_iterator cend() const noexcept
Definition: id_set.hpp:400
bool get_binary_search(T id) const noexcept
Definition: id_set.hpp:346
const_iterator end() const noexcept
Definition: id_set.hpp:392
IdSetDenseIterator< T > begin() const
Definition: id_set.hpp:298
bool operator==(const IdSetDenseIterator< T > &rhs) const noexcept
Definition: id_set.hpp:144
size_t size() const noexcept
Definition: id_set.hpp:286
Definition: id_set.hpp:92
Namespace for everything in the Osmium library.
Definition: assembler.hpp:73
bool empty() const noexcept override final
Definition: id_set.hpp:279
const_iterator begin() const noexcept
Definition: id_set.hpp:388
static unsigned char bitmask(T id) noexcept
Definition: id_set.hpp:190
const IdSetDense< T > * m_set
Definition: id_set.hpp:94
bool get(T id) const noexcept override final
Definition: id_set.hpp:265
id_set_type & operator()(osmium::item_type type) noexcept
Definition: id_set.hpp:415
IdSetDenseIterator(const IdSetDense< T > *set, T value, T last) noexcept
Definition: id_set.hpp:123
T operator*() const noexcept
Definition: id_set.hpp:152
T m_value
Definition: id_set.hpp:95
bool check_and_set(T id)
Definition: id_set.hpp:225
const id_set_type & operator()(osmium::item_type type) const noexcept
Definition: id_set.hpp:419
size_t size() const noexcept
Definition: id_set.hpp:381
std::vector< std::unique_ptr< unsigned char[]> > m_data
Definition: id_set.hpp:179
IdSetDenseIterator< T > operator++(int) noexcept
Definition: id_set.hpp:138
IdSetDenseIterator< T > & operator++() noexcept
Definition: id_set.hpp:130
T value_type
Definition: id_set.hpp:119
value_type & reference
Definition: id_set.hpp:121
IdSetDenseIterator< T > end() const
Definition: id_set.hpp:302
Definition: id_set.hpp:313
bool operator!=(const IdSetDenseIterator< T > &rhs) const noexcept
Definition: id_set.hpp:148
const_iterator cbegin() const noexcept
Definition: id_set.hpp:396
typename std::vector< T >::const_iterator const_iterator
Iterator type. There is no non-const iterator.
Definition: id_set.hpp:386
void next() noexcept
Definition: id_set.hpp:98
static size_t chunk_id(T id) noexcept
Definition: id_set.hpp:182
virtual bool empty() const =0
bool empty() const noexcept override final
Definition: id_set.hpp:353
void clear() override final
Definition: id_set.hpp:293
void sort_unique()
Definition: id_set.hpp:368
unsigned char & get_element(T id)
Definition: id_set.hpp:198