Hacker News Reader

Comment by c-smile | Hacker News Reader

Interesting, from libHTML:

    class Node {
      Vector<Node*> m_children;
      Node* m_next_sibling { nullptr };
      Node* m_previous_sibling { nullptr };
    }

Either m_children or m_next_sibling/m_previous_sibling are clearly superfluous.

m_children + m_parent are enough for tree representation.

View on HN

You usually keep next/previous sibling to speed up iteration

See: http://aosabook.org/en/posa/parsing-xml-at-the-speed-of-ligh...

You can store index of the node in parent m_children collection.

Iteration on array is faster (cache locality) than DL list traversal. And there are issues when you traverse tree while changing it.

In any case I've found that storing child nodes as m_children collection is more convenient in many cases. At least in Sciter (https://sciter.com).

    struct node {
      weak_ref<element> m_parent;
      uint              m_node_index;
    }

    struct element : node {
      vector<ref<node>> m_children; // strict ownership, sic!
   }

Unless sibling is sideways (same level of the tree) and children is downward (one level closer to the leaves).

I haven't looked at the code but that's my first impression given the nomenclature.

No, you didn't get it.

You may have children accounted as DL list and so each Node should have m_next / m_previous node references. + Parent node to have m_first_child reference (if list is circular). + m_parent (Node) reference.

So you need 4 pointers per each non-terminal node. Or 3 pointers for terminals.

Otherwise (vector of children):

You need only m_parent (Node) reference in terminals. And in container nodes additional vector<NodePtr> m_children; to store child references.

You don’t need parent because you can use a breadcrumb stack to track parents.

You want sibling nodes otherwise you will have to traverse back to the root node sometimes to find a sibling.

> You don’t need parent

You do need parent, check this: https://developer.mozilla.org/en-US/docs/Web/API/Node/parent...

> You want sibling nodes otherwise you will have to traverse back to the root node sometimes to find a sibling.

The only need for this is in Node.nextSibling implementation: https://developer.mozilla.org/en-US/docs/Web/API/Node/nextSi...

Where vector<>::find is pretty sufficient.

But in reality (at least in my Sciter) node stores its index in parent's m_children so it is O(1) operation.

How about the + operator in CSS?

And what is wrong with it?

and ~ combinator and :nth-child(n) selector for that matter too.

I'm responding to the claim that you only need the ability to find a sibling for the nextSibling method.

Is there source code available online illustrating your more-efficient DOM data-structure ?

Reply on news.ycombinator.com