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

1 files changed, 74 insertions, 0 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_