Search algorithms in __gnu_cxx::

[Dhruv Matani]

On 9/15/06, Paolo Carlini <pcarlini@suse.de> wrote:
> Dhruv Matani wrote:
> >> __is_char which we
> >> already have, and so on,
> > Where???? I did a complete grep -r "__is_char" . and didn't find
> > anything. Is it under some other name?

> Of course, because you are not following our public and private
> recommendations that new features must be developed first vs *mainline*.

Ok, then I'll submit a patch for this first.

> Then, please cite the bibliographic reference for this variant and
> follow it in detail. Alternately, you can implement one among the well
> known variants in that web page (or elsewhere), there are no other
> options, sorry.

On this page:
http://www.movsd.com/bm.htm
you can find a complete description of the 3 different kinds of tables
which _may_ be used in any Boyer Moore algorithm implementation. I am
using the Good Character & Bad Character shift tables ONLY. As you can
see from the description, that's perfectly fine to do.

>
> Also, I think we have to do something for that unordered_map, I don't
> think covering the general case via lookups in a map leads to something
> close to the original spirit, in any possible sense...

Nope, it doesn't because the algorithm wasn't meant for any search,
but was designed for string searching in particular. Hence the use of
the static tables, etc.... However, using the unordered_map<> as an
approximation to preserve generality will only hurt the performance
and not the correctness. Again, since this is an extension, people
will use it only for strings if we document it accordingly.


Regards,
-Dhruv.





-- 
   -Dhruv Matani.
http://www.geocities.com/dhruvbird/

"Life is wasted on the living"
  - Zaphod Beeblebrox the Fourth.