segment boolean

main.cc

#include <vector>

using namespace std;

struct segment_t {
    int shape;
    double lower, upper;
};

inline auto operator<(const segment_t &a, const segment_t &b) {
    return a.lower < b.lower;
}

struct segment_list_t {
    vector<segment_t> data;
    auto compact() {
        sort(data.begin(), data.end());
        auto list = data;
        data.resize(0);
        vector<segment_t> tmp;
        for (auto &item : list) {
            tmp.resize(0);
            while (data.size() && data.back().lower >= item.lower) {
                tmp.push_back(data.back());
                data.pop_back();
            }
            append(item);
            while (tmp.size()) {
                append(tmp.back());
                tmp.pop_back();
            }
        }
    }
    inline void append(segment_t item) {
        if (data.size()) {
            auto &last = data.back(),
                rest = merge(last, item);
            if (item.lower < item.upper) {
                data.push_back(item);
            }
            if (rest.lower < rest.upper) {
                data.push_back(rest);
            }
        } else {
            data.push_back(item);
        }
    }
    static segment_t merge(segment_t &last, segment_t &item) {
        if (item.lower <= last.upper) {
            if (item.upper <= last.upper) {
                if (item.shape > last.shape) {
                    auto upper = last.upper;
                    last.upper = item.lower;
                    return segment_t { last.shape, item.upper, upper };
                } else {
                    item.upper = item.lower;
                }
            } else {
                if (item.shape > last.shape) {
                    last.upper = item.lower;
                } else if (item.shape == last.shape) {
                    last.upper = item.upper;
                    item.upper = item.lower;
                } else {
                    item.lower = last.upper;
                }
            }
        }
        return segment_t { };
    }
};

int main() {
    segment_list_t segs;
    segs.data = {
        { -1, -10, 10 },
        { 0, 1.0, 2.0 },
        { 1, 1.2, 1.5 },
        { 2, 1.5, 2.5 },
        { 2, 1.2, 2.0 },
    };
    segs.compact();
    for (auto item : segs.data) {
        printf("%d %f %f\n", item.shape, item.lower, item.upper);
    }
}