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;
105 default_chunk_bits = 22u
110 template <
typename T, std::
size_t chunk_bits = detail::default_chunk_bits>
116 template <
typename T, std::
size_t chunk_bits>
129 assert(cid < m_set->m_data.size());
131 m_value = (cid + 1) << (chunk_bits + 3);
177 return !(*
this == rhs);
194 template <
typename T, std::
size_t chunk_bits>
195 class IdSetDense :
public IdSet<T> {
204 std::vector<std::unique_ptr<unsigned char[]>>
m_data;
208 return id >> (chunk_bits + 3u);
211 static std::size_t
offset(T
id) noexcept {
212 return (
id >> 3u) & ((1u << chunk_bits) - 1u);
216 return 1u << (
id & 0x7u);
225 if (cid >=
m_data.size()) {
229 auto& chunk =
m_data[cid];
253 if ((element &
bitmask(
id)) == 0) {
279 if ((element &
bitmask(
id)) != 0) {
290 bool get(T
id)
const noexcept
final {
328 return {
this, 0,
last()};
341 template <
typename T>
360 bool get(T
id)
const noexcept
final {
361 const auto it = std::find(
m_data.cbegin(),
m_data.cend(), id);
362 return it !=
m_data.cend();
376 return std::binary_search(
m_data.cbegin(),
m_data.cend(), id);
399 const auto last = std::unique(
m_data.begin(),
m_data.end());
410 std::size_t
size() const noexcept {
415 return m_data.capacity() *
sizeof(T);
440 template <
template <
typename>
class IdSetType>
463 #endif // OSMIUM_INDEX_ID_SET_HPP T size() const noexcept
Definition: id_set.hpp:311
const_iterator end() const
Definition: id_set.hpp:331
type
Definition: entity_bits.hpp:63
IdSetType< osmium::unsigned_object_id_type > id_set_type
Definition: id_set.hpp:443
IdSetDenseIterator & operator++() noexcept
Definition: id_set.hpp:158
Definition: id_set.hpp:441
Definition: id_set.hpp:57
void next() noexcept
Definition: id_set.hpp:126
T last() const noexcept
Definition: id_set.hpp:219
item_type
Definition: item_type.hpp:43
IdSetDenseIterator(const id_set *set, T value, T last) noexcept
Definition: id_set.hpp:151
static std::size_t chunk_id(T id) noexcept
Definition: id_set.hpp:207
const id_set * m_set
Definition: id_set.hpp:122
void clear() final
Definition: id_set.hpp:389
std::vector< T > m_data
Definition: id_set.hpp:344
T value_type
Definition: id_set.hpp:147
Definition: id_set.hpp:111
bool get(T id) const noexcept final
Definition: id_set.hpp:360
unsigned int item_type_to_nwr_index(item_type type) noexcept
Definition: item_type.hpp:82
bool get(T id) const noexcept final
Definition: id_set.hpp:290
IdSetDenseIterator operator++(int) noexcept
Definition: id_set.hpp:166
const_iterator cend() const noexcept
Definition: id_set.hpp:433
value_type & reference
Definition: id_set.hpp:149
T m_size
Definition: id_set.hpp:205
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:414
bool get_binary_search(T id) const noexcept
Definition: id_set.hpp:375
T m_last
Definition: id_set.hpp:124
void set(T id) final
Definition: id_set.hpp:267
const_iterator end() const noexcept
Definition: id_set.hpp:425
const_iterator begin() const
Definition: id_set.hpp:327
Definition: id_set.hpp:201
Definition: id_set.hpp:117
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
const_iterator begin() const noexcept
Definition: id_set.hpp:421
bool check_and_set(T id)
Definition: id_set.hpp:250
id_set_type & operator()(osmium::item_type type) noexcept
Definition: id_set.hpp:449
bool operator!=(const IdSetDenseIterator &rhs) const noexcept
Definition: id_set.hpp:176
id_set_type m_sets[3]
Definition: id_set.hpp:445
value_type * pointer
Definition: id_set.hpp:148
void unset(T id)
Definition: id_set.hpp:276
T m_value
Definition: id_set.hpp:123
IdSet & operator=(const IdSet &)=default
const id_set_type & operator()(osmium::item_type type) const noexcept
Definition: id_set.hpp:453
void set(T id) final
Definition: id_set.hpp:351
T operator*() const noexcept
Definition: id_set.hpp:180
void clear() final
Definition: id_set.hpp:318
virtual std::size_t used_memory() const noexcept=0
Definition: id_set.hpp:342
std::size_t size() const noexcept
Definition: id_set.hpp:410
std::vector< std::unique_ptr< unsigned char[]> > m_data
Definition: id_set.hpp:204
static std::size_t offset(T id) noexcept
Definition: id_set.hpp:211
const_iterator cbegin() const noexcept
Definition: id_set.hpp:429
typename std::vector< T >::const_iterator const_iterator
Iterator type. There is no non-const iterator.
Definition: id_set.hpp:419
unsigned char & get_element(T id)
Definition: id_set.hpp:223
virtual bool get(T id) const noexcept=0
std::forward_iterator_tag iterator_category
Definition: id_set.hpp:146
bool empty() const noexcept final
Definition: id_set.hpp:382
static unsigned int bitmask(T id) noexcept
Definition: id_set.hpp:215
bool operator==(const IdSetDenseIterator &rhs) const noexcept
Definition: id_set.hpp:172
virtual bool empty() const =0
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:323
void sort_unique()
Definition: id_set.hpp:397
bool empty() const noexcept final
Definition: id_set.hpp:304