blob: db5cb350a1e3ae0a5970e14086c84db82c4ab82c [file] [log] [blame]
// Copyright (c) 2012 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.
#include <algorithm>
#include <vector>
#include "base/basictypes.h"
#include "base/compiler_specific.h"
#include "base/logging.h"
#include "base/memory/scoped_ptr.h"
#include "base/memory/scoped_vector.h"
#include "base/observer_list.h"
#include "base/strings/string16.h"
#include "ui/base/models/tree_model.h"
namespace ui {
// TreeNodeModel and TreeNodes provide an implementation of TreeModel around
// TreeNodes.
// TreeNodes own their children, so that deleting a node deletes all
// descendants.
// TreeNodes do NOT maintain a pointer back to the model. As such, if you
// are using TreeNodes with a TreeNodeModel you will need to notify the observer
// yourself any time you make any change directly to the TreeNodes. For example,
// if you directly invoke set_title on a node it does not notify the observer,
// you will need to do it yourself. This includes the following methods: Add,
// Remove and set_title. TreeNodeModel provides cover methods that mutate the
// TreeNodes and notify the observer. If you are using TreeNodes with a
// TreeNodeModel use the cover methods to save yourself the headache.
// The following example creates a TreeNode with two children and then
// creates a TreeNodeModel from it:
// TreeNodeWithValue<int>* root = new TreeNodeWithValue<int>();
// root->Add(new TreeNodeWithValue<int>(ASCIIToUTF16("child 1"), 0));
// root->Add(new TreeNodeWithValue<int>(ASCIIToUTF16("child 2"), 1));
// TreeNodeModel<TreeNodeWithValue<int> > model(root);
// Two variants of TreeNode are provided here:
// . TreeNode itself is intended for subclassing. It has one type parameter
// that corresponds to the type of the node. When subclassing use your class
// name as the type parameter, eg:
// class MyTreeNode : public TreeNode<MyTreeNode> .
// . TreeNodeWithValue is a trivial subclass of TreeNode that has one type
// type parameter: a value type that is associated with the node.
// Which you use depends upon the situation. If you want to subclass and add
// methods, then use TreeNode. If you don't need any extra methods and just
// want to associate a value with each node, then use TreeNodeWithValue.
// Regardless of which TreeNode you use, if you are using the nodes with a
// TreeView take care to notify the observer when mutating the nodes.
// TreeNode -------------------------------------------------------------------
template <class NodeType>
class TreeNode : public TreeModelNode {
TreeNode() : parent_(NULL) {}
explicit TreeNode(const base::string16& title)
: title_(title), parent_(NULL) {}
virtual ~TreeNode() {}
// Adds |node| as a child of this node, at |index|.
virtual void Add(NodeType* node, int index) {
DCHECK_GE(index, 0);
DCHECK_LE(index, child_count());
// If |node| has a parent, remove it from its parent.
NodeType* parent = node->parent_;
if (parent)
node->parent_ = static_cast<NodeType*>(this);
children_.insert(children_.begin() + index, node);
// Removes |node| from this node and returns it. It's up to the caller to
// delete it.
virtual NodeType* Remove(NodeType* node) {
typename std::vector<NodeType*>::iterator i =
std::find(children_.begin(), children_.end(), node);
DCHECK(i != children_.end());
node->parent_ = NULL;
return node;
// Removes all the children from this node. This does NOT delete the nodes.
void RemoveAll() {
for (size_t i = 0; i < children_.size(); ++i)
children_[i]->parent_ = NULL;
// Removes all existing children without deleting the nodes and adds all nodes
// contained in |children| into this node as children.
void SetChildren(const std::vector<NodeType*>& children) {
for (size_t i = 0; i < children.size(); ++i)
Add(children[i], i);
// Returns the parent node, or NULL if this is the root node.
const NodeType* parent() const { return parent_; }
NodeType* parent() { return parent_; }
// Returns true if this is the root node.
bool is_root() const { return parent_ == NULL; }
// Returns the number of children.
int child_count() const { return static_cast<int>(children_.size()); }
// Returns true if this node has no children.
bool empty() const { return children_.empty(); }
// Returns the number of all nodes in the subtree rooted at this node,
// including this node.
int GetTotalNodeCount() const {
int count = 1; // Start with one to include the node itself.
for (size_t i = 0; i < children_.size(); ++i)
count += children_[i]->GetTotalNodeCount();
return count;
// Returns the node at |index|.
const NodeType* GetChild(int index) const {
DCHECK_GE(index, 0);
DCHECK_LT(index, child_count());
return children_[index];
NodeType* GetChild(int index) {
return const_cast<NodeType*>(
static_cast<const NodeType&>(*this).GetChild(index));
// Returns the index of |node|, or -1 if |node| is not a child of this.
int GetIndexOf(const NodeType* node) const {
typename std::vector<NodeType*>::const_iterator i =
std::find(children_.begin(), children_.end(), node);
return i != children_.end() ? static_cast<int>(i - children_.begin()) : -1;
// Sets the title of the node.
virtual void SetTitle(const base::string16& title) { title_ = title; }
// TreeModelNode:
virtual const base::string16& GetTitle() const OVERRIDE { return title_; }
// Returns true if this == ancestor, or one of this nodes parents is
// ancestor.
bool HasAncestor(const NodeType* ancestor) const {
if (ancestor == this)
return true;
if (!ancestor)
return false;
return parent_ ? parent_->HasAncestor(ancestor) : false;
std::vector<NodeType*>& children() { return children_.get(); }
// Title displayed in the tree.
base::string16 title_;
// This node's parent.
NodeType* parent_;
// This node's children.
ScopedVector<NodeType> children_;
// TreeNodeWithValue ----------------------------------------------------------
template <class ValueType>
class TreeNodeWithValue : public TreeNode< TreeNodeWithValue<ValueType> > {
TreeNodeWithValue() {}
explicit TreeNodeWithValue(const ValueType& value)
: ParentType(base::string16()), value(value) {}
TreeNodeWithValue(const base::string16& title, const ValueType& value)
: ParentType(title), value(value) {}
ValueType value;
typedef TreeNode< TreeNodeWithValue<ValueType> > ParentType;
// TreeNodeModel --------------------------------------------------------------
// TreeModel implementation intended to be used with TreeNodes.
template <class NodeType>
class TreeNodeModel : public TreeModel {
// Creates a TreeNodeModel with the specified root node. The root is owned
// by the TreeNodeModel.
explicit TreeNodeModel(NodeType* root) : root_(root) {}
virtual ~TreeNodeModel() {}
NodeType* AsNode(TreeModelNode* model_node) {
return static_cast<NodeType*>(model_node);
void Add(NodeType* parent, NodeType* node, int index) {
DCHECK(parent && node);
parent->Add(node, index);
NotifyObserverTreeNodesAdded(parent, index, 1);
NodeType* Remove(NodeType* parent, NodeType* node) {
int index = parent->GetIndexOf(node);
NodeType* delete_node = parent->Remove(node);
NotifyObserverTreeNodesRemoved(parent, index, 1);
return delete_node;
void NotifyObserverTreeNodesAdded(NodeType* parent, int start, int count) {
TreeNodesAdded(this, parent, start, count));
void NotifyObserverTreeNodesRemoved(NodeType* parent, int start, int count) {
TreeNodesRemoved(this, parent, start, count));
void NotifyObserverTreeNodeChanged(TreeModelNode* node) {
TreeNodeChanged(this, node));
// TreeModel:
virtual NodeType* GetRoot() OVERRIDE {
return root_.get();
virtual int GetChildCount(TreeModelNode* parent) OVERRIDE {
return AsNode(parent)->child_count();
virtual NodeType* GetChild(TreeModelNode* parent, int index) OVERRIDE {
return AsNode(parent)->GetChild(index);
virtual int GetIndexOf(TreeModelNode* parent, TreeModelNode* child) OVERRIDE {
return AsNode(parent)->GetIndexOf(AsNode(child));
virtual TreeModelNode* GetParent(TreeModelNode* node) OVERRIDE {
return AsNode(node)->parent();
virtual void AddObserver(TreeModelObserver* observer) OVERRIDE {
virtual void RemoveObserver(TreeModelObserver* observer) OVERRIDE {
virtual void SetTitle(TreeModelNode* node,
const base::string16& title) OVERRIDE {
// The observers.
ObserverList<TreeModelObserver> observer_list_;
// The root.
scoped_ptr<NodeType> root_;
} // namespace ui