Selection in the codomain of interval_map

Question

In my current project processes, distinguishable intervals, needs to be combined, if they are adjacent.

For this purpose I wanted to use the fantastic boost::icl library. Every process can be uniquely identified by its id.

First I'm adding some intervals to my interval_map. Now I wanted to accomplish two things:

• Iterate over all occurring process-types (Here id=1,4,7)
• Secondly, iterate over all processes being in a certain subset of kinds, in such a way that merging of overlapping intervals is automatically done.

This is what I got so far:

#include <iostream>
#include <set>
#include <boost/icl/interval_map.hpp>
#include "boost/icl/closed_interval.hpp"

struct Process {
    int id;
};

bool operator==(const Process& p, const Process& q) {
    return p.id == q.id;
}

bool operator<(const Process& p, const Process& q) {
    return p.id < q.id;
}

std::ostream& operator<<(std::ostream& str, const Process& p) {
    str << "Process{" << p.id << "}";
    return str;
}
int main(int, char**) {
    using namespace boost::icl;
    interval_map<double, std::set<Process>> imap;   
    imap.add({ interval<double>::closed(0., 4.),{ Process{ 4 } } });
    imap.add({ interval<double>::closed(2., 6.),{ Process{ 1 } } });
    imap.add({ interval<double>::closed(4., 9.),{ Process{ 4 } } });
    imap.add({ interval<double>::closed(8., 8.),{ Process{ 7 } } });
    for (auto&& iter : imap) {
        std::cout << iter.first << " - " << iter.second<<  std::endl;
    }
    for (auto iter : find(imap, { Process{4} })) { // How to implement find on codomain
        // Should print:
        // [0.,4.] - { Process{4}}
        // [4.,9.] - { Process{4}}
        std::cout << iter.first << " - " << iter.second << std::endl;
        }
}

Answer 1

First, an observation, since the intervals are closed, [0,4] and [4,6] aren't actually adjacent, but overlapping. Did you mean right_open?

Second, the interval map models a function, the mapping is not guaranteed to be injective.

In the limited scope of your example, it seems you'd rather invert the datastructure, to arrive at:

#include "boost/icl/closed_interval.hpp"
#include <boost/icl/interval_map.hpp>
#include <iostream>
#include <set>
#include <map>

struct Process {
    int id;

    friend bool operator==(const Process& p, const Process& q) { return p.id == q.id; }
    friend bool operator<(const Process& p, const Process& q) { return p.id < q.id; }
    friend std::ostream& operator<<(std::ostream& str, const Process& p) {
        return str << "Process{" << p.id << "}";
    }
};

int main(int, char**) {
    using namespace boost::icl;
    using Map = std::map<Process, boost::icl::interval_set<double> >; // instead of boost::icl::interval_map<double, std::set<Process> >;
    using IVal = Map::mapped_type::interval_type;
    Map imap;
    imap[{4}] += IVal::right_open(0, 4);
    imap[{1}] += IVal::right_open(2, 6);
    imap[{4}] += IVal::right_open(4, 9);
    imap[{7}] += IVal::closed(8, 8);
    //for (auto&& el : imap) { std::cout << el.first << " - " << el.second << std::endl; }

    Process key{4};
    std::cout << key << " - " << imap[key]; 
}

This results in:

Process{4} - {[0,9)}

Which is what I think you meant with "in such a way that merging of overlapping intervals is automatically done".

Having Both

Of course you can derive the inverse mappings from the original data-structure:

template <typename IMap>
auto inverted(IMap const& imap) {
    std::map<typename IMap::codomain_type::value_type, boost::icl::interval_set<typename IMap::domain_type> > output;

    for (auto& el : imap)
        for (auto& key: el.second)
            output[key] += el.first;

    return output;
}

See it Live On Coliru

#include "boost/icl/closed_interval.hpp"
#include <boost/icl/interval_map.hpp>
#include <iostream>
#include <set>

struct Process {
    int id;

    friend bool operator==(const Process& p, const Process& q) { return p.id == q.id; }
    friend bool operator<(const Process& p, const Process& q) { return p.id < q.id; }
};

std::ostream& operator<<(std::ostream& str, const Process& p) {
    str << "Process{" << p.id << "}";
    return str;
}

template <typename IMap>
auto inverted(IMap const& imap) {
    std::map<typename IMap::codomain_type::value_type, boost::icl::interval_set<typename IMap::domain_type> > output;

    for (auto& el : imap)
        for (auto& key: el.second)
            output[key] += el.first;

    return output;
}

int main(int, char**) {
    using namespace boost::icl;
    using IMap = boost::icl::interval_map<double, std::set<Process> >;
    using IVal = IMap::interval_type;
    IMap imap;
    imap.add({ IVal::right_open(0, 4), {Process{ 4 }} });
    imap.add({ IVal::right_open(2, 6), {Process{ 1 }} });
    imap.add({ IVal::right_open(4, 9), {Process{ 4 }} });
    imap.add({ IVal::closed(8, 8), {Process{ 7 }} });
    std::cout << imap << "\n\n";
    for (auto&& iter : imap) {
        std::cout << iter.first << " - " << iter.second << std::endl;
    }
    Process key{4};
    std::cout << key << " - " << inverted(imap)[key] << "\n";
}

More Notes

Querying multiple keys in the domain is directly supported, see a good assortion of pointers here:

• split_interval_map usage, efficient find all interval intersecting a point
• boost multi_index_container search for records that fall within intervals defined by two fields

You can always construct your own data-structure that affords bi-directional indexes, such as shown e.g.

• here boost::multi_index_container, operations on std::set inside container