At 8:44 AM -0400 10/8/02, John Cowan wrote:
>The underlying data structure here is called a "range table", and is >a list of ranges in codepoint order, expressed thus: > > start of first range > end of first range + 1 > start of second range > end of second range + 1 > >etc. etc. What you are doing is equivalent to a linear search over >this range followed by loop unrolling. However, you can do better, >especially in complex cases, with a *binary* search over the range >followed by loop unrolling. The trick here is that if the binary >search returns an even value, it succeeds; an odd value fails. > Interesting. Do you have any references on that I can explore further? A quick google search didn't turn up anything relevant. I'm curious to see how the algorithm actually works. -- +-----------------------+------------------------+-------------------+ | Elliotte Rusty Harold | [EMAIL PROTECTED] | Writer/Programmer | +-----------------------+------------------------+-------------------+ | XML in a Nutshell, 2nd Edition (O'Reilly, 2002) | | http://www.cafeconleche.org/books/xian2/ | | http://www.amazon.com/exec/obidos/ISBN%3D0596002920/cafeaulaitA/ | +----------------------------------+---------------------------------+ | Read Cafe au Lait for Java News: http://www.cafeaulait.org/ | | Read Cafe con Leche for XML News: http://www.cafeconleche.org/ | +----------------------------------+---------------------------------+
