5

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.

vy32
  • 28,461
  • 37
  • 122
  • 246

2 Answers2

5

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

Zeks
  • 2,265
  • 20
  • 32
  • It's not clear to me if the Boost.lcl will combine adjacent extents. Do you know for sure that it does? We're going to have hundreds of thousands of contiguous extents. – vy32 Dec 21 '12 at 00:30
  • Yes it will. I use it in this way all the time. Check this page:http://www.boost.org/doc/libs/1_52_0/libs/icl/doc/html/index.html#boost_icl.introduction.interval_combining_styles – Zeks Dec 21 '12 at 07:27
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;
    }
}
Gigi
  • 4,953
  • 24
  • 25
  • Thanks. Question --- I've seen a whole bunch of people defining classes with `struct`, as you have here, rather than with a proper C++ class declaration. Why define a class as a structure? – vy32 Dec 21 '12 at 01:52
  • 1
    See [here](http://stackoverflow.com/questions/92859/what-are-the-differences-between-struct-and-class-in-c) for a SO question regarding the differences between struct and class. Personally, I do it because I always declare public methods on top of the class and I don't want to always type 'public:'. With time it has became an habit. – Gigi Dec 21 '12 at 02:08