XOM API for Processing XML with Java

[Elliotte Rusty Harold <elharo AT metalab.unc.edu>]

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 | elharo AT metalab.unc.edu | 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/    |
+----------------------------------+---------------------------------+