Last active
October 23, 2022 18:27
-
-
Save Ryoga-exe/caa449d5f5c69c0baa1c94bfc674b5ec to your computer and use it in GitHub Desktop.
WIP
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
| # include <cstdint> | |
| # include <iostream> | |
| # include <vector> | |
| # include <cassert> | |
| # include <set> | |
| namespace Ryoga_exe | |
| { | |
| using int32 = std::int32_t; | |
| using int64 = std::int64_t; | |
| template <class Type> using Array = std::vector<Type>; | |
| template <class Type> | |
| class RangeSet | |
| { | |
| public: | |
| using value_type = Type; | |
| using range_type = std::pair<value_type, value_type>; | |
| using container_type = std::set<range_type>; | |
| using iterator = typename container_type::iterator; | |
| using size_type = typename container_type::size_type; | |
| private: | |
| container_type m_set; | |
| public: | |
| explicit constexpr RangeSet() = default; | |
| iterator begin() const noexcept | |
| { | |
| return m_set.begin(); | |
| } | |
| iterator end() const noexcept | |
| { | |
| return m_set.end(); | |
| } | |
| bool isEmpty() const noexcept | |
| { | |
| return m_set.empty(); | |
| } | |
| // numRanges | |
| size_type size() const noexcept | |
| { | |
| return m_set.size(); | |
| } | |
| value_type length() const noexcept | |
| { | |
| value_type result = 0; | |
| for (const auto& [l, r] : m_set) | |
| { | |
| result += (r - l); | |
| } | |
| return result; | |
| } | |
| container_type asSet() const noexcept | |
| { | |
| return m_set; | |
| } | |
| Array<range_type> asArray() const noexcept | |
| { | |
| Array<range_type> result; | |
| for (const auto range : m_set) | |
| { | |
| result.push_back(range); | |
| } | |
| return result; | |
| } | |
| std::pair<iterator, bool> insert(value_type left, value_type right) | |
| { | |
| assert(left <= right); | |
| if (left == right) | |
| { | |
| return { m_set.end(), false }; | |
| } | |
| auto itr = m_set.lower_bound({ left, right }); | |
| if (itr != m_set.end() && itr->first == left) | |
| { | |
| return { itr, false }; | |
| } | |
| if (itr != m_set.begin()) | |
| { | |
| if (const auto prev_itr = std::prev(itr); prev_itr->first != left && right <= prev_itr->second) | |
| { | |
| return { std::prev(itr), false }; | |
| } | |
| } | |
| itr = m_set.emplace_hint(itr, left, right); | |
| while (itr != std::prev(m_set.end()) && std::next(itr)->first <= itr->second) | |
| { | |
| if (std::next(itr)->second <= itr->second) | |
| { | |
| m_set.erase(std::next(itr)); | |
| } | |
| else | |
| { | |
| itr = m_set.emplace_hint(std::next(itr), itr->first, std::next(itr)->second); | |
| m_set.erase(std::prev(itr)); | |
| m_set.erase(std::next(itr)); | |
| } | |
| } | |
| while (itr != m_set.begin() && itr->first <= std::prev(itr)->second) | |
| { | |
| if (itr->first == std::prev(itr)->first) | |
| { | |
| m_set.erase(std::prev(itr)); | |
| } | |
| else | |
| { | |
| itr = m_set.emplace_hint(itr, std::prev(itr)->first, itr->second); | |
| m_set.erase(std::prev(itr)); | |
| m_set.erase(std::next(itr)); | |
| } | |
| } | |
| return { itr, true }; | |
| } | |
| // 整数型のみ | |
| void insert(value_type value) | |
| { | |
| return insert(value, value + 1); | |
| } | |
| void erase(value_type left, value_type right) | |
| { | |
| assert(left <= right); | |
| if (left == right) | |
| { | |
| return; | |
| } | |
| auto itl = m_set.upper_bound({ left, left }); | |
| auto itr = m_set.upper_bound({ right, right }); | |
| if (itl != m_set.begin()) | |
| { | |
| if (std::prev(itl)->second >= left) | |
| { | |
| itl--; | |
| } | |
| } | |
| if (itl == itr) | |
| { | |
| return; | |
| } | |
| auto tl = std::min(left, itl->first); | |
| auto tr = std::max(right, std::prev(itr)->second); | |
| m_set.erase(itl, itr); | |
| if (tl < left) | |
| { | |
| m_set.insert({ tl, left }); | |
| } | |
| if (right < tr) | |
| { | |
| m_set.insert({ right, tr }); | |
| } | |
| } | |
| // 整数型のみ | |
| void erase(value_type value) | |
| { | |
| return erase(value, value + 1); | |
| } | |
| }; | |
| } | |
| int main() | |
| { | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment