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

Subject: Re: [boost] [Review:Algorithms] My review of Boost.Algorithm
From: Marshall Clow (mclow.lists_at_[hidden])
Date: 2011-09-29 23:39:21

On Sep 29, 2011, at 8:16 PM, Lorenzo Caminiti wrote:

> 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.

Thanks!

> 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 );

I think that bind handles this for us:
        all_of ( first, last, bind ( pred, _1, v ))  ?

> 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.)

Yes, there is a run time cost with the destruction of the tables. For the vector-based tables, it's a single memory allocation.
For the unordered_map based ones, it would be several allocations (how many depends on the implementation of unordered_map)
For custom skip tables, it would depend on the skip table.

And yes, the cost is the same for both the object and the functional versions.

> 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).

I don't think that this will be a problem.

> 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.

Yes. And I will make sure that this is documented.
I suppose that I could make a version that keeps a copy of the pattern, but I'm not really fond of that idea.

> 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 ;) .)

I really dislike the name "is_ordered_until", but if people are united in favoring that name, I can live with it.

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

That's on the list of documentation changes ;-)
        https://github.com/mclow/Boost.Algorithm/issues/10

> 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

Right before these examples is:
        Examples: Given the container c containing { 0, 1, 2, 3, 4, 5 }, then

I guess I need to make that more noticeable.

> 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".

Fixed.

> 
> 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).

OK.
Added to: https://github.com/mclow/Boost.Algorithm/issues/9

Thanks again!

-- Marshall

Marshall Clow     Idio Software   <mailto:mclow.lists_at_[hidden]>

A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
        -- Yu Suzuki