Wymagane: klasa C++ do obsługi 1-wymiarowej listy zakresów

Question

Poszukuję klasy C++, która może obsługiwać 1-wymiarową listę zakresów.

Każdy zakres jest zdefiniowany jako para (start,len).

Chcę móc dodawać dodatkowe zakresy do listy i automatycznie je konsolidować. Oznacza to, że jeśli mamy na liście (0,5) i (10,5) i zostanie dodana (5,5), nowa lista powinna zawierać tylko (0,15).

Zakresy nigdy nie są usuwane z listy.

Czy coś takiego istnieje?

Dzięki.

Answer 1

Poszukujesz narzędzia Boost.Icl. Robi dokładnie to, co opisałeś.

http://www.boost.org/doc/libs/1_52_0/libs/icl/doc/html/index.html

Answer 2

Oto przykład implementacja prostego przedziale pojemnika:

#include <iostream> 
#include <vector> 
#include <memory> 
#include <algorithm> 

using std::vector; 
using std::pair; 
using std::make_pair; 

typedef pair<int, int> interval;  

struct interval_container 
{ 
    void add(int start, int len) 
    { 
     _data.emplace_back(make_pair(start, len)); 
    } 

    void consolidate() 
    { 
     // sort intervals first by start then by length 
     std::sort(_data.begin(), _data.end()); 

     // create temp data 
     vector<interval> consolidated; 

     // iterate over all sorted intervals 
     for(const interval& i : _data) 
     { 
      int start = i.first; 
      int len = i.second; 

      // special case: first interval 
      if (consolidated.empty()) 
      { 
       consolidated.emplace_back(i); 
      } 
      // all other cases 
      else 
      { 
       // get last interval in the consolidated array 
       interval& last = consolidated.back(); 
       int& last_start = last.first; 
       int& last_len = last.second; 


       // if the current interval can be merged with the last one 
       if ((start >= last_start) and (start < (last_start + last_len))) 
       { 
        // merge the interval with the last one 
        last_len = std::max(last_len, (start + len - last_start)); 
       } 
       // if the current interval can't be merged with the last one 
       else 
       { 
        consolidated.emplace_back(i); 
       } 
      } 
     } 

     // copy consolidated data 
     _data = consolidated; 
    } 


    vector<interval>& data() { return _data; } 

private: 
    vector<interval> _data; 
}; 


int main() 
{ 
    interval_container intervals; 

    intervals.add(0, 2); 
    intervals.add(1, 3); 
    intervals.add(5, 3); 

    intervals.consolidate(); 

    int c(0); 
    for(interval i : intervals.data()) 
    { 
     std::cout << (c++) << ": from " << i.first << " to " << (i.first + i.second) << std::endl; 
    } 
}