Re: [boost] Proposed Library Boost.Algorithm

Subject: Re: [boost] Proposed Library Boost.Algorithm
From: Marshall Clow (mclow.lists_at_[hidden])
Date: 2011-03-31 13:30:44

On Mar 31, 2011, at 10:08 AM, TONGARI wrote:
> 2011/3/31 Marshall Clow <mclow.lists_at_[hidden]>
> 
>> (Finally) I have uploaded to the vault <
>> http://www.boostpro.com/vault/index.php?action=downloadfile&filename=Boost.Algorithm-008.zip&directory=Algorithms&>
>> a proposal for the Boost.Algorithm library.
>> 
> 
> Thanks for working on this!
> 
> I've taken a glimpse at your code, and I'd like to suggest to specify the
> requirement of the iterator explicitly, for example, RandomAccessIterator
> rather than 'patIter', and be sure to document these requirements clearly (I
> only saw them in comments).

I'll look into it.
Part of the problem here is that I don't want to lose the feature that the "pattern iterator" and the "corpus iterator" 
can be different types (as long as they point to the same underlying data type)

> 1) Three search algorithms: Boyer-Moore, Boyer-Moore-Horspool and
>> Knuth-Morris-Pratt. (search.hpp)
>> 
> 
> Recently I just implemented the KMP algorithm, and in my implementation, it
> requires the corpus iterator to be InputIterator for search to return a
> bool, and ForwardIterator to return the iterator, maybe you also want to
> lower down the requirement for RandomAccessIterator here?

Since I want to return the match, I think that InputIterators are out, but I'll look at ForwardIterator.

> To be more flexible in searching, it could also give a way to search all or
> some of the results up to a threshold, not just the first one.
> The interface may like what Regex provides (I'm not certainly sure), or it
> should let users provide a visitor for the resultant corpus iterators.

Since the search algorithms return an iterator to the start of the "found pattern", you can find all the matches in a loop:

//	uncompiled code warning!
        xxx search_obj ( pat_start, pat_end );		// choose your search object
        corpus_iterator it = corpus_start;
        do {
                if (( it = search_obj ( it, corpus_end )) == corpus_end )
                        break;
        //	do something with the match
                it++;
        } while (true);

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