Re: [boost] [Boost-users] [Review] ITL review starts today, February 18th
Hi John, thank you for reviewing the ITL library! 2010/3/3 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
Hartmut Kaiser wrote:
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
I have to say first I have been evaluating the version of ITL called itl_plus_3_2_1 rather than the version in the boost vault. Perhaps someone can tell me whether that is a big mistake or not.
Using itl_plus_3_2_1 is completely ok. It is a later release than the review version itl_3_2_0. But the differences are marginal. Also itl_plus_3_2_1 contains more than the core library that is submitted for review. But you did not refer to these parts. So everything is fine.
Please always state in your review, whether you think the library should be accepted as a Boost library.
I think it should be accepted subject to the inclusion of an interval tree implementation.
- What is your evaluation of the design?
I suspect that making the open/closedness of an interval a template parameter would suit more users although I don't have a strong opinion on this one.
There has been a discussion on this point already. http://permalink.gmane.org/gmane.comp.lib.boost.devel/199905 For continuous data types it seems like interval bounds are needed as data member. For intervals of integral types the bound_type can be a static property. I will adapt the design in this point.
- What is your evaluation of the implementation?
I would have liked to see interval trees in the implementation. For what I've needed the library for so far this has not been a problem as most of the intervals don't overlap. In the future I can see use cases where the lack of interval trees would make the library impractical. I don't know how much impact adding an interval tree implementation would have on the existing interface.
I think the current implementation has its value and application. It should not and can not completely be replaced by an implementation based on an interval_tree. This would improve certain use cases but lead to problems in others. I will report on this in more detail. An interval_tree based split_interval_map will be a valuable optimization that should be done as an additional class template. The current implementation is fully functional, correct, useful and efficient in most cases of application.
- What is your evaluation of the documentation?
Good. A tutorial would be a welcome addition. Some functions were undocumented, I'm assuming they're documented in the review version.
The "handcrafted" documentation relates to the major interface of overloaded functions and function templates. In order to keep that short, more specific functions are only documented in the part of the documentation that is generated from doxygen comments: http://www.joachim-faulhaber.de/boost_itl/doc/libs/itl/doc/html/interval_tem... And yes, there may be few that have been forgotten. Please tell me, which ones you missed specifically.
- What is your evaluation of the potential usefulness of the library?
Very useful. It seems to have many applications in several different domains.
- Did you try to use the library? With what compiler? Did you have any problems?
I used gcc 4.4.1 and boost.python to make a python module for most of the main elements of the library. I used this module successfully in an application in genomics. However so far I have only had use for the SplitIntervalMap so I have not used most of the library.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
A reasonable amount - enough to get up to speed and use the library.
- Are you knowledgeable about the problem domain?
Not especially.
Thank you again. Best regards, Joachim
Joachim Faulhaber wrote:
There has been a discussion on this point already. http://permalink.gmane.org/gmane.comp.lib.boost.devel/199905
For continuous data types it seems like interval bounds are needed as data member. For intervals of integral types the bound_type can be a static property. I will adapt the design in this point.
I assume most uses of the library will either be over discrete domains or continuous domains where the presence/absence of individual elements is irrelevant. In both cases right-open intervals are a natural way of implementing a solution. I haven't thought of an application over a continuous domain where it is necessary to cater for the inclusion/exclusion of individual elements. Do you know of one? So it might be better to have both continuous and discrete intervals as right-open by default and to allow some mechanism whereby the user can choose to allow different runtime bound types if they need them. I have some further unrelated design questions/points: Is there a function to return the distance between two intervals? The default interval type is closed. Isn't right-open a more natural choice for most applications? It makes interval subtraction slightly simpler for example. I've always found right-open intervals an easier concept to think about and they make coding easier although this library removes any concerns about the latter. What is the meaning of the cardinality of a continuous interval? It seems to be defined to be 0? Why not make it only available for discrete domains? I would like to see interoperability with other boost libraries such as boost.hash and boost.serialization. Both would be very useful for my current application. Why were the interval combining styles implemented as subclasses? Wouldn't the design have been more flexible if they were implemented as a policy template parameter? That's just my feeling about it, I don't feel qualified to offer a strong opinion.
- What is your evaluation of the documentation? Good. A tutorial would be a welcome addition. Some functions were undocumented, I'm assuming they're documented in the review version.
The "handcrafted" documentation relates to the major interface of overloaded functions and function templates. In order to keep that short, more specific functions are only documented in the part of the documentation that is generated from doxygen comments: http://www.joachim-faulhaber.de/boost_itl/doc/libs/itl/doc/html/interval_tem...
And yes, there may be few that have been forgotten. Please tell me, which ones you missed specifically.
I'll try to find them again.
John Reid wrote:
I have some further unrelated design questions/points:
Is there a function to return the gap between 2 intervals? I guess I can subtract the 2 intervals from their hull but one function call would be nice.
John Reid wrote:
John Reid wrote:
I have some further unrelated design questions/points:
Is there a function to return the gap between 2 intervals? I guess I can subtract the 2 intervals from their hull but one function call would be nice.
I actually had a need to iterate on the implied intervals that constitute the empty space between the intervals stored in an interval map. This was used as a post processing step to assure at least one pixel wide gaps were not lost in a bar chart display of scaled data.
2010/3/6 Jeff Flinn <TriumphSprint2000@hotmail.com>:
John Reid wrote:
John Reid wrote:
I have some further unrelated design questions/points:
Is there a function to return the gap between 2 intervals? I guess I can subtract the 2 intervals from their hull but one function call would be nice.
I actually had a need to iterate on the implied intervals that constitute the empty space between the intervals stored in an interval map. This was used as a post processing step to assure at least one pixel wide gaps were not lost in a bar chart display of scaled data.
Hi Jeff and John, I have implemented gap and distance functions and checked them into the sandbox. template <class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval> Interval<DomainT,Compare> inner_complement(const Interval<DomainT,Compare>& left, const Interval<DomainT,Compare>& right); template <class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval> inline typename Interval<DomainT,Compare>::difference_type distance(const Interval<DomainT,Compare>& left, const Interval<DomainT,Compare>& right); According to your suggestions I am going to rework the design in general and for intervals in particular, such that intervals will generally be simpler, static bound_types can be chosen and user defined interval types can be used. This will take a little longer but I am looking forward to improve my design. It's always an adventure to discover one's own partial ignorance :-D Cheers, Joachim
Hi John, 2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
Joachim Faulhaber wrote:
There has been a discussion on this point already. http://permalink.gmane.org/gmane.comp.lib.boost.devel/199905
For continuous data types it seems like interval bounds are needed as data member. For intervals of integral types the bound_type can be a static property. I will adapt the design in this point.
I assume most uses of the library will either be over discrete domains or continuous domains where the presence/absence of individual elements is irrelevant. In both cases right-open intervals are a natural way of implementing a solution. I haven't thought of an application over a continuous domain where it is necessary to cater for the inclusion/exclusion of individual elements. Do you know of one?
Personally, I haven't seen one. But the design of the ITL is based on the premise that interval sets/maps are sets/maps of elements. I have called this the fundamental view. Within this design it must always be possible to add or subtract individual elements or element value pairs to and from interval_sets/maps for all possible domain types. Given this premise, I need to provide a correct implementation for e.g. a subtraction of an element for continuous domain_types. Using open interval bounds this implementation can be given. I'm not aware of a good alternative.
So it might be better to have both continuous and discrete intervals as right-open by default and to allow some mechanism whereby the user can choose to allow different runtime bound types if they need them.
I agree, that right-open intervals are suitable as default. But I am afraid, for the continuous case, we can not guarantee that all operations can maintain such an invariant. BTW existing interval libraries e.g. boost::numeric::interval or FILIB++ work with closed intervals. Subtract a closed interval from an interval set with continuous domain_type and you need open bounds.
I have some further unrelated design questions/points:
Is there a function to return the distance between two intervals?
hull(x,y).left_subtract(x).right_subtract(y).length(); I admit this is not extremely elegant... I deliberately left functions and calculations out, that rely on distance measures, because, in the general case ITL intervals and interval containers only require an ordered domain type. So you can use strings, sequences or other data types that do not implement a distance measure.
The default interval type is closed. Isn't right-open a more natural choice for most applications?
Good question ... I tried to change this in the past but encountered problems with unsigned integral domain types that flipped to max_int by singular applications of decrement operator -- in the current implementation. May be I should check this point more thoroughly again. I could get rid of the unloved unon<T>() meta function. ...
It makes interval subtraction slightly simpler for example. I've always found right-open intervals an easier concept to think about and they make coding easier although this library removes any concerns about the latter.
What is the meaning of the cardinality of a continuous interval? It seems to be defined to be 0? Why not make it only available for discrete domains?
Try this: interval<double> x(0.0, 1.0); if(x.cardinality() == numeric_limits<interval<double>::size_type>::infinity()) cout << "cardinality is infinite\n"; for doubles a, b with a < b: [a,b).cardinality() == infinity but {[a,a],[b,b]}.cardinality() == 2 Function cardinality() has been introduced to make clear: This function yields the number of *elements*, and not the number of iteratable entities in the interval container. For continuous domain_types the cardinality of an interval container can be infinite but it can be finite as well.
I would like to see interoperability with other boost libraries such as boost.hash and boost.serialization. Both would be very useful for my current application.
I haven't checked this yet. There should be some kind of basic interoperability through (segment) iterators and element_iterators.
Why were the interval combining styles implemented as subclasses? Wouldn't the design have been more flexible if they were implemented as a policy template parameter? That's just my feeling about it, I don't feel qualified to offer a strong opinion.
Part of these things have an "historical" background. The lib started with an OO design in a commercial company and has seen a lot of refactorings, that tried to keep a kind of back compatibility.
- What is your evaluation of the documentation?
Good. A tutorial would be a welcome addition. Some functions were undocumented, I'm assuming they're documented in the review version.
The "handcrafted" documentation relates to the major interface of overloaded functions and function templates. In order to keep that short, more specific functions are only documented in the part of the documentation that is generated from doxygen comments:
http://www.joachim-faulhaber.de/boost_itl/doc/libs/itl/doc/html/interval_tem...
And yes, there may be few that have been forgotten. Please tell me, which ones you missed specifically.
I'll try to find them again.
Thanks and best regards, Joachim
Joachim Faulhaber wrote:
So it might be better to have both continuous and discrete intervals as right-open by default and to allow some mechanism whereby the user can choose to allow different runtime bound types if they need them.
I agree, that right-open intervals are suitable as default. But I am afraid, for the continuous case, we can not guarantee that all operations can maintain such an invariant. BTW existing interval libraries e.g. boost::numeric::interval or FILIB++ work with closed intervals. Subtract a closed interval from an interval set with continuous domain_type and you need open bounds.
I was suggesting that your design could feature sets/maps that only had right-open intervals. This would be the default in both continuous and discrete domains. If the user really wanted to use all the different interval bound types over a continuous domain then perhaps he/she could choose to do so via a template parameter. This would probably be a rare use case though.
I have some further unrelated design questions/points:
Is there a function to return the distance between two intervals?
hull(x,y).left_subtract(x).right_subtract(y).length();
This isn't quite right if y < x.
I admit this is not extremely elegant... I deliberately left functions and calculations out, that rely on distance measures, because, in the general case ITL intervals and interval containers only require an ordered domain type. So you can use strings, sequences or other data types that do not implement a distance measure.
See below.
The default interval type is closed. Isn't right-open a more natural choice for most applications?
Good question ... I tried to change this in the past but encountered problems with unsigned integral domain types that flipped to max_int by singular applications of decrement operator -- in the current implementation. May be I should check this point more thoroughly again. I could get rid of the unloved unon<T>() meta function. ...
You seem to suggest you apply operator-- on integral domains here. Why not make the distance between intervals available when the domain is integral? This would be similar to the availability of first and last when the domain is discrete.
It makes interval subtraction slightly simpler for example. I've always found right-open intervals an easier concept to think about and they make coding easier although this library removes any concerns about the latter.
I would like to see interoperability with other boost libraries such as boost.hash and boost.serialization. Both would be very useful for my current application.
I haven't checked this yet. There should be some kind of basic interoperability through (segment) iterators and element_iterators.
I'm not sure what you mean by basic operability. I would like to take the hash value of an interval and serialize intervals, interval sets and interval maps. I think this is a suitable way to make intervals hashable: // // Make intervals hashable. // namespace boost { namespace itl { template< class DomainT , ITL_COMPARE Compare
std::size_t hash_value( interval< DomainT, Compare > const & x ) { std::size_t seed = 0; boost::hash_combine( seed, x.lower() ); boost::hash_combine( seed, x.upper() ); return seed; } } // namespace itl } // namespace boost
John Reid wrote:
Joachim Faulhaber wrote:
So it might be better to have both continuous and discrete intervals as right-open by default and to allow some mechanism whereby the user can choose to allow different runtime bound types if they need them.
I agree, that right-open intervals are suitable as default. But I am afraid, for the continuous case, we can not guarantee that all operations can maintain such an invariant. BTW existing interval libraries e.g. boost::numeric::interval or FILIB++ work with closed intervals. Subtract a closed interval from an interval set with continuous domain_type and you need open bounds.
I was suggesting that your design could feature sets/maps that only had right-open intervals. This would be the default in both continuous and discrete domains. If the user really wanted to use all the different interval bound types over a continuous domain then perhaps he/she could choose to do so via a template parameter. This would probably be a rare use case though.
I should just say that I think all the invariants can be maintained in sets of right-open intervals. Please correct me if I'm wrong.
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
John Reid wrote:
Joachim Faulhaber wrote:
So it might be better to have both continuous and discrete intervals as right-open by default and to allow some mechanism whereby the user can choose to allow different runtime bound types if they need them.
I agree, that right-open intervals are suitable as default. But I am afraid, for the continuous case, we can not guarantee that all operations can maintain such an invariant. BTW existing interval libraries e.g. boost::numeric::interval or FILIB++ work with closed intervals. Subtract a closed interval from an interval set with continuous domain_type and you need open bounds.
I was suggesting that your design could feature sets/maps that only had right-open intervals. This would be the default in both continuous and discrete domains. If the user really wanted to use all the different interval bound types over a continuous domain then perhaps he/she could choose to do so via a template parameter. This would probably be a rare use case though.
I should just say that I think all the invariants can be maintained in sets of right-open intervals. Please correct me if I'm wrong.
I think it can be maintained for intervals of integral domain_types but it can not be maintained for intervals of continuous domain_types. To be more accurate: I have my doubts if it can be maintained and to be even more precise: I don't know if it can be maintained in this case, without loss of generality or correctness of the implementation. For discrete domain_type at least, I am prepared to provide it. Joachim.
Joachim Faulhaber wrote:
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
John Reid wrote:
Joachim Faulhaber wrote:
So it might be better to have both continuous and discrete intervals as right-open by default and to allow some mechanism whereby the user can choose to allow different runtime bound types if they need them. I agree, that right-open intervals are suitable as default. But I am afraid, for the continuous case, we can not guarantee that all operations can maintain such an invariant. BTW existing interval libraries e.g. boost::numeric::interval or FILIB++ work with closed intervals. Subtract a closed interval from an interval set with continuous domain_type and you need open bounds. I was suggesting that your design could feature sets/maps that only had right-open intervals. This would be the default in both continuous and discrete domains. If the user really wanted to use all the different interval bound types over a continuous domain then perhaps he/she could choose to do so via a template parameter. This would probably be a rare use case though.
I should just say that I think all the invariants can be maintained in sets of right-open intervals. Please correct me if I'm wrong.
I think it can be maintained for intervals of integral domain_types but it can not be maintained for intervals of continuous domain_types. To be more accurate: I have my doubts if it can be maintained and to be even more precise: I don't know if it can be maintained in this case, without loss of generality or correctness of the implementation.
Given a set of right-open intervals, I can't think of any operation on that set with an operand of another set of half-open intervals that would invalidate the invariant. I wonder how often a user will want to insert/erase individual elements in a continuous domain. If there was an implementation for continuous domains that did not allow this, users could take advantage of more efficient interval data structures that were all right-open. I don't think that would preclude the provision of an interface that supported inserting/erasing individual elements. I'm interested to read the report you mentioned on your plan for an interval tree implementation. Unfortunately though I'm going on holiday tomorrow so I'll miss the end of this review and perhaps your report. Thanks for taking the time to submit ITL. It is proving very useful. Regards, John.
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
Joachim Faulhaber wrote:
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
John Reid wrote:
Joachim Faulhaber wrote:
So it might be better to have both continuous and discrete intervals as right-open by default and to allow some mechanism whereby the user can choose to allow different runtime bound types if they need them.
I agree, that right-open intervals are suitable as default. But I am afraid, for the continuous case, we can not guarantee that all operations can maintain such an invariant. BTW existing interval libraries e.g. boost::numeric::interval or FILIB++ work with closed intervals. Subtract a closed interval from an interval set with continuous domain_type and you need open bounds.
I was suggesting that your design could feature sets/maps that only had right-open intervals. This would be the default in both continuous and discrete domains. If the user really wanted to use all the different interval bound types over a continuous domain then perhaps he/she could choose to do so via a template parameter. This would probably be a rare use case though.
I should just say that I think all the invariants can be maintained in sets of right-open intervals. Please correct me if I'm wrong.
I think it can be maintained for intervals of integral domain_types but it can not be maintained for intervals of continuous domain_types. To be more accurate: I have my doubts if it can be maintained and to be even more precise: I don't know if it can be maintained in this case, without loss of generality or correctness of the implementation.
Given a set of right-open intervals, I can't think of any operation on that set with an operand of another set of half-open intervals that would invalidate the invariant.
I wonder how often a user will want to insert/erase individual elements in a continuous domain. If there was an implementation for continuous domains that did not allow this, users could take advantage of more efficient interval data structures that were all right-open. I don't think that would preclude the provision of an interface that supported inserting/erasing individual elements.
I'm interested to read the report you mentioned on your plan for an interval tree implementation. Unfortunately though I'm going on holiday tomorrow so I'll miss the end of this review and perhaps your report.
Thanks for taking the time to submit ITL. It is proving very useful.
Thanks, that good to hear :) Sorry I am already late ;-/ More on the tomorrow. Cheers, Joachim
Hi John, yesterday I was in a hurry, so I wasn't able to continue this interesting discussion with you. In my last reply I didn't even notice you are going to go on holidays so you won't be able to follow the thread today. I don't think this is a big problem, since I am not planning to stop being open for suggestion after the review ;-) 2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
Joachim Faulhaber wrote:
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
John Reid wrote:
Joachim Faulhaber wrote:
So it might be better to have both continuous and discrete intervals as right-open by default and to allow some mechanism whereby the user can choose to allow different runtime bound types if they need them.
I agree, that right-open intervals are suitable as default. But I am afraid, for the continuous case, we can not guarantee that all operations can maintain such an invariant. BTW existing interval libraries e.g. boost::numeric::interval or FILIB++ work with closed intervals. Subtract a closed interval from an interval set with continuous domain_type and you need open bounds.
I was suggesting that your design could feature sets/maps that only had right-open intervals. This would be the default in both continuous and discrete domains. If the user really wanted to use all the different interval bound types over a continuous domain then perhaps he/she could choose to do so via a template parameter. This would probably be a rare use case though.
I should just say that I think all the invariants can be maintained in sets of right-open intervals. Please correct me if I'm wrong.
I think it can be maintained for intervals of integral domain_types but it can not be maintained for intervals of continuous domain_types. To be more accurate: I have my doubts if it can be maintained and to be even more precise: I don't know if it can be maintained in this case, without loss of generality or correctness of the implementation.
Given a set of right-open intervals, I can't think of any operation on that set with an operand of another set of half-open intervals that would invalidate the invariant.
I wonder how often a user will want to insert/erase individual elements in a continuous domain. If there was an implementation for continuous domains that did not allow this, users could take advantage of more efficient interval data structures that were all right-open. I don't think that would preclude the provision of an interface that supported inserting/erasing individual elements.
Thank you for insisting =) I wasn't open to consider the possibility of sacrificing some functionality that I had considered being fundamental in my design. But since you were reiterating your point, I began to see that such a sacrifice can be relatively small and enable, on the other hand, a use case, with a simplified interval type and simplified interval containers that would serve an important class of use cases while leaving out a minor one. The loss of generality here: We won't be able to express singleton intervals for continuous domain_types [x,x]. Every interval [x,y) would be empty, if y<=x, or infinite, if x<y. So we would also have to sacrifice the possibility to perform additions, subtraction etc. of *element*, since elements would have to be expressed via closed intervals [x,x]. This is interesting and I am going to consider this thoroughly. Since I am going to rework my interval concept due to the suggestions of Jeff Flinn and Luke Simonson anyway, I think I can integrate your suggestion as well.
I'm interested to read the report you mentioned on your plan for an interval tree implementation. Unfortunately though I'm going on holiday tomorrow so I'll miss the end of this review and perhaps your report.
I wish you nice holidays then :)
Thanks for taking the time to submit ITL. It is proving very useful.
Thank you again for your review and your substantial contributions on this discussion. Joachim.
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
The default interval type is closed. Isn't right-open a more natural choice for most applications?
Good question ... I tried to change this in the past but encountered problems with unsigned integral domain types that flipped to max_int by singular applications of decrement operator -- in the current implementation. May be I should check this point more thoroughly again. I could get rid of the unloved unon<T>() meta function. ...
You seem to suggest you apply operator-- on integral domains here. Why not make the distance between intervals available when the domain is integral? This would be similar to the availability of first and last when the domain is discrete.
For all of the interval functions it turns out, that the functionality that I offer, which does not include interval arithmetics, only needs very few basic operations: <, ++, and -- on the the bound members of type domain_type. This keeps the requirements on my Interval parameter minimal and allows for a greater class of instance_types for parameter domain_type. I know, that I am not completely consequent here. Functions length() and cardinality() use operator - . But if you don't need to call them, you can work with more primitive domain_type. Regards, Joachim
Joachim Faulhaber wrote:
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
The default interval type is closed. Isn't right-open a more natural choice for most applications? Good question ... I tried to change this in the past but encountered problems with unsigned integral domain types that flipped to max_int by singular applications of decrement operator -- in the current implementation. May be I should check this point more thoroughly again. I could get rid of the unloved unon<T>() meta function. ... You seem to suggest you apply operator-- on integral domains here. Why not make the distance between intervals available when the domain is integral? This would be similar to the availability of first and last when the domain is discrete.
For all of the interval functions it turns out, that the functionality that I offer, which does not include interval arithmetics, only needs very few basic operations: <, ++, and -- on the the bound members of type domain_type. This keeps the requirements on my Interval parameter minimal and allows for a greater class of instance_types for parameter domain_type.
I know, that I am not completely consequent here. Functions length() and cardinality() use operator - . But if you don't need to call them, you can work with more primitive domain_type.
For my uses I would like to see a method to calculate the distance between 2 intervals available when the domain supports it. I feel many users are going to write this functionality themselves. Also a method to return the gap between 2 intervals would be useful. Just my 2 cents.
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
Joachim Faulhaber wrote:
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
The default interval type is closed. Isn't right-open a more natural choice for most applications?
Good question ... I tried to change this in the past but encountered problems with unsigned integral domain types that flipped to max_int by singular applications of decrement operator -- in the current implementation. May be I should check this point more thoroughly again. I could get rid of the unloved unon<T>() meta function. ...
You seem to suggest you apply operator-- on integral domains here. Why not make the distance between intervals available when the domain is integral? This would be similar to the availability of first and last when the domain is discrete.
For all of the interval functions it turns out, that the functionality that I offer, which does not include interval arithmetics, only needs very few basic operations: <, ++, and -- on the the bound members of type domain_type. This keeps the requirements on my Interval parameter minimal and allows for a greater class of instance_types for parameter domain_type.
I know, that I am not completely consequent here. Functions length() and cardinality() use operator - . But if you don't need to call them, you can work with more primitive domain_type.
For my uses I would like to see a method to calculate the distance between 2 intervals available when the domain supports it. I feel many users are going to write this functionality themselves. Also a method to return the gap between 2 intervals would be useful. Just my 2 cents.
I dont't have a problem adding these functions. Best regards, Joachim
Joachim Faulhaber wrote:
What is the meaning of the cardinality of a continuous interval? It seems to be defined to be 0? Why not make it only available for discrete domains?
Try this:
interval<double> x(0.0, 1.0); if(x.cardinality() == numeric_limits<interval<double>::size_type>::infinity()) cout << "cardinality is infinite\n";
for doubles a, b with a < b: [a,b).cardinality() == infinity but {[a,a],[b,b]}.cardinality() == 2
Function cardinality() has been introduced to make clear: This function yields the number of *elements*, and not the number of iteratable entities in the interval container. For continuous domain_types the cardinality of an interval container can be infinite but it can be finite as well.
This seems to make the cardinality of empty intervals infinite! I get this output from the code below: empty interval cardinality is 0 empty interval cardinality is infinite unit interval cardinality is 0 unit interval cardinality is infinite singleton interval cardinality is 1 { const interval< double > empty_interval; cout << "empty interval cardinality is " << empty_interval.cardinality() << "\n"; if( empty_interval.cardinality() == numeric_limits< interval< double
::size_type >::infinity() ) cout << "empty interval cardinality is infinite\n"; }
{ const interval< double > unit_interval( 0.0, 1.0 ); cout << "unit interval cardinality is " << unit_interval.cardinality() << "\n"; if( unit_interval.cardinality() == numeric_limits< interval< double
::size_type >::infinity() ) cout << "unit interval cardinality is infinite\n"; }
{ const interval< double > singleton_interval( 0.0 ); cout << "singleton interval cardinality is " << singleton_interval.cardinality() << "\n"; if( singleton_interval.cardinality() == numeric_limits< interval< double >::size_type >::infinity() ) cout << "singleton interval cardinality is infinite\n"; } Do you agree this is potentially confusing?
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
Joachim Faulhaber wrote:
What is the meaning of the cardinality of a continuous interval? It seems to be defined to be 0? Why not make it only available for discrete domains?
Try this:
interval<double> x(0.0, 1.0); if(x.cardinality() == numeric_limits<interval<double>::size_type>::infinity()) cout << "cardinality is infinite\n";
for doubles a, b with a < b: [a,b).cardinality() == infinity but {[a,a],[b,b]}.cardinality() == 2
Function cardinality() has been introduced to make clear: This function yields the number of *elements*, and not the number of iteratable entities in the interval container. For continuous domain_types the cardinality of an interval container can be infinite but it can be finite as well.
This seems to make the cardinality of empty intervals infinite! I get this output from the code below:
empty interval cardinality is 0 empty interval cardinality is infinite unit interval cardinality is 0 unit interval cardinality is infinite singleton interval cardinality is 1
{ const interval< double > empty_interval; cout << "empty interval cardinality is " << empty_interval.cardinality() << "\n"; if( empty_interval.cardinality() == numeric_limits< interval< double >::size_type >::infinity() ) cout << "empty interval cardinality is infinite\n"; }
{ const interval< double > unit_interval( 0.0, 1.0 ); cout << "unit interval cardinality is " << unit_interval.cardinality() << "\n"; if( unit_interval.cardinality() == numeric_limits< interval< double >::size_type >::infinity() ) cout << "unit interval cardinality is infinite\n"; }
{ const interval< double > singleton_interval( 0.0 ); cout << "singleton interval cardinality is " << singleton_interval.cardinality() << "\n"; if( singleton_interval.cardinality() == numeric_limits< interval< double >::size_type >::infinity() ) cout << "singleton interval cardinality is infinite\n"; }
Well, I've looked at my code. It looks correct. The problem seems to be, that numeric_limits< interval<double >::size_type >::infinity() maps infinity() to 0. if(numeric_limits< std::size_t >::infinity()==0) cout << "infinity()==0"; Sine the test code, that I have done for that only checks for that value numeric_limits< interval<double >::size_type >::infinity() against cardinality(), I didn't detect the problem. Is there a standard way to deal with this kind of problem? Regards, Joachim
AMDG Joachim Faulhaber wrote:
Well, I've looked at my code. It looks correct. The problem seems to be, that numeric_limits< interval<double >::size_type >::infinity() maps infinity() to 0.
if(numeric_limits< std::size_t >::infinity()==0) cout << "infinity()==0";
Sine the test code, that I have done for that only checks for that value numeric_limits< interval<double >::size_type >::infinity() against cardinality(), I didn't detect the problem.
Is there a standard way to deal with this kind of problem?
Check numeric_limits<...>::has_infinity? 18.2.1.2: "static T infinity() throw(); Representation of positive infinity, if available. Meaningful for all specializations for which has_infinity != false. Required in specializations for which is_iec559 != false." In Christ, Steven Watanabe
2010/3/4 Steven Watanabe <watanabesj@gmail.com>:
AMDG
Joachim Faulhaber wrote:
Well, I've looked at my code. It looks correct. The problem seems to be, that numeric_limits< interval<double >::size_type >::infinity() maps infinity() to 0.
if(numeric_limits< std::size_t >::infinity()==0) cout << "infinity()==0";
Sine the test code, that I have done for that only checks for that value numeric_limits< interval<double >::size_type >::infinity() against cardinality(), I didn't detect the problem.
Is there a standard way to deal with this kind of problem?
Check numeric_limits<...>::has_infinity?
18.2.1.2: "static T infinity() throw(); Representation of positive infinity, if available. Meaningful for all specializations for which has_infinity != false. Required in specializations for which is_iec559 != false."
Thank you, Steven :) Joachim.
John Reid wrote:
I have some further unrelated design questions/points:
From what I understand of the documentation, the following code should return an intersection of the 2 maps performing addition on the values where the maps overlap. #include <boost/itl/interval_map.hpp> using namespace boost::itl; int main( int argc, char * argv[] ) { interval_map< int, float > map_1; interval_map< int, float > map_2; map_1 & map_2; return 0; } I get a compile error on gcc 4.4.1 complaining about "invalid operands of types ‘float’ and ‘const float’ to binary ‘operator &’". Is this a bug or did I get the wrong end of the stick?
John Reid wrote:
From what I understand of the documentation, the following code should return an intersection of the 2 maps performing addition on the values where the maps overlap.
#include <boost/itl/interval_map.hpp>
using namespace boost::itl;
int main( int argc, char * argv[] ) {
interval_map< int, float > map_1; interval_map< int, float > map_2;
map_1 & map_2;
return 0; }
I get a compile error on gcc 4.4.1 complaining about "invalid operands of types ‘float’ and ‘const float’ to binary ‘operator &’". Is this a bug or did I get the wrong end of the stick?
I see now that this works for ints: there is no compile error when the type is interval_map< int, int >.
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
John Reid wrote:
I have some further unrelated design questions/points:
From what I understand of the documentation, the following code should return an intersection of the 2 maps performing addition on the values where the maps overlap.
#include <boost/itl/interval_map.hpp>
using namespace boost::itl;
int main( int argc, char * argv[] ) {
interval_map< int, float > map_1; interval_map< int, float > map_2;
map_1 & map_2;
return 0; }
I get a compile error on gcc 4.4.1 complaining about "invalid operands of types ‘float’ and ‘const float’ to binary ‘operator &’". Is this a bug or did I get the wrong end of the stick?
You obviously found a problem here. The compiler does not infer the right argument type. I am going to check this, but probably not today. Thanks for investigating my library. Regards, Joachim
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
John Reid wrote:
I have some further unrelated design questions/points:
From what I understand of the documentation, the following code should return an intersection of the 2 maps performing addition on the values where the maps overlap.
#include <boost/itl/interval_map.hpp>
using namespace boost::itl;
int main( int argc, char * argv[] ) {
interval_map< int, float > map_1; interval_map< int, float > map_2;
map_1 & map_2;
return 0; }
I get a compile error on gcc 4.4.1 complaining about "invalid operands of types ‘float’ and ‘const float’ to binary ‘operator &’". Is this a bug or did I get the wrong end of the stick?
Found the culprit :) Although never actually called for this instantiation, interval_map< int, float >, the intersection functor is set to inplace_et and appears in the code that is called when map_1 & map_2; is applied. I have added partial instantiations for inplace_et<float>. This is a quickfix, but fully fuctional. The more proper fix will be done within the next days. You can update file https://svn.boost.org/svn/boost/sandbox/itl/boost/itl/functors.hpp from the sandbox to get the fix. Thanks, Joachim
Joachim Faulhaber wrote:
2010/3/3 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
Some functions were undocumented, I'm assuming they're documented in the review version.
The "handcrafted" documentation relates to the major interface of overloaded functions and function templates. In order to keep that short, more specific functions are only documented in the part of the documentation that is generated from doxygen comments: http://www.joachim-faulhaber.de/boost_itl/doc/libs/itl/doc/html/interval_tem...
And yes, there may be few that have been forgotten. Please tell me, which ones you missed specifically.
For example in interval_base_map.html the std::map-like methods are undocumented. I can always look these up in any std::map reference although it would be nice if the docs were complete.
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
Joachim Faulhaber wrote:
2010/3/3 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
Some functions were undocumented, I'm assuming they're documented in the review version.
The "handcrafted" documentation relates to the major interface of overloaded functions and function templates. In order to keep that short, more specific functions are only documented in the part of the documentation that is generated from doxygen comments:
http://www.joachim-faulhaber.de/boost_itl/doc/libs/itl/doc/html/interval_tem...
And yes, there may be few that have been forgotten. Please tell me, which ones you missed specifically.
For example in interval_base_map.html the std::map-like methods are undocumented. I can always look these up in any std::map reference although it would be nice if the docs were complete.
Agreed, I put it on my todo list.
participants (4)
-
Jeff Flinn -
Joachim Faulhaber -
John Reid -
Steven Watanabe