On Mar 31, 2011, at 10:08 AM, TONGARI wrote:
2011/3/31 Marshall Clow <mclow.lists@gmail.com>
(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@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki