Adds an iterator over tree nodes.

BUG=4065
TEST=none

Review URL: http://codereview.chromium.org/13264

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@6552 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 128 insertions, 0 deletions

diff --git a/chrome/test/unit/unit_tests.scons b/chrome/test/unit/unit_tests.scons
index e870062..c2df8b0 100644
--- a/chrome/test/unit/unit_tests.scons
+++ b/chrome/test/unit/unit_tests.scons
@@ -229,6 +229,7 @@ if env['PLATFORM'] == 'win32':
       '$CHROME_DIR/views/focus_manager_unittest.cc',
       '$CHROME_DIR/views/grid_layout_unittest.cc',
       '$CHROME_DIR/views/table_view_unittest.cc',
+      '$CHROME_DIR/views/tree_node_iterator_unittest.cc',
       '$CHROME_DIR/views/view_unittest.cc',
 
       # Commented out for now because googleurl_tests doesn't build with
diff --git a/chrome/test/unit/unittests.vcproj b/chrome/test/unit/unittests.vcproj
index 11bf464..fa01082 100644
--- a/chrome/test/unit/unittests.vcproj
+++ b/chrome/test/unit/unittests.vcproj
@@ -755,6 +755,14 @@
 			</File>

 		</Filter>

 		<Filter

+			Name="TreeTreeNodeIterator"

+			>

+			<File

+				RelativePath="..\..\views\tree_node_iterator_unittest.cc"

+				>

+			</File>

+		</Filter>

+		<Filter

 			Name="TestWindowSizer"

 			>

 			<File

diff --git a/chrome/views/tree_node_iterator.h b/chrome/views/tree_node_iterator.h
new file mode 100644
index 0000000..2b73954
--- /dev/null
+++ b/chrome/views/tree_node_iterator.h
@@ -0,0 +1,74 @@
+// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROME_VIEWS_TREE_NODE_ITERATOR_H_
+#define CHROME_VIEWS_TREE_NODE_ITERATOR_H_
+
+#include <stack>
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+
+namespace views {
+
+// Iterator that iterates over the descendants of a node. The iteration does
+// not include the node itself, only the descendants. The following illustrates
+// typical usage:
+// while (iterator.has_next()) {
+//   Node* node = iterator.Next();
+//   // do something with node.
+// }
+template <class NodeType>
+class TreeNodeIterator {
+ public:
+  explicit TreeNodeIterator(NodeType* node) {
+    if (node->GetChildCount() > 0)
+      positions_.push(Position<NodeType>(node, 0));
+  }
+
+  // Returns true if there are more descendants.
+  bool has_next() const { return !positions_.empty(); }
+
+  // Returns the next descendant.
+  NodeType* Next() {
+    if (!has_next()) {
+      NOTREACHED();
+      return NULL;
+    }
+
+    NodeType* result = positions_.top().node->GetChild(positions_.top().index);
+
+    // Make sure we don't attempt to visit result again.
+    positions_.top().index++;
+
+    // Iterate over result's children.
+    positions_.push(Position<NodeType>(result, 0));
+
+    // Advance to next position.
+    while (!positions_.empty() && positions_.top().index >=
+           positions_.top().node->GetChildCount()) {
+      positions_.pop();
+    }
+
+    return result;
+  }
+
+ private:
+  template <class NodeType>
+  struct Position {
+    Position(NodeType* node, int index) : node(node), index(index) {}
+    Position() : node(NULL), index(-1) {}
+
+    NodeType* node;
+    int index;
+  };
+
+  std::stack<Position<NodeType> > positions_;
+
+  DISALLOW_COPY_AND_ASSIGN(TreeNodeIterator);
+};
+
+}  // namespace views
+
+#endif  // CHROME_VIEWS_TREE_NODE_ITERATOR_H_
diff --git a/chrome/views/tree_node_iterator_unittest.cc b/chrome/views/tree_node_iterator_unittest.cc
new file mode 100644
index 0000000..165b5c3
--- /dev/null
+++ b/chrome/views/tree_node_iterator_unittest.cc
@@ -0,0 +1,41 @@
+// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+#include "chrome/views/tree_node_iterator.h"
+#include "chrome/views/tree_node_model.h"
+
+typedef testing::Test TreeNodeIteratorTest;
+
+using views::TreeNodeWithValue;
+
+TEST_F(TreeNodeIteratorTest, Test) {
+  TreeNodeWithValue<int> root;
+  root.Add(0, new TreeNodeWithValue<int>(1));
+  root.Add(1, new TreeNodeWithValue<int>(2));
+  TreeNodeWithValue<int>* f3 = new TreeNodeWithValue<int>(3);
+  root.Add(2, f3);
+  TreeNodeWithValue<int>* f4 = new TreeNodeWithValue<int>(4);
+  f3->Add(0, f4);
+  f4->Add(0, new TreeNodeWithValue<int>(5));
+
+  views::TreeNodeIterator<TreeNodeWithValue<int> > iterator(&root);
+  ASSERT_TRUE(iterator.has_next());
+  ASSERT_EQ(root.GetChild(0), iterator.Next());
+
+  ASSERT_TRUE(iterator.has_next());
+  ASSERT_EQ(root.GetChild(1), iterator.Next());
+
+  ASSERT_TRUE(iterator.has_next());
+  ASSERT_EQ(root.GetChild(2), iterator.Next());
+
+  ASSERT_TRUE(iterator.has_next());
+  ASSERT_EQ(f4, iterator.Next());
+
+  ASSERT_TRUE(iterator.has_next());
+  ASSERT_EQ(f4->GetChild(0), iterator.Next());
+
+  ASSERT_FALSE(iterator.has_next());
+}
diff --git a/chrome/views/views.vcproj b/chrome/views/views.vcproj
index 3a476eb..e4cdc56 100644
--- a/chrome/views/views.vcproj
+++ b/chrome/views/views.vcproj
@@ -582,6 +582,10 @@
 			>

 		</File>

 		<File

+			RelativePath=".\tree_node_iterator.h"

+			>

+		</File>

+		<File

 			RelativePath=".\tree_node_model.h"

 			>

 		</File>