Re: [boost] [Review] ITL review starts today, February 18th
Hartmut Kaiser wrote:
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. ... Hmm, not much discussion yet. While this is not my review I'll make a few comments.
I was able to port at least my necessary portions of split interval map to CodeWarrior 9.4 and was successful in using it to generate a column coverage graph of what is effectively the columns of possibly large sparse matrices. I would have expected the containers to be templated on an interval type, negating the need for run-time determination of boundtype. With the current design, a rather heavy interval is required with it's boundtype data member. My domain type is a simple int, an index into a row of a sparse matrix. Our in-house Interval class is always right_open, so there is only the need for a begin and end value leading to minimal memory usage. The current library design requires me to convert between ITL intervals and my own application's intervals. I'd have like to be able to provide a model of an interval concept that the ITL container would use. I wasn't able to find any description of the class invariants for interval. For example in our own Interval class the upper/end value must be greater than/equal to the lower/begin value which is a precondition to the constructor taking a pair of domain values. We do provide a static makeNormalized method to produce a proper interval when the order of the domain arguments is unknown, which is not very often in our usage so you don't pay that cost. In my case I hadn't the need for 'reversed' intervals, but I could see that being required for some use cases. Does ITL handle that? Along the same lines I've found little need for the mutators. An interval really only needs default and copy constructors, and one taking the upper and lower values. All mutations merely construct a new interval using calculated values and begin/end values from source intervals. Jeff
Hi Jeff! Congratulations =) Your are the first one to comment on my project in this review period. You are raising some good points about aspects of the design I stopped thinking about ... 2010/2/22 Jeff Flinn <TriumphSprint2000@hotmail.com>:
Hartmut Kaiser wrote:
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. ... Hmm, not much discussion yet. While this is not my review I'll make a few comments.
I was able to port at least my necessary portions of split interval map to CodeWarrior 9.4 and was successful in using it to generate a column coverage graph of what is effectively the columns of possibly large sparse matrices.
I would have expected the containers to be templated on an interval type, negating the need for run-time determination of boundtype. With the current design, a rather heavy interval is required with it's boundtype data member.
To represent the four boundtypes only 2 bits are required, which are currently coded into one byte. But yes, due to memory alignment the boundtype finally covers 4 bytes which is, using an interval<int>, 50% more than what you would like to have.
My domain type is a simple int, an index into a row of a sparse matrix. Our in-house Interval class is always right_open, so there is only the need for a begin and end value leading to minimal memory usage. The current library design requires me to convert between ITL intervals and my own application's intervals. I'd have like to be able to provide a model of an interval concept that the ITL container would use.
The breakthroughs of yesterday can be the obstacles of today. Basic to the design of itl::interval was the desire to make the library as generic as possible. The "key_type", which I have named "domain_type" of intervals and interval containers are supposed to be not limited to integral types or even numeric types. I wanted to be able to have e.g. interval_set<int> but also interval_set<double> interval_set<rationale<int>> and even interval_set<string>. And one of the breakthroughs of the design was the realisation that this could be done using interval bounds. Since we were using ITL in a context where the memory demand of the bound_type member never was a problem, I never asked myself the question if there could be the desire for a simpler interval template. So the first moment I thought you caught me on a serious design flaw. But after browsing the code I am fairly sure, that I can provide what you desire. (1) There is a template template parameter Interval already that requires the domain_type and an ordering on the domain_type. (2) For a simpler interval class template like e.g. integral_rightopen_interval<T> the implementation will then be probably simpler or even trivial. e.g: bool is(bound_type bt){ return bt==left_open ? true : false; } and since the bound type is always the same, is does not have to be a class member anymore.
I wasn't able to find any description of the class invariants for interval.
Can be added.
For example in our own Interval class the upper/end value must be greater than/equal to the lower/begin value which is a precondition to the constructor taking a pair of domain values. We do provide a static makeNormalized method to produce a proper interval when the order of the domain arguments is unknown, which is not very often in our usage so you don't pay that cost. In my case I hadn't the need for 'reversed' intervals, but I could see that being required for some use cases. Does ITL handle that?
Nope.
Along the same lines I've found little need for the mutators. An interval really only needs default and copy constructors, and one taking the upper and lower values. All mutations merely construct a new interval using calculated values and begin/end values from source intervals.
For a nice and simple integral_rightopen_interval<T> the mutating operations are pretty simple and you can work with a fairly minimal class. If you work with arbitrary interval bounds these computations can be quite nasty, so I prefer defining functions that hide the distinction of cases that one always gets wrong. Thank you for your comments and for raising these interesting points. I will adapt the documentation and check, if an integral_rightopen_interval<T> class template can be used seamlessly. Best, Joachim
Joachim Faulhaber wrote:
So the first moment I thought you caught me on a serious design flaw. But after browsing the code I am fairly sure, that I can provide what you desire.
(1) There is a template template parameter Interval already that requires the domain_type and an ordering on the domain_type.
(2) For a simpler interval class template like e.g. integral_rightopen_interval<T> the implementation will then be probably simpler or even trivial. e.g:
bool is(bound_type bt){ return bt==left_open ? true : false; }
and since the bound type is always the same, is does not have to be a class member anymore.
I had a similar concern to Jeff. I didn't seen any template parameter for Interval before, but there it is. template<class, ITL_COMPARE>class Interval = itl::interval, However, I'm not entirely satisfied with it because all of the utility functions for intervals are implemented as members of the interval class. That means I have to duplicate them to implement my own interval class that satisfies the interval interface. If they were non-member generic functions I could call them on my interval type and the bound checking would compile away with constant propagation to produce efficient code. The interval set operations are simple enough to implement (particularly with compile time policies for open/closed) that I doubt people would try to satisfy the interface of the Interval parameter required by your interval set class and would choose to implement the algorithm themselves. The way I always implemented open/closed semantics (with integer coordinates) was to left shift by one and bloat the interval by one on the ends that are closed. This gives max performance and minimal storage since it uses bits that were going to waste anyway and does the work of doing bounds comparison in the same instruction that does coordinate comparison. The OO style of the library design with large numbers of member functions for interval and container classes is somewhat off-putting. I would rather see a separation between data structures and algorithms. The algorithms are what are important. Right now the library provides most of the generic programming magic required to make the operators work with any type that is a set or map of intervals, but requires the object type to provide member functions for operations that could have been implemented as free functions. There are two algorithms for interval set operations (one is O(n log m) and the other is O(n + m)). I would like to use the container and algorithm appropriate for what I expect n and m to be. Also, if I call A = B & C I would like the O(n + m) algorithm to be used and not the O(n log m) algorithm in addition to an O(n + m) copy. If I want to invoke the O(n + m) set operation algorithm why can't I use any container type for the input and output interval sets since I don't need any O(log n) insertion or removal? I think the quality of the library is quite good, and I hope to find time for a full review before the end of the review period. I found the number of styles of set operation, element vs. interval and sets vs. maps to be a somewhat bewildering combination of features and I'm still getting oriented in the documentation and code. I see a lot of improvement over the course of the two years or so since it was first discussed on the mailing list. I think the law proving test library used in the tests is a much more generally useful and stronger candidate for becoming a boost library. The whole community could benefit from better test utilities. Not everyone uses interval sets, but everyone writes tests. Best wishes, Luke
Hi Luke, thank you for commenting on my library. 2010/2/23 Simonson, Lucanus J <lucanus.j.simonson@intel.com>:
Joachim Faulhaber wrote:
So the first moment I thought you caught me on a serious design flaw. But after browsing the code I am fairly sure, that I can provide what you desire.
(1) There is a template template parameter Interval already that requires the domain_type and an ordering on the domain_type.
(2) For a simpler interval class template like e.g. integral_rightopen_interval<T> the implementation will then be probably simpler or even trivial. e.g:
bool is(bound_type bt){ return bt==left_open ? true : false; }
ooops: simpler of course bool is(bound_type bt){ return bt==left_open; }
and since the bound type is always the same, is does not have to be a class member anymore.
I had a similar concern to Jeff. I didn't seen any template parameter for Interval before, but there it is.
template<class, ITL_COMPARE>class Interval = itl::interval,
However, I'm not entirely satisfied with it because all of the utility functions for intervals are implemented as members of the interval class.
Not *all* of them. Non-member generic functions are: ==, !=, <, >, <=, >=, hull, left_subract, right_subtract, &, intersects, is_disjoint
That means I have to duplicate them to implement my own interval class that satisfies the interval interface.
Yes. I see now the importance to keep the class interface minimal here, which currently is not the case. But I think, this can be achieved quickly by a number of straight forward refactorings.
If they were non-member generic functions I could call them on my interval type and the bound checking would compile away with constant propagation to produce efficient code. The interval set operations are simple enough to implement (particularly with compile time policies for open/ closed) that I doubt people would try to satisfy the interface of the Interval parameter required by your interval set class and would choose to implement the algorithm themselves.
The way I always implemented open/closed semantics (with integer coordinates) was to left shift by one and bloat the interval by one on the ends that are closed. This gives max performance and minimal storage since it uses bits that were going to waste anyway and does the work of doing bounds comparison in the same instruction that does coordinate comparison.
I think this works for integer coordinates only.
The OO style of the library design with large numbers of member functions for interval and container classes is somewhat off-putting.
Most of the core functions including all set theoretic operations for the interval containers are provided as non-member generic functions.
I would rather see a separation between data structures and algorithms. The algorithms are what are important. Right now the library provides most of the generic programming magic required to make the operators work with any type that is a set or map of intervals, but requires the object type to provide member functions for operations that could have been implemented as free functions.
There are two algorithms for interval set operations (one is O(n log m) and the other is O(n + m)). I would like to use the container and algorithm appropriate for what I expect n and m to be. Also, if I call A = B & C I would like the O(n + m) algorithm to be used and not the O(n log m) algorithm in addition to an O(n + m) copy.
I agree. This is not done yet. Smart as you are you spotted this immediately ;-)
If I want to invoke the O(n + m) set operation algorithm why can't I use any container type for the input and output interval sets since I don't need any O(log n) insertion or removal?
I think the quality of the library is quite good, and I hope to find time for a full review before the end of the review period. I found the number of styles of set operation, element vs. interval and sets vs. maps to be a somewhat bewildering
nice wording ;-) I think the admissible combinations are chosen carefully and each of them has use cases. I could add examples to the docs.
combination of features and I'm still getting oriented in the documentation and code. I see a lot of improvement over the course of the two years or so since it was first discussed on the mailing list. oh thanks!
I think the law proving test library used in the tests is a much more generally useful and stronger candidate for becoming a boost library.
... but much less advanced in the boostifying process and suffering from many more problems
The whole community could benefit from better test utilities. Not everyone uses interval sets,
... not yet ;-)
but everyone writes tests.
Thank you for your straight and valuable comments. Best regards, Joachim
On Mon, Feb 22, 2010 at 8:00 PM, Joachim Faulhaber <afojgo@googlemail.com> wrote:
/* snip */
I am interested in testing this, but I am away from my main programming computer until I get back home on the 27th... I might be able to do a quick test with the programming side of it then, will try to read the docs well before then though.
On Mon, Feb 22, 2010 at 8:00 PM, Joachim Faulhaber <afojgo@googlemail.com> wrote:
/* snip */
I am interested in testing this, but I am away from my main programming computer until I get back home on the 27th... I might be able to do a quick test with the programming side of it then, will try to read the docs well before then though.
If you tell me when you expect to submit a review I can hold off the final decision. Regards Hartmut --------------- Meet me at BoostCon www.boostcon.com
Joachim Faulhaber wrote:
Hi Jeff! ...
The Interval Template Library (ITL) is a library of interval containers that facilitates computations on collections of intervals and associated values. ... I would have expected the containers to be templated on an interval type, negating the need for run-time determination of boundtype. With the current design, a rather heavy interval is required with it's boundtype data member.
To represent the four boundtypes only 2 bits are required, which are currently coded into one byte. But yes, due to memory alignment the boundtype finally covers 4 bytes which is, using an interval<int>, 50% more than what you would like to have.
Yes, I can foresee needing maps with over 10M intervals in the not too distant future.
My domain type is a simple int, an index into a row of a sparse matrix. Our in-house Interval class is always right_open, so there is only the need for a begin and end value leading to minimal memory usage. The current library design requires me to convert between ITL intervals and my own application's intervals. I'd have like to be able to provide a model of an interval concept that the ITL container would use.
The breakthroughs of yesterday can be the obstacles of today. Basic to the design of itl::interval was the desire to make the library as generic as possible. The "key_type", which I have named "domain_type" of intervals and interval containers are supposed to be not limited to integral types or even numeric types. I wanted to be able to have e.g. interval_set<int> but also interval_set<double> interval_set<rationale<int>> and even interval_set<string>. And one of the breakthroughs of the design was the realisation that this could be done using interval bounds.
Yes, I agree bound_type is an important concept. The question is whether an interval's bound_type should be a runtime data member or part of the interval's type. My inclination is the latter. I would think that the problem domain would be dealing with only intervals of a particular bound_type, hence a container would be templated on the bound_type in addition to the domain and co domain types. If there is a need for mixed bound_types within a single problem domain, there could be a run time bound_type. But I shouldn't have to pay those run time costs if my problem domain doesn't need to.
Since we were using ITL in a context where the memory demand of the bound_type member never was a problem, I never asked myself the question if there could be the desire for a simpler interval template.
As a generic container I think scalability is very important.
So the first moment I thought you caught me on a serious design flaw. But after browsing the code I am fairly sure, that I can provide what you desire.
(1) There is a template template parameter Interval already that requires the domain_type and an ordering on the domain_type.
(2) For a simpler interval class template like e.g. integral_rightopen_interval<T> the implementation will then be probably simpler or even trivial. e.g:
bool is(bound_type bt){ return bt==left_open ? true : false; }
and since the bound type is always the same, is does not have to be a class member anymore.
If the bound_type is always the same, why would the container or the algorithms ever ask for bound_type discrimination?
I wasn't able to find any description of the class invariants for interval.
Can be added.
For example in our own Interval class the upper/end value must be greater than/equal to the lower/begin value which is a precondition to the constructor taking a pair of domain values. We do provide a static makeNormalized method to produce a proper interval when the order of the domain arguments is unknown, which is not very often in our usage so you don't pay that cost. In my case I hadn't the need for 'reversed' intervals, but I could see that being required for some use cases. Does ITL handle that?
Nope.
Perhaps directionality should be another concept of intervals.
Along the same lines I've found little need for the mutators. An interval really only needs default and copy constructors, and one taking the upper and lower values. All mutations merely construct a new interval using calculated values and begin/end values from source intervals.
For a nice and simple integral_rightopen_interval<T> the mutating operations are pretty simple and you can work with a fairly minimal class. If you work with arbitrary interval bounds these computations can be quite nasty, so I prefer defining functions that hide the distinction of cases that one always gets wrong.
Perhaps bound_type should be refactored from an enum into a class that provides the facilities dealing with bound-ness. I'm always suspect of enum's that encode type information anyway. Jeff
Jeff Flinn wrote:
For a nice and simple integral_rightopen_interval<T> the mutating operations are pretty simple and you can work with a fairly minimal class. If you work with arbitrary interval bounds these computations can be quite nasty, so I prefer defining functions that hide the distinction of cases that one always gets wrong.
Perhaps bound_type should be refactored from an enum into a class that provides the facilities dealing with bound-ness. I'm always suspect of enum's that encode type information anyway.
I was thinking that bound-ness can be factored out of the algorithms entirely by adding it to the domain type. An underlying domain type paired with a bool expresses bound-ness. The domain type would need traits like get_mirror(domain_type value) that returns value if we are ignoring bound-ness and returns a value with the complimentary bound-ness if we are using it. This would simplify the implementation of the algorithms and the interval data structure and increase the usefulness of the library. The interval map can store one domain_type value and one bool per interval it contains if bound-ness is needed and one domain_type value per interval it contains otherwise. The other value (and bound-ness) is implied by the adjacent interval in the map. The interval map would need to store whether the interval is empty or not associated with each entry paired with the codomain value. That is how my interval maps work in the internal details of 2D geometry set operations. In my case it is easy because I ignore bound-ness and the codomain type is a count and a count of zero means the interval is empty, so emptyness is implicit. I also never interate over intervals in the map, but instead use their end points and codomain values above and below. Regards, Luke
Why is the element iterator type a member of the interval set and map class when it isn't even applicable for "continuous" domain types? Why not just provide a utility iterator adaptor for iterators over intervals that lazily generates elements as a separate template class and let people use it where it is applicable? There shouldn't be the need to warn the user or depricate the element iterators if they aren't class members of the containers and it is obvious to the user that they may iterate a large number of time for intervals with large extents. I also don't understand why there is an itl::map and itl::set since they don't seem to add anything that can't be easily accomplished with interval_set and interval_map plus the element iterator adaptor or with std::set and std::map. It just isn't clear to me what they are for. Also, the absorb_neutrons function seems strangely out of place and has no documentation. What does it do? I'll probably come up with more questions as I continue the review and I don't want to save them up for the end because then we don't get as much good discussion. Thanks, Luke
Hi Luke, 2010/2/24 Simonson, Lucanus J <lucanus.j.simonson@intel.com>
Why is the element iterator type a member of the interval set and map class when it isn't even applicable for "continuous" domain types? Why not just provide a utility iterator adaptor for iterators over intervals that lazily generates elements as a separate template class and let people use it where it is applicable? There shouldn't be the need to warn the user or depricate the element iterators if they aren't class members of the containers and it is obvious to the user that they may iterate a large number of time for intervals with large extents. I also don't understand why there is an itl::map and itl::set since they don't seem to add anything that can't be easily accomplished with interval_set and interval_map plus the element iterator adaptor or with std::set and std::map. It just isn't clear to me what they are for. Also, the absorb_neutrons function seems strangely out of place and has no documentation. What does it do?
I'll probably come up with more questions as I continue the review and I don't want to save them up for the end because then we don't get as much good discussion.
thanks again. Obviously your scanning my code ;-)
It's 2:45 am in Europe now and tomorrow I can't be on the list till evening. So just a short reply. And more tomorrow evening: If you look on the function synopsis http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/int... you can see that all itl::Sets/Maps have a uniform interface, including yes, member functions add and subtract (in addition to insert and erase). I use itl::maps of elements in other projects to e.g. aggregate associated values for keys of tuples to compute things like cross tables. As I said elsewhere the aggregate on collision feature is pretty useful in different ways. I'm also using the element containers to validate the implementations against each other using law based tests: https://svn.boost.org/svn/boost/sandbox/itl/boost/validate/validater/interva... absorb_neutrons is also used to validate semantical properties in the law ProtonicEquality here: https://svn.boost.org/svn/boost/sandbox/itl/boost/validate/laws/map_laws.hpp More tomorrow, Good night Joachim
2010/2/24 Simonson, Lucanus J <lucanus.j.simonson@intel.com>
Why is the element iterator type a member of the interval set and map class when it isn't even applicable for "continuous" domain types? Why not just provide a utility iterator adaptor for iterators over intervals that lazily generates elements as a separate template class and let people use it where it is applicable? There shouldn't be the need to warn the user or depricate the element iterators if they aren't class members of the containers and it is obvious to the user that they may iterate a large number of time for intervals with large extents.
This is a good idea. I'm going change the code accordingly.
I also don't understand why there is an itl::map and itl::set since they don't seem to add anything that can't be easily accomplished with interval_set and interval_map plus the element iterator adaptor or with std::set and std::map. It just isn't clear to me what they are for.
(1) Within the ITL, for all sets and maps there are some functions that are uniformly available and that are not implemented for std::sets/maps. Some of them are member functions. add, subtract : implement generalized addition and subtraction of elements and segments add_intersection, flip : intersection and symmetric difference contains, contained_in : superset/subset relation cardinality : extension of size can be infinite for continuous interval containers iterative_size: number of iteratable entities This is done to give all all itl::containers, interval and element containers a uniform basic interface that can be used in global functions. (2) For element containers itl::set itl::map set theoretic functions are implemented. In an instantiation e.g. interval_map<int, itl::set<int> >, sets can therefor be aggregated out of the box, if itl::sets/maps are used. (3) element_iterators are a pretty recent extension. The idea to substitute element containers since element_iterators are available is new. One obstacle may be that element_iterators lack some of the properties of first class containers, since they only point to transient objects. (4) element containers namely itl::maps have own applications in other projects that use aggregate on collision via the generalized add, subtract functions. (5) element containers are used to test the behavioral equivalence between interval_sets/maps and itl::sets/maps that implement identical concepts itl::Set and itl::Maps. These equivalence laws tests can be represented by commuting diagrams: (use typewriter font to beautify) interval_container a, b, c element_container a', b', c' f: interval_container -> element_container; // e.g. atomize o : a binary operation, like + (a,b) ---o---> c | | |f = |f V V (a',b')---o---> c' or as a formula: f(a o b) == f(a) o f(b) These tests can be found in https://svn.boost.org/svn/boost/sandbox/itl/boost/validate/validater/interva... and the law template in: https://svn.boost.org/svn/boost/sandbox/itl/boost/validate/laws/pushouts.hpp Also, the absorb_neutrons function seems strangely out of place and has no
documentation. What does it do?
It removes all value pairs, that have neutral elements as associated values from the map. Neutron absorption is a fallout of law based testing ;) In many use cases value pairs of maps can be deleted, if the associated value is a neutral element which keeps the map more minimal. This is desired in many cases, but in some it's not.
Moreover an interval itl::Map of itl::Sets is a model of itl::Set only, if it absorbs neutrons. For a map that is not a neutron absorber, absorb_neutrons can be called to discard those elements explicitly. See also http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/con... http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/sem... Best, Joachim
Joachim Faulhaber wrote:
I also don't understand why there is an itl::map and itl::set since they don't seem to add anything that can't be easily accomplished with interval_set and interval_map plus the element iterator adaptor or with std::set and std::map. It just isn't clear to me what they are for.
(1) Within the ITL, for all sets and maps there are some functions that are uniformly available and that are not implemented for std::sets/maps. Some of them are member functions. add, subtract : implement generalized addition and subtraction of elements and segments add_intersection, flip : intersection and symmetric difference contains, contained_in : superset/subset relation cardinality : extension of size can be infinite for continuous interval containers iterative_size: number of iteratable entities
This is done to give all all itl::containers, interval and element containers a uniform basic interface that can be used in global functions.
Ok, I would suggest that these member functions be made free functions that accept std::set and std::map as well as itl::interval_map and itl::interval_set. Wrapping a class to add behaviors defeats generic programming and erects barriers to interoperability.
(2) For element containers itl::set itl::map set theoretic functions are implemented. In an instantiation e.g. interval_map<int, itl::set<int> >, sets can therefor be aggregated out of the box, if itl::sets/maps are used.
I believe that the same could be accomplished with std::set/map if the set theoretic functions were free functions.
(3) element_iterators are a pretty recent extension. The idea to substitute element containers since element_iterators are available is new. One obstacle may be that element_iterators lack some of the properties of first class containers, since they only point to transient objects.
You can only provide a const iterator. You can't get non-const access to the key type of a map or set anyway. The codomain value of the map would be const with the iterator adaptr and non const with the first class container.
Also, the absorb_neutrons function seems strangely out of place and has no
documentation. What does it do?
It removes all value pairs, that have neutral elements as associated values from the map.
Neutron absorption is a fallout of law based testing ;) In many use cases value pairs of maps can be deleted, if the associated value is a neutral element which keeps the map more minimal. This is desired in many cases, but in some it's not.
Moreover an interval itl::Map of itl::Sets is a model of itl::Set only, if it absorbs neutrons.
For a map that is not a neutron absorber, absorb_neutrons can be called to discard those elements explicitly.
See also http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/con... http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/sem...
I think you should rename this function to remove_null or something less misleading. Also, you should probably implement it with a free function and allow the user to specify a value for the neutral element: template <MapType> void remove_value(MapType& map, typename MapType::codomain_type neutral_value = typename MapType::codomain_type()); I'm a little confused about what it means for a map to be a neutron absorber. Does it automatically remove elements with neutral codomain values? I'm also confused about what a itl::Map of itl::Sets is and how it can be a model of itl::Set. Regards, Luke
2010/2/24 Simonson, Lucanus J <lucanus.j.simonson@intel.com>
Joachim Faulhaber wrote:
I also don't understand why there is an itl::map and itl::set since they don't seem to add anything that can't be easily accomplished with interval_set and interval_map plus the element iterator adaptor or with std::set and std::map. It just isn't clear to me what they are for.
(1) Within the ITL, for all sets and maps there are some functions that are uniformly available and that are not implemented for std::sets/maps. Some of them are member functions. add, subtract : implement generalized addition and subtraction of elements and segments add_intersection, flip : intersection and symmetric difference contains, contained_in : superset/subset relation cardinality : extension of size can be infinite for continuous interval containers iterative_size: number of iteratable entities
This is done to give all all itl::containers, interval and element containers a uniform basic interface that can be used in global functions.
Ok, I would suggest that these member functions be made free functions that accept std::set and std::map as well as itl::interval_map and itl::interval_set. Wrapping a class to add behaviors defeats generic programming and erects barriers to interoperability.
... I will consider this, ...
(2) For element containers itl::set itl::map set theoretic functions are implemented. In an instantiation e.g. interval_map<int, itl::set<int> >, sets can therefor be aggregated out of the box, if itl::sets/maps are used.
I believe that the same could be accomplished with std::set/map if the set theoretic functions were free functions.
All the set theoretic operators of the itl are free functions already. What is missing is an implementation of them for std::set and std::map, which is not difficult to implement.
(3) element_iterators are a pretty recent extension. The idea to substitute element containers since element_iterators are available is new. One obstacle may be that element_iterators lack some of the properties of first class containers, since they only point to transient objects.
You can only provide a const iterator. You can't get non-const access to the key type of a map or set anyway. The codomain value of the map would be const with the iterator adaptr and non const with the first class container.
.. I still have my doubts if this would be behavioral equivalent to the corresponding element container. Moreover, if you have an element container with isolated values represented by an interval container you waste a considerable amount of memory.
Also, the absorb_neutrons function seems strangely out of place and has no
documentation. What does it do?
It removes all value pairs, that have neutral elements as associated values from the map.
Neutron absorption is a fallout of law based testing ;) In many use cases value pairs of maps can be deleted, if the associated value is a neutral element which keeps the map more minimal. This is desired in many cases, but in some it's not.
Moreover an interval itl::Map of itl::Sets is a model of itl::Set only, if it absorbs neutrons.
For a map that is not a neutron absorber, absorb_neutrons can be called to discard those elements explicitly.
See also
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/con...
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/sem...
I think you should rename this function to remove_null or something less misleading.
I thought you'd enjoy a little radioactivity ;-)
Also, you should probably implement it with a free function and allow the user to specify a value for the neutral element:
The neutral value is a static property that depends on an itl::Map's domain_type and it's Combine functor. The user should not be able to set it to arbitrary values. This would spoil the semantical properties of itl containers with pretty unknown effects.
template <MapType> void remove_value(MapType& map, typename MapType::codomain_type neutral_value = typename MapType::codomain_type());
I'm a little confused about what it means for a map to be a neutron absorber. Does it automatically remove elements with neutral codomain values?
yes.
I'm also confused about what a itl::Map of itl::Sets is and how it can be a model of itl::Set.
This was the real fun stuff, when I tried to define and validate semantical properties (laws). While the semantics of itl::Set (I use capital first letter for concepts here http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/con... ) is determined by a "classical" set of laws known from algebras of sets e.g. http://en.wikipedia.org/wiki/Algebra_of_sets The semantics of itl::Maps can not be described by a *single* set of laws. The set of laws that holds for an itl::Map<D,C> is determined by the Concept that the codomain parameter is model of and some conditions given by the Map's Trait parameter. So the semantics of itl::Map is a mapping itself, that maps the Concept C of a Map's codomain_type to the instantiation of the Map<D,C>. I think this is beautiful and shows that the definition of the generalized addition/subtraction on maps is sound. Also it is the basis of the possibility to implement for instance a set large_bitset simply as an interval_map of bitsets, and it works http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/pro... See also: http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/sem... Best, Joachim
2010/2/24 Joachim Faulhaber <afojgo@googlemail.com>
2010/2/24 Simonson, Lucanus J <lucanus.j.simonson@intel.com>
Joachim Faulhaber wrote:
Also, the absorb_neutrons function seems strangely out of place and has no
documentation. What does it do?
It removes all value pairs, that have neutral elements as associated values from the map.
Neutron absorption is a fallout of law based testing ;) In many use cases value pairs of maps can be deleted, if the associated value is a neutral element which keeps the map more minimal. This is desired in many cases, but in some it's not.
Moreover an interval itl::Map of itl::Sets is a model of itl::Set only, if it absorbs neutrons.
For a map that is not a neutron absorber, absorb_neutrons can be called to discard those elements explicitly.
See also
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/con...
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/sem...
I think you should rename this function to remove_null or something less misleading.
I thought you'd enjoy a little radioactivity ;-)
Also, you should probably implement it with a free function and allow the user to specify a value for the neutral element:
The neutral value is a static property that depends on an itl::Map's domain_type and it's Combine functor. The user should not be able to set it to arbitrary values. This would spoil the semantical properties of itl containers with pretty unknown effects.
Correction: The neutral value is a static property that depends on an itl::Map's codomain_type and it's Combine functor. The user should not be able to set it to arbitrary values. This would spoil the semantical properties of itl containers with pretty unknown effects. .. Joachim
Jeff Flinn wrote: <snip>
Yes, I agree bound_type is an important concept. The question is whether an interval's bound_type should be a runtime data member or part of the interval's type. My inclination is the latter. I would think that the problem domain would be dealing with only intervals of a particular bound_type, hence a container would be templated on the bound_type in addition to the domain and co domain types. If there is a need for mixed bound_types within a single problem domain, there could be a run time bound_type. But I shouldn't have to pay those run time costs if my problem domain doesn't need to.
The (under development) ConstrainedValue library has a clever scheme to support compile-time or run-time through the same interface. See http://student.agh.edu.pl/~kawulak/constrained_value/constrained_value/tutor... and http://student.agh.edu.pl/~kawulak/constrained_value/reference/classboost_1_... The bound can be either an mpl::int_ which stores it at compile time or an int which stores it at runtime. Because an mpl::int_ implicitly converts to an int the same code can be used for both, and compressed_pair means the mpl version uses no space. You could do something similar by using either the enumeration type or an mpl wrapper around a particular value thereof. John Bytheway
2010/2/23 Jeff Flinn <TriumphSprint2000@hotmail.com>:
Joachim Faulhaber wrote:
Hi Jeff!
...
The Interval Template Library (ITL) is a library of interval containers that facilitates computations on collections of intervals and associated values.
...
To represent the four boundtypes only 2 bits are required, which are currently coded into one byte. But yes, due to memory alignment the boundtype finally covers 4 bytes which is, using an interval<int>, 50% more than what you would like to have.
Yes, I can foresee needing maps with over 10M intervals in the not too distant future. [...]
Basic to the design of itl::interval was the desire to make the library as generic as possible. The "key_type", which I have named "domain_type" of intervals and interval containers are supposed to be not limited to integral types or even numeric types. I wanted to be able to have e.g. interval_set<int> but also interval_set<double> interval_set<rationale<int>> and even interval_set<string>. And one of the breakthroughs of the design was the realisation that this could be done using interval bounds.
Yes, I agree bound_type is an important concept. The question is whether an interval's bound_type should be a runtime data member or part of the interval's type. My inclination is the latter. I would think that the problem domain would be dealing with only intervals of a particular bound_type, hence a container would be templated on the bound_type in addition to the domain and co domain types. If there is a need for mixed bound_types within a single problem domain, there could be a run time bound_type. But I shouldn't have to pay those run time costs if my problem domain doesn't need to.
Here is an example demonstrating that different bound_types may occur at run time. // Pseudo code: interval_set<double> x = {[0.0, 2.0)}; x -= 1.0; // or equivalently x -= [1.0, 1.0]; // x now contains: // x == {[0.0, 1.0),(1.0, 2.0)}
Since we were using ITL in a context where the memory demand of the bound_type member never was a problem, I never asked myself the question if there could be the desire for a simpler interval template.
As a generic container I think scalability is very important.
So the first moment I thought you caught me on a serious design flaw. But after browsing the code I am fairly sure, that I can provide what you desire.
(1) There is a template template parameter Interval already that requires the domain_type and an ordering on the domain_type.
(2) For a simpler interval class template like e.g. integral_rightopen_interval<T> the implementation will then be probably simpler or even trivial. e.g:
bool is(bound_type bt){ return bt==left_open; }
and since the bound type is always the same, is does not have to be a class member anymore.
If the bound_type is always the same, why would the container or the algorithms ever ask for bound_type discrimination?
as the example above shows, for continuous domain_types bound_types of intervals in interval containers can be different at run time. All 4 types [..], [..), (..], (..) can be generated by application of operations. So you need a function that selects or tests them if you want to print an interval container, for instance. The current implementation of itl::interval is a "one size fits all" type of class template that has been so handy, that I never considered to really use a different one. Meanwhile, I have implemented an integral_interval<T> that does what you need and it works correctly within interval containers. So, yes, you can use ITL with different and also smaller interval types. Still, it turns out, that the interface, that has to be implemented is not as minimal as would be desired. Currently I think, that there are two important kinds of intervals. Intervals of integral types and intervals of continuous types. The latter need IMO dynamic border_type info. The former don't and are much simpler to implement. So I think I will provide two interval templates as defaults for the Interval template parameter, that are set at compile time dependent on the type traits of the domain_type of the interval container. Both implement the same common interface that is used in algorithms. But intervals of integral types need less effort, if the user wants to customize her own.
I wasn't able to find any description of the class invariants for interval.
Can be added.
For example in our own Interval class the upper/end value must be greater than/equal to the lower/begin value which is a precondition to the constructor taking a pair of domain values. We do provide a static makeNormalized method to produce a proper interval when the order of the domain arguments is unknown, which is not very often in our usage so you don't pay that cost. In my case I hadn't the need for 'reversed' intervals, but I could see that being required for some use cases. Does ITL handle that?
Nope.
Perhaps directionality should be another concept of intervals.
To be honest, I'm not very fond of this idea.
Thank you again, Jeff. Best regards, Joachim
participants (6)
-
Hartmut Kaiser -
Jeff Flinn -
Joachim Faulhaber -
John Bytheway -
OvermindDL1 -
Simonson, Lucanus J