1 #ifndef OSMIUM_INDEX_ID_SET_HPP 2 #define OSMIUM_INDEX_ID_SET_HPP 45 #include <type_traits> 69 virtual ~IdSet() =
default;
74 virtual void set(T id) = 0;
79 virtual bool get(T id)
const noexcept = 0;
84 virtual bool empty()
const = 0;
89 virtual void clear() = 0;
94 virtual std::size_t
used_memory()
const noexcept = 0;
104 template <
typename T>
113 while (m_value != m_last && !m_set->
get(m_value)) {
115 assert(cid < m_set->m_data.size());
116 if (!m_set->
m_data[cid]) {
145 if (m_value != m_last) {
159 return m_set == rhs.m_set && m_value == rhs.m_value;
163 return !(*
this == rhs);
167 assert(m_value < m_last);
180 template <
typename T>
190 constexpr
static const std::size_t chunk_bits = 22u;
191 constexpr
static const std::size_t chunk_size = 1u << chunk_bits;
193 std::vector<std::unique_ptr<unsigned char[]>>
m_data;
197 return id >> (chunk_bits + 3u);
200 static std::size_t
offset(T
id) noexcept {
201 return (
id >> 3u) & ((1u << chunk_bits) - 1u);
205 return 1u << (
id & 0x7u);
209 return static_cast<T
>(m_data.size()) * chunk_size * 8;
213 const auto cid = chunk_id(
id);
214 if (cid >= m_data.size()) {
215 m_data.resize(cid + 1);
218 auto& chunk = m_data[cid];
220 chunk.reset(
new unsigned char[chunk_size]);
221 ::memset(chunk.get(), 0, chunk_size);
224 return chunk[offset(
id)];
240 auto& element = get_element(
id);
242 if ((element & bitmask(
id)) == 0) {
243 element |= bitmask(
id);
256 void set(T id)
final {
257 (void)check_and_set(
id);
266 auto& element = get_element(
id);
268 if ((element & bitmask(
id)) != 0) {
269 element &= ~bitmask(
id);
279 bool get(T id)
const noexcept
final {
280 if (chunk_id(
id) >= m_data.size()) {
283 auto* r = m_data[chunk_id(
id)].get();
287 return (r[offset(
id)] & bitmask(
id)) != 0;
313 return m_data.size() * chunk_size;
317 return {
this, 0, last()};
321 return {
this, last(), last()};
330 template <
typename T>
340 void set(T id)
final {
341 m_data.push_back(
id);
349 bool get(T id)
const noexcept
final {
350 const auto it = std::find(m_data.cbegin(), m_data.cend(), id);
351 return it != m_data.cend();
365 return std::binary_search(m_data.cbegin(), m_data.cend(), id);
372 return m_data.empty();
387 std::sort(m_data.begin(), m_data.end());
388 const auto last = std::unique(m_data.begin(), m_data.end());
389 m_data.erase(last, m_data.end());
399 std::size_t
size() const noexcept {
400 return m_data.size();
404 return m_data.capacity() *
sizeof(T);
411 return m_data.cbegin();
415 return m_data.cend();
419 return m_data.cbegin();
423 return m_data.cend();
429 template <
template <
typename>
class IdSetType>
452 #endif // OSMIUM_INDEX_ID_SET_HPP void unset(T id)
Definition: id_set.hpp:265
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:312
T m_last
Definition: id_set.hpp:110
type
Definition: entity_bits.hpp:63
IdSetType< osmium::unsigned_object_id_type > id_set_type
Definition: id_set.hpp:432
Definition: id_set.hpp:430
std::forward_iterator_tag iterator_category
Definition: id_set.hpp:132
Definition: id_set.hpp:57
static std::size_t offset(T id) noexcept
Definition: id_set.hpp:200
item_type
Definition: item_type.hpp:43
T last() const noexcept
Definition: id_set.hpp:208
value_type * pointer
Definition: id_set.hpp:134
void clear() final
Definition: id_set.hpp:378
std::vector< T > m_data
Definition: id_set.hpp:333
bool get(T id) const noexcept final
Definition: id_set.hpp:279
Definition: id_set.hpp:99
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:422
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:403
bool get_binary_search(T id) const noexcept
Definition: id_set.hpp:364
const_iterator end() const noexcept
Definition: id_set.hpp:414
IdSetDenseIterator< T > begin() const
Definition: id_set.hpp:316
bool operator==(const IdSetDenseIterator< T > &rhs) const noexcept
Definition: id_set.hpp:158
Definition: id_set.hpp:105
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
const_iterator begin() const noexcept
Definition: id_set.hpp:410
static unsigned char bitmask(T id) noexcept
Definition: id_set.hpp:204
const IdSetDense< T > * m_set
Definition: id_set.hpp:108
id_set_type & operator()(osmium::item_type type) noexcept
Definition: id_set.hpp:438
IdSetDenseIterator(const IdSetDense< T > *set, T value, T last) noexcept
Definition: id_set.hpp:137
T operator*() const noexcept
Definition: id_set.hpp:166
T m_value
Definition: id_set.hpp:109
IdSet & operator=(const IdSet &)=default
bool check_and_set(T id)
Definition: id_set.hpp:239
const id_set_type & operator()(osmium::item_type type) const noexcept
Definition: id_set.hpp:442
bool empty() const noexcept final
Definition: id_set.hpp:293
std::vector< std::unique_ptr< unsigned char[]> > m_data
Definition: id_set.hpp:193
IdSetDenseIterator< T > operator++(int) noexcept
Definition: id_set.hpp:152
IdSetDenseIterator< T > & operator++() noexcept
Definition: id_set.hpp:144
T value_type
Definition: id_set.hpp:133
value_type & reference
Definition: id_set.hpp:135
IdSetDenseIterator< T > end() const
Definition: id_set.hpp:320
virtual std::size_t used_memory() const noexcept=0
Definition: id_set.hpp:331
std::size_t size() const noexcept
Definition: id_set.hpp:399
bool operator!=(const IdSetDenseIterator< T > &rhs) const noexcept
Definition: id_set.hpp:162
const_iterator cbegin() const noexcept
Definition: id_set.hpp:418
typename std::vector< T >::const_iterator const_iterator
Iterator type. There is no non-const iterator.
Definition: id_set.hpp:408
void next() noexcept
Definition: id_set.hpp:112
bool empty() const noexcept final
Definition: id_set.hpp:371
void clear() final
Definition: id_set.hpp:307
T size() const noexcept
Definition: id_set.hpp:300
virtual bool empty() const =0
static std::size_t chunk_id(T id) noexcept
Definition: id_set.hpp:196
void sort_unique()
Definition: id_set.hpp:386
unsigned char & get_element(T id)
Definition: id_set.hpp:212