tree_node_iterator.h revision 5821806d5e7f356e8fa4b058a389a808ea183019
1727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease// Copyright (c) 2011 The Chromium Authors. All rights reserved. 2727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease// Use of this source code is governed by a BSD-style license that can be 3727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease// found in the LICENSE file. 4727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 5727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease#ifndef UI_BASE_MODELS_TREE_NODE_ITERATOR_H_ 6727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease#define UI_BASE_MODELS_TREE_NODE_ITERATOR_H_ 7727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 8727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease#include <stack> 9727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 10727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease#include "base/basictypes.h" 11727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease#include "base/logging.h" 12727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 13727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Leasenamespace ui { 14727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 15727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease// Iterator that iterates over the descendants of a node. The iteration does 16727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease// not include the node itself, only the descendants. The following illustrates 17727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease// typical usage: 18727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease// while (iterator.has_next()) { 19727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease// Node* node = iterator.Next(); 20727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease// // do something with node. 21727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease// } 22727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Leasetemplate <class NodeType> 23727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Leaseclass TreeNodeIterator { 24727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease public: 25727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // This contructor accepts an optional filter function |prune| which could be 26727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // used to prune complete branches of the tree. The filter function will be 27727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // evaluated on each tree node and if it evaluates to true the node and all 28727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // its descendants will be skipped by the iterator. 29727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease TreeNodeIterator(NodeType* node, bool (*prune)(NodeType*)) 30727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease : prune_(prune) { 31727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease int index = 0; 32727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 33727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // Move forward through the children list until the first non prunable node. 34727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // This is to satisfy the iterator invariant that the current index in the 35727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // Position at the top of the _positions list must point to a node the 36727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // iterator will be returning. 37727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease for (; index < node->child_count(); ++index) 38727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease if (!prune || !prune(node->GetChild(index))) 39727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease break; 40727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 41727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease if (index < node->child_count()) 42727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease positions_.push(Position<NodeType>(node, index)); 43727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease } 44727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 45727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease explicit TreeNodeIterator(NodeType* node) : prune_(NULL) { 46727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease if (!node->empty()) 47727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease positions_.push(Position<NodeType>(node, 0)); 48727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease } 49727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 50727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // Returns true if there are more descendants. 51727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease bool has_next() const { return !positions_.empty(); } 52727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 53727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // Returns the next descendant. 54727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease NodeType* Next() { 55727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease if (!has_next()) { 56727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease NOTREACHED(); 57727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease return NULL; 58727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease } 59727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 60727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // There must always be a valid node in the current Position index. 61727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease NodeType* result = positions_.top().node->GetChild(positions_.top().index); 62727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 63727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // Make sure we don't attempt to visit result again. 64727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease positions_.top().index++; 65727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 66727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // Iterate over result's children. 67727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease positions_.push(Position<NodeType>(result, 0)); 68727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 69727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // Advance to next valid node by skipping over the pruned nodes and the 70727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // empty Positions. At the end of this loop two cases are possible: 71727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // - the current index of the top() Position points to a valid node 72727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease // - the _position list is empty, the iterator has_next() will return false. 73727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease while (!positions_.empty()) { 74727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease if (positions_.top().index >= positions_.top().node->child_count()) 75727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease positions_.pop(); // This Position is all processed, move to the next. 76727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease else if (prune_ && 77727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease prune_(positions_.top().node->GetChild(positions_.top().index))) 78727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease positions_.top().index++; // Prune the branch. 79727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease else 80727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease break; // Now positioned at the next node to be returned. 81727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease } 82727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 83727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease return result; 84 } 85 86 private: 87 template <class PositionNodeType> 88 struct Position { 89 Position(PositionNodeType* node, int index) : node(node), index(index) {} 90 Position() : node(NULL), index(-1) {} 91 92 PositionNodeType* node; 93 int index; 94 }; 95 96 std::stack<Position<NodeType> > positions_; 97 bool (*prune_)(NodeType*); 98 99 DISALLOW_COPY_AND_ASSIGN(TreeNodeIterator); 100}; 101 102} // namespace ui 103 104#endif // UI_BASE_MODELS_TREE_NODE_ITERATOR_H_ 105