Attempt 2 at landing tree node iterator. I needed an include

in tree_node_model.

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

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

4 files changed, 121 insertions, 1 deletions

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/tree_node_model.h b/chrome/views/tree_node_model.h
index 0d33fff..695e4ab 100644
--- a/chrome/views/tree_node_model.h
+++ b/chrome/views/tree_node_model.h
@@ -5,6 +5,7 @@
 #ifndef CHROME_VIEWS_TREE_NODE_MODEL_H__
 #define CHROME_VIEWS_TREE_NODE_MODEL_H__
 
+#include <algorithm>
 #include <vector>
 
 #include "base/basictypes.h"
@@ -116,7 +117,7 @@ class TreeNode : public TreeModelNode {
   int IndexOfChild(const NodeType* node) {
     DCHECK(node);
     typename std::vector<NodeType*>::iterator i =
-        find(children_->begin(), children_->end(), node);
+        std::find(children_->begin(), children_->end(), node);
     if (i != children_->end())
       return static_cast<int>(i - children_->begin());
     return -1;
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>