*** FOR PROTOTYPE PURPOSES ONLY! NOT INTENDED FOR COMMIT! ***

Source/core/rendering/RenderObject.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2000 Dirk Mueller (mueller@kde.org)
  *           (C) 2004 Allan Sandfeld Jensen (kde@carewolf.com)
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved.
  * Copyright (C) 2009 Google Inc. All rights reserved.
  * Copyright (C) 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
  *
  * This library is free software; you can redistribute it and/or
@@ skipping 341 matching lines @@
 void RenderObject::removeChild(RenderObject* oldChild)
 {
     RenderObjectChildList* children = virtualChildren();
     ASSERT(children);
     if (!children)
         return;
 
     children->removeChildNode(this, oldChild);
 }
 
+// This is a non-recursive algorithm for visiting the tree in both pre and post
+// order as well as skipping children when necessary and staying within a given
+// root.  Further, the algorithm takes into account nodes that still use recursive
+// traversal and provides a clean way to switch between the two modes of traversal.
+// This will allow us to incrementally change each class to non-recursive traversal
+// instead of having to change everything at once.  I developed this algorithm
+// using a toy model of a tree like structure with methods similar to the render
+// tree and its layout methods.
+//
+// NOTE: Once we switch everything over to non-recursive this algorithm can be made
+// much simpler :)
+RenderObject* RenderObject::nextForLayout(Order& order, const RenderObject* stayWithin, bool skippingChildren) const
+{
+    RenderObject* node = const_cast<RenderObject*>(this);
+    if (node == stayWithin && order == Post)
+        return 0;
+
+    if (!node->isNonRecursiveLayout()) {
+        if (node->parent() && node->parent()->isNonRecursiveLayout()) {
+            if (node->nextSibling()) {
+                order = Pre;
+                return node->nextSibling();
+            }
+            order = Post;
+            return node->parent();
+        }
+        return 0;
+    }
+
+    if (order == Pre) {
+        if (node->firstChild() && !skippingChildren)
+            return node->firstChild();
+        order = Post;
+        return node;
+    }
+
+    if (node->nextSibling()) {
+        order = Pre;
+        return node->nextSibling();
+    }
+
+    for (RenderObject* parent = node->parent(); parent; parent = parent->parent()) {
+        if (order == Post) {
+            if (parent->isNonRecursiveLayout())
+                return parent;
+            return 0;
+        }
+
+        if (parent->nextSibling())
+            return parent->nextSibling();
+    }
+    return 0;
+}
+
 RenderObject* RenderObject::nextInPreOrder() const
 {
     if (RenderObject* o = firstChild())
         return o;
 
     return nextInPreOrderAfterChildren();
 }
 
 RenderObject* RenderObject::nextInPreOrderAfterChildren() const
 {
@@ skipping 3009 matching lines @@
 {
     if (object1) {
         const WebCore::RenderObject* root = object1;
         while (root->parent())
             root = root->parent();
         root->showRenderTreeAndMark(object1, "*", object2, "-", 0);
     }
 }
 
 #endif