RE: Equality tests on DOM nodes

>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.

We're getting way into implementation-specific details here, but in the
first proposed solution:  Suppose we are in an environment that requires us
to both be able to insert nodes quickly and obtain a node's order quickly
and we have a large number of nodes.  And we're implementing the first
solution.  There isn't really a reason that the number has to be an integer,
is there?  For quick insertion and ordering, we could very well keep two
integers, numerator and denominator, and if something belongs between 1/1
and 2/1 we just stick it at 1/2 rather than changing the numbers on the next
20000 nodes.  And then, later, when the system is taking a breather, we can
come back, lock the whole set of siblings, and rearrange the numbers?

Not that anyone actually implements things this way, probably for good
reason, but if I can't throw out crazy ideas here, where can I?

Paul

P.S.  Ray, you missed my point on the whole Object.equals thing.  My point
is that if we look to java for guidance (which must make *someone* out there
cringe :), than the way equals is implemented in String is the exception
rather than the norm.  I don't think nodes are like strings at all.

Received on Saturday, 12 December 1998 10:33:06 UTC