CODEWITHSUNDEEP
c++boostintervals
gsf
gsf

Reputation: 7262

c++ tracking discrete space sequence

I have a discrete space (say integers). They are split in groups say:

group A: 1, 4, 6
group B: 2, 3, 5
etc

Where the items in the group are in order and there is no repeating numbers between the groups.

I have a handler that pools every group for new items, where there might be zero or more new items.

Say:

pool Group A - returns 1, 4
pool Group B - returns 2, 3
pool Group A - returns 6
pool Group B - returns 5

The process of adding new items to the groups and pooling them is continuous.

I need to be able to tell at any point is there a hole in the discrete space that was already handled.

In this example when I handle 1 - the result is no - no hole. Then as soon I handle 4, this creates a hole between 1 and 4. Then Adding 2, there is still hole, but when I add 3 there is no hole anymore.

I am considering using boost::interval where I just add every item when it occurs. Seems extremely easy to implement, but boost interval is optimized for intervals. I do not like using std::vector or boost::dynamic_bitset, because there is no reason for me to keep increasing the memory footprint of the tracking. I do not need which numbers were handled - all I need is to be able to tell is there a hole or not.

The performance requirement is high. I am curious is there a better way to do this. Any ideas?

Upvotes: 1

Views: 142

Answers (1)

sehe
sehe

Reputation: 393719

You can indeed use Boost ICL, as you suspected.

The default interval combining style is "Joining". This is exactly what you need! So, it's home run.

Here's a trivial demo with exactly the input events as given in the example. I print the state of the record at each event (yay for Boost ICL IO support!).

Live On Coliru

#include <boost/icl/interval_set.hpp>
#include <iostream>

using Set      = boost::icl::interval_set<int>;
using Interval = Set::interval_type;

int main() {

    Set record;

    // pool Group A - returns 1, 4
    // pool Group B - returns 2, 3
    // pool Group A - returns 6
    // pool Group B - returns 5

    int stepcount = 0;

    for (int sample : {
            1, 4,
            2, 3,
            6,
            5 })
    {
        record.insert(sample);
        std::cout << "state at #" << ++stepcount << ": " << record << "\n";
    }
}

Which prints:

state at #1: {[1,1]}
state at #2: {[1,1][4,4]}
state at #3: {[1,2][4,4]}
state at #4: {[1,4]}
state at #5: {[1,4][6,6]}
state at #6: {[1,6]}

As you can see, the gap did indeed disappear right when 3 closed it. This seems to be exactly what you want/described.

Note You'll be happy to know that if holes are rare/big (contiguous ranges are "holes") then ICL will even get you highly compressed storage representation. That's in the core of the library features. So, profile things, I think you'll be fine with this.

If you need better scalability you can perhaps choose to truncate the "history" that you don't need anymore as the number go up. You'd do

record.erase(Interval::open(0, 4));
std::cout << "state after erase: " << record << "\n";

Which would print

state after erase: {[4,6]}

Upvotes: 1

Related Questions