Set of real numbers as closed integer intervals (tools/real_interval_set.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2021-10-23 20:26:02+09:00
• Include: #include "tools/real_interval_set.hpp"

It is a set of real numbers, and provides the following two operations.

• Add the real numbers $x$ such that $l \leq x \leq r$ to the set, where $l$ and $r$ are given integers.
• Remove the real numbers $x$ such that $l < x < r$ from the set, where $l$ and $r$ are given integers.

It manages the elements as a set of mutually exclusive closed integer intervals. The set of intervals is implemented as std::map<T, T> m, whose key is the lower bound of an interval and value is the upper bound of it. It provides limited (read-only) access to m.

License

• CC0

Author

• anqooqie

Constructor

real_interval_set<T> set;

It creates an empty set of real numbers. The type parameter <T> represents the type of integer bounds.

Constraints

• None

Time Complexity

• $O(1)$

begin

std::map<T, T>::const_iterator set.begin();

It returns an iterator pointing to the least closed integer interval. In other words, it returns m.begin().

Constraints

• None

Time Complexity

• $O(1)$

end

std::map<T, T>::const_iterator set.end();

It returns an iterator pointing to the interval which would follow the greatest closed integer interval. In other words, it returns m.end().

Constraints

• None

Time Complexity

• $O(1)$

empty

bool set.empty();

It returns whether the set is empty or not.

Constraints

• None

Time Complexity

• $O(1)$

size

std::map<T, T>::size_type set.size();

It returns the number of mutually exclusive closed integer intervals. In other words, it returns m.size().

Constraints

• None

Time Complexity

• $O(1)$

find

std::map<T, T>::const_iterator set.find(T x);

It returns an iterator pointing to the interval which contains $x$. If such the interval does not exist, it returns set.end().

Constraints

• None

Time Complexity

• $O(\log n)$ where $n$ is the number of mutually exclusive closed integer intervals.

contains

bool set.contains(T x);

It returns whether the set contains $x$ or not.

Constraints

• None

Time Complexity

• $O(\log n)$ where $n$ is the number of mutually exclusive closed integer intervals.

lower_bound

std::map<T, T>::const_iterator set.lower_bound(T x);

It returns an iterator pointing to the least interval whose upper bound is greater than or equal to $x$. If such the interval does not exist, it returns set.end().

Constraints

• None

Time Complexity

• $O(\log n)$ where $n$ is the number of mutually exclusive closed integer intervals.

upper_bound

std::map<T, T>::const_iterator set.upper_bound(T x);

It returns an iterator pointing to the least interval whose lower bound is greater than $x$. If such the interval does not exist, it returns set.end().

Constraints

• None

Time Complexity

• $O(\log n)$ where $n$ is the number of mutually exclusive closed integer intervals.

insert

void set.insert(T l, T r);

It inserts the real numbers $x$ such that $l \leq x \leq r$ to the set.

Constraints

• None

Time Complexity

• $O(\log n)$ where $n$ is the number of mutually exclusive closed integer intervals.

erase

void set.erase(T l, T r);

It removes the real numbers $x$ such that $l < x < r$ from the set.

Constraints

• None

Time Complexity

• $O(\log n)$ where $n$ is the number of mutually exclusive closed integer intervals.

Depends on

• tools/detail/interval_set.hpp

Verified with

• tests/real_interval_set.test.cpp

Code

#ifndef TOOLS_REAL_INTERVAL_SET_HPP
#define TOOLS_REAL_INTERVAL_SET_HPP

#include "tools/detail/interval_set.hpp"

namespace tools {
  template <typename T>
  using real_interval_set = ::tools::detail::interval_set<T, false>;
}

#endif

#line 1 "tools/real_interval_set.hpp"



#line 1 "tools/detail/interval_set.hpp"



#include <map>
#include <iterator>
#include <optional>
#include <utility>
#include <iostream>
#include <string>

namespace tools {
  namespace detail {
    template <typename T, bool Mergeable>
    class interval_set {
    private:
      // closed intervals
      ::std::map<T, T> m_intervals;
  
    public:
      interval_set() = default;
      interval_set(const ::tools::detail::interval_set<T, Mergeable>&) = default;
      interval_set(::tools::detail::interval_set<T, Mergeable>&&) = default;
      ~interval_set() = default;
      ::tools::detail::interval_set<T, Mergeable>& operator=(const ::tools::detail::interval_set<T, Mergeable>&) = default;
      ::tools::detail::interval_set<T, Mergeable>& operator=(::tools::detail::interval_set<T, Mergeable>&&) = default;
  
      auto begin() const {
        return this->m_intervals.begin();
      }
  
      auto end() const {
        return this->m_intervals.end();
      }
  
      bool empty() const {
        return this->m_intervals.empty();
      }
  
      auto size() const {
        return this->m_intervals.size();
      }
  
      auto find(const T& x) const {
        const auto next = this->m_intervals.upper_bound(x);
        if (next == this->m_intervals.begin()) return this->m_intervals.end();
        const auto prev = ::std::prev(next);
        if (prev->second < x) return this->m_intervals.end();
        return prev;
      }
  
      bool contains(const T& x) const {
        return this->find(x) != this->m_intervals.end();
      }
  
      auto lower_bound(const T& x) const {
        const auto next = this->m_intervals.lower_bound(x);
        if (next == this->m_intervals.begin()) return next;
        const auto prev = ::std::prev(next);
        if (prev->second < x) return next;
        return prev;
      }
  
      auto upper_bound(const T& x) const {
        return this->m_intervals.upper_bound(x);
      }
  
      void insert(const T& l, const T& r) {
        if (!(l <= r)) {
          return;
        }
  
        const auto l_it = this->find(l - (Mergeable ? 1 : 0));
        const T min = l_it != this->m_intervals.end() ? l_it->first : l;
        const auto r_it = this->find(r + (Mergeable ? 1 : 0));
        const T max = r_it != this->m_intervals.end() ? r_it->second : r;
  
        this->m_intervals.erase(this->lower_bound(l - (Mergeable ? 1 : 0)), this->upper_bound(r + (Mergeable ? 1 : 0)));
        this->m_intervals.emplace(min, max);
      }
  
      void erase(const T& l, const T& r) {
        if (!(l <= r + (Mergeable ? 0 : 1))) {
          return;
        }
  
        const auto l_it = this->find(l);
        const auto l_new_interval = l_it != this->m_intervals.end() && l_it->first <= l - (Mergeable ? 1 : 0)
          ? ::std::make_optional(::std::make_pair(l_it->first, l - (Mergeable ? 1 : 0)))
          : ::std::nullopt;
        const auto r_it = this->find(r);
        const auto r_new_interval = r_it != this->m_intervals.end() && r + (Mergeable ? 1 : 0) <= r_it->second
          ? ::std::make_optional(::std::make_pair(r + (Mergeable ? 1 : 0), r_it->second))
          : ::std::nullopt;
  
        this->m_intervals.erase(this->lower_bound(l), this->upper_bound(r));
  
        if (l_new_interval) {
          this->m_intervals.emplace(l_new_interval->first, l_new_interval->second);
        }
        if (r_new_interval) {
          this->m_intervals.emplace(r_new_interval->first, r_new_interval->second);
        }
      }
  
      friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::detail::interval_set<T, Mergeable>& self) {
        os << '{';
        ::std::string delimiter = "";
        for (const auto& [l, r] : self) {
          os << delimiter << '[' << l << ", " << r << ']';
          delimiter = ", ";
        }
        os << '}';
        return os;
      }
    };
  }
}


#line 5 "tools/real_interval_set.hpp"

namespace tools {
  template <typename T>
  using real_interval_set = ::tools::detail::interval_set<T, false>;
}

Back to top page