[boost] [Review:Algorithms] - Review by Neil Groves

Subject: [boost] [Review:Algorithms] - Review by Neil Groves
From: Neil Groves (neil_at_[hidden])
Date: 2011-10-01 11:20:35

*Evaluation of the design.*

The design is pleasingly consistent with other algorithms with the exception
of clamp_range. The clamp_range function copies, which is inconsitent with
the other Boost string algorithms that have the _copy suffix. The
clamp_range feature would be better designed as a clamped range adaptor.

*Evaluation of the implementation*

Generally, the algorithms would benefit from concept checking. In particular
the iterator traversals, and range concept requirements should be checked.

The implementation of the functions in all.hpp and clamp.hpp are correctly
implemented. The clamp function does not provide the usual guarantees about
NaN values that most of the floating-point operations do. That is any one
argument being NaN does not guarantee a NaN result. This is probably
intended, if so a note should be made in the documentation.The argument
types may benefit from using call_traits to optimally chose between constant
reference and value types.

It might be worth considering an assertion that p(lo,hi) is true in the
clamp function.

The mixing of differing integer types makes the search algorithms defective.
The int type is signed, and typically <= the size of std::size_t yet these
are mixed. The skip table uses ints, but std::size_t values are inserted.
Certainly there should not be any c style casts. It would seem logical to
use the boost::iterator_difference<Iterator>::type instead. Currently these
algorithms are defective albeit under unusual conditions.

There are numerous invocations of non-member functions that should use
qualified calls to avoid accidental argument-dependent lookup.

range_const_iterator<Rng> has been deprecated in favour of
range_iterator<const Rng>

The Range versions of the functions should provide a non-const reference
version since there are no requirements for the interoperability of
range_iterator<const Range> and range_iterator<Range> although they normally
exist..

The tests have some defects with respect to dereferencing end iterators.

As others have mentioned there should be range versions of all of the
functions.

*Evaluation of the documentation*

The documentation should make very clear that the result for empty ranges
into all_of, any_of, none_of as this is currently ambiguous. The
documentation should provide more clear performance guarantees about the
number of predicate evaluations where this is possible eg. any_of can and
does early exit. The documentation should also provide the exception
guarantees.

*Evaluation of usefulness*

If corrected and properly documented these functions will be very useful.
The functions any_of etc. are extremely useful for runtime assertions of
pre- and post-conditions.

*Did I try to use the library?*

I used the library with GCC 4.6.1. I had no problems, although I did defect
the defects noted above.

*How much effort did I put into my evaluation?*

I reviewed the code for a couple of hours which was sufficient for the small
amount of code under review.

*Am I knowledgeable about the problem domain?*

Yes, I maintain Boost.Range hence my comments with respect to ranges are
reasonably well informed. I have long been a fan of Design by Contract and
hence I have experience using my own versions of the functions all_of etc.

I vote for inclusion into Boost if and only if:

1. the defects in the search functions and test are resolved

2. clamp_range is removed or replaced.

Regards,

Neil Groves