Re: Equality tests on DOM nodes

Richard L. Lavallee wrote:

> Regarding the problem of comparing DOM nodes,
> one implementation solution is to assign a "DOM node identifier" (DNI)
> to each DOM node, and use these as the basis for comparison.
>
> A DNI is an integer, base 1, which monotonically increases up to the
> maximum number of nodes in a particular DOM.
> The root node DNI is assigned "1", and the remainder are assigned
> in pre-order.
>
> When nodes persist their DNI's persist with them, for any given
> version of the particular DOM instance.
>
> So:  how may any two DOM nodes be compared?
>
> Just examine their respective DNI's numerically.
>
> E.g.. a DOM node with DNI 42 is "==" to a DOM node with DNI 42.
>
> DNI_42 > DNI_5
>
> DNI_9 < DNI_12
>
> Of course, this works best for read-only DOM's;
> because arbitrary node insertion would disrupt the DNI sequencing.
> But I would argue that node insertion results in a new document version
> which necessarily has its own uniques set of DNI's anyway.

I think what you are proposing is yet another type of comparison function
that detects the order of two nodes in traversal order of the hierarchy.
This is a very useful function, too, which should be assigned to yet
another function.

I had to improve on the methodology you describe as follows to efficiently
manage a mutable (modifiable) hierarchy:

First, don't run the numbers continuously through the hierarchy, but rather
keep different sequences for each set of siblings.  Then, count the depth
of each node being compared, replace the node that is deeper with its
ancestor at the higher level, and go up the tree until you find the
siblings with the common ancestor.  Then, use the numbers to find the order
there.  But if you have large numbers of siblings, this is still a problem
shifting large ranges, potentially of millions of siblings.

So my final solution was to represent siblings in a btree, and then order
just within fixed-length btree nodes, so you never have to shift many at
all, and you can still compare quite rapidly.

Ray Whitmer

Received on Friday, 11 December 1998 18:22:25 UTC