[ICL] interval_map question
Hi all, I'm trying to use interval_map to implement some kind of range to value directory, but I have some non expected results. The test code I'm using is: ------------------------ #include <iostream> #include <boost/icl/interval_map.hpp> #include <boost/icl/discrete_interval.hpp> using namespace std; using namespace boost::icl; int main(int argc, char const **argv) { interval_map<size_t, int> imap; typedef discrete_interval<size_t> interval_t; imap += make_pair(construct<interval_t>(0, 7, interval_bounds::closed()),0); cout << "imap: " << imap << endl; imap.set(make_pair(construct<interval_t>(0, 0, interval_bounds::closed()),1)); cout << "imap: " << imap << endl; imap.erase(construct<interval_t>(3, 3, interval_bounds::closed())); cout << "imap: " << imap << endl; } ------------------------ The result I got is: imap: {} imap: {([0,0]->1)} imap: {([0,0]->1)} but the result I was expecting is: imap: {([0,7]->0)} imap: {([0,0]->1)((0,7]->0)} imap: {([0,0]->1)((0,3)->0)((3,7]->0)} Do I missing something? Thanks, Antal
Hi Antal, the output of your program is correct. This is because interval_maps do *not* store interval value pairs (I,v), if v==0 or more precisely, if v is the identity element of the codomain_type of associated values. 2011/5/25 Antal A. Buss <abuss@cs.tamu.edu>:
Hi all,
I'm trying to use interval_map to implement some kind of range to value directory, but I have some non expected results.
The test code I'm using is: ------------------------ #include <iostream> #include <boost/icl/interval_map.hpp> #include <boost/icl/discrete_interval.hpp>
using namespace std; using namespace boost::icl;
int main(int argc, char const **argv) { interval_map<size_t, int> imap;
// use interval_map<size_t, int, partial_enricher> imap; // if you want to store zeroes as associated values.
typedef discrete_interval<size_t> interval_t;
imap += make_pair(construct<interval_t>(0, 7, interval_bounds::closed()),0); cout << "imap: " << imap << endl;
imap.set(make_pair(construct<interval_t>(0, 0, interval_bounds::closed()),1)); cout << "imap: " << imap << endl;
imap.erase(construct<interval_t>(3, 3, interval_bounds::closed())); cout << "imap: " << imap << endl; } ------------------------
The result I got is: imap: {} imap: {([0,0]->1)} imap: {([0,0]->1)}
Correct result, because [0,7]->0 is not stored. There is a MapTraits parameter http://www.joachim-faulhaber.de/boost_icl/doc/libs/icl/doc/html/boost_icl/co... Default for MapTraits is the value 'partial_absorber'. The _absorber part of the name indicates, that interval-value-pairs associated to 0 are absorbed. So a segment of the interval_map "quantified" zero disappears, keeping the map minimal. If you need to store zeros, choose partial_enricher as MapTrait. It is called _enricher, because (I,0)-segments, that may occur through aggregating operations accumulate over time. So using this type of interval map: interval_map<size_t, int, partial_enricher> imap;
but the result I was expecting is: imap: {([0,7]->0)} imap: {([0,0]->1)((0,7]->0)} imap: {([0,0]->1)((0,3)->0)((3,7]->0)}
you will get the desired result. Best regards, Joachim -- Interval Container Library [Boost.Icl] http://www.joachim-faulhaber.de
Another side note on this to make the issue more comprehensible. An interval_map is usable as a map, but it is also an aggregation device. You may think of it a "counter" or "quantifier" for associated "things" that can occur in time (e.g. count number of party guests). Looking from this important use case it is often desirabel to omit segments from the map, that are counted 0 times (in other words, that are zero-quantified). 2011/5/25 Antal A. Buss <abuss@cs.tamu.edu>:
Hi all,
I'm trying to use interval_map to implement some kind of range to value directory, but I have some non expected results.
The test code I'm using is: ------------------------ #include <iostream> #include <boost/icl/interval_map.hpp> #include <boost/icl/discrete_interval.hpp>
using namespace std; using namespace boost::icl;
int main(int argc, char const **argv) { interval_map<size_t, int> imap; typedef discrete_interval<size_t> interval_t;
imap += make_pair(construct<interval_t>(0, 7, interval_bounds::closed()),0); cout << "imap: " << imap << endl;
imap.set(make_pair(construct<interval_t>(0, 0, interval_bounds::closed()),1)); cout << "imap: " << imap << endl;
imap.erase(construct<interval_t>(3, 3, interval_bounds::closed())); cout << "imap: " << imap << endl; } ------------------------
The result I got is: imap: {} imap: {([0,0]->1)} imap: {([0,0]->1)}
but the result I was expecting is: imap: {([0,7]->0)} imap: {([0,0]->1)((0,7]->0)} imap: {([0,0]->1)((0,3)->0)((3,7]->0)}
So again, from the perspective of counting or "quantification" both results are equal, if we are not interested in zero-counted segments. If we omit the zero-quantified segments in the second imap, it equals the first one. Thank you for the question. This is probably a trap for many users, because it is different from the standard semantics of a std::map that we tend to expect. From the perspective of most use cases of interval_map as a means for aggregation though, the current default-behavior seems to be justified. HTH, Joachim -- Interval Container Library [Boost.Icl] http://www.joachim-faulhaber.de
participants (2)
-
Antal A. Buss -
Joachim Faulhaber