We should unify various forms of tree traversal in DOM

Source/wtf/TreeNode.h

 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 32 matching lines @@
 //    FIXME: lifetime management could be parameterized so that ref counted implementations can be used.
 //  * It ASSERT()s invalid input. The callers have to ensure that given parameter is sound.
 //  * There is no branch-leaf difference. Every node can be a parent of other node.
 //
 template <class T>
 class TreeNode {
 public:
     typedef T NodeType;
 
     TreeNode()
-        : m_next(0)
-        , m_previous(0)
+        : m_nextSibling(0)
+        , m_previousSibling(0)
         , m_parent(0)
         , m_firstChild(0)
         , m_lastChild(0)
     {
     }
 
-    NodeType* next() const { return m_next; }
-    NodeType* previous() const { return m_previous; }
+    NodeType* nextSibling() const { return m_nextSibling; }
+    NodeType* previousSibling() const { return m_previousSibling; }
     NodeType* parent() const { return m_parent; }
     NodeType* firstChild() const { return m_firstChild; }
     NodeType* lastChild() const { return m_lastChild; }
     NodeType* here() const { return static_cast<NodeType*>(const_cast<TreeNode*>(this)); }
 
-    bool orphan() const { return !m_parent && !m_next && !m_previous && !m_firstChild && !m_lastChild; }
+    bool orphan() const { return !m_parent && !m_nextSibling && !m_previousSibling && !m_firstChild && !m_lastChild; }
     bool hasChildren() const { return m_firstChild; }
 
     void insertBefore(NodeType* newChild, NodeType* refChild)
     {
         ASSERT(!newChild->parent());
-        ASSERT(!newChild->next());
-        ASSERT(!newChild->previous());
+        ASSERT(!newChild->nextSibling());
+        ASSERT(!newChild->previousSibling());
 
         ASSERT(!refChild || this == refChild->parent());
 
         if (!refChild) {
             appendChild(newChild);
             return;
         }
 
-        NodeType* newPrevious = refChild->previous();
+        NodeType* newPrevious = refChild->previousSibling();
         newChild->m_parent = here();
-        newChild->m_next = refChild;
-        newChild->m_previous = newPrevious;
-        refChild->m_previous = newChild;
+        newChild->m_nextSibling = refChild;
+        newChild->m_previousSibling = newPrevious;
+        refChild->m_previousSibling = newChild;
         if (newPrevious)
-            newPrevious->m_next = newChild;
+            newPrevious->m_nextSibling = newChild;
         else
             m_firstChild = newChild;
     }
 
     void appendChild(NodeType* child)
     {
         ASSERT(!child->parent());
-        ASSERT(!child->next());
-        ASSERT(!child->previous());
+        ASSERT(!child->nextSibling());
+        ASSERT(!child->previousSibling());
 
         child->m_parent = here();
 
         if (!m_lastChild) {
             ASSERT(!m_firstChild);
             m_lastChild = m_firstChild = child;
             return;
         }
 
-        ASSERT(!m_lastChild->m_next);
+        ASSERT(!m_lastChild->m_nextSibling);
         NodeType* oldLast = m_lastChild;
         m_lastChild = child;
 
-        child->m_previous = oldLast;
-        oldLast->m_next = child;
+        child->m_previousSibling = oldLast;
+        oldLast->m_nextSibling = child;
     }
 
     NodeType* removeChild(NodeType* child)
     {
         ASSERT(child->parent() == this);
 
         if (m_firstChild == child)
-            m_firstChild = child->next();
+            m_firstChild = child->nextSibling();
         if (m_lastChild == child)
-            m_lastChild = child->previous();
+            m_lastChild = child->previousSibling();
 
-        NodeType* oldNext = child->next();
-        NodeType* oldPrevious = child->previous();
-        child->m_parent = child->m_next = child->m_previous = 0;
+        NodeType* oldNext = child->nextSibling();
+        NodeType* oldPrevious = child->previousSibling();
+        child->m_parent = child->m_nextSibling = child->m_previousSibling = 0;
 
         if (oldNext)
-            oldNext->m_previous = oldPrevious;
+            oldNext->m_previousSibling = oldPrevious;
         if (oldPrevious)
-            oldPrevious->m_next = oldNext;
+            oldPrevious->m_nextSibling = oldNext;
 
         return child;
     }
 
 private:
-    NodeType* m_next;
-    NodeType* m_previous;
+    NodeType* m_nextSibling;
+    NodeType* m_previousSibling;
     NodeType* m_parent;
     NodeType* m_firstChild;
     NodeType* m_lastChild;
 };
 
-template<class T>
-inline typename TreeNode<T>::NodeType* traverseNext(const TreeNode<T>* current, const TreeNode<T>* stayWithin = 0)
+/* non-recursive pre-order traversal */
+template<class NodeType, class ContainerType>

[Inactive, 2014/01/08 03:08:01]

BTW, I am not a big fan of the NodeType / ContainerType naming. They are both
Node types, but they may be different.

ContainerType may be a Node here (as opposed to a ContainerNode) so I think the
naming is a bit confusing. I would have preferred more generic names (e.g.
NodeType1 / NodeType2), what do others think?

+inline NodeType* traverseNext(const ContainerType& current)
 {
-    if (typename TreeNode<T>::NodeType* next = current->firstChild())
-        return next;
-    if (current == stayWithin)
-        return 0;
-    if (typename TreeNode<T>::NodeType* next = current->next())
-        return next;
-    for (typename TreeNode<T>::NodeType* parent = current->parent(); parent; parent = parent->parent()) {
-        if (parent == stayWithin)
-            return 0;
-        if (typename TreeNode<T>::NodeType* next = parent->next())
-            return next;
+    if (NodeType* firstChild = current.firstChild())
+        return firstChild;
+    if (NodeType* nextSibling = current.nextSibling())
+        return nextSibling;
+    for (NodeType* parent = current.parent(); parent; parent = parent->parent()) {
+        if (NodeType* nextSibling = parent->nextSibling())
+            return nextSibling;
     }
 
     return 0;
 }
 
-template<class T>
-inline typename TreeNode<T>::NodeType* traverseFirstPostOrder(const TreeNode<T>* current)
+template<class ContainerType>
+inline ContainerType* traverseNext(const ContainerType& current)
+{ return traverseNext<ContainerType, ContainerType>(current); }
+
+template<class NodeType, class ContainerType>
+inline NodeType* traverseNext(const ContainerType& current, const NodeType* stayWithin)
 {
-    typename TreeNode<T>::NodeType* first = current->here();
+    if (NodeType* firstChild = current.firstChild())
+        return firstChild;
+    if (&current == stayWithin)
+        return 0;
+    if (NodeType* nextSibling = current.nextSibling())
+        return nextSibling;
+    for (NodeType* parent = current.parent(); parent; parent = parent->parent()) {
+        if (parent == stayWithin)
+            return 0;
+        if (NodeType* nextSibling = parent->nextSibling())
+            return nextSibling;
+    }
+
+    return 0;
+}
+
+template<class ContainerType>
+inline ContainerType* traverseNext(const ContainerType& current, const ContainerType* stayWithin)
+{ return traverseNext<ContainerType, ContainerType>(current, stayWithin); }
+
+/* non-recursive post-order traversal */
+template<class NodeType, class ContainerType>
+inline NodeType* traverseFirstPostOrder(const ContainerType& current)
+{
+    NodeType* first = current.here();
     while (first->firstChild())
         first = first->firstChild();
     return first;
 }
 
-template<class T>
-inline typename TreeNode<T>::NodeType* traverseNextPostOrder(const TreeNode<T>* current, const TreeNode<T>* stayWithin = 0)
+template<class ContainerType>
+inline ContainerType* traverseFirstPostOrder(const ContainerType& current)
+{ return traverseFirstPostOrder<ContainerType, ContainerType>(current); }
+
+template<class NodeType, class ContainerType>
+inline NodeType* traverseNextPostOrder(const ContainerType& current)
+{
+    NodeType* nextSibling = current.nextSibling();
+    if (!nextSibling)
+        return current.parent();
+    while (nextSibling->firstChild())
+        nextSibling = nextSibling->firstChild();
+    return nextSibling;
+}
+
+template<class ContainerType>
+inline ContainerType* traverseNextPostOrder(const ContainerType& current)
+{ return traverseNextPostOrder<ContainerType, ContainerType>(current); }
+
+template<class NodeType, class ContainerType>
+inline NodeType* traverseNextPostOrder(const ContainerType& current, const NodeType* stayWithin)
+{
+    if (&current == stayWithin)
+        return 0;
+
+    NodeType* nextSibling = current.nextSibling();
+    if (!nextSibling)
+        return current.parent();
+    while (nextSibling->firstChild())
+        nextSibling = nextSibling->firstChild();
+    return nextSibling;
+}
+
+template<class ContainerType>
+inline ContainerType* traverseNextPostOrder(const ContainerType& current, const ContainerType* stayWithin)
+{ return traverseNextPostOrder<ContainerType, ContainerType>(current, stayWithin); }
+
+/* non-recursive traversal skipping children */
+template <class NodeType, class ContainerType>
+inline NodeType* traverseNextSkippingChildren(const ContainerType& current)
+{
+    if (current.nextSibling())
+        return current.nextSibling();
+    for (NodeType* parent = current.parent(); parent; parent = parent->parent()) {
+        if (NodeType* nextSibling = parent->nextSibling())
+            return nextSibling;
+    }
+
+    return 0;
+}
+
+template <class ContainerType>
+inline ContainerType* traverseNextSkippingChildren(const ContainerType& current)
+{ return traverseNextSkippingChildren<ContainerType, ContainerType>(current); }
+
+template <class NodeType, class ContainerType>
+inline NodeType* traverseNextSkippingChildren(const ContainerType& current, const NodeType* stayWithin)
 {
     if (current == stayWithin)
         return 0;
+    if (current.nextSibling())
+        return current.nextSibling();
+    for (NodeType* parent = current.parent(); parent; parent = parent->parent()) {
+        if (parent == stayWithin)
+            return 0;
+        if (NodeType* nextSibling = parent->nextSibling())
+            return nextSibling;
+    }
 
-    typename TreeNode<T>::NodeType* next = current->next();
-    if (!next)
-        return current->parent();
-    while (next->firstChild())
-        next = next->firstChild();
-    return next;
+    return 0;
 }
 
-}
+template <class ContainerType>
+inline ContainerType* traverseNextSkippingChildren(const ContainerType& current, const ContainerType* stayWithin)
+{ return traverseNextSkippingChildren<ContainerType, ContainerType>(current, stayWithin); }
+
+} // namespace WTF
 
 using WTF::TreeNode;
 using WTF::traverseNext;
+using WTF::traverseFirstPostOrder;
 using WTF::traverseNextPostOrder;
+using WTF::traverseNextSkippingChildren;
 
-#endif
+#endif // TreeNode_h