Найти первый диапазон, не входящий в набор диапазонов - PullRequest
Новая
       16

Найти первый диапазон, не входящий в набор диапазонов

0 голосов
/ 02 февраля 2020

Я уже знаком с пакетом 1D bin, упаковывающим nextFit, firstFit и bestFit + их варианты автономного алгоритма. Я упоминаю это только для контекста. Моя проблема заключается в попытке найти самый узкий диапазон (i,i+required_size) с шириной> = 1, который не в наборе неперекрывающихся диапазонов: 

int required_size;
std::set<std::pair<int,int>> ranges;
std::pair<int,int> result = findNarrowestFitFor(ranges,required_size);

Как мне попытаться решить эту проблему ?

Объясняя это утке: очевидно, мне нужно перебрать диапазоны и найти два смежных элемента, которые не перекрываются.

Бета запросила пример кода, поэтому вот что я нахожусь: 

std::vector<char> buffer;
std::map<int,int> ranges;

// Search for free space by finding narrowest range
// that is not in ranges
const char * find_free_area(size_t nbytes) {
    ptrdiff_t fit = buffer.capacity();
    auto pos = ranges.begin();
    auto itr = pos;
    if(ranges.empty()) {
        return buffer.data();
    }
    while(itr != ranges.end()) {
        // Find next hole begin
        itr = std::adjacent_find(ritr, ranges.end(),
            []( const std::pair<const int,int> & a,
                const std::pair<const int,int> & b) {
                return a.second != b.first;
        });
        if(itr == ranges.end()) {
            itr = ranges.rbegin().base();
        }
        // Get next range
        auto next = std::next(itr);
        if(next != ranges.end()) {
            auto space = next->first - itr->second;
            if(space < fit) {
                fit = space;
                pos = ranges.begin();
                std::advance(pos, itr->second);
            }
        } else if(itr->second ) {
            // todo..
        }
    }
}
...