From d3cdb0ffdcb632b53bf2b756b13a848cf74de48c Mon Sep 17 00:00:00 2001
From: "sky@google.com" <sky@google.com@0039d316-1c4b-4281-b951-d872f2087c98>
Date: Mon, 8 Dec 2008 23:14:20 +0000
Subject: 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
---
chrome/views/tree_node_iterator.h | 74 +++++++++++++++++++++++++++++
chrome/views/tree_node_iterator_unittest.cc | 41 ++++++++++++++++
chrome/views/views.vcproj | 4 ++
3 files changed, 119 insertions(+)
create mode 100644 chrome/views/tree_node_iterator.h
create mode 100644 chrome/views/tree_node_iterator_unittest.cc
(limited to 'chrome/views')
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>
--
cgit v1.1