Are TextRuns always sorted?

[Matt Newell]

On Thursday 07 August 2003 10:13, Dirk Mueller wrote:
> On Don, 07 Aug 2003, Leo Savernik wrote:
> > I looked at it, but this works for coordinates. I need it for offsets.
> > I'm using RenderText::findTextSlave which returns the appropriate text
> > slave for an offset into the string data, and I want to optimize it by
> > binary search, that's why I'm asking.
>
> Yeah, well the TextSlaves are sorted visually, which has little to do with
> the string order in the general case.
>
> you can still do a "fuzzy" binary search but an exact binary search will
> not work. I assume that you're looking into optimising text selection?
>
> I've seen that the safari tree attempted to do something like that but I
> don't know how they made it work yet (or if they simply ignored the bidi
> problems).

I've sent this patch before.  It fixes one of the problems wrt text selection 
speed.  In khtmlPart::htmlMouseMoveEvent, after the selection nodes are 
found, it currently does a linear search from the first node to either the 
end, or the second node, whichever comes first.  This means that selecting 
from right to left on a large page causes an unnecessary traversal of the 
tree for every pixel that the mouse is moved.  My patch finds the first 
common anscestor of each node, and then iterates through its children to see 
which comes first.

Simply put, the worst case complexity of that function goes from O(n) to 
O(depth of tree).


Matt