324176 - O(1) time access to random DOM node

Status: NEW

(Core :: DOM: Core & HTML, enhancement, P5)

Description

[Eyal Rozenberg]

I would like to be able to make O(1) time random samples of elements of a DOM tree. The minimal usable thing would be a random DOM element according to any distribution with full support. Any of the following, if done, would be more useful:

- Allow distribution with support only on leaves or DOM nodes of certain types.
- Allow a uniform distribution over candidate nodes.
- Allow a representation-length-uniform distribution over candidate nodes.
- Allow limiting the distribution to a subset of all the elements defined by a start and end fractions, i.e. "give me an node which is located, in preorder/postorder/inorder after at least a 0.2 fraction of the nodes and before a 0.4 fraction of them" (this can be simulated using a uniform distribution, but at a hefty price in the O() constants).
- Provide a O(1) time estimate of relative position of a node in a DOM tree (w.r.t. some order).

If you're wondering what this is good for, think: probabilistic heuristics on (very, but not necessarily all that) large documents.

Comment 1

[Firefox Bug Husbandry Bot]

https://bugzilla.mozilla.org/show_bug.cgi?id=1472046

Move all DOM bugs that haven’t been updated in more than 3 years and has no one currently assigned to P5.

If you have questions, please contact :mdaly.