node.dart 3.99 KB
Newer Older
1 2 3 4
// Copyright 2015 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.

Adam Barth's avatar
Adam Barth committed
5 6 7 8
/// An abstract node in a tree
///
/// AbstractNode has as notion of depth, attachment, and parent, but does not
/// have a model for children.
Adam Barth's avatar
Adam Barth committed
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
///
/// * When a subclass is changing the parent of a child, it should
///   call either parent.adoptChild(child) or parent.dropChild(child)
///   as appropriate. Subclasses should expose an API for
///   manipulating the tree if you want to (e.g. a setter for a
///   'child' property, or an 'add()' method to manipulate a list).
///
/// * You can see the current parent by querying 'parent'.
///
/// * You can see the current attachment state by querying
///   'attached'. The root of any tree that is to be considered
///   attached should be manually attached by calling 'attach()'.
///   Other than that, don't call 'attach()' or 'detach()'. This is
///   all managed automatically assuming you call the 'adoptChild()'
///   and 'dropChild()' methods appropriately.
///
/// * Subclasses that have children must override 'attach()' and
///   'detach()' as described below.
///
/// * Nodes always have a 'depth' greater than their ancestors'.
///   There's no guarantee regarding depth between siblings. The
///   depth of a node is used to ensure that nodes are processed in
///   depth order. The 'depth' of a child can be more than one
///   greater than the 'depth' of the parent, because the 'depth'
///   values are never decreased: all that matters is that it's
///   greater than the parent. Consider a tree with a root node A, a
///   child B, and a grandchild C. Initially, A will have 'depth' 0,
///   B 'depth' 1, and C 'depth' 2. If C is moved to be a child of A,
///   sibling of B, then the numbers won't change. C's 'depth' will
///   still be 2. This is all managed automatically assuming you call
///   'adoptChild()' and 'dropChild()' appropriately.
40 41 42 43 44 45
class AbstractNode {

  // AbstractNode represents a node in a tree.
  // The AbstractNode protocol is described in README.md.

  int _depth = 0;
Adam Barth's avatar
Adam Barth committed
46 47 48 49
  /// The depth of this node in the tree.
  ///
  /// The depth of nodes in a tree monotonically increases as you traverse down
  /// the trees.
50
  int get depth => _depth;
Adam Barth's avatar
Adam Barth committed
51 52 53

  /// Call only from overrides of [redepthChildren]
  void redepthChild(AbstractNode child) {
54 55 56 57 58 59
    assert(child._attached == _attached);
    if (child._depth <= _depth) {
      child._depth = _depth + 1;
      child.redepthChildren();
    }
  }
Adam Barth's avatar
Adam Barth committed
60 61 62 63

  /// Override this function in subclasses with child nodes to call
  /// redepthChild(child) for each child. Do not call directly.
  void redepthChildren() { }
64 65

  bool _attached = false;
Adam Barth's avatar
Adam Barth committed
66
  /// Whether this node is in a tree whose root is attached to something.
67
  bool get attached => _attached;
Adam Barth's avatar
Adam Barth committed
68 69 70

  /// Mark this node as attached.
  ///
71 72
  /// Typically called only from the parent's attach(), and to mark the root of
  /// a tree attached.
73 74 75
  void attach() {
    _attached = true;
  }
Adam Barth's avatar
Adam Barth committed
76 77 78

  /// Mark this node as detached.
  ///
79 80
  /// Typically called only from the parent's detach(), and to mark the root of
  /// a tree detached.
81 82 83
  void detach() {
    _attached = false;
  }
Adam Barth's avatar
Adam Barth committed
84

85
  AbstractNode _parent;
Adam Barth's avatar
Adam Barth committed
86
  /// The parent of this node in the tree.
87
  AbstractNode get parent => _parent;
Adam Barth's avatar
Adam Barth committed
88 89 90

  /// Subclasses should call this function when they acquire a new child.
  void adoptChild(AbstractNode child) {
91 92
    assert(child != null);
    assert(child._parent == null);
93 94 95 96 97 98 99
    assert(() {
      AbstractNode node = this;
      while (node.parent != null)
        node = node.parent;
      assert(node != child); // indicates we are about to create a cycle
      return true;
    });
100 101 102 103 104
    child._parent = this;
    if (attached)
      child.attach();
    redepthChild(child);
  }
Adam Barth's avatar
Adam Barth committed
105 106 107

  /// Subclasses should call this function when they lose a child.
  void dropChild(AbstractNode child) {
108 109 110 111 112 113 114 115 116
    assert(child != null);
    assert(child._parent == this);
    assert(child.attached == attached);
    child._parent = null;
    if (attached)
      child.detach();
  }

}