Permanent folders changes

ui/base/models/tree_node_iterator.h

 // Copyright (c) 2011 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 UI_BASE_MODELS_TREE_NODE_ITERATOR_H_
 #define UI_BASE_MODELS_TREE_NODE_ITERATOR_H_
 #pragma once
 
 #include <stack>
 
 #include "base/basictypes.h"
 #include "base/logging.h"
 
 namespace ui {
 
 // 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) {
+  // This contructor accepts an optional filter function |prune| which could be
+  // used to prune complete branches of the tree. The filter function will be
+  // evaluated on each tree node and if it evaluates to true the node and all
+  // its descendants will be skipped by the iterator.
+  TreeNodeIterator(NodeType* node, bool (*prune)(NodeType*))
+      : prune_(prune) {
+    int index = 0;
+
+    // Move forward through the children list until the first non prunable node.
+    // This is to satisfy the iterator invariant that the current index in the
+    // Position at the top of the _positions list must point to a node the
+    // iterator will be returning.
+    for (; index < node->child_count(); ++index)
+      if (!prune || !prune(node->GetChild(index)))
+        break;
+
+    if (index < node->child_count())
+      positions_.push(Position<NodeType>(node, index));
+  }
+
+  explicit TreeNodeIterator(NodeType* node) : prune_(NULL) {
     if (!node->empty())
       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;
     }
 
+    // There must always be a valid node in the current Position index.
     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->child_count()) {
-      positions_.pop();
+    // Advance to next valid node by skipping over the pruned nodes and the
+    // empty Positions. At the end of this loop two cases are possible:
+    // - the current index of the top() Position points to a valid node
+    // - the _position list is empty, the iterator has_next() will return false.
+    while (!positions_.empty()) {
+      if (positions_.top().index >= positions_.top().node->child_count())
+        positions_.pop(); // This Position is all processed, move to the next.
+      else if (prune_ &&
+          prune_(positions_.top().node->GetChild(positions_.top().index)))
+        positions_.top().index++;  // Prune the branch.
+      else
+        break;  // Now positioned at the next node to be returned.
     }
 
     return result;
   }
 
  private:
   template <class PositionNodeType>
   struct Position {
     Position(PositionNodeType* node, int index) : node(node), index(index) {}
     Position() : node(NULL), index(-1) {}
 
     PositionNodeType* node;
     int index;
   };
 
   std::stack<Position<NodeType> > positions_;
+  bool (*prune_)(NodeType*);
 
   DISALLOW_COPY_AND_ASSIGN(TreeNodeIterator);
 };
 
 }  // namespace ui
 
 #endif  // UI_BASE_MODELS_TREE_NODE_ITERATOR_H_