dl_discrete_range.h

浏览该文件的文档.

#pragma once
 
#include <optional>
 
namespace dl
{
template<typename T>
class DiscreteRange
{
    using Range = std::array<T, 2>;
public:
    void Add(const T& v)
    {
        auto iter = _data.begin();
        while (iter != _data.end())
        {
            Range& r = *iter;
            if (v < r[0])
            {// 小于区间左侧，必定不在所有区间内
                if (v + 1 == r[0])
                {// 刚好在边上
                    --r[0];
                    // 左移后不会连接到上一个区间，因为上一个区间已经判断
                    return;
                }
                // 添加新区间
                break;
            }
            if (v > r[1])
            {// 大于区间右侧，必定不在当前区间内
                if (v == r[1] + 1)
                {// 刚好在边上
                    auto iter_next = std::next(iter);
                    if (iter_next != _data.end() && (*iter_next)[0] == v + 1)
                    {
                        // 右移后会连接到下一个区间
                        r[1] = (*iter_next)[1];
                        _data.erase(iter_next);
                    }
                    else
                        ++r[1];
                    return;
                }
                ++iter;
                continue;
            }
            // 剩下条件在范围内
            return;
        }
        _data.insert(iter, { v, v });
    }
 
    std::string ToString()
    {
        std::string ret;
        for (auto& iter : _data)
        {
            ret += fmt::format("[{}] ", to_string(iter));
        }
        return ret;
    }
 
    std::optional<Range> GetTotalRange()
    {
        if (_data.empty())
            return {};
        if (_data.size() == 1)
            return _data.front();
        return Range{ _data.front()[0], _data.back()[1] };
    }
private:
    std::list<Range> _data;
};
}