...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Example overlap counter provides the simplest application of an interval_map that maps intervals to integers. An interval_map<int,int> serves as an overlap counter if we only add interval value pairs that carry 1 as associated value.
Doing so, the associated values that are accumulated in the interval_map are just the number of overlaps of all added intervals.
#include <iostream> #include <boost/icl/split_interval_map.hpp> using namespace std; using namespace boost::icl; /* The most simple example of an interval_map is an overlap counter. If intervals are added that are associated with the value 1, all overlaps of added intervals are counted as a result in the associated values. */ typedef interval_map<int, int> OverlapCounterT; void print_overlaps(const OverlapCounterT& counter) { for(OverlapCounterT::const_iterator it = counter.begin(); it != counter.end(); it++) { discrete_interval<int> itv = (*it).first; int overlaps_count = (*it).second; if(overlaps_count == 1) cout << "in interval " << itv << " intervals do not overlap" << endl; else cout << "in interval " << itv << ": "<< overlaps_count << " intervals overlap" << endl; } } void overlap_counter() { OverlapCounterT overlap_counter; discrete_interval<int> inter_val; inter_val = discrete_interval<int>::right_open(4,8); cout << "-- adding " << inter_val << " -----------------------------------------" << endl; overlap_counter += make_pair(inter_val, 1); print_overlaps(overlap_counter); cout << "-----------------------------------------------------------" << endl; inter_val = discrete_interval<int>::right_open(6,9); cout << "-- adding " << inter_val << " -----------------------------------------" << endl; overlap_counter += make_pair(inter_val, 1); print_overlaps(overlap_counter); cout << "-----------------------------------------------------------" << endl; inter_val = discrete_interval<int>::right_open(1,9); cout << "-- adding " << inter_val << " -----------------------------------------" << endl; overlap_counter += make_pair(inter_val, 1); print_overlaps(overlap_counter); cout << "-----------------------------------------------------------" << endl; } int main() { cout << ">>Interval Container Library: Sample overlap_counter.cpp <<\n"; cout << "-----------------------------------------------------------\n"; overlap_counter(); return 0; } // Program output: // >>Interval Container Library: Sample overlap_counter.cpp << // ----------------------------------------------------------- // -- adding [4,8) ----------------------------------------- // in interval [4,8) intervals do not overlap // ----------------------------------------------------------- // -- adding [6,9) ----------------------------------------- // in interval [4,6) intervals do not overlap // in interval [6,8): 2 intervals overlap // in interval [8,9) intervals do not overlap // ----------------------------------------------------------- // -- adding [1,9) ----------------------------------------- // in interval [1,4) intervals do not overlap // in interval [4,6): 2 intervals overlap // in interval [6,8): 3 intervals overlap // in interval [8,9): 2 intervals overlap // -----------------------------------------------------------