Necessario: classe C++ per il mantenimento di un elenco di estensioni 1-dimensionale

Question

Sto cercando una classe C++ in grado di mantenere un elenco di estensioni 1-dimensionale.

Ogni estensione è definita come una coppia (start,len).

Desidero poter aggiungere ulteriori estensioni all'elenco e farle automaticamente consolidare. Cioè, se abbiamo (0,5) e (10,5) nell'elenco e (5,5) è aggiunto, il nuovo elenco dovrebbe contenere solo (0,15).

Le estensioni non vengono mai rimosse dall'elenco.

Esiste qualcosa del genere?

Grazie.

Answer 1

Stai cercando Boost.Icl. Fa esattamente quello che hai descritto.

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

Answer 2

Ecco un esempio di implementazione di un semplice contenitore intervallo:

#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; 
    } 
}