blob: ff77b38c90cb9dfedfedb4183be2d733923cacec [file] [log] [blame]
// Copyright 2019 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
import 'package:logging/logging.dart';
import 'package:meta/meta.dart';
import '../../surface/surface.dart';
import '../../surface/surface_relation.dart';
import './_surface_node.dart';
/// A logger for Surface Tree warnings
Logger log = Logger.root;
/// A SurfaceTree of SurfaceNodes
class SurfaceTree extends Iterable<Surface> {
/// Construct [SurfaceTree]
/// The root of the SurfaceTree. SurfaceNodes added to the Tree without
/// specifying parents are added to the root.
final SurfaceNode kRoot = SurfaceNode(surface: Surface(surfaceId: '_kRoot_'));
/// Map from SurfaceIds to SurfaceNodes, for all the SurfaceNodes in the Forest
final Map<String, SurfaceNode> _nodeMap = {};
/// Add a SurfaceNode node to the SurfaceTree. The node will be added to a
/// parent matching optional parentId, or to the root.
void _addNode({
@required SurfaceNode node,
String parentId,
}) {
// If the Surface is already in the Tree, return;
if (_nodeMap.containsKey(node.surface.surfaceId)) {
'Surface with id "${node.surface.surfaceId}" already in tree. '
'Use update() to modify existing Surfaces. '
'Surface will not be not re-added.');
// If an invalid parent was specified throw an error
if (parentId != null && !_nodeMap.containsKey(parentId)) {
throw (ArgumentError.value(
parentId, 'parentId', 'not found in SurfaceTree'));
// If a valid parent was specified, add to the parent
if (parentId != null) {
// add node as child of parent if we can find the parent
_nodeMap[parentId].add(childNode: node);
_nodeMap[node.surface.surfaceId] = node;
// else add to the root
} else {
kRoot.add(childNode: node);
_nodeMap[node.surface.surfaceId] = node;
/// Add a Surface to this Tree, optionally attach this Surface to the given
/// parent.
void add({
@required Surface surface,
String parentId,
SurfaceRelation relationToParent,
}) {
SurfaceNode node = SurfaceNode(surface: surface);
if (relationToParent != null) {
node.relationToParent = relationToParent;
_addNode(node: node, parentId: parentId);
/// Destructively removes the node from the SurfaceTree, and reparents any
/// children to the root
void remove({@required String surfaceId}) {
if (_nodeMap.containsKey(surfaceId)) {
SurfaceNode node = _nodeMap[surfaceId];
// detach the node from its parent
node.parentNode?.detach(childNode: node);
// reparent any children on the root of the tree
for (SurfaceNode child in node.childNodes) {
// make the children orphans
node.detach(childNode: child);
// remove them from the graph
// add them to the root
_addNode(node: child);
// remove the node from the nodeMap
/// Update the [parentId] and the [relation] to the parent of a [Surface]
/// The Surface must exist in the [Tree]
/// NOTE! If the parentId is not specified, the child will be orphaned and
/// reparented on the root!
void update({
@required Surface surface,
String parentId,
SurfaceRelation relation,
}) {
if (parentId == null && relation != null) {
throw (ArgumentError.value(
'Relationship provided, but parent not specified. Relationships are'
'between parents and children'));
SurfaceNode oldNode = _nodeMap[surface.surfaceId];
SurfaceNode newNode =
SurfaceNode(surface: surface, relationToParent: relation);
/// If the node had a parent, detach and reparent the updated node
if (parentId != null && _nodeMap[parentId] != null) {
..detach(childNode: oldNode)
..add(childNode: newNode);
_nodeMap[surface.surfaceId] = newNode;
Iterator<Surface> get iterator {
return flatten().iterator;
/// Breadth first flattening of SurfaceNode
Iterable<Surface> flatten() {
return kRoot.flatten().map((f) => f.surface).toList()
..remove(kRoot.surface); // The root is an implementation detail
/// Find Surface by surfaceId
SurfaceNode findNode({String surfaceId}) => _nodeMap[surfaceId];
/// Reduces a Forest to a list of objects.
Iterable<V> reduceSurfaceTree<V>(
V f(Surface surface, Iterable<V> children)) => t) => t.reduceSurfaceNode(f));
/// Get a flattened iterable of all of the values in the forest
Iterable get values => flatten();
String toString() => 'SurfaceTree($kRoot)';
/// Creates a spanning tree with a given condition
SurfaceTree spanningTree(
{@required String startNodeId, @required bool condition(SurfaceNode s)}) {
SurfaceNode startNode;
if (_nodeMap.containsKey(startNodeId)) {
startNode = _nodeMap[startNodeId];
} else {
log.warning('node $startNodeId not found in tree, '
'returning empty spanningTree');
return SurfaceTree();
// find the topmost point of the connected tree where the relationship holds
// (excluding the kRoot, which is not a valid Surface)
while (startNode?.parentNode != null &&
condition(startNode) &&
// the root not a valid surface
startNode?.parentNode != kRoot) {
startNode = startNode.parentNode;
// then return all the descendents who satisfy condition
SurfaceTree spanTree = SurfaceTree()..add(surface: startNode.surface);
current: startNode, tree: spanTree, condition: condition);
return spanTree;
// recursively search down surface nodes, adding children that match condition
// to tree;
void __copyTreeWithConditional(
{SurfaceNode current, SurfaceTree tree, bool condition(SurfaceNode s)}) {
for (SurfaceNode child in current.childNodes) {
if (condition(child)) {
tree.add(surface: child.surface, parentId: current.surface.surfaceId);
current: child, tree: tree, condition: condition);