Needed: C++ class for maintaining a 1-dimensional list of extents

Question

I am looking for a C++ class that can maintain a 1-dimensional list of extents.

Each extent is defined as a (start,len) pair.

I want to be able to add additional extents to the list and have them automatically consolidated. That is, if we have (0,5) and (10,5) in the list, and (5,5) is added, the new list should contain only (0,15).

Extents are never removed from the list.

Does anything like this exist?

Thanks.

Answer 1

Your are looking for Boost.Icl. It does exactly what you described.

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

Answer 2

Here is an example implementation of a simple interval container:

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