On Mon, 2008-03-24 at 11:25 +0100, Henrik Nordstrom wrote: > On Sun, 2008-03-23 at 18:29 +0900, Adrian Chadd wrote: > > > The real solution is a tree for offset lookups, and a linear walk of order > > O(1) for subsequent sequential accesses. > > Walking a tree is usually a cheap operation, unless the tree is wrongly > designed. You just need to remember the current tree node to enable > linear walk from there. > > But it's true splay trees is not the appropriate lookup structure for > this. To much runtime churn with the tree rebalancing itself..
I believe this to be the case, however as the code only uses the tree interface, it should be easy to substitute in a different tree ADT here. -Rob -- GPG key available at: <http://www.robertcollins.net/keys.txt>.
signature.asc
Description: This is a digitally signed message part