mercredi 30 septembre 2015

A container for integer intervals, such as RangeSet, for C++

I am trying to work with ranges, as in ranges of numbers. By that I mean integer intervals, in maths speak. And I want to store a set of them. I also want this set to naturally merge (or coalesce) ranges I insert.

Let's go for a simple example, I start with an empty set: { }

  • I insert the range [0,5], now I have { [0,5] }
  • I insert the range [10,15], now I have { [0,5], [10,15] }
  • I insert the range [5,7], now I have { [0,7], [10,15] }
  • I insert the range [12,17], now I have { [0,7], [10,17] }
  • I insert the range [6,13], now I have { [0,17] }

I found out thanks to a similar question that this exists in Java as a Google Guava library and is called a RangeSet.

I was initially thinking of using a std::set of std::pairs that would be sorted on the lower bound (so the first element of each pair). Then after each insertion I would have to manually merge any overlapping sets.

As this seems a common problem, is a good implementation I couldn't find due to the noise with all the synonyms of "range" in C++ ? Or does anyone care to share his own? I only want to print the final ranges but bonus points for generality if you have other set operations.

Aucun commentaire:

Enregistrer un commentaire