[boost] [Review:Algorithms] My review of Boost.Algorithm

Subject: [boost] [Review:Algorithms] My review of Boost.Algorithm
From: Lorenzo Caminiti (lorcaminiti_at_[hidden])
Date: 2011-09-29 23:16:17

Review of Boost.Algorithm 2011-09-29 - Lorenzo Caminiti
==============================

Do you think the library should be accepted as a Boost library?
------------------------------

Yes, in my opinion Boost.Alrogithm should be accepted as a Boost library.

Key points are:

a) I would find the library usefull as is, especially for all_of_equal
and for the search algorithms.

b) I would like to see more algorithms supported into the library in
the (near) future (IMO the "only" non-trivial algorithms currently
offered are the 3 search algorithms).

c) The documentation (which is clear and straightforward) should list
more examples.

My comments below are all numbered an marked as:
[MUST] If these comments are not addressed, I would no longer
recommend this library for addition to Boost.
[WANT] I would like to see these comments addressed (at least replied
to) but I would recommend this library for addition to Boost
regardless.
[NOTE] I do not feel strongly about these comments and they can be ignored.

What is your evaluation of the design?
------------------------------

1) [WANT] Could all/any/none/one_of_equal be made more general and
merged with all/any/none/one_of by accepting a binary predicate via
overloading?

template<typename InputIterator, typename UnaryPred>
bool all_of ( InputIterator first, InputIterator last, Pred p );

template<typename InputIterator, typename BinaryPred, typename V>
bool all_of ( InputIterator first, InputIterator last, BinaryPred p, V
const& v );

// could even overload for ternary, etc predicates

bool BOOST_LOCAL_FUNCTION_PARAMS(int x) {
    return x > 0;
} BOOST_LOCAL_FUNCTION_NAME(positive)

int a[3] = {2, 2, 2};
all_of(a, a + 3, positive); // existing form
all_of(a, a + 3, std::equal_to<int>(), 2); // instead of all_of_equal
all_of(a, a + 3, std::less<int>(), 10); // can also do this now :) not
just equal

BTW, you can use Boost.Local to define the predicate functions at local scope ;)

2) [NOTE] Is there a (run-time) cost with the destruction of the
tables used by Boyer-Moore and the other search algorithms? If so, is
the same cost encountered by both the object and functional version of
the algorithms? (BTW, it made sense to me to have both an object and
function version of the algorithms.)

3) [MUST] There should be a range version for all search algorithms
(unless it's not possible for some reason that I can't foresee).

4) [WANT] When using the object interface, is the caller responsible
to keep the pattern in scope until the search object is destructed?
Either way, this requirement should be clearly documented.

5) [NOTE] I'd be OK with any renaming of is_order based on other's
opinions-- I'd follow C++11 if at all possible (is_sorted_until?). (No
comment on clamp's argument ordering ;) .)

What is your evaluation of the implementation?
------------------------------

6) I very quickly read through the code. It looks clean and well
organized... the iterator algorithms made sense. I did not study the
search algorithm implementation close enough to comment on it.

What is your evaluation of the documentation?
------------------------------

7) [WANT] Please add more examples to the docs (you can take a few
from the ones you already have in examples and tests).

8) [WANT] Always state complexity guarantees (they are mentioned in
docs section but not in the code reference section).

9) [WANT] Are these examples from the docs incorrect? (What's 3, 9, etc?)

one_of ( c.begin (), c.end (), 3 ) --> true
one_of ( c, 3 ) --> true
none_of ( c, 9 ) --> true
any_of ( c.begin (), c.end (), 9 ) --> false

10) [WANT] Typos that I noted in the docs:

* "are will" in "Since they have to return a place in the input
sequence, input iterators are will not suffice".
* check indentation of close `};` for `class boyer_moore`.
* "and here are the corresponding procedural interface:" should say
and "here is".

11) [WANT] Extend document of Boyer-Moore-Horspool and/or
Knuth-Morris-Pratt with class code, etc to match docs of Boyer-Moore
(interface is listed in the code reference section but not in the
search algorithm section).

What is your evaluation of the potential usefulness of the library?
------------------------------

12) I would find the library useful as is (especially, for the handy
all_of_equal and faster searches) but I would like to see more
algorithms supported by the library in the near future. IMO,
any/none/one/all and clamp are nice utilities, same goes for the
ordered stuff, but at the end I got the sense that the search
algorithms were the "only" real meat of the library.

Did you try to use the library? With what compiler? Did you have any problem?
------------------------------

13) Yes, I compiled all examples and tests on GCC 4.3.4 under Cygwin
(BTW, in all_example.cpp rename all_of_val to all_of_equal). I got
some warnings on MVSC 10 under Windows (see attached file).

How much effort did you put into your evaluation? A glance? A quick
reading? In-depth study?
------------------------------

14) I'd say a quick reading, I spent about 7 hours on it. I red all
the docs and compiled all the examples (at least on GCC).

Are you knowledgeable about the problem domain?
------------------------------

15) Thankfully, not anymore ;) but reading the docs reminded of my
class work on Boyer-Moore and variations-- it was a while ago. I'd say
I am marginally familiar with the problem domain.

--Lorenzo