| OLD | NEW |
| 1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #ifndef UI_BASE_MODELS_TREE_NODE_ITERATOR_H_ | 5 #ifndef UI_BASE_MODELS_TREE_NODE_ITERATOR_H_ |
| 6 #define UI_BASE_MODELS_TREE_NODE_ITERATOR_H_ | 6 #define UI_BASE_MODELS_TREE_NODE_ITERATOR_H_ |
| 7 | 7 |
| 8 #include <stack> | 8 #include <stack> |
| 9 | 9 |
| 10 #include "base/callback.h" | 10 #include "base/callback.h" |
| 11 #include "base/logging.h" | 11 #include "base/logging.h" |
| 12 #include "base/macros.h" | 12 #include "base/macros.h" |
| 13 | 13 |
| 14 namespace ui { | 14 namespace ui { |
| 15 | 15 |
| 16 // Iterator that iterates over the descendants of a node. The iteration does | 16 // Iterator that iterates over the descendants of a node. The iteration does |
| 17 // not include the node itself, only the descendants. The following illustrates | 17 // not include the node itself, only the descendants. The following illustrates |
| 18 // typical usage: | 18 // typical usage: |
| 19 // while (iterator.has_next()) { | 19 // while (iterator.has_next()) { |
| 20 // Node* node = iterator.Next(); | 20 // Node* node = iterator.Next(); |
| 21 // // do something with node. | 21 // // do something with node. |
| 22 // } | 22 // } |
| 23 template <class NodeType> | 23 template <class NodeType> |
| 24 class TreeNodeIterator { | 24 class TreeNodeIterator { |
| 25 public: | 25 public: |
| 26 typedef base::Callback<bool(NodeType*)> PruneCallback; | 26 typedef base::Callback<bool(NodeType*)> PruneCallback; |
| 27 | 27 |
| 28 // This contructor accepts an optional filter function |prune| which could be | 28 // This constructor accepts an optional filter function |prune| which could be |
| 29 // used to prune complete branches of the tree. The filter function will be | 29 // used to prune complete branches of the tree. The filter function will be |
| 30 // evaluated on each tree node and if it evaluates to true the node and all | 30 // evaluated on each tree node and if it evaluates to true the node and all |
| 31 // its descendants will be skipped by the iterator. | 31 // its descendants will be skipped by the iterator. |
| 32 TreeNodeIterator(NodeType* node, const PruneCallback& prune) | 32 TreeNodeIterator(NodeType* node, const PruneCallback& prune) |
| 33 : prune_(prune) { | 33 : prune_(prune) { |
| 34 int index = 0; | 34 int index = 0; |
| 35 | 35 |
| 36 // Move forward through the children list until the first non prunable node. | 36 // Move forward through the children list until the first non prunable node. |
| 37 // This is to satisfy the iterator invariant that the current index in the | 37 // This is to satisfy the iterator invariant that the current index in the |
| 38 // Position at the top of the _positions list must point to a node the | 38 // Position at the top of the _positions list must point to a node the |
| (...skipping 11 matching lines...) Expand all Loading... |
| 50 positions_.push(Position<NodeType>(node, 0)); | 50 positions_.push(Position<NodeType>(node, 0)); |
| 51 } | 51 } |
| 52 | 52 |
| 53 // Returns true if there are more descendants. | 53 // Returns true if there are more descendants. |
| 54 bool has_next() const { return !positions_.empty(); } | 54 bool has_next() const { return !positions_.empty(); } |
| 55 | 55 |
| 56 // Returns the next descendant. | 56 // Returns the next descendant. |
| 57 NodeType* Next() { | 57 NodeType* Next() { |
| 58 if (!has_next()) { | 58 if (!has_next()) { |
| 59 NOTREACHED(); | 59 NOTREACHED(); |
| 60 return NULL; | 60 return nullptr; |
| 61 } | 61 } |
| 62 | 62 |
| 63 // There must always be a valid node in the current Position index. | 63 // There must always be a valid node in the current Position index. |
| 64 NodeType* result = positions_.top().node->GetChild(positions_.top().index); | 64 NodeType* result = positions_.top().node->GetChild(positions_.top().index); |
| 65 | 65 |
| 66 // Make sure we don't attempt to visit result again. | 66 // Make sure we don't attempt to visit result again. |
| 67 positions_.top().index++; | 67 positions_.top().index++; |
| 68 | 68 |
| 69 // Iterate over result's children. | 69 // Iterate over result's children. |
| 70 positions_.push(Position<NodeType>(result, 0)); | 70 positions_.push(Position<NodeType>(result, 0)); |
| (...skipping 12 matching lines...) Expand all Loading... |
| 83 break; // Now positioned at the next node to be returned. | 83 break; // Now positioned at the next node to be returned. |
| 84 } | 84 } |
| 85 | 85 |
| 86 return result; | 86 return result; |
| 87 } | 87 } |
| 88 | 88 |
| 89 private: | 89 private: |
| 90 template <class PositionNodeType> | 90 template <class PositionNodeType> |
| 91 struct Position { | 91 struct Position { |
| 92 Position(PositionNodeType* node, int index) : node(node), index(index) {} | 92 Position(PositionNodeType* node, int index) : node(node), index(index) {} |
| 93 Position() : node(NULL), index(-1) {} | 93 Position() : node(nullptr), index(-1) {} |
| 94 | 94 |
| 95 PositionNodeType* node; | 95 PositionNodeType* node; |
| 96 int index; | 96 int index; |
| 97 }; | 97 }; |
| 98 | 98 |
| 99 std::stack<Position<NodeType> > positions_; | 99 std::stack<Position<NodeType> > positions_; |
| 100 PruneCallback prune_; | 100 PruneCallback prune_; |
| 101 | 101 |
| 102 DISALLOW_COPY_AND_ASSIGN(TreeNodeIterator); | 102 DISALLOW_COPY_AND_ASSIGN(TreeNodeIterator); |
| 103 }; | 103 }; |
| 104 | 104 |
| 105 } // namespace ui | 105 } // namespace ui |
| 106 | 106 |
| 107 #endif // UI_BASE_MODELS_TREE_NODE_ITERATOR_H_ | 107 #endif // UI_BASE_MODELS_TREE_NODE_ITERATOR_H_ |
| OLD | NEW |