Created
September 30, 2024 09:06
-
-
Save Mukundan314/27b313fb91d426098bb25d750ffc5e2f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
template <class Key, class Compare = std::less<Key>> class InsertionSet { | |
private: | |
constexpr static std::size_t block_size = 700; | |
std::vector<Key> macro; | |
std::vector<std::vector<Key>> micros; | |
std::size_t _size; | |
public: | |
using key_type = Key; | |
using value_type = Key; | |
using size_type = std::size_t; | |
using difference_type = std::ptrdiff_t; | |
using key_compare = Compare; | |
using value_compare = Compare; | |
// using allocator_type = Allocator; | |
using reference = value_type &; | |
using const_reference = const value_type &; | |
// using pointer = std::allocator_traits<Allocator>::pointer | |
// using const_pointer = std::allocator_traits<Allocator>::const_pointer | |
class iterator { | |
private: | |
typename std::vector<std::vector<Key>>::const_iterator it_micros; | |
typename std::vector<Key>::const_iterator it_micro; | |
iterator(typename std::vector<std::vector<Key>>::const_iterator _it_micros, | |
typename std::vector<Key>::const_iterator _it_micro) | |
: it_micros(_it_micros), it_micro(_it_micro) { | |
while (it_micro == it_micros->end()) | |
it_micro = (++it_micros)->begin(); | |
} | |
friend InsertionSet; | |
public: | |
using iterator_category = std::bidirectional_iterator_tag; | |
using value_type = const Key; | |
using difference_type = std::ptrdiff_t; | |
using pointer = const Key *; | |
using reference = const Key &; | |
iterator &operator++() { | |
++it_micro; | |
while (it_micro == it_micros->end()) | |
it_micro = (++it_micros)->begin(); | |
return *this; | |
} | |
iterator operator++(int) { | |
iterator tmp = *this; | |
++*this; | |
return tmp; | |
} | |
iterator &operator--() { | |
while (it_micro == it_micros->begin()) | |
it_micro = (--it_micros)->end(); | |
--it_micro; | |
return *this; | |
} | |
iterator operator--(int) { | |
iterator tmp = *this; | |
--*this; | |
return tmp; | |
} | |
bool operator==(iterator other) const { | |
return it_micros == other.it_micros && it_micro == other.it_micro; | |
} | |
bool operator!=(iterator other) const { return !(*this == other); } | |
value_type operator*() const { return *it_micro; } | |
}; | |
using const_iterator = iterator; | |
using reverse_iterator = std::reverse_iterator<iterator>; | |
using const_reverse_iterator = std::reverse_iterator<const_iterator>; | |
InsertionSet() : _size(0) { micros = {{}, {0}}; } | |
template <class InputIt> | |
InsertionSet(InputIt first, InputIt last) : _size(0) { | |
micros = {{}, {0}}; | |
insert(first, last); | |
} | |
// Iterators | |
iterator begin() const noexcept { | |
return iterator(micros.begin(), micros[0].begin()); | |
} | |
iterator cbegin() const noexcept { return begin(); } | |
iterator end() const noexcept { | |
return iterator(micros.end() - 1, micros.back().begin()); | |
} | |
iterator cend() const noexcept { return end(); } | |
reverse_iterator rbegin() const noexcept { return reverse_iterator(end()); } | |
reverse_iterator crbegin() const noexcept { return rbegin(); } | |
reverse_iterator rend() const noexcept { return reverse_iterator(begin()); } | |
reverse_iterator crend() const noexcept { return rend(); } | |
// Capacity | |
bool empty() const noexcept { return _size == 0; } | |
size_type size() const noexcept { return _size; } | |
size_type max_size() const noexcept { | |
return std::numeric_limits<difference_type>::max(); | |
} | |
// Modifiers | |
void clear() noexcept { | |
for (auto micro : micros) | |
micro.clear(); | |
_size = 0; | |
} | |
iterator insert(const value_type &value) { | |
return insert(std::move(value_type(value))); | |
} | |
iterator insert(value_type &&value) { | |
typename std::vector<Key>::iterator it_macro = | |
std::lower_bound(macro.begin(), macro.end(), value, Compare{}); | |
typename std::vector<std::vector<Key>>::iterator it_micros = | |
micros.begin() + (it_macro - macro.begin()); | |
typename std::vector<Key>::iterator it_micro = | |
it_micros->insert(std::upper_bound(it_micros->begin(), it_micros->end(), | |
value, Compare{}), | |
std::move(value)); | |
_size++; | |
if (it_micros->size() == block_size) { | |
macro.insert(it_macro, (*it_micros)[block_size >> 1]); | |
it_micros = | |
micros.insert(it_micros + 1, | |
std::vector<Key>(it_micros->begin() + (block_size >> 1), | |
it_micros->end())) - | |
1; | |
int idx = it_micro - it_micros->begin(); | |
it_micros->resize(block_size >> 1); | |
if (idx >= block_size >> 1) | |
it_micro = (++it_micros)->begin() + idx - (block_size >> 1); | |
} | |
return iterator(it_micros, it_micro); | |
} | |
iterator insert(iterator pos, const value_type &value) { | |
insert(pos, std::move(value_type(value))); | |
} | |
iterator insert(iterator pos, value_type &&value) { | |
// TODO: use hint | |
insert(std::move(value)); | |
} | |
template <class InputIt> void insert(InputIt first, InputIt last) { | |
for (; first != last; ++first) | |
insert(*first); | |
} | |
void insert(std::initializer_list<value_type> ilist) { | |
insert(ilist.begin(), ilist.end()); | |
} | |
template <class... Args> iterator emplace(Args &&...args) { /* TODO */ } | |
template <class... Args> | |
iterator emplace_hint(iterator hint, Args &&...args) { /* TODO */ } | |
iterator erase(iterator pos) { | |
std::ptrdiff_t micros_idx = pos.it_micros - micros.begin(); | |
pos.it_micro = micros[micros_idx].erase(pos.it_micro); | |
if (micros_idx == 0 || !pos.it_micros->empty()) | |
return pos; | |
macro.erase(macro.begin() + micros_idx - 1); | |
pos.it_micros = micros.erase(pos.it_micros); | |
pos.it_micro = pos.it_micros->begin(); | |
return pos; | |
} | |
iterator erase(iterator first, iterator last) { /* TODO */ } | |
size_type erase(const Key &key) { /* TODO */ } | |
void swap(InsertionSet &other) { /* TODO */ } | |
// Lookup | |
size_type count(const Key &key) const { /* TODO */ } | |
iterator find(const Key &key) const { | |
iterator it = lower_bound(key); | |
return it == end() || *it == key ? it : end(); | |
} | |
std::pair<iterator, iterator> equal_range(const Key &key) const { | |
return {lower_bound(key), upper_bound(key)}; | |
} | |
iterator lower_bound(const Key &key) const { | |
typename std::vector<Key>::const_iterator it_macro = | |
std::lower_bound(macro.begin(), macro.end(), key, Compare{}); | |
typename std::vector<std::vector<Key>>::const_iterator it_micros = | |
micros.begin() + (it_macro - macro.begin()); | |
return iterator( | |
it_micros, | |
std::lower_bound(it_micros->begin(), it_micros->end(), key, Compare{})); | |
} | |
iterator upper_bound(const Key &key) const { | |
typename std::vector<Key>::const_iterator it_macro = | |
std::upper_bound(macro.begin(), macro.end(), key, Compare{}); | |
typename std::vector<std::vector<Key>>::const_iterator it_micros = | |
micros.begin() + (it_macro - macro.begin()); | |
return iterator( | |
it_micros, | |
std::upper_bound(it_micros->begin(), it_micros->end(), key, Compare{})); | |
} | |
// Observers | |
key_compare key_comp() const { return Compare{}; } | |
value_compare value_comp() const { return Compare{}; } | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment