1// Copyright (c) 2012 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#ifndef UI_BASE_MODELS_TREE_NODE_MODEL_H_ 6#define UI_BASE_MODELS_TREE_NODE_MODEL_H_ 7 8#include <algorithm> 9#include <vector> 10 11#include "base/basictypes.h" 12#include "base/compiler_specific.h" 13#include "base/logging.h" 14#include "base/memory/scoped_ptr.h" 15#include "base/memory/scoped_vector.h" 16#include "base/observer_list.h" 17#include "base/strings/string16.h" 18#include "ui/base/models/tree_model.h" 19 20namespace ui { 21 22// TreeNodeModel and TreeNodes provide an implementation of TreeModel around 23// TreeNodes. 24// 25// TreeNodes own their children, so that deleting a node deletes all 26// descendants. 27// 28// TreeNodes do NOT maintain a pointer back to the model. As such, if you 29// are using TreeNodes with a TreeNodeModel you will need to notify the observer 30// yourself any time you make any change directly to the TreeNodes. For example, 31// if you directly invoke set_title on a node it does not notify the observer, 32// you will need to do it yourself. This includes the following methods: Add, 33// Remove and set_title. TreeNodeModel provides cover methods that mutate the 34// TreeNodes and notify the observer. If you are using TreeNodes with a 35// TreeNodeModel use the cover methods to save yourself the headache. 36// 37// The following example creates a TreeNode with two children and then 38// creates a TreeNodeModel from it: 39// 40// TreeNodeWithValue<int>* root = new TreeNodeWithValue<int>(); 41// root->Add(new TreeNodeWithValue<int>(ASCIIToUTF16("child 1"), 0)); 42// root->Add(new TreeNodeWithValue<int>(ASCIIToUTF16("child 2"), 1)); 43// TreeNodeModel<TreeNodeWithValue<int> > model(root); 44// 45// Two variants of TreeNode are provided here: 46// 47// . TreeNode itself is intended for subclassing. It has one type parameter 48// that corresponds to the type of the node. When subclassing use your class 49// name as the type parameter, eg: 50// class MyTreeNode : public TreeNode<MyTreeNode> . 51// . TreeNodeWithValue is a trivial subclass of TreeNode that has one type 52// type parameter: a value type that is associated with the node. 53// 54// Which you use depends upon the situation. If you want to subclass and add 55// methods, then use TreeNode. If you don't need any extra methods and just 56// want to associate a value with each node, then use TreeNodeWithValue. 57// 58// Regardless of which TreeNode you use, if you are using the nodes with a 59// TreeView take care to notify the observer when mutating the nodes. 60 61// TreeNode ------------------------------------------------------------------- 62 63template <class NodeType> 64class TreeNode : public TreeModelNode { 65 public: 66 TreeNode() : parent_(NULL) {} 67 68 explicit TreeNode(const base::string16& title) 69 : title_(title), parent_(NULL) {} 70 71 virtual ~TreeNode() {} 72 73 // Adds |node| as a child of this node, at |index|. 74 virtual void Add(NodeType* node, int index) { 75 DCHECK(node); 76 DCHECK_GE(index, 0); 77 DCHECK_LE(index, child_count()); 78 // If |node| has a parent, remove it from its parent. 79 NodeType* parent = node->parent_; 80 if (parent) 81 parent->Remove(node); 82 node->parent_ = static_cast<NodeType*>(this); 83 children_.insert(children_.begin() + index, node); 84 } 85 86 // Removes |node| from this node and returns it. It's up to the caller to 87 // delete it. 88 virtual NodeType* Remove(NodeType* node) { 89 typename std::vector<NodeType*>::iterator i = 90 std::find(children_.begin(), children_.end(), node); 91 DCHECK(i != children_.end()); 92 node->parent_ = NULL; 93 children_.weak_erase(i); 94 return node; 95 } 96 97 // Removes all the children from this node. This does NOT delete the nodes. 98 void RemoveAll() { 99 for (size_t i = 0; i < children_.size(); ++i) 100 children_[i]->parent_ = NULL; 101 children_.weak_clear(); 102 } 103 104 // Removes all existing children without deleting the nodes and adds all nodes 105 // contained in |children| into this node as children. 106 void SetChildren(const std::vector<NodeType*>& children) { 107 RemoveAll(); 108 for (size_t i = 0; i < children.size(); ++i) 109 Add(children[i], i); 110 } 111 112 // Returns the parent node, or NULL if this is the root node. 113 const NodeType* parent() const { return parent_; } 114 NodeType* parent() { return parent_; } 115 116 // Returns true if this is the root node. 117 bool is_root() const { return parent_ == NULL; } 118 119 // Returns the number of children. 120 int child_count() const { return static_cast<int>(children_.size()); } 121 122 // Returns true if this node has no children. 123 bool empty() const { return children_.empty(); } 124 125 // Returns the number of all nodes in the subtree rooted at this node, 126 // including this node. 127 int GetTotalNodeCount() const { 128 int count = 1; // Start with one to include the node itself. 129 for (size_t i = 0; i < children_.size(); ++i) 130 count += children_[i]->GetTotalNodeCount(); 131 return count; 132 } 133 134 // Returns the node at |index|. 135 const NodeType* GetChild(int index) const { 136 DCHECK_GE(index, 0); 137 DCHECK_LT(index, child_count()); 138 return children_[index]; 139 } 140 NodeType* GetChild(int index) { 141 return const_cast<NodeType*>( 142 static_cast<const NodeType&>(*this).GetChild(index)); 143 } 144 145 // Returns the index of |node|, or -1 if |node| is not a child of this. 146 int GetIndexOf(const NodeType* node) const { 147 DCHECK(node); 148 typename std::vector<NodeType*>::const_iterator i = 149 std::find(children_.begin(), children_.end(), node); 150 return i != children_.end() ? static_cast<int>(i - children_.begin()) : -1; 151 } 152 153 // Sets the title of the node. 154 virtual void SetTitle(const base::string16& title) { title_ = title; } 155 156 // TreeModelNode: 157 virtual const base::string16& GetTitle() const OVERRIDE { return title_; } 158 159 // Returns true if this == ancestor, or one of this nodes parents is 160 // ancestor. 161 bool HasAncestor(const NodeType* ancestor) const { 162 if (ancestor == this) 163 return true; 164 if (!ancestor) 165 return false; 166 return parent_ ? parent_->HasAncestor(ancestor) : false; 167 } 168 169 protected: 170 std::vector<NodeType*>& children() { return children_.get(); } 171 172 private: 173 // Title displayed in the tree. 174 base::string16 title_; 175 176 // This node's parent. 177 NodeType* parent_; 178 179 // This node's children. 180 ScopedVector<NodeType> children_; 181 182 DISALLOW_COPY_AND_ASSIGN(TreeNode); 183}; 184 185// TreeNodeWithValue ---------------------------------------------------------- 186 187template <class ValueType> 188class TreeNodeWithValue : public TreeNode< TreeNodeWithValue<ValueType> > { 189 public: 190 TreeNodeWithValue() {} 191 192 explicit TreeNodeWithValue(const ValueType& value) 193 : ParentType(base::string16()), value(value) {} 194 195 TreeNodeWithValue(const base::string16& title, const ValueType& value) 196 : ParentType(title), value(value) {} 197 198 ValueType value; 199 200 private: 201 typedef TreeNode< TreeNodeWithValue<ValueType> > ParentType; 202 203 DISALLOW_COPY_AND_ASSIGN(TreeNodeWithValue); 204}; 205 206// TreeNodeModel -------------------------------------------------------------- 207 208// TreeModel implementation intended to be used with TreeNodes. 209template <class NodeType> 210class TreeNodeModel : public TreeModel { 211 public: 212 // Creates a TreeNodeModel with the specified root node. The root is owned 213 // by the TreeNodeModel. 214 explicit TreeNodeModel(NodeType* root) : root_(root) {} 215 virtual ~TreeNodeModel() {} 216 217 NodeType* AsNode(TreeModelNode* model_node) { 218 return static_cast<NodeType*>(model_node); 219 } 220 221 void Add(NodeType* parent, NodeType* node, int index) { 222 DCHECK(parent && node); 223 parent->Add(node, index); 224 NotifyObserverTreeNodesAdded(parent, index, 1); 225 } 226 227 NodeType* Remove(NodeType* parent, NodeType* node) { 228 DCHECK(parent); 229 int index = parent->GetIndexOf(node); 230 NodeType* delete_node = parent->Remove(node); 231 NotifyObserverTreeNodesRemoved(parent, index, 1); 232 return delete_node; 233 } 234 235 void NotifyObserverTreeNodesAdded(NodeType* parent, int start, int count) { 236 FOR_EACH_OBSERVER(TreeModelObserver, 237 observer_list_, 238 TreeNodesAdded(this, parent, start, count)); 239 } 240 241 void NotifyObserverTreeNodesRemoved(NodeType* parent, int start, int count) { 242 FOR_EACH_OBSERVER(TreeModelObserver, 243 observer_list_, 244 TreeNodesRemoved(this, parent, start, count)); 245 } 246 247 void NotifyObserverTreeNodeChanged(TreeModelNode* node) { 248 FOR_EACH_OBSERVER(TreeModelObserver, 249 observer_list_, 250 TreeNodeChanged(this, node)); 251 } 252 253 // TreeModel: 254 virtual NodeType* GetRoot() OVERRIDE { 255 return root_.get(); 256 } 257 258 virtual int GetChildCount(TreeModelNode* parent) OVERRIDE { 259 DCHECK(parent); 260 return AsNode(parent)->child_count(); 261 } 262 263 virtual NodeType* GetChild(TreeModelNode* parent, int index) OVERRIDE { 264 DCHECK(parent); 265 return AsNode(parent)->GetChild(index); 266 } 267 268 virtual int GetIndexOf(TreeModelNode* parent, TreeModelNode* child) OVERRIDE { 269 DCHECK(parent); 270 return AsNode(parent)->GetIndexOf(AsNode(child)); 271 } 272 273 virtual TreeModelNode* GetParent(TreeModelNode* node) OVERRIDE { 274 DCHECK(node); 275 return AsNode(node)->parent(); 276 } 277 278 virtual void AddObserver(TreeModelObserver* observer) OVERRIDE { 279 observer_list_.AddObserver(observer); 280 } 281 282 virtual void RemoveObserver(TreeModelObserver* observer) OVERRIDE { 283 observer_list_.RemoveObserver(observer); 284 } 285 286 virtual void SetTitle(TreeModelNode* node, 287 const base::string16& title) OVERRIDE { 288 DCHECK(node); 289 AsNode(node)->SetTitle(title); 290 NotifyObserverTreeNodeChanged(node); 291 } 292 293 private: 294 // The observers. 295 ObserverList<TreeModelObserver> observer_list_; 296 297 // The root. 298 scoped_ptr<NodeType> root_; 299 300 DISALLOW_COPY_AND_ASSIGN(TreeNodeModel); 301}; 302 303} // namespace ui 304 305#endif // UI_BASE_MODELS_TREE_NODE_MODEL_H_ 306