[Review] ITL review starts today, February 18th
Hi all, The formal review of the Interval Template Library (ITL) starts today, February 18th, 2010 and will end February 27th, 2010. ITL is being developed by Joachim Faulhaber. ------------------------------------------------ About the library: The Interval Template Library (ITL) is a library of interval containers that facilitates computations on collections of intervals and associated values. Use cases of such computations typically occur in the date and time problem domain, when collections of time intervals with associated data are analyzed, combined and aggregated. But the scope of applications for interval containers is more general and not limited to date and time problems. Interval containers allow to access and manipulate collections of intervals on an abstract level as sets and maps (of elements), but also to exploit segmental information that is given by the interval borders. Interval containers are fairly generic. They can be instantiated with discrete domain (or key) types like integral numeric types or boost::date or time types. But they also work with continuous domain types like double, rational or string. Using the latter allows to represent infinite sets and maps. The interface of the interval containers strives to be very intuitive and in line with the stl and other boost libraries. * The set theoretic operations union, difference, intersection and symmetric difference are available as operators for all interval containers and for many useful overloads between them. * There is iterator support on the level of segments and interval containers can be combined with stl containers of intervals via stl algorithms. * For discrete domain types, element iterators are available which makes interval sets and maps models of SortedAssociative Containers so they can be used with many stl algorithms. All interval containers are addable and subtractable. The addability and subtractability concept of the ITL leads to a general mechanism of aggregation on interval_maps which is called 'aggregate on overlap'. Exploiting 'aggregate on overlap' allows to compute many useful aggregation results in a simple and abstract manner. The ITL's Set and Map concepts are defined by a signature and collections of laws or axioms. Those semantical constraints have been validated using automatic law based tests. This gives the library both a well founded formal specification and an unusual thorough test base. The ITL emerged out of real world use cases and is successfully used at Cortex Software GmbH since a couple of years in the production code of various applications. On the boost developer's list it has been proposed in four previews and a review request since May 2008 and has been refactored and refined according to boost standards and suggestions from the list. The ITL is available from the boost vault: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=itl_3_2 _0.zip&directory=Containers Documentation is online available at: http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/index.html The current sources are in the sandbox: https://svn.boost.org/svn/boost/sandbox/itl/ ------------------------------------------------ Everybody on this list is invited to participate in this formal review. I hope to see your review of this library, including your vote, and I welcome your participation in the discussions on the Boost mailing list. Please always state in your review, whether you think the library should be accepted as a Boost library. Additionally, please consider giving feedback on the following general topics: - What is your evaluation of the design? - What is your evaluation of the implementation? - What is your evaluation of the documentation? - What is your evaluation of the potential usefulness of the library? - Did you try to use the library? With what compiler? Did you have any problems? - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? - Are you knowledgeable about the problem domain? Regards Hartmut Review Manager --------------- Meet me at BoostCon www.boostcon.com
Hi Joachim, This is not yet the review. I'm about halfway and I'm enthousiastic. I've done two small projects inspired on my needs and all I tried is working good, it definitely is a useful library. Questions /remarks though. 1) The set union is modelled as += (doc: "So interval_sets define an operator += that is naturally implemented as set union and an operator -= that is consequently implemented as set difference"), set intersection as &= (according to the doc definition and man_power sample). However, a union is more or less like an OR operation, an intersection like and AND operation, so I would have expected that union would be |=. According to the manual, in another place, that is also supported. Boost.Polygon(BP)/GTL also supports both, for union. Is it intentional that two operators are implemented for the same operation in these two libraries? And if so, why is that not done for the intersection (having synonym *= in BP). Boost.dynamic_bitset also implement all of these: dynamic_bitset& operator&=(const dynamic_bitset& b); Bitwise-AND ... dynamic_bitset& operator|=(const dynamic_bitset& b); Bitwise-OR's... dynamic_bitset& operator^=(const dynamic_bitset& b); Bitwise-XOR's... dynamic_bitset& operator-=(const dynamic_bitset& b); Computes the set difference of this bitset... Boost.Geometry does not (yet) implement operators so we look in a way to conform, if possible, and would like to avoid to introduce synonyms. So I would advocate, for (at least) the four libraries Boost.dynamic_bitset, Boost.Polygon, Boost.Geometry and ITL, the usage of operators conform dynamic bitset, so the following: &= for intersection |= for union ^= for symmetric difference (as is done in both ITL and BP) -= for difference (as is done in both ITL and BP) 2) Same scope, the "boolean" functions "is_disjoint", "contained_in", we in Boost.Geometry have named them (according to ISO/OGC) as "disjoint" and "within". The following functions match: "intersects", "contains" and "touches". And, besides that, ISO/OGC also describe "equals", "overlaps" (where overlaps is roughly intersects, but not completely within, and not touches). So actually we're nearly there, there are just some small differences in names/synonyms. Do you find it a good idea to have / create a common picture of operators and functions and if yes, is it still possible to adapt? Regards, Barend
Hi Barend! I am delighted to hear that you are enthusiastic about my library :) 2010/2/26 Barend Gehrels <barend@geodan.nl>
Hi Joachim,
This is not yet the review.
I'm about halfway and I'm enthousiastic. I've done two small projects inspired on my needs and all I tried is working good, it definitely is a useful library.
Questions /remarks though.
1) The set union is modelled as += (doc: "So interval_sets define an operator += that is naturally implemented as set union and an operator -= that is consequently implemented as set difference"), set intersection as &= (according to the doc definition and man_power sample).
However, a union is more or less like an OR operation, an intersection like and AND operation, so I would have expected that union would be |=. According to the manual, in another place, that is also supported.
Yes, it is. I assigned the identical union semantics both to += and |= although reluctantly because I think operators are "precious"...
Boost.Polygon(BP)/GTL also supports both, for union. Is it intentional that two operators are implemented for the same operation in these two libraries? And if so, why is that not done for the intersection (having synonym *= in BP).
... because operators are "precious".
(1) They are not (yet) producible in c++. We have to get by on a small set of them. So its unwise to waste them. (2) operators are like semantical archetypes. Pretty early in school we make contact with =, <, +, - . They carry semantical invariants not only for mathematicians but for almost every educated human being. This is like a treasure that can be harnessed for those parts of generic libraries that we want to be maximally intuitive to use. (3) While with += and |= I feel kind of coerced to assign the same semantics: + is the primary operator of combining object of some type, which is union (for sets) | is equivalently intuitive from the boolean view of set union a | b = { x : x in a || x in b} (4) With *= and &= this is different. * is in my view not an "archetype" for intersection. (5) Yet, the most important reason is that I'd like to save * for scaling: 2 * {1,2} = {2,4} because this *is* IMO an archetypal meaning for * (6) In the more freaky parts of my semancial studies on interval_maps I found that specific instantiations e.g.: interval_map<int,double,total_absorber> are models of a concept 'indefinite vector' of a vector space, if a scalar multiplication was added. To be able to add this basic operation later I wanted to save * and *= .
Boost.dynamic_bitset also implement all of these: dynamic_bitset& operator&=(const dynamic_bitset& b); Bitwise-AND ... dynamic_bitset& operator|=(const dynamic_bitset& b); Bitwise-OR's... dynamic_bitset& operator^=(const dynamic_bitset& b); Bitwise-XOR's... dynamic_bitset& operator-=(const dynamic_bitset& b); Computes the set difference of this bitset...
Boost.Geometry does not (yet) implement operators so we look in a way to conform, if possible, and would like to avoid to introduce synonyms. So I would advocate, for (at least) the four libraries Boost.dynamic_bitset, Boost.Polygon, Boost.Geometry and ITL, the usage of operators conform dynamic bitset, so the following: &= for intersection |= for union ^= for symmetric difference (as is done in both ITL and BP) -= for difference (as is done in both ITL and BP)
2) Same scope, the "boolean" functions "is_disjoint", "contained_in", we in Boost.Geometry have named them (according to ISO/OGC) as "disjoint" and "within". The following functions match: "intersects", "contains" and "touches". And, besides that, ISO/OGC also describe "equals", "overlaps" (where overlaps is roughly intersects, but not completely within, and not touches).
So actually we're nearly there, there are just some small differences in names/synonyms.
Not being a geometry developer I'm not very aware of the ISO/OGC standard. So I mainly oriented my decisions on greps of boost/ , maths, sometimes google source search, my own preferences and the principle of least astonishment. Because the functions you mentioned are functions on sets, which are so fundamental, the naming should IMO be uniform across all of boost. An existing standard is a strong orientation, but even standards sometimes contain namings that can be unfortunate.
and functions and if yes, is it still possible to adapt?
The more fundamental concepts are, and sets / maps are *very* fundamental,
I am always struggling with this: is_whatever(x) : This is my preference for boolean functions (except natural cases like intersects, contains), because whatever(x) is often a good choice for a non boolean function. On the other hand the whatever(x) version is stl-style and also of course generally shorter. So is_disjoint would be my favorite but I could live with disjoint too. is_disjoint / disjoint could be completely abandoned in my view, because it has a negated meaning [disjoint == !intersects] the positive naming is always more intuitive. I made a google code search. intersects greatly outnumbers disjoint / is_disjoint. Do you find it a good idea to have / create a common picture of operators the more important is the quest for a really good, intuitive and systematic naming. I am in favor of that and I am willing to adapt. Cheers, Joachim
Hi Joachim,
Boost.Polygon(BP)/GTL also supports both, for union. Is it intentional that two operators are implemented for the same operation in these two libraries? And if so, why is that not done for the intersection (having synonym *= in BP).
(1) They are not (yet) producible in c++. We have to get by on a small set of them. So its unwise to waste them.
Yep
(2) operators are like semantical archetypes. Pretty early in school we make contact with =, <, +, - . They carry semantical invariants not only for mathematicians but for almost every educated human being. This is like a treasure that can be harnessed for those parts of generic libraries that we want to be maximally intuitive to use.
I understand but only if it is really intuitive for everyone. I've seen that you refer to segmentational fineness, coupled to operator>, which is for me not so intuitive ("x > y // means that x is_finer_than y"). I would state that a function with a describing term is often more easy to use and to interpret.
(3) While with += and |= I feel kind of coerced to assign the same semantics: + is the primary operator of combining object of some type, which is union (for sets) | is equivalently intuitive from the boolean view of set union a | b = { x : x in a || x in b}
I doubt that += is so intuitive in this case. Combined with a scalar, an interval [2,5) += 3 might intuitively go to [5,8), e.g. delayed by 3 minutes.. I like the symmetry of || and && for or/and and |= and &= for union and intersection, which are the or and and in set theory. Therefore, I would reserve the += for something else, because they are sparse, as you stated ;-). Or just don't use it. On the other hand, the difference is -=, so subtracting a set, and a union is +=, so adding a set, yes it is intuitive and symmetric... We need the operators U and U/upsidedown here to make it mathematical... ;-)
(4) With *= and &= this is different. * is in my view not an "archetype" for intersection.
I do agree with that. Besides that, the *= might stand for the Cartesian product as well.
(5) Yet, the most important reason is that I'd like to save * for scaling: 2 * {1,2} = {2,4} because this *is* IMO an archetypal meaning for * (6) In the more freaky parts of my semancial studies on interval_maps I found that specific instantiations e.g.: interval_map<int,double,total_absorber> are models of a concept 'indefinite vector' of a vector space, if a scalar multiplication was added. To be able to add this basic operation later I wanted to save * and *= .
Yes, 2* is inuitively convenient for scaling, but is scaling of intervals an often occuring need?. In the 2/3 D case we have transformations which scale,translate and rotate, here you probably have scale and translate, and I think I would not attach an operator on it, or make it consequent with translation... There is another function as well, not being discussed yet, what we in GIS call the "buffer". So {1,2} buffered by 0.1 would be {0.9,2.1}. Is that supported by ITL and do you think it needs an operator, and which? It is different than scaling because an interval set {1,2},{3,4} would be {0.9,2.1},{2.9,4.1}. For intervals useful if you need 5 minutes extra in all schedules on both sides.
I am always struggling with this: is_whatever(x) : This is my preference for boolean functions (except natural cases like intersects, contains), because whatever(x) is often a good choice for a non boolean function. On the other hand the whatever(x) version is stl-style and also of course generally shorter.
So why actually is "contains" a natural case and "disjoint" is not? You are right that disjoint == !intersects and !disjoint is a sort of double negation. But that is the same for !is_disjoint...
Do you find it a good idea to have / create a common picture of operators
and functions and if yes, is it still possible to adapt?
The more fundamental concepts are, and sets / maps are *very* fundamental,
the more important is the quest for a really good, intuitive and systematic naming. I am in favor of that and I am willing to adapt.
OK. So we have fundamental concepts for at least operators, and for boolean operators which overlap these libraries... Regards, Barend
Hi Joachim,
(2) operators are like semantical archetypes. Pretty early in school we
make contact with =, <, +, - . They carry semantical invariants not only for mathematicians but for almost every educated human being. This is like a treasure that can be harnessed for those parts of generic libraries that we want to be maximally intuitive to use.
I understand but only if it is really intuitive for everyone. I've seen that you refer to segmentational fineness, coupled to operator>, which is for me not so intuitive ("x > y // means that x is_finer_than y"). I would state that a function with a describing term is often more easy to use and to interpret.
The example is a little specific. The operator > is induced by the fact
2010/2/27 Barend Gehrels <barend@geodan.nl> that segmentational_fineness<T>::value yields an integer constant, which is larger if the type T is finer. Looking at the stl I think operator < is a good example for a very pervasive operator with a consistent interpretation across a lot of class and function templates. It is also generally expected as default for compare functor types. I would say that operator < in the stl is the classical example for a consistent and pervasive usage of an operator. (3) While with += and |= I feel kind of coerced to assign the same
semantics: + is the primary operator of combining object of some type, which is union (for sets) | is equivalently intuitive from the boolean view of set union a | b = { x : x in a || x in b}
I doubt that += is so intuitive in this case. Combined with a scalar, an
interval [2,5) += 3 might intuitively go to [5,8), e.g. delayed by 3 minutes.. I like the symmetry of || and && for or/and and |= and &= for union and intersection, which are the or and and in set theory. Therefore, I would reserve the += for something else, because they are sparse, as you stated ;-). Or just don't use it.
... hmm ... I have thought about that as well. [2,5) += 3 starts to introduce interval arithmetics. Although this could be pretty handy I decided to leave interval arithmetics out. The reason is, that the domain_type of intervals and interval containers does not need to be a number. It only requires a strict weak ordering. So arithmetic operations would work for a subset of all possible domain_types only.
For numeric domain_types it is obviously interesting to be able to perform arithmetic operations and to reserve += for that. To keep things simple I ruled that out for the time being. But yes, this is an argument to think about *saving* operator += . But there are more problems. If we defined += for arithmetic addition (e.g. on interval_sets), we would want to use -= for subtraction, which is already occupied for set difference :(
On the other hand, the difference is -=, so subtracting a set, and a union is +=, so adding a set, yes it is intuitive and symmetric... We need the operators U and U/upsidedown here to make it mathematical... ;-)
(4) With *= and &= this is different. * is in my view not an "archetype"
for intersection.
I do agree with that. Besides that, the *= might stand for the Cartesian product as well.
Right, also a good candidate.
(5) Yet, the most important reason is that I'd like to save * for scaling:
2 * {1,2} = {2,4} because this *is* IMO an archetypal meaning for * (6) In the more freaky parts of my semancial studies on interval_maps I found that specific instantiations e.g.: interval_map<int,double,total_absorber> are models of a concept 'indefinite vector' of a vector space, if a scalar multiplication was added. To be able to add this basic operation later I wanted to save * and *= .
Yes, 2* is inuitively convenient for scaling, but is scaling of intervals an often occuring need?.
Yes, we had use cases, where we had intervals from of different time granularity. So we had to scale them to a common time scale. For the boost submission I took that function out of the ITL. But it has its applications.
In the 2/3 D case we have transformations which scale,translate and rotate, here you probably have scale and translate, and I think I would not attach an operator on it, or make it consequent with translation...
There is another function as well, not being discussed yet, what we in GIS call the "buffer". So {1,2} buffered by 0.1 would be {0.9,2.1}. Is that supported by ITL and do you think it needs an operator, and which? It is different than scaling because an interval set {1,2},{3,4} would be {0.9,2.1},{2.9,4.1}. For intervals useful if you need 5 minutes extra in all schedules on both sides.
Seems not terribly essential to me but may be useful to add.
I am always struggling with this: is_whatever(x) : This is my preference for boolean functions (except natural cases like intersects, contains), because whatever(x) is often a good choice for a non boolean function. On the other hand the whatever(x) version is stl-style and also of course generally shorter.
So why actually is "contains" a natural case and "disjoint" is not?
(1) My glass contains beer.
(2) Your glass disjoint from mine. =)
Do you find it a good idea to have / create a common picture of operators
and functions and if yes, is it still possible to adapt?
The more fundamental concepts are, and sets / maps are *very* fundamental,
the more important is the quest for a really good, intuitive and systematic naming. I am in favor of that and I am willing to adapt.
OK. So we have fundamental concepts for at least operators, and for boolean
operators which overlap these libraries...
In a way all of boost is kind of an effort to converge on common designs, concepts and notations. I like that =)
Best, Joachim
(1) My glass contains beer. (2) Your glass disjoint from mine. =)
:-) I see now. I'm so used to it that I forgot that these things are indeed illogical named. However, for me, they are the standard... E.g. http://msdn.microsoft.com/en-us/library/bb933960.aspx http://postgis.refractions.net/documentation/manual-1.5/reference.html#Spati... I understand that if a standard is not so applicable to you (geometry vs interval) and not so logical in some cases, you will not be so glad to follow it... Regards, Barend
2010/2/28 Barend Gehrels <barend@geodan.nl>
(1) My glass contains beer. (2) Your glass disjoint from mine. =)
:-) I see now. I'm so used to it that I forgot that these things are indeed illogical named.
I would not say illogical, is_disjoint(x) is just a little closer to the
However, for me, they are the standard... E.g. http://msdn.microsoft.com/en-us/library/bb933960.aspx
http://postgis.refractions.net/documentation/manual-1.5/reference.html#Spati...
I understand that if a standard is not so applicable to you (geometry vs interval) and not so logical in some cases, you will not be so glad to follow it...
... in order to be compliant with a well established standard, I have no
usage in natural language. problems to scarify some little is_ prefixes ;) Regards, Joachim
"consider trying to store the lifespans of people in a genealogy program: recording a few thousand people living over a few hundred years would approach the worse-case space complexity and need megabytes of storage" This was part of my motivation to do project 1 above, because these few
Hi List, Hartmut, Joachim, This is my review of the Interval Template Library (ITL). YES, I vote +1, this library should be accepted into Boost. It is very very useful. During my review my enthousiasm was only growing. Even if there was a thing confusing on the operators (for me). Yes, I can use this library in real life and it will solve problems for me. 1) WHAT I DID For this review I've done three projects of which two are related to my day-to-day or hobby programming efforts. a) The first project is related to genealogy. I took up the idea of Phil and generated an interval map of livetimes of all persons in my genealogical database. This database contains ~3000 persons. Many of the persons are still alive. ITL contains a right open interval but that denotes the right-hand-side excluding, while I need an interval that is unlimited at one side. Of course I could workaround using 9999 as year of death. An additional problem is that for many people death date is unknown. I don't expect ITL to handle fuzzy intervals so I ignore this. Everything went smoothly. There was not any delay noticable (see below). I started with a provided example but changed some things, such as using a const_iterator and const references, not yet using the documentation, and everything is standard and works as expected. The function I drafted is below. b) The second project is related to planning and "leave requests". I've implemented this some years ago and remember that it got quite complex, with weekends, national holiday days and people working sometimes 40 hours a week, but sometimes not on Friday afternoon etc. So I tried if Boost.Interval would have simplified my live there. And yes, it would have done for sure! Starting with the manpower example I made adaptions, actually only simplifying it, plus subtracting days-of-per-week, until I had what I wanted. The whole routine is in one screen now and definitely logic and simple. The drafted functions are below. c) I did some small other studies as well, especially on the map operators, and to draft an alternative "intro for dummies"... Of this, pieces are here in this review. Let me repeat that I found this library VERY USEFUL and that I'm surprised that there are not many reviews yet. 2) DOCUMENTATION The documentation is extensive and good. I've some small remarks about the introduction. When I started I was confused by the definitions of interval_set and interval_map, and when to use them. It might be explained a little better for people not having worked with intervals before, probably with some sample code and images. The documentation contains, at the start: "It means that we can use an interval_set or interval_map like a set or map of elements. It exposes the same functions." and then gives the example " mySet.contains(42)". But contains is NOT an method of std::set, but YES from interval_set. This was confusing. I then expected a sample for the map below but not there... Furthermore, that threelined set-sample means that the *interval* 42-42 is inserted, which was also not clear to me at first sight... I would change that section. I would suggest something like this: void intro_sets_for_dummies() { namespace itl = boost::itl; // STANDARD std::set works with values std::set<int> std_set; std_set.insert(3); std_set.insert(7); BOOST_FOREACH(int const& value, std_set) { std::cout << " " << value; } //std::cout << " " << (std_set.contains(3) ? "YES" : "NO"); //not implemented in std::set std::cout << std::endl; // BOOST.ITL itl::interval_set works with intervals instead of values itl::interval_set<int> itl_set; // Interval's of integer, e.g. seconds or years itl_set.insert(itl::interval<int>(3,5)); itl_set.insert(itl::interval<int>(4,8)); // Overlap with previous is detected automatically itl_set.insert(1); // Interval of (1,1) BOOST_FOREACH(itl::interval<int> const& interval, itl_set) { std::cout << " " << interval.first() << ".." << interval.last(); } std::cout << " " << (itl_set.contains(3) ? "YES" : "NO") << std::endl; // 1..1 3..8 YES } The same for map. The itl::interval_map is REALLY very useful. My suggestion: void intro_maps_for_dummies() { namespace itl = boost::itl; // STANDARD std::map std::map<int, int> std_map; std_map[3] = 4; std_map[7] = 8; for(std::map<int,int>::const_iterator it = std_map.begin(); it != std_map.end(); ++it) { std::cout << " " << it->first << ": " << it->second; } std::cout << std::endl; // BOOST.ITL itl::interval_map itl::interval_map<int, int> itl_map; itl_map += std::make_pair(itl::interval<int>(3,5), 4); // add 4 to [3,5] itl_map += std::make_pair(itl::interval<int>(4,8), 8); // add 8 to [4,8] -> will generate 3 intervals itl_map -= std::make_pair(itl::interval<int>(5,5), 2); // subtract 2 -> will split another interval for(itl::interval_map<int, int>::const_iterator it = itl_map.begin(); it != itl_map.end(); ++it) { itl::interval<int> const& interval = it->first; std::cout << " " << interval.first() << ".." << interval.last() << ": " << it->second; } std::cout << std::endl; // OUTPUT: 3..3: 4 4..4: 12 5..5: 10 6..8: 8 } This would give me a clearer picture how it works. At the same time I now realize that during our discussion on +=, -=, |= , I didn't realize enough that += really does mathematics behind the screens. So it adds values where to the map on the specified interval, it subtracts values from the map on the specified interval. This goes beyond "set theoretic operations", "set union" and especially "set difference". See below for more on this. I realize that a similar sample is there in the documentation, and that this principle, "aggregate on overlap" is well explained there. However, a sample with the numeric values is (for me) somewhat more clear than the given sample with names which are added to a set; the sample of interval_map with itl::set probably does too much at a time... But let me repeat that the overall documentation is impressive and complete! 3) PERFORMANCE Phil claimed that: thousand people over a few hundred years is exactly what I have. Boost.Itl calculates and reports the livespans in 0.031 seconds. So, measured in time, no problem at all. I compared it with another implementation which run in 0.032 seconds, so the same. I will not say that it cannot be enhanced somehow or whatever, I didn't study it in depth, I would only say: the library is well performing, also if the input set grows larger. It should not be rejected for the assumption that it could have been built otherwise. Besides that, Boost.Itl does more than normal intervals: the interval_map associates values to intervals. 4) SOME NOTES - the samples do not use it, but sets and maps are working with Boost.Range - sets are also working with BOOST_FOREACH - in the code samples, "using" is used in many places (or everywhere). While many Boost libraries do this, I would say that this is unclear for users visiting for the first time. What is that "date"? Is it a gregorian date, or an ITL date? So I would say something like namespace gr = boost::gregorian; namespace itl = boost::itl; and use this like "gr::date" and "itl::interval<...>" everywhere, such that the origin of all those terms is immediately clear. As said, this is not criticism on Boost.ITL, it is a hint for enhancing Boost docs for first time users. I'm often struggling with the origin of terms especially if two libraries are used together. I realize we've done this ourselves in Geometry as well and I think changing it would make it more clear. 5) OPERATORS and FUNCTIONS During the review period I had a discussion on the list with Joachim about the operators and the naming of functions. However, I thought that the += and |= were both doing a pure union, but it appears that they are doing a union PLUS a (sometimes mathematic) addition. So my current opinion is: For sets (o.a. interval_set), the following operators are appropriate, as also used in Boost.dynamic_bitset: &= for intersection |= for union ^= for symmetric difference -= for difference So this is how it is implemented but I would remove += as a synonym for |= For interval_map, it is currently much less clear to me now. The operators do two things at the same time, which is confusing me. Let's see the following code pieces: 1| itl::interval_map<int, int> map1, map2; 2| map1 += std::make_pair(itl::interval<int>(3,5), 4); 3| map2 += std::make_pair(itl::interval<int>(4,6), 5); 4| map1 |= map2; This gives: 3..3: 4 4..5: 9 6..6: 5. So it is a set-theoretic union, PLUS mathematical addition. Aggregation on overlap. It IS very useful, but it does two things at the same time, and should be implemented and described carefully. Changing the last line to intersection: 4| map1 &= map2 gives 4..5: 9, so it is a set-theoretic intersection on intervals, PLUS mathematical addition. I still agree. But now: 4| map1 -= map2 gives 3..3: 4 4..5: -1 This is actually unexpected. It is not set-difference, because that would leave only 3..3 in the set and remove 4..5 completely. So what it actually does is subtracting 5 from all there was before in map1, ONLY mathematical operation (minus), no set-theory here... The documentation describes it like this: "Subtraction on Maps implements a map difference function similar to set difference", and it forwards to a link with more info about this ("While addition and subtraction on Sets are implemented as set union and set difference,"), I still don't agree, it is not set difference here. To be complete: 4| map1 ^= map2 gives 3..3: 4 6..6: 5. So yes, this IS the set-symmetric difference and (by nature of that) does or does not mathematical addtion, that is not important here. Therefore I find the interval_map operators still confusing, even more confusing than before. Are they doing mathematics or set-theory? So I would suggest something like this: 4| map1 |= something(map2, std::plus); to make it more explicit. This is the set-theoretic union where on all overlaps the two sets are added, and 4| map1 |= something(map2, std::minus); where the two sets are unioned, and the values of map2 are subtracted from map1. This is slightly different from the current -= implementation. 4| map1 |= something(map2, std::multiplies); item, but values are multiplied And then the same for &= (intersection), -= (set theoretic difference). Then ^= probably need no policy because it always handled the intervals which are not common, an operator is not applicable here. There are combine functors described (I saw later), but they are used different (I think) than this suggestion. This would make it less confusing AND probably would give it more functionality, because the *= is currently not implemented (and might be reserved for scaling). This was map + map. The same applies for the operator-= on map, interval, so: 1| itl::interval_map<int, int> map; 2| map += std::make_pair(itl::interval<int>(3,5), 4); 3| map -= std::make_pair(itl::interval<int>(4,6), 3); result in 3..3: 4 4..5: 1 This could actually be stated clearer by using the std::map approach, on intervals, I tried it intuitively but it does not compile: map[itl::interval<int>(3,5)]+= 4; map[itl::interval<int>(4,6)]-= 3; I would not have any problems with this, and I would expect still doing aggregate on overlap behind the scenes, and not set-theory, resulting in: 3..3: 4 4..5: 1 6..6: -3 6) STANDARD QUESTIONS
- What is your evaluation of the design?
The library is well designed. The comments above were only on one detail.
- What is your evaluation of the implementation?
I had only a glance to the implementation. It is clear, nice short functions everywhere, and well documented. It is build on top of the std::set and std::map, which is reported to be problematic, but I don't think it is. My test runs very fast.
- What is your evaluation of the documentation?
Impressive and quite complete. The introduction might add a section or tutorial for real-starters
- What is your evaluation of the potential usefulness of the library?
Very useful. I mentioned two projects where the library would have helped me if it had been into Boost earlier, and I'm considering rewriting them such that the problems make use of the library, and simplify them in that way.
- Did you try to use the library? With what compiler? Did you have any problems?
I used it using Visual C++ 2008 Express Edition and I didn't have any problems.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
About 10 hours spread over three days.
- Are you knowledgeable about the problem domain?
Finally, thanks to Joachim for developing and submitting this excellent library, and to Hartmut for managing this review. Regards, Barend Gehrels, Amsterdam Ad a: void CreateTimeline(std::ofstream& stream) { namespace itl = boost::itl; typedef itl::interval_map<int, int> map; map livetimes; for (TGenealogyVertexIterator vi = vertices(m_graph).first; vi != vertices(m_graph).second; ++vi) { CGenealogyVertexProperty p = GetProperty(*vi); if (p.indi.type == TYPE_PERSON && p.indi.birth.date.hasdate) { int death_date = p.indi.death.date.hasdate ? p.indi.death.date.year : 9999; livetimes += std::make_pair(itl::interval<int>(p.indi.birth.date.year, death_date), 1); } } stream << "LIVETIMES: " << std::endl; for (map::const_iterator it = livetimes.begin(); it != livetimes.end(); ++it) { boost::itl::interval<int> const& when = it->first; stream << when.first() << " - " << when.upper() << " : " << it->second << std::endl; } } Ad b: void calculate_leave_request() { namespace gr = boost::gregorian; namespace itl = boost::itl; itl::interval<gr::date> scope ( gr::from_simple_string("2010-04-01"), gr::from_simple_string("2010-05-31") ); itl::interval_set<gr::date> weekends_plus_festival_days(scope); weekends_plus_festival_days -= weekends(scope); weekends_plus_festival_days -= gr::from_simple_string("2010-04-05"); // Eastern weekends_plus_festival_days -= gr::from_simple_string("2010-04-30"); // Queensday weekends_plus_festival_days -= gr::from_simple_string("2010-05-13"); // Ascension day weekends_plus_festival_days -= gr::from_simple_string("2010-05-24"); // Whitsun itl::interval_map<gr::date, double> request_in_hours; // Add 8 hour per day request_in_hours += std::make_pair(scope, 8.0); request_in_hours &= weekends_plus_festival_days; // Subtract 4 hour for all Fridays { gr::date date = gr::next_weekday(scope.first(), gr::greg_weekday(gr::Friday)); gr::week_iterator it(date); while(it <= scope.last()) { itl::interval<gr::date> scope(*it, *it); request_in_hours -= std::make_pair(scope, 4.0); ++it; } } report("Request", scope, request_in_hours); } // where report is: template <typename Scope, typename Map> double report(std::string const& caption, Scope const& scope, Map const& map) { namespace itl = boost::itl; namespace gr = boost::gregorian; std::cout << caption << ": " << scope.first() << " - " << scope.last() << std::endl; double hours = 0; for(typename boost::range_iterator<Map const>::type it = boost::begin(map); it != boost::end(map); ++it) { itl::interval<gr::date> const& interval = it->first; // Add 1, because Boost.Date counts [2010-05-01 ... 2010-05-02 as one day] int days = 1 + gr::date_period(interval.first(), interval.last()).length().days(); std::cout << interval.first() << " - " << interval.last() << " -> " << days << " * " << it->second << std::endl; hours += days * it->second; } std::cout << "Total hours: " << hours << std::endl; return hours; }
5) OPERATORS and FUNCTIONS During the review period I had a discussion on the list with Joachim about the operators and the naming of functions. However, I thought that the += and |= were both doing a pure union, but it appears that they are doing a union PLUS a (sometimes mathematic) addition. So my current opinion is:
For sets (o.a. interval_set), the following operators are appropriate, as also used in Boost.dynamic_bitset: &= for intersection |= for union ^= for symmetric difference -= for difference So this is how it is implemented but I would remove += as a synonym for |=
For interval_map, it is currently much less clear to me now. The operators do two things at the same time, which is confusing me. ...
I won't be able to review ITL, but I would like to comment that I think that this issue of operators needs to be resolved before ITL is included in Boost.
Hi Daniel,
For sets (o.a. interval_set), the following operators are appropriate, as also used in Boost.dynamic_bitset: &= for intersection |= for union ^= for symmetric difference -= for difference So this is how it is implemented but I would remove += as a synonym for |=
For interval_map, it is currently much less clear to me now. The operators do two things at the same time, which is confusing me. ...
I won't be able to review ITL, but I would like to comment that I think that this issue of operators needs to be resolved before ITL is included in Boost.
Since I wrote that above, I'll react on this. I didn't intend such a reaction in my review. The ITL library is excellent, the thing (and the only thing I found) which was not logical (in my opinion, maybe Joachim will explain it all) is that the -= operator is not the set theoretic difference but the mathematical subtraction of values. I really don't think that this is a major concern. Regards, Barend
Since I wrote that above, I'll react on this. I didn't intend such a reaction in my review. The ITL library is excellent, the thing (and the only thing I found) which was not logical (in my opinion, maybe Joachim will explain it all) is that the -= operator is not the set theoretic difference but the mathematical subtraction of values. I really don't think that this is a major concern.
I agree. After I hit the send button, I wished that I would have said something like: "I think that this issue of operators needs to be resolved before ITL is included in Boost, but this minor issue should not solely prevent its inclusion." My main thought was that these issues with the exact definitions of operators should be ironed out as early as possible so that users will not experience backward-compatibility problems that may be hard to troubleshoot.
2010/2/28 Barend Gehrels <barend@geodan.nl>
Hi Daniel,
For sets (o.a. interval_set), the following operators are appropriate,
as also used in Boost.dynamic_bitset: &= for intersection |= for union ^= for symmetric difference -= for difference So this is how it is implemented but I would remove += as a synonym for |=
For interval_map, it is currently much less clear to me now. The operators do two things at the same time, which is confusing me. ...
I won't be able to review ITL, but I would like to comment that I think that this issue of operators needs to be resolved before ITL is included in Boost.
Since I wrote that above, I'll react on this. I didn't intend such a reaction in my review. The ITL library is excellent, the thing (and the only thing I found) which was not logical (in my opinion, maybe Joachim will explain it all) is that the -= operator is not the set theoretic difference but the mathematical subtraction of values. I really don't think that this is a major concern.
actually the semantics of this generalized addition, subtraction and intersection (symmetric difference is induced), is at the core of the whole library. I will happily take the opportunity to explain .... stay tuned ;-) Joachim
Barend Gehrels wrote:
"consider trying to store the lifespans of people in a genealogy program: recording a few thousand people living over a few hundred years would approach the worse-case space complexity and need megabytes of storage" This was part of my motivation to do project 1 above, because these few
Phil claimed that: thousand people over a few hundred years is exactly what I have. Boost.Itl calculates and reports the livespans in 0.031 seconds. So, measured in time, no problem at all. I compared it with another implementation which run in 0.032 seconds, so the same. I will not say that it cannot be enhanced somehow or whatever, I didn't study it in depth, I would only say: the library is well performing, also if the input set grows larger. It should not be rejected for the assumption that it could have been built otherwise.
Barend, there are a couple of problems with your test. The space complexity is only quadratic in the case where the map's value types for overlapping intervals are all stored. Looking at your example code:
typedef itl::interval_map<int, int> map; map livetimes; ... livetimes += std::make_pair(itl::interval<int>(p.indi.birth.date.year, death_date), 1);
You are just storing the number of people living on any particular date. Try changing your code to record all of the names, e.g. something like: typedef itl::interval_map<int, string> map; map livetimes; .. livetimes += std::make_pair(itl::interval<int>(p.indi.birth.date.year, death_date), p.name); More fundamentally, you are taking my observation that it has poor space complexity and then measuring the execution time. This is obviously flawed, as time and space complexity are different things. Phil.
Barend, there are a couple of problems with your test.
The space complexity is only quadratic in the case where the map's value types for overlapping intervals are all stored. OK, I see. But you didn't mention that in your review. So yes, I understand, if you store names to the intervals as sets, and split an interval each time, you will get a fragmented map of fragmented sets. However, I did this at start, so read on. Looking at your example code:
typedef itl::interval_map<int, int> map; map livetimes; ... livetimes += std::make_pair(itl::interval<int>(p.indi.birth.date.year, death_date), 1);
You are just storing the number of people living on any particular date. Try changing your code to record all of the names, e.g. something like: Yes, I did this in my review. The first version of my program listed
Hi Phil, like this: typedef boost::itl::set<std::string> itl_set_string; typedef boost::itl::interval_map<int, itl_set_string> itl_map; (...) itl_set_string person; person.insert(p.indi.name); int death_date = p.indi.death.date.hasdate ? p.indi.death.date.year : 9999; livetimes.add(std::make_pair( boost::itl::interval<int>::rightopen(p.indi.birth.date.year, death_date), person)); (...) itl_set_string const& who = it->second; stream << when.first() << " - " << when.upper() << " : " << who.size() << std::endl; But I then realized that this did too much, because I only wanted to know how much persons are alive in what period. So I did a second implementation and timing. Also this first test did have no noticeable delay. It is subsecond, and I did also write the names of all these persons in this test which should not be timed, so it is not problematic.
typedef itl::interval_map<int, string> map; map livetimes; .. livetimes += std::make_pair(itl::interval<int>(p.indi.birth.date.year, death_date), p.name);
More fundamentally, you are taking my observation that it has poor space complexity and then measuring the execution time. This is obviously flawed, as time and space complexity are different things.
but to do so it needs worst-case O(N2) space and I think it needs O(N2 log N) time to build that structure. so I measured time and, admitted, I didn't measure space. I only observe
You mentioned the time as well: that it runs fast in the example you are giving. Regards, Barend
Barend Gehrels wrote:
You are just storing the number of people living on any particular date. Try changing your code to record all of the names, e.g. something like: Yes, I did this in my review. The first version of my program listed like this: typedef boost::itl::set<std::string> itl_set_string; typedef boost::itl::interval_map<int, itl_set_string> itl_map; (...) itl_set_string person; person.insert(p.indi.name);
int death_date = p.indi.death.date.hasdate ? p.indi.death.date.year : 9999; livetimes.add(std::make_pair( boost::itl::interval<int>::rightopen(p.indi.birth.date.year, death_date), person)); (...) itl_set_string const& who = it->second; stream << when.first() << " - " << when.upper() << " : " << who.size() << std::endl;
Also this first test did have no noticeable delay. It is subsecond, and I did also write the names of all these persons in this test which should not be timed, so it is not problematic.
Because you're using only the years of birth and death, this is limited to O(N_YEARS * N_PEOPLE). With N_YEARS ~ hundreds and N_PEOPLE ~ thousands, I can believe this would run in a short time (modern computers are fast). If you have time, I would be interested to know how the performance changes if you use a higher-resolution date type, e.g. integer number of days. Regards, Phil.
Hi Barend, thank you again for all the effort and diligence that you invested to investigate my library :) I am going to address the issues you raised piecemeal in a sequence of importance that I consider for them. Generalized addition, subtraction and intersection operators are at the heart of the library. So I'll begin here: 5) OPERATORS and FUNCTIONS
During the review period I had a discussion on the list with Joachim about the operators and the naming of functions. However, I thought that the += and |= were both doing a pure union, but it appears that they are doing a union PLUS a (sometimes mathematic) addition.
this is correct. As I have outlined in the documentation, all Sets and Maps of the ITL are Addable and Subtractable. Addability is more fundamental than Subtractability. Addability in the sense I have in mind could also be called Combinability: Some kind of a primary possibility to combine values of a type T: string, sequence : concatenation numbers : addition sets : union maps : ? ... Since a map is a set of pairs we could use set union. But this is NOT done in the ITL. The ITL defines a generalized addition, based on a union operation, that propagates operator + to combine associated values, if the inserted intervals overlap (or inserted elements collide). By default we propagate operator + to combine associated values. This yields to concatenation, if lists, strings, etc. are associated addition, if numbers are associated union, if sets are associated generalized union, if maps are associated. This is [reason 1], why union on sets and generalized union on maps must be expressed to operator +, += See also: http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/con... So again, this design is based on the assumption, that, for a combinable type T, we can identify a primary operation for the combination of it's values and for this primary operations we expect operator + . This is crucial for the combination of maps in the ITL. Maps propagate this primary combine function. And as default we always use operator + . Since associated type can be sets, interval_sets and, yes, maps and interval_maps : We must assign operator + to the primary way of combining sets and maps in the ITL. Because, by introducing a generalized addition on maps, we start to propagate the combination operator. The best choice for this? Clearly the archetypal operator that is there for the combination of *something*: operator + . This way we can, out of the box, work with things like (Phil, please close your eyes for a monent ;) interval_map<int, interval_map<int, string> > m1, m2; // fill ... m1 += m2; // performing aggreations on interval_map<int, string> // via += on interval_map<int,string> that in turn calls // += on strings. [...]
For interval_map, it is currently much less clear to me now. The operators do two things at the same time, which is confusing me.
Let's see the following code pieces: 1| itl::interval_map<int, int> map1, map2; 2| map1 += std::make_pair(itl::interval<int>(3,5), 4); 3| map2 += std::make_pair(itl::interval<int>(4,6), 5); 4| map1 |= map2; This gives: 3..3: 4 4..5: 9 6..6: 5. So it is a set-theoretic union, PLUS mathematical addition. Aggregation on overlap. It IS very useful, but it does two things at the same time, and should be implemented and described carefully.
Changing the last line to intersection: 4| map1 &= map2 gives 4..5: 9, so it is a set-theoretic intersection on intervals, PLUS mathematical addition. I still agree.
As for generalized addition on maps, where operator + is propagated, all itl::Maps propagate the & operator to combine associated values, if the associated values are intersectable. For numeric codomain_types this is not so. Here the generalizes intersection degenerated to an addition on the intersection of the domain values of the intersected values. This is what happens here.
But now: 4| map1 -= map2 gives 3..3: 4 4..5: -1 This is actually unexpected. It is not set-difference, because that would leave only 3..3 in the set and remove 4..5 completely. So what it actually does is subtracting 5 from all there was before in map1, ONLY mathematical operation (minus), no set-theory here... The documentation describes it like this: "Subtraction on Maps implements a map difference function similar to set difference",
this citation is incomplete it continues: "If, on subtraction of an element value pair (k,v) it's key k is in the map already, the subtraction function is propagated to the associated value. On the associated value an aggregation is performed, that reverses the effect of the corresponding addition function." Now for the interpretation of this subtraction operation: {[3 .. 5]->4} - { [4 .. 6]->5} it leaves [3..3]->4 on the overlap it subtracts : [4..5]->(4-5), which is consistent with the definition the part of map2 that has no match in map1 is not subtracted (kind of set theoretic ;-)
To be complete: 4| map1 ^= map2 gives 3..3: 4 6..6: 5. So yes, this IS the set-symmetric difference and (by nature of that) does or does not mathematical addtion, that is not important here.
Therefore I find the interval_map operators still confusing, even more confusing than before. Are they doing mathematics or set-theory?
Well set theory is a field of math. The distinction is little helpful. The generalized map operations are defined on the bases of the set theoretic operations and by propagation of the respective operation, for the case of overlaps. Their properties are formally defined by sets of laws. More about laws later.
So I would suggest something like this: 4| map1 |= something(map2, std::plus); to make it more explicit. This is the set-theoretic union where on all overlaps the two sets are added, and 4| map1 |= something(map2, std::minus); where the two sets are unioned, and the values of map2 are subtracted from map1. This is slightly different from the current -= implementation.
4| map1 |= something(map2, std::multiplies); item, but values are multiplied
And then the same for &= (intersection), -= (set theoretic difference). Then ^= probably need no policy because it always handled the intervals which are not common, an operator is not applicable here. There are combine functors described (I saw later), but they are used different (I think) than this suggestion.
Defining the operations like that brings a loss of simplicity, introduces complexity and opens a Pandorra's box of possible errors. The aggregation operations in itl::Maps are properties of the type and are not to be changed at runtime. As long as I work with this I found not a single use case where
yes, and it does not account for the fact that the result of set_difference does not contain the part of map2, which is not contained in map1. W.r.t. to your example: [6,6]->-5 would be in the result. this seems to make sense. But it opens up the possibility of spoiling aggregation result by accidently using inconsistent operations for aggregations.
This would make it less confusing AND probably would give it more functionality, because the *= is currently not implemented (and might be reserved for scaling).
This was map + map. The same applies for the operator-= on map, interval, so: 1| itl::interval_map<int, int> map; 2| map += std::make_pair(itl::interval<int>(3,5), 4); 3| map -= std::make_pair(itl::interval<int>(4,6), 3); result in 3..3: 4 4..5: 1
This could actually be stated clearer by using the std::map approach, on intervals, I tried it intuitively but it does not compile: map[itl::interval<int>(3,5)]+= 4; map[itl::interval<int>(4,6)]-= 3; I would not have any problems with this, and I would expect still doing aggregate on overlap behind the scenes, and not set-theory, resulting in: 3..3: 4 4..5: 1 6..6: -3
try this:
itl::interval_map<int, int, total_absorber> map; map += std::make_pair(itl::interval<int>(3,5), 4); map -= std::make_pair(itl::interval<int>(4,6), 3); cout << map << endl; So much for today ;) More tomorrow Good night from stormy Germany, Joachim
----- Original Message ----- From: "Joachim Faulhaber" <afojgo@googlemail.com> To: <boost@lists.boost.org> Sent: Monday, March 01, 2010 12:23 AM Subject: Re: [boost] [Review] ITL review starts today, February 18th
Hi Barend,
thank you again for all the effort and diligence that you invested to investigate my library :)
I am going to address the issues you raised piecemeal in a sequence of importance that I consider for them. Generalized addition, subtraction and intersection operators are at the heart of the library. So I'll begin here:
5) OPERATORS and FUNCTIONS
During the review period I had a discussion on the list with Joachim about the operators and the naming of functions. However, I thought that the += and |= were both doing a pure union, but it appears that they are doing a union PLUS a (sometimes mathematic) addition.
this is correct.
As I have outlined in the documentation, all Sets and Maps of the ITL are Addable and Subtractable. Addability is more fundamental than Subtractability. Addability in the sense I have in mind could also be called Combinability: Some kind of a primary possibility to combine values of a type T:
string, sequence : concatenation numbers : addition sets : union maps : ? ... Since a map is a set of pairs we could use set union. But this is NOT done in the ITL. The ITL defines a generalized addition, based on a union operation, that propagates operator + to combine associated values, if the inserted intervals overlap (or inserted elements collide).
By default we propagate operator + to combine associated values. This yields to concatenation, if lists, strings, etc. are associated addition, if numbers are associated union, if sets are associated generalized union, if maps are associated. This is [reason 1], why union on sets and generalized union on maps must be expressed to operator +, +=
From the examples, the single type that supports the operators + and += are numbers and strings. Maybe it is not a good idea to use the operators for the library, but just clear names.
See also: http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/con...
So again, this design is based on the assumption, that, for a combinable type T, we can identify a primary operation for the combination of it's values and for this primary operations we expect operator + . This is crucial for the combination of maps in the ITL. Maps propagate this primary combine function. And as default we always use operator + . Since associated type can be sets, interval_sets and, yes, maps and interval_maps : We must assign operator + to the primary way of combining sets and maps in the ITL. Because, by introducing a generalized addition on maps, we start to propagate the combination operator. The best choice for this? Clearly the archetypal operator that is there for the combination of *something*: operator + .
Have you think about adding the Combiner Trait template parameter not to the container class, but to the container operation (add, substract, ...)? Of course this eliminates the use of operators + +=. but IMO is clearer, you add a new element to a map if not ovelap, otherwise the operator use the combiner on the overlaping interval. for example if I have {[2,4)->5, [6,7)->10, [12, 15)->0} adding [1, 10)->1) could result in {[1, 10)->1, [12, 15)->0)} if the combiner gives the new value for the overlaping intervals. Best, Vicente Best, Vicente
Hi Vicente, 2010/3/1 vicente.botet <vicente.botet@wanadoo.fr>
----- Original Message ----- From: "Joachim Faulhaber" <afojgo@googlemail.com>
5) OPERATORS and FUNCTIONS
By default we propagate operator + to combine associated values. This yields to concatenation, if lists, strings, etc. are associated addition, if numbers are associated union, if sets are associated generalized union, if maps are associated. This is [reason 1], why union on sets and generalized union on maps must be expressed to operator +, +=
From the examples, the single type that supports the operators + and += are numbers and strings. Maybe it is not a good idea to use the operators for the library, but just clear names.
For this kind of fundamental semantics, I think using operators is desirable. This makes the code small, elegant and intuitive.
See also:
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/con...
So again, this design is based on the assumption, that, for a combinable type T, we can identify a primary operation for the combination of it's values and for this primary operations we expect operator + . This is crucial for the combination of maps in the ITL. Maps propagate this
primary
combine function. And as default we always use operator + . Since associated type can be sets, interval_sets and, yes, maps and interval_maps : We must assign operator + to the primary way of combining sets and maps in the ITL. Because, by introducing a generalized addition on maps, we start to propagate the combination operator. The best choice for this? Clearly the archetypal operator that is there for the combination of *something*: operator + .
Have you think about adding the Combiner Trait template parameter not to the container class, but to the container operation (add, substract, ...)?
Yes, I have thought about this. There even are function templates x.add<Combine>(pair) and x.subtract<Combine>(pair). I chose to make them private, because I consider the Combine functor an invariant of the given instantiation of an itl::Map. It is similar to the handling of compare functors for an SortedAssociatedContainer. You can not dynamically change the sorting order at runtime by calling a find<MyOrdering>(key).
Of course this eliminates the use of operators + +=. but IMO is clearer, you add a new element to a map if not ovelap, otherwise the operator use the combiner on the overlaping interval.
for example if I have {[2,4)->5, [6,7)->10, [12, 15)->0}
adding [1, 10)->1) could result in {[1, 10)->1, [12, 15)->0)} if the combiner gives the new value for the overlaping intervals.
Similarly it seems not to make very much sense to change the way in which an interval_map aggregates dynamically. I haven't found use cases for that in years. Best, Joachim
Hi Joachim,
I am going to address the issues you raised piecemeal in a sequence of importance that I consider for them. Generalized addition, subtraction and intersection operators are at the heart of the library.
Thanks for your extensive answer. I think you made it quite clear, however at this moment I have no time to dive into it (back to normal work...). I hope to find some time later this week. Regards, Barend
Hi Joachim,
I am going to address the issues you raised piecemeal in a sequence of importance that I consider for them. Generalized addition, subtraction and intersection operators are at the heart of the library.
Thanks again for your long answer, a week ago. Unfortunately I did not have any time last week or this weekend to continue with this, nor with Phil his question on a variation of my timings. However, I think you addressed the things I mentioned in my comments clear enough. Regards, Barend
Hi Barend, sorry for the delay, I intended to reply on the various comments of your thorough review earlier, but since I know that you are pretty busy yourself, a little delay might be ok for you. 2010/2/28 Barend Gehrels <barend@geodan.nl>:
2) DOCUMENTATION The documentation is extensive and good. I've some small remarks about the introduction.
When I started I was confused by the definitions of interval_set and interval_map, and when to use them. It might be explained a little better for people not having worked with intervals before, probably with some sample code and images. The documentation contains, at the start:
"It means that we can use an interval_set or interval_map like a set or map of elements. It exposes the same functions."
and then gives the example " mySet.contains(42)". But contains is NOT an method of std::set, but YES from interval_set. This was confusing.
my view on sets here is not governed by std::sets but rather by the mathematical notion of a set or the itl::Set concept that is part of my documentation. In this view the "is element of" function is pretty fundamental and it is available for itl::interval_set and for itl::set as bool T::contains(const domain_type&); Let me put it this way: std::set : could be model of itl::Set, if operators were implemented itl::set : is model of itl::Set itl::interval_set : is model of itl::Set but implemented via intervals boost::dynamic_bitset : is almost model of itl::Set but implemented via arrays of machine words. There is a common semantic core of all of those. For interval_set and bitset, their implementation is not completely hidden. You can access some aspects of it because this may be useful. Which is the common interface, the fundamental aspect, that constitutes this semantic kernel? Would that signature contain find(x)? Would it contain contains(x)? Would it provide iterators? boost::dynamic_bitset does not implement find, it does not implement iterators. Would we therefore say it is not a set? Its signature does not provide contains(x) but it contains test(x), which IMO should be called contains(x). I think std::set is one implementation of Set but not THE set.
I then expected a sample for the map below but not there... Furthermore, that threelined set-sample means that the *interval* 42-42 is inserted,
since interval_set is basically a set (of elements) it should be irrelevant how mySet.insert(42); works internally.
which was also not clear to me at first sight...
which is intentional, because I did *not* want to emphasize on implementation but on abstraction here.
I would change that section. I would suggest something like this:
void intro_sets_for_dummies() { Â namespace itl = boost::itl;
 // STANDARD std::set works with values  std::set<int> std_set;  std_set.insert(3);  std_set.insert(7);  BOOST_FOREACH(int const& value, std_set)  {    std::cout << " " << value;  }  //std::cout << " " << (std_set.contains(3) ? "YES" : "NO"); //not implemented in std::set  std::cout << std::endl;
 // BOOST.ITL itl::interval_set works with intervals instead of values  itl::interval_set<int> itl_set; // Interval's of integer, e.g. seconds or years  itl_set.insert(itl::interval<int>(3,5));  itl_set.insert(itl::interval<int>(4,8)); // Overlap with previous is detected automatically  itl_set.insert(1); // Interval of (1,1)  BOOST_FOREACH(itl::interval<int> const& interval, itl_set)  {    std::cout << " " << interval.first() << ".." << interval.last();  }  std::cout << " " << (itl_set.contains(3) ? "YES" : "NO") << std::endl;  //  1..1 3..8 YES }
The same for map. The itl::interval_map is REALLY very useful. My suggestion: void intro_maps_for_dummies() { Â namespace itl = boost::itl;
 // STANDARD std::map  std::map<int, int> std_map;  std_map[3] = 4;  std_map[7] = 8;  for(std::map<int,int>::const_iterator it = std_map.begin(); it != std_map.end(); ++it)  {    std::cout << " " << it->first << ": " << it->second;  }  std::cout << std::endl;
 // BOOST.ITL itl::interval_map  itl::interval_map<int, int> itl_map;  itl_map += std::make_pair(itl::interval<int>(3,5), 4); // add 4 to [3,5]  itl_map += std::make_pair(itl::interval<int>(4,8), 8); // add 8 to [4,8] -> will generate 3 intervals  itl_map -= std::make_pair(itl::interval<int>(5,5), 2); // subtract 2 -> will split another interval  for(itl::interval_map<int, int>::const_iterator it = itl_map.begin(); it != itl_map.end(); ++it)  {    itl::interval<int> const& interval = it->first;    std::cout << " " << interval.first() << ".." << interval.last() << ": " << it->second;  }  std::cout << std::endl;  // OUTPUT:  3..3: 4  4..4: 12  5..5: 10  6..8: 8 }
This would give me a clearer picture how it works.
Thank you again for sharing your experiences with the introduction. Developers want to *see how it works* :-D Yet I wanted to focus on concept and abstraction.
At the same time I now realize that during our discussion on +=, -=, |= , I didn't realize enough that += really does mathematics behind the screens. So it adds values where to the map on the specified interval, it subtracts values from the map on the specified interval. This goes beyond "set theoretic operations", "set union" and especially "set difference". See below for more on this.
I realize that a similar sample is there in the documentation, and that this principle, "aggregate on overlap" is well explained there. However, a sample with the numeric values is (for me) somewhat more clear than the given sample with names which are added to a set; the sample of interval_map with itl::set probably does too much at a time...
But let me repeat that the overall documentation is impressive and complete!
I think I'll change the intro a little according to the suggested. But to address the issues that you are raising here in a broader way, I think it'll be better to put that into a tutorial. Anyway your suggestions will not be forgotten. So much on this part. More next time. Cheers, Joachim
Joachim Faulhaber wrote:
2010/2/28 Barend Gehrels <barend@geodan.nl>:
and then gives the example " mySet.contains(42)". But contains is NOT an method of std::set, but YES from interval_set. This was confusing.
my view on sets here is not governed by std::sets but rather by the mathematical notion of a set or the itl::Set concept that is part of my documentation. In this view the "is element of" function is pretty fundamental and it is available for itl::interval_set and for itl::set as bool T::contains(const domain_type&); [snip] Which is the common interface, the fundamental aspect, that constitutes this semantic kernel? Would that signature contain find(x)? Would it contain contains(x)? Would it provide iterators?
boost::dynamic_bitset does not implement find, it does not implement iterators. Would we therefore say it is not a set? Its signature does not provide contains(x) but it contains test(x), which IMO should be called contains(x).
I'm speaking from partial ignorance, but... Wouldn't it be better to use non-member functions for those operations expected of a set? Then, boost::dynamic_bitset would satisfy itl::contains(bitset, x) because it could be implemented in terms of test(). Likewise, std::set would satisfy because itl::contains(s, x) could be implemented in terms of find(). Using that approach, your concepts would apply to any type for which a specified set of non-member functions can be applied while meeting specific semantic requirements. I should think many more types could be adapted to ITL without needing specific support form ITL with that approach. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
2010/3/5 Stewart, Robert <Robert.Stewart@sig.com>:
Joachim Faulhaber wrote:
2010/2/28 Barend Gehrels <barend@geodan.nl>:
and then gives the example " mySet.contains(42)". But contains is NOT an method of std::set, but YES from interval_set. This was confusing.
my view on sets here is not governed by std::sets but rather by the mathematical notion of a set or the itl::Set concept that is part of my documentation. In this view the "is element of" function is pretty fundamental and it is available for itl::interval_set and for itl::set as bool T::contains(const domain_type&); [snip] Which is the common interface, the fundamental aspect, that constitutes this semantic kernel? Would that signature contain find(x)? Would it contain contains(x)? Would it provide iterators?
boost::dynamic_bitset does not implement find, it does not implement iterators. Would we therefore say it is not a set? Its signature does not provide contains(x) but it contains test(x), which IMO should be called contains(x).
I'm speaking from partial ignorance, but...
Wouldn't it be better to use non-member functions for those operations expected of a set? Then, boost::dynamic_bitset would satisfy itl::contains(bitset, x) because it could be implemented in terms of test(). Likewise, std::set would satisfy because itl::contains(s, x) could be implemented in terms of find().
Using that approach, your concepts would apply to any type for which a specified set of non-member functions can be applied while meeting specific semantic requirements. I should think many more types could be adapted to ITL without needing specific support form ITL with that approach.
The decision to keep a few functions, like bool T::contains(const domain_type&); member functions although they could have been implemented as global functions comes from a residual resistance of a brain that has been thinking in OO-designs for too long ;-) Also I found s.contains(x) a little more readable than contains(s,x) but this is a minor advantage compared to the benefits of the global function that you described concisely. Luke already took the same line in this discussion and I certainly will improve the design in this respect. Thank you for the hint. Joachim
Joachim Faulhaber wrote:
2010/3/5 Stewart, Robert <Robert.Stewart@sig.com>:
Joachim Faulhaber wrote:
2010/2/28 Barend Gehrels <barend@geodan.nl>:
and then gives the example " mySet.contains(42)". But contains is NOT an method of std::set, but YES from interval_set. This was confusing. my view on sets here is not governed by std::sets but rather by the mathematical notion of a set or the itl::Set concept that is part of my documentation. In this view the "is element of" function is pretty fundamental and it is available for itl::interval_set and for itl::set as bool T::contains(const domain_type&); [snip] Which is the common interface, the fundamental aspect, that constitutes this semantic kernel? Would that signature contain find(x)? Would it contain contains(x)? Would it provide iterators?
boost::dynamic_bitset does not implement find, it does not implement iterators. Would we therefore say it is not a set? Its signature does not provide contains(x) but it contains test(x), which IMO should be called contains(x). I'm speaking from partial ignorance, but...
Wouldn't it be better to use non-member functions for those operations expected of a set? Then, boost::dynamic_bitset would satisfy itl::contains(bitset, x) because it could be implemented in terms of test(). Likewise, std::set would satisfy because itl::contains(s, x) could be implemented in terms of find().
I use std::set::count for contains.
Using that approach, your concepts would apply to any type for which a specified set of non-member functions can be applied while meeting specific semantic requirements. I should think many more types could be adapted to ITL without needing specific support form ITL with that approach.
The decision to keep a few functions, like
bool T::contains(const domain_type&);
member functions although they could have been implemented as global functions comes from a residual resistance of a brain that has been thinking in OO-designs for too long ;-) Also I found
s.contains(x)
a little more readable than
contains(s,x)
but this is a minor advantage compared to the benefits of the global function that you described concisely. Luke already took the same line in this discussion and I certainly will improve the design in this respect.
That's good to hear. Better interaction with existing std and user defined types en lieu of itl specific types addresses my main concern with the library. So give this a +1 from me. Jeff
----- Original Message ----- From: "Hartmut Kaiser" <hartmut.kaiser@gmail.com> To: <boost@lists.boost.org>; <boost-announce@lists.boost.org>; <boost-users@lists.boost.org> Sent: Thursday, February 18, 2010 2:22 PM Subject: [boost] [Review] ITL review starts today, February 18th
The formal review of the Interval Template Library (ITL) starts today, February 18th, 2010 and will end February 27th, 2010. ITL is being developed by Joachim Faulhaber.
------------------------------------------------
Hi,
- What is your evaluation of the design?
I think the library must made a clear distinction between continuous and discrete intervals, as we are unable to iterate on continuous interval_set using the element iterators. As other have suggested, the template parameter domain must follow some basic interval requirements, in particular the separation between compile time and run-time bound checking. I have taken some time to undesrstand the subtilities of the different interval combining styles. Once understood I think all these are useful alternatives.
- What is your evaluation of the implementation?
Not reviewed.
- What is your evaluation of the documentation?
Even if the examples show a lot of things, a tutorial will allow you to explain how to do specific things, starting from basic uses cases and going to more advanced ones. As noted off-list, the hint parameter of the map insert function is missing.
- What is your evaluation of the potential usefulness of the library?
In particular I had two uses cases of this library * Storage of sparse free local unique identifiers (see Boost.LUID on the Sandbox). * Map memory areas (representing variables) to the transactional cache (in Boost.STM). The memory areas can not overlap as the represent the memory occuped by variables, but a memory area can be embedded on another, the memory of a field is embedded on the struct variable. The variable stored in the maps contains already the size of the variable, and the interval are all of the same type, so the run-time check about the bound types could be avoided in this case. Both use cases can be implemented using the library.
- Did you try to use the library? With what compiler? Did you have any problems?
I have tryed to implemented the map memory area without not too much issues, but I had no time to comile and test :(.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
I've followed the library evolution since its first announcement, and I have do a quick reading of the last documentation.
- Are you knowledgeable about the problem domain?
I have never need to work with continuous intervals, so I don't knwo the subtilities of this doamin. However I have already implemented maps and set of intervals and I find that Boost.ITL do this task much better than my in house implementation. +1/2. I consider that Boost.ITL must be accepted provisionaly and should be accepted after a fast review once the modification I and others have suggest are taken in account. Best, Vicente
----- Original Message ----- From: "Hartmut Kaiser" <hartmut.kaiser@gmail.com> To: <boost@lists.boost.org>; <boost-announce@lists.boost.org>; <boost- users@lists.boost.org> Sent: Thursday, February 18, 2010 2:22 PM Subject: [boost] [Review] ITL review starts today, February 18th
The formal review of the Interval Template Library (ITL) starts today,
February 18th, 2010 and will end February 27th, 2010. ITL is being developed by Joachim Faulhaber.
- What is your evaluation of the design?
Clearly meets some users needs. (see below on interval_trees).
- What is your evaluation of the implementation?
Works for some users. I note some reservations and discussion about the underlying storage that might be a problem with large scale projects. It doesn't seem to be practical problem for some reasonably large scaled projects, and a different framework might very well have other disadvantages. So I don't think this is a reason to put the library on hold now. (Aside - I note that this is yet another example of a reviewer coming up with a fundamental objection that would been very much better aired a very long time OK. I believe this would be less likely to happen if 'candidate libraries' were more exposed to public view, and acquire more users who could spot weaknesses. I also can be very sympathetic to authors who won't want to go back to square one at this point in the process. They or others (Phil? ;-) - are more likely to do this with real uses and real uses waiting).
- What is your evaluation of the documentation?
Comprehensive, clear, good enough. (One can never have enough tutorial, and examples of which there are already good ones). If one was starting now, I would recommend using Doxygen. This would ensure that docs and code don't get out of step. But this is a very significant task to retrofit - especially adding Doxygen comments to the very many functions etc - been there, done that! Note to would be Boost submitters, add Doxygen comments as you go along - they will help you and others later.) I also didn't much like inventions of new 'jargon' like "aggrovering" or "unon".
- What is your evaluation of the potential usefulness of the library?
- Did you try to use the library? With what compiler? Did you have any
The examples given show that there must be many uses. problems? Played with previous version. No problems with MSVC.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
A quick re-reading.
I've slightly followed the library evolution since its first announcement, and I did quick reading of the last documentation.
- Are you knowledgeable about the problem domain?
Novice. FWIW, I think that it should be accepted into Boost. Paul --- Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com
Hi Paul, Paul A. Bristow wrote:
I note some reservations and discussion about the underlying storage that might be a problem with large scale projects.
It doesn't seem to be practical problem for some reasonably large scaled projects, and a different framework might very well have other disadvantages. So I don't think this is a reason to put the library on hold now.
(Aside - I note that this is yet another example of a reviewer coming up with a fundamental objection that would been very much better aired a very long time [ago?]
I first raised my concerns in March 2009 when Joachim announced "preview 4" and asked for feedback. I was one of only two people to post comments at that time. See http://lists.boost.org/Archives/boost/2009/03/149365.php . Prior to that, in July 2008 Dave Abrahams mentioned an interval tree that he had written (http://lists.boost.org/Archives/boost/2008/07/140452.php) and in reply, Joachim wrote (http://lists.boost.org/Archives/boost/2008/08/140653.php) : "You [Dave] mention your own implementation of an interval map using rb-trees. As you might have noticed my library implements interval sets finally via std::sets and interval_maps via std::maps. I am well aware that a specifically tailored interval tree has an optimization potential over a std::container implementation. So this is also on my todo list. Yet I wanted to focus on design, clarity and correctness first before improving performance using a more optimally tailored implementation." So as you can see, this fundamental issue was indeed raised a very long time ago (in fact just 3 months after the library was first mentioned), and Joachim re-assured us that he knew about the issues with his design and that he intended to rectify them.
OK. I believe this would be less likely to happen if 'candidate libraries' were more exposed to public view, and acquire more users who could spot weaknesses.
More users can certainly help to spot problems, but in this case the issue is not that the problem was not spotted.
I also can be very sympathetic to authors who won't want to go back to square one at this point in the process. They or others (Phil? ;-) - are more likely to do this with real uses and real uses waiting).
Regards, Phil.
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Phil Endecott Sent: Monday, March 01, 2010 5:54 PM To: boost@lists.boost.org Subject: Re: [boost] [Review] ITL review starts today, February 18th
Paul A. Bristow wrote:
I note some reservations and discussion about the underlying storage that might be a problem with large scale projects.
It doesn't seem to be practical problem for some reasonably large scaled projects, and a different framework might very well have other disadvantages. So I don't think this is a reason to put the library on hold now.
(Aside - I note that this is yet another example of a reviewer coming up with a fundamental objection that would been very much better aired a very long time [ago?]
I first raised my concerns in March 2009 when Joachim announced "preview 4" and asked for feedback. I was one of only two people to post comments at that time. See http://lists.boost.org/Archives/boost/2009/03/149365.php .
Prior to that, in July 2008 Dave Abrahams mentioned an interval tree that he had written (http://lists.boost.org/Archives/boost/2008/07/140452.php) and in reply, Joachim wrote (http://lists.boost.org/Archives/boost/2008/08/140653.php) :
"You [Dave] mention your own implementation of an interval map using rb-trees. As you might have noticed my library implements interval sets finally via std::sets and interval_maps via std::maps. I am well aware that a specifically tailored interval tree has an optimization potential over a std::container implementation. So this is also on my todo list. Yet I wanted to focus on design, clarity and correctness first before improving performance using a more optimally tailored implementation."
So as you can see, this fundamental issue was indeed raised a very long time ago (in fact just 3 months after the library was first mentioned), and Joachim re-assured us that he knew about the issues with his design and that he intended to rectify them.
OK. I believe this would be less likely to happen if 'candidate libraries' were more exposed to public view, and acquire more users who could spot weaknesses.
More users can certainly help to spot problems, but in this case the issue is not that the problem was not spotted.
I also can be very sympathetic to authors who won't want to go back to square one at this point in the process. They or others (Phil? ;-) - are more likely to do this with real uses and real uses waiting).
OK - grovel - sorry - I've not been following the list carefully enough :-( In this case my 'accusation' is entirely wrong - but it has occurred before. Hopefully, there may still be potential for this optimisation in future - but I doubt it's a trivial task. Paul Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com
Hi Paul, thank you for your review on the ITL. 2010/3/1 Paul A. Bristow <pbristow@hetp.u-net.com>
----- Original Message ----- From: "Hartmut Kaiser" <hartmut.kaiser@gmail.com> To: <boost@lists.boost.org>; <boost-announce@lists.boost.org>; <boost- users@lists.boost.org> Sent: Thursday, February 18, 2010 2:22 PM Subject: [boost] [Review] ITL review starts today, February 18th
The formal review of the Interval Template Library (ITL) starts today,
February 18th, 2010 and will end February 27th, 2010. ITL is being developed by Joachim Faulhaber.
- What is your evaluation of the design?
Clearly meets some users needs. (see below on interval_trees).
- What is your evaluation of the implementation?
Works for some users.
I note some reservations and discussion about the underlying storage that might be a problem with large scale projects.
It doesn't seem to be practical problem for some reasonably large scaled projects, and a different framework might very well have other disadvantages. So I don't think this is a reason to put the library on hold now.
[...]
- What is your evaluation of the documentation?
Comprehensive, clear, good enough. (One can never have enough tutorial, and examples of which there are already good ones). If one was starting now, I would recommend using Doxygen. This would ensure that docs and code don't get out of step. But this is a very significant task to retrofit - especially adding Doxygen comments to the very many functions etc - been there, done that! Note to would be Boost submitters, add Doxygen comments as you go along - they will help you and others later.)
I also didn't much like inventions of new 'jargon' like "aggrovering" or "unon".
[...]
There is criticism of this by ohters too. Since my "inventions" are only a few this can be changed without too much effort.
- What is your evaluation of the potential usefulness of the library?
The examples given show that there must be many uses.
- Did you try to use the library? With what compiler? Did you have any problems?
Played with previous version. No problems with MSVC.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
A quick re-reading.
I've slightly followed the library evolution since its first announcement, and I did quick reading of the last documentation.
- Are you knowledgeable about the problem domain?
Novice.
FWIW, I think that it should be accepted into Boost.
Thanks again. Best regards, Joachim
----- Original Message ----- From: "Hartmut Kaiser" <hartmut.kaiser@gmail.com> To: <boost@lists.boost.org>; <boost-announce@lists.boost.org>; < boost-users@lists.boost.org> Sent: Thursday, February 18, 2010 2:22 PM Subject: [boost] [Review] ITL review starts today, February 18th
The formal review of the Interval Template Library (ITL) starts today, February 18th, 2010 and will end February 27th, 2010. ITL is being developed by Joachim Faulhaber.
------------------------------------------------
Hi,
- What is your evaluation of the design?
I think the library must made a clear distinction between continuous and discrete intervals, as we are unable to iterate on continuous interval_set using the element iterators.
As other have suggested, the template parameter domain must follow some basic interval requirements, in particular the separation between compile time and run-time bound checking.
I am not completely sure, if I understand you correctly here. But in any case, in the discussion with Jeff Flinn I already wrote, that I can simplify
Hi Vicente, thank you again for reviewing my library. 2010/2/28 vicente.botet <vicente.botet@wanadoo.fr> the usage of own interval class templates, particularly interval types that require an integral element_type with static bounds, no dynamic bound setting and without memory overhead for dynamic bound_types. I hope that this will make you happy as well ;-)
I have taken some time to undesrstand the subtilities of the different interval combining styles. Once understood I think all these are useful alternatives.
- What is your evaluation of the documentation?
Even if the examples show a lot of things, a tutorial will allow you to explain how to do specific things, starting from basic uses cases and going to more advanced ones.
As noted off-list, the hint parameter of the map insert function is missing.
will be done shortly.
- What is your evaluation of the potential usefulness of the library?
In particular I had two uses cases of this library * Storage of sparse free local unique identifiers (see Boost.LUID on the Sandbox). * Map memory areas (representing variables) to the transactional cache (in Boost.STM). The memory areas can not overlap as the represent the memory occuped by variables, but a memory area can be embedded on another, the memory of a field is embedded on the struct variable.
The variable stored in the maps contains already the size of the variable, and the interval are all of the same type, so the run-time check about the bound types could be avoided in this case.
Both use cases can be implemented using the library.
- Did you try to use the library? With what compiler? Did you have any problems?
I have tryed to implemented the map memory area without not too much issues, but I had no time to comile and test :(.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
I've followed the library evolution since its first announcement, and I have do a quick reading of the last documentation.
- Are you knowledgeable about the problem domain?
I have never need to work with continuous intervals, so I don't knwo the subtilities of this doamin. However I have already implemented maps and set of intervals and I find that Boost.ITL do this task much better than my in house implementation.
+1/2. I consider that Boost.ITL must be accepted provisionaly and should be accepted after a fast review once the modification I and others have suggest are taken in account.
I hope you can benefit from the ITL in your projects, specifically Boost.STM. This seems to be a very interesting use case. Best regards, Joachim
participants (9)
-
Barend Gehrels -
Daniel Trebbien -
Hartmut Kaiser -
Jeff Flinn -
Joachim Faulhaber -
Paul A. Bristow -
Phil Endecott -
Stewart, Robert -
vicente.botet