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], static_cast<int>(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