Re: [Qexo-general] Re: TreeList implementation

[Per Bothner]

Joseph Coffland wrote:

> My point about TreeList is that without the ability to move the gap I
> don't see the point in having the gap at all.

"Ability" is a matter of implementation.  The data structure and code
supports moving the gap.  However, I have not implemented that yet,
because I have not needed to.

The data structure is carefully designed to use relative offset so
that when you move the gap most of the "pointers" (i.e. offsets)
don't need to change.  Actually implementing the methods to move
the gap is not a big deal, though it would require care.

> Also, like you said it is inefficient for certain  operations.

All data structures involve tradeoffs.  For example with NodeTree it
is inefficient to get the parent of a text node.  Is that important?
Probably not.  Efficiently getting the next sibling of a node probably
is important, so we may want to make sure all text nodes include an
explicit count, rather than just be a sequence of characters.

I.e. the TreeList/NodeTree classes could do with some fine tuning.
That does not mean replacing them with something completely different,
unless you existing (and license-compatible) working code that is
clearly an improvement.

> It might be nice to optionally support Xerces DOM.  There are some nice
> side affects
> to this.  1) You can enforce schema compliance.  2) PSVI information is
> already 
> integrated.  3) It allows modification.  4) It's more efficient for some
> operations
> like "$node/..".

However, it does require multiple objects per node, and so requires
much more space and probably more time for typical XQuery operations.

Making it optional is difficult.  The current implementation assumes
a node is defined by a (AbstractSequence, int)-pair, and (to a lesser
extent) that the AbstractSequence is a NodeTree where nodes in the same
document (fragment) are all in the same NodeTree.  It is possible for
Qexo to be modified to assume a Node is a pointer, but that requires
generating different bytecode, which would be less efficient when
using a NodeTree.

It might be nice to have a compile-time option to generate code
optimized for either (AbstractSequence, int) or Node, and allowing
(less efficient) run-time conversion so you can access a Node using
the (AbstractSequence, int) API and vice versa.
--
        --Per Bothner
address@hidden   http://per.bothner.com/