interval_set.hh

#pragma once
 
#include <algorithm>
#include <clingo/util/small_vector.hh>
 
namespace CppClingo::Util {
 
 
template <class T> class interval_set {
  public:
    using value_type = T;
    struct right_bound;
 
    struct left_bound {
        constexpr left_bound(value_type bound, bool inclusive) : bound{std::move(bound)}, inclusive{inclusive} {}
        explicit left_bound(right_bound const &x) : bound(x.bound), inclusive(!x.inclusive) {}
 
        value_type bound;
        bool inclusive;
    };
 
    struct right_bound {
        constexpr right_bound(value_type bound, bool inclusive) : bound{std::move(bound)}, inclusive{inclusive} {}
        explicit right_bound(left_bound const &x) : bound(x.bound), inclusive(!x.inclusive) {}
 
        value_type bound;
        bool inclusive;
    };
 
    struct interval {
        constexpr interval(left_bound left, right_bound right) : left{std::move(left)}, right{std::move(right)} {}
        auto contains(value_type const &x) const -> bool { return !(x < *this) && !(*this < x); }
        [[nodiscard]] auto empty() const -> bool { return !(left < right); }
 
        left_bound left;
        right_bound right;
    };
    using interval_vector = small_vector<interval>;
    using iterator = typename interval_vector::const_iterator;
 
    friend auto operator<(left_bound const &x, left_bound const &y) -> bool {
        return x.bound < y.bound || (x.bound == y.bound && x.inclusive && !y.inclusive);
    }
    friend auto operator<=(left_bound const &x, left_bound const &y) -> bool {
        return x.bound < y.bound || (x.bound == y.bound && (x.inclusive || !y.inclusive));
    }
    friend auto operator<(left_bound const &x, right_bound const &y) -> bool {
        return x.bound < y.bound || (x.bound == y.bound && x.inclusive && y.inclusive);
    }
 
    friend auto operator<(right_bound const &x, right_bound const &y) -> bool {
        return x.bound < y.bound || (y.bound == x.bound && !x.inclusive && y.inclusive);
    }
    friend auto operator<=(right_bound const &x, right_bound const &y) -> bool {
        return x.bound < y.bound || (y.bound == x.bound && (!x.inclusive || y.inclusive));
    }
    friend auto operator<(right_bound const &x, left_bound const &y) -> bool {
        return x.bound < y.bound || (y.bound == x.bound && !x.inclusive && !y.inclusive);
    }
 
    friend auto operator<(interval const &x, interval const &y) -> bool { return x.right < y.left; }
    friend auto operator<(value_type const &x, interval const &y) -> bool {
        return x < y.left.bound || (y.left.bound == x && !y.left.inclusive);
    }
    friend auto operator<(interval const &x, value_type const &y) -> bool {
        return x.right.bound < y || (y == x.right.bound && !x.right.inclusive);
    }
 
    interval_set() = default;
    ~interval_set() = default;
 
    interval_set(interval_set const &other) = default;
    auto operator=(interval_set const &other) -> interval_set & = default;
 
    interval_set(interval_set &&other) noexcept = default;
    auto operator=(interval_set &&other) noexcept -> interval_set & = default;
 
    interval_set(std::initializer_list<interval> list) {
        for (auto &x : list) {
            add(x);
        }
    }
 
    void reserve(size_t n) { vec_.reserve(n); }
 
    auto release() -> interval_vector { return std::move(vec_); }
 
    auto add(interval const &x) -> interval_set & {
        if (!x.empty()) {
            auto it = std::lower_bound(vec_.begin(), vec_.end(), x);
            if (it == vec_.end()) {
                vec_.emplace_back(x);
            } else {
                auto jt = std::upper_bound(it, vec_.end(), x);
                if (it == jt) {
                    vec_.emplace(it, x);
                } else {
                    it->left = std::min(x.left, it->left);
                    it->right = std::max(x.right, (jt - 1)->right);
                    vec_.erase(it + 1, jt);
                }
            }
        }
        return *this;
    }
 
    auto remove(interval const &x) -> interval_set & {
        if (!x.empty()) {
            auto it = std::lower_bound(vec_.begin(), vec_.end(), x);
            if (it != vec_.end()) {
                auto jt = std::upper_bound(it, vec_.end(), x);
                if (it + 1 == jt) {
                    auto r = interval{left_bound{x.right}, it->right};
                    it->right = right_bound{x.left};
                    if (it->empty()) {
                        if (r.empty()) {
                            vec_.erase(it);
                        } else {
                            *it = r;
                        }
                    } else if (!r.empty()) {
                        vec_.emplace(it + 1, r);
                    }
                } else if (it != jt) {
                    it->right = right_bound{x.left};
                    (jt - 1)->left = left_bound{x.right};
                    vec_.erase(it + !it->empty(), jt - !(jt - 1)->empty());
                }
            }
        }
        return *this;
    }
 
    [[nodiscard]] auto contains(interval const &x) const -> bool {
        if (x.empty()) {
            return true;
        }
        for (auto &y : vec_) {
            if (x.right <= y.right) {
                return y.left <= x.left;
            }
        }
        return false;
    }
 
    [[nodiscard]] auto contains(T const &x) const -> bool {
        for (auto &y : vec_) {
            if (!(y < x)) {
                return !(x < y);
            }
        }
        return false;
    }
 
    [[nodiscard]] auto intersects(interval const &x) const -> bool {
        if (!x.empty()) {
            for (auto &y : vec_) {
                if (x.left < y.right) {
                    return y.left < x.right;
                }
            }
        }
        return false;
    }
 
    [[nodiscard]] auto empty() const -> bool { return vec_.empty(); }
 
    [[nodiscard]] auto size() const -> size_t { return vec_.size(); }
 
    [[nodiscard]] auto front() const -> interval const & { return vec_.front(); }
 
    [[nodiscard]] auto back() const -> interval const & { return vec_.back(); }
 
    [[nodiscard]] auto begin() const -> iterator { return vec_.begin(); }
 
    [[nodiscard]] auto end() const -> iterator { return vec_.end(); }
 
    void clear() { return vec_.clear(); }
 
    [[nodiscard]] auto intersect(interval_set const &set) const -> interval_set {
        auto it = vec_.begin();
        interval_set intersection;
        for (auto &x : set.vec_) {
            for (; it != vec_.end() && it->right < x.left; ++it) {
            }
            for (; it != vec_.end() && it->right <= x.right; ++it) {
                intersection.vec_.emplace_back(interval{std::max(it->left, x.left), it->right});
            }
            if (it != vec_.end() && it->left < x.right) {
                intersection.vec_.emplace_back(interval{std::max(it->left, x.left), x.right});
            }
        }
        return intersection;
    }
 
    auto difference(interval_set const &set) const -> interval_set {
        auto it = set.vec_.begin();
        interval_set difference;
        for (auto &x : vec_) {
            interval current = x;
            for (; it != set.vec_.end() && it->right < current.left; ++it) {
            }
            for (; it != set.vec_.end() && it->right <= current.right; ++it) {
                if (current.left < it->left) {
                    difference.vec_.emplace_back(current);
                    difference.vec_.back().right = right_bound{it->left};
                }
                current.left = left_bound{it->right};
            }
            if (it != set.vec_.end() && it->left < current.right) {
                current.right = right_bound{it->left};
            }
            if (current.left < current.right) {
                difference.vec_.emplace_back(current);
            }
        }
        return difference;
    }
 
  private:
    interval_vector vec_;
};
 
 
} // namespace CppClingo::Util