Skip to content

Instantly share code, notes, and snippets.

@pingbird

pingbird/tree_view_boxy.dart

Last active February 21, 2023 17:43
Download ZIP

Revisions

  1. pingbird revised this gist Feb 21, 2023. 1 changed file with 471 additions and 63 deletions.
    534 changes: 471 additions & 63 deletions tree_view_boxy.dart
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,7 @@
    import 'dart:math';

    import 'package:boxy/boxy.dart';
    import 'package:flutter/foundation.dart';
    import 'package:flutter/material.dart';

    const darkBlue = Color.fromARGB(255, 18, 32, 47);
    @@ -31,10 +32,10 @@ class MyHomePage extends StatelessWidget {
    body: Center(
    child: Container(
    decoration: BoxDecoration(
    border: Border.all(color: Colors.white),
    border: Border.all(color: Colors.white12),
    ),
    padding: const EdgeInsets.all(64.0),
    child: MyWidget(),
    padding: const EdgeInsets.all(8.0),
    child: const MyWidget(),
    ),
    ),
    );
    @@ -50,15 +51,16 @@ class MyWidget extends StatelessWidget {
    root: TreeNode(
    ExampleNode('Object', Colors.blue),
    [
    TreeNode(ExampleNode('num', Colors.pink), [
    TreeNode(ExampleNode('int', Colors.purple)),
    TreeNode(ExampleNode('double', Colors.purple)),
    ]),
    TreeNode(ExampleNode('String', Colors.pink)),
    TreeNode(
    ExampleNode('num', Colors.pink),
    [
    TreeNode(ExampleNode('int', Colors.purple)),
    TreeNode(ExampleNode('double', Colors.purple)),
    ],
    ),
    TreeNode(ExampleNode('List<T>', Colors.pink)),
    TreeNode(ExampleNode(
    'List<T>',
    Colors.pink,
    size: Size(300, 200),
    )),
    ],
    ),
    horizontalSpacing: 8,
    @@ -68,16 +70,22 @@ class MyWidget extends StatelessWidget {
    }

    class ExampleNode extends StatelessWidget {
    const ExampleNode(this.label, this.color, {Key? key}) : super(key: key);
    const ExampleNode(
    this.label,
    this.color, {
    Key? key,
    this.size = const Size(150, 100),
    }) : super(key: key);

    final String label;
    final Color color;
    final Size size;

    @override
    Widget build(BuildContext context) {
    return Container(
    width: 150,
    height: 100,
    width: size.width,
    height: size.height,
    decoration: BoxDecoration(
    color: color,
    borderRadius: BorderRadius.circular(16.0),
    @@ -96,14 +104,16 @@ class ExampleNode extends StatelessWidget {
    }
    }

    /// A node in our tree containing a widget and a list of child nodes.
    class TreeNode {
    const TreeNode(this.widget, [this.children = const []]);

    final Widget widget;
    final List<TreeNode> children;

    Iterable<Widget> get allWidgets =>
    [widget].followedBy(children.expand((e) => e.allWidgets));
    // A flat iterable of all of the nodes in this subtree.
    Iterable<TreeNode> get flatten =>
    [this].followedBy(children.expand((e) => e.flatten));
    }

    class TreeView extends StatelessWidget {
    @@ -126,12 +136,164 @@ class TreeView extends StatelessWidget {
    verticalSpacing: verticalSpacing,
    horizontalSpacing: horizontalSpacing,
    ),
    // Flatten the tree into a single list of widgets
    children: [...root.allWidgets],
    // Flatten the tree into a single list of widgets.
    children: [...root.flatten.map((e) => e.widget)],
    );
    }
    }

    /// A linked list that each node uses to track the relative offsets of each
    /// point on the left and right edges of the subtree. This enables the layout
    /// algorithm to efficiently pack nodes horizontally without overlapping.
    class _Edge {
    _Edge(
    this.height, {
    this.dx = 0.0,
    this.dy = 0.0,
    this.next,
    });

    /// The height of the node.
    final double height;

    /// The relative x offset of [next].
    double dx;

    /// The relative y offset of [next].
    double dy;

    /// The edge below this one.
    _Edge? next;

    /// Appends [other] to the end of this edge, assuming [other] has an x offset
    /// of [x] relative to us.
    void append(_Edge other, double x) {
    // First find the tail of the current edge and its offset relative to
    // the root.
    var base = this;
    var bx = 0.0;
    var by = 0.0;
    while (true) {
    final next = base.next;
    if (next == null) {
    break;
    }
    bx += base.dx;
    by += base.dy;
    base = next;
    }

    // Find the first node in [other] that is below base and append it.
    final bottom = by + base.height + precisionErrorTolerance;
    var tail = other;
    var tx = x;
    var ty = 0.0;
    while (true) {
    if (ty + tail.height > bottom) {
    // Found one, append it and return.
    base.dx = tx - bx;
    base.dy = ty - by;
    base.next = tail;
    return;
    }
    final next = tail.next;
    if (next == null) {
    // No more nodes, nothing left to do.
    break;
    }
    tx += tail.dx;
    ty += tail.dy;
    tail = next;
    }
    }

    /// Calculates the maximum amount that this edge overlaps with [other]
    /// assuming they start at the same point.
    double overlap(_Edge other) {
    var ax = 0.0;
    var ay = 0.0;
    var bx = 0.0;
    var by = 0.0;
    var a = this;
    var b = other;
    var overlap = 0.0;

    while (true) {
    // Check if the two edges overlap on the y axis, if so, add their
    // difference on the x axis to the overlap.
    final ay2 = ay + a.height;
    final by2 = by + b.height;
    if (ay < by2 + precisionErrorTolerance &&
    by < ay2 + precisionErrorTolerance) {
    overlap = max(overlap, ax - bx);
    }

    // Move to the next node on whichever side has the lowest y.
    if (ay2 > by2) {
    final next = b.next;
    if (next == null) {
    break;
    }
    bx += b.dx;
    by += b.dy;
    b = next;
    } else {
    final next = a.next;
    if (next == null) {
    break;
    }
    ax += a.dx;
    ay += a.dy;
    a = next;
    }
    }

    return overlap;
    }
    }

    class _NodeGeometry {
    _NodeGeometry(
    this.totalSize,
    this.nodeSize,
    this.nodeOffset,
    this.childOffset,
    this.leftEdge,
    this.rightEdge,
    );

    /// The size of this node's entire subtree.
    final Size totalSize;

    /// The size of the widget of this node.
    final Size nodeSize;

    /// The x offset of this node relative to the subtree.
    final double nodeOffset;

    /// The x offset of the node's first child relative to the subtree.
    final double childOffset;

    double get middle => nodeOffset + nodeSize.width / 2;

    final _Edge leftEdge;
    final _Edge rightEdge;

    /// The x offset of the next sibling relative to this one, this value can
    /// be negative.
    var spacing = 0.0;

    @override
    String toString() {
    return '_NodeSize('
    ' totalSize: $totalSize'
    ' nodeSize: $nodeSize'
    ' nodeOffset: $nodeOffset'
    ' childOffset: $childOffset'
    ')';
    }
    }

    class _TreeViewBoxy extends BoxyDelegate {
    _TreeViewBoxy({
    required this.root,
    @@ -146,74 +308,320 @@ class _TreeViewBoxy extends BoxyDelegate {
    @override
    Size layout() {
    var index = 0;
    Size visit(TreeNode node, Offset offset) {
    final nodeIndex = index++;
    final child = children[nodeIndex];
    final size = child.layout(const BoxConstraints());
    final Size subtreeSize;

    // To lay out the nodes we use a two-pass recursive algorithm that first
    // calculates the size of the subtree and relative offsets of the child
    // and grandchildren.
    _NodeGeometry measureNode(TreeNode node) {
    final nodeIndex = index++;
    final nodeHandle = children[nodeIndex];
    final nodeSize = nodeHandle.layout(const BoxConstraints());
    if (node.children.isEmpty) {
    subtreeSize = size;
    } else {
    var width = 0.0;
    var height = 0.0;
    var x = 0.0;
    final y = offset.dy + child.size.height + verticalSpacing;
    for (final child in node.children) {
    final childSize = visit(child, Offset(offset.dx + x, y));
    height = max(height, childSize.height);
    width += childSize.width;
    x += childSize.width + horizontalSpacing;
    // No children, just return the node's size.
    return nodeHandle.parentData = _NodeGeometry(
    nodeSize,
    nodeSize,
    0.0,
    0.0,
    _Edge(nodeSize.height),
    _Edge(nodeSize.height),
    );
    }

    var minChildOffset = 0.0;
    var maxChildOffset = 0.0;
    var childHeight = 0.0;
    var childOffset = 0.0;
    var childTreeWidth = 0.0;
    final middles = <double>[];
    late _NodeGeometry firstChildGeometry;
    late _NodeGeometry lastChildGeometry;

    // The x offset of the right edge of the last child.
    late double lastChildEdge;

    // Loop through each child and get the size of them all laid out
    // side-by-side, also get a list of x offsets to their center.
    final childCount = node.children.length;
    for (var i = 0; i < childCount; i++) {
    final childNode = node.children[i];
    final childGeometry = measureNode(childNode);
    childHeight = max(childHeight, childGeometry.totalSize.height);
    if (i == 0) {
    firstChildGeometry = childGeometry;
    } else {
    // Calculate the offset of the child we just measured by finding
    // how much the right edge of the previous child overlaps with the
    // left edge of the current.
    final dist =
    lastChildGeometry.rightEdge.overlap(childGeometry.leftEdge);
    final lastChildOffset = childOffset;
    childOffset = lastChildEdge +
    dist +
    horizontalSpacing -
    childGeometry.nodeOffset;

    // Without checking overlap we would do something like this:
    // childOffset = lastChildOffset +
    // lastChildGeometry.totalSize.width +
    // horizontalSpacing;

    lastChildGeometry.spacing = childOffset - lastChildOffset;

    // Append the previous sibling's right edge to the current.
    childGeometry.rightEdge.append(
    lastChildGeometry.rightEdge,
    lastChildEdge -
    (childOffset +
    childGeometry.nodeOffset +
    childGeometry.nodeSize.width),
    );

    // Append the current child's left edge to the first so we can
    // return it from measureNode.
    firstChildGeometry.leftEdge.append(
    childGeometry.leftEdge,
    (childOffset + childGeometry.nodeOffset) -
    firstChildGeometry.nodeOffset,
    );
    }
    width += (node.children.length - 1) * horizontalSpacing;
    subtreeSize = Size(
    max(width, size.width),
    size.height + height + verticalSpacing,

    minChildOffset = min(minChildOffset, childOffset);
    maxChildOffset = max(
    maxChildOffset,
    childOffset + childGeometry.totalSize.width,
    );

    // Calculate the right edge of the current child.
    lastChildEdge = childOffset +
    childGeometry.nodeOffset +
    childGeometry.nodeSize.width;
    middles.add(childOffset + childGeometry.middle);
    childTreeWidth = childOffset + childGeometry.totalSize.width;
    lastChildGeometry = childGeometry;
    }

    // Loop through the middle offsets and find the one that's closest to
    // the center of our children.
    final idealMiddle = childTreeWidth / 2;
    var middle = middles.first;
    for (var i = 1; i < middles.length; i++) {
    // Check if positioning the node at the center of two children is ideal.
    final split = (middles[i] + middles[i - 1]) / 2;
    if ((split - idealMiddle).abs() < (middle - idealMiddle).abs()) {
    middle = split;
    }

    if ((middles[i] - idealMiddle).abs() < (middle - idealMiddle).abs()) {
    middle = middles[i];
    }
    }

    child.position(
    offset +
    Offset(
    subtreeSize.width / 2 - child.size.width / 2,
    0,
    ),
    // Offset of node relative to first child
    final nodeOffset = middle - nodeSize.width / 2;

    // Leftmost and rightmost side of screen relative to first child
    final minTotalOffset = min(minChildOffset, nodeOffset);
    final maxTotalOffset = max(maxChildOffset, nodeOffset + nodeSize.width);

    // The offset of the first child relative to the whole subtree
    final firstChildOffset = -minTotalOffset;

    final totalSize = Size(
    maxTotalOffset - minTotalOffset,
    nodeSize.height + verticalSpacing + childHeight,
    );

    return subtreeSize;
    // Assign the BoxyChild's parentData here so we can access it again in
    // positionNode.
    return nodeHandle.parentData = _NodeGeometry(
    totalSize,
    nodeSize,
    nodeOffset - minTotalOffset,
    firstChildOffset,
    _Edge(
    nodeSize.height,
    // Calculate the offset from the top left of this node to the
    // top left of the first child.
    dx: firstChildOffset + firstChildGeometry.nodeOffset - nodeOffset,
    dy: nodeSize.height + verticalSpacing,
    next: firstChildGeometry.leftEdge,
    ),
    _Edge(
    nodeSize.height,
    // Calculate the offset from the top right of this node to the
    // top right of the last child.
    dx: (firstChildOffset + lastChildEdge) -
    (nodeOffset + nodeSize.width),
    dy: nodeSize.height + verticalSpacing,
    next: lastChildGeometry.rightEdge,
    ),
    );
    }

    return visit(root, Offset.zero);
    final sizeData = measureNode(root);

    // On the second pass we calculate the real offset of each child using the
    // `_NodeGeometry` saved on the first pass.
    _NodeGeometry positionNode(TreeNode node, Offset offset) {
    final nodeIndex = index++;
    final nodeHandle = children[nodeIndex];
    final sizeData = nodeHandle.parentData as _NodeGeometry;
    nodeHandle.position(offset + Offset(sizeData.nodeOffset, 0.0));
    var dx = offset.dx + sizeData.childOffset;
    final dy = offset.dy + sizeData.nodeSize.height + verticalSpacing;
    for (final childNode in node.children) {
    final childSizeData = positionNode(childNode, Offset(dx, dy));
    dx += childSizeData.spacing;
    }
    return sizeData;
    }

    index = 0;
    positionNode(root, Offset.zero);

    return sizeData.totalSize;
    }

    @override
    void paint() {
    var index = 0;
    void paintLines(TreeNode node) {

    final path = Path();

    void addLines(TreeNode node) {
    final nodeOffset = children[index++].rect.bottomCenter;
    for (final child in node.children) {
    final childOffset = children[index].rect.topCenter;
    canvas.drawPath(
    Path()
    final c = verticalSpacing;

    for (var i = 0; i < node.children.length; i++) {
    final firstChildOffset = children[index].rect.topCenter;
    final right = firstChildOffset.dx > nodeOffset.dx;
    final distance = (firstChildOffset.dx - nodeOffset.dx).abs();
    final c2 = c * (right ? 1.0 : -1.0);
    final mx = firstChildOffset.dx - c2;
    final my = firstChildOffset.dy - c / 2;

    if (distance > verticalSpacing * 2) {
    // For long distances we use two curves joined by a straight line,
    // this looks like an aesthetically pleasing curly brace.

    // Avoid drawing overlapping lines
    if (i == 0 || i == node.children.length - 1) {
    path
    ..moveTo(nodeOffset.dx, nodeOffset.dy)
    ..cubicTo(
    nodeOffset.dx,
    nodeOffset.dy + c / 2,
    nodeOffset.dx + c2 / 2,
    nodeOffset.dy + c / 2,
    nodeOffset.dx + c2,
    nodeOffset.dy + c / 2,
    )
    ..lineTo(mx, my);
    } else {
    path.moveTo(mx, my);
    }

    path.cubicTo(
    firstChildOffset.dx - c2 / 2,
    firstChildOffset.dy - c / 2,
    firstChildOffset.dx,
    firstChildOffset.dy - c / 2,
    firstChildOffset.dx,
    firstChildOffset.dy,
    );
    } else {
    // For shorter distances we just use a single curve that is smoother
    // the closer the parent is to its child.
    final ratio = min(1.0, distance / verticalSpacing) * 0.9;
    path
    ..moveTo(nodeOffset.dx, nodeOffset.dy)
    ..cubicTo(
    nodeOffset.dx,
    nodeOffset.dy + verticalSpacing,
    childOffset.dx,
    childOffset.dy - verticalSpacing,
    childOffset.dx,
    childOffset.dy,
    ),
    Paint()
    ..color = Colors.white
    ..style = PaintingStyle.stroke
    ..strokeWidth = 3.0,
    nodeOffset.dy + c * ratio,
    firstChildOffset.dx,
    firstChildOffset.dy - c * ratio,
    firstChildOffset.dx,
    firstChildOffset.dy,
    );
    }
    addLines(node.children[i]);
    }
    }

    addLines(root);

    canvas.drawPath(
    path,
    Paint()
    ..color = Colors.white
    ..style = PaintingStyle.stroke
    ..strokeWidth = 3.0,
    );
    }

    static var debugShowEdges = false;

    @override
    void paintForeground() {
    if (!debugShowEdges) {
    return;
    }

    final leftPath = Path();
    final rightPath = Path();

    var index = 0;
    void visit(TreeNode node) {
    final nodeHandle = children[index++];
    final nodeSize = nodeHandle.parentData as _NodeGeometry;
    for (final child in node.children) {
    visit(child);
    }
    final rect = nodeHandle.rect;

    final leftEdge = nodeSize.leftEdge;
    leftPath
    ..moveTo(rect.left, rect.top)
    ..lineTo(rect.left, rect.top + leftEdge.height);
    if (leftEdge.next != null) {
    leftPath.lineTo(
    rect.left + leftEdge.dx,
    rect.top + max(rect.height, leftEdge.dy),
    );
    }

    final rightEdge = nodeSize.rightEdge;
    rightPath
    ..moveTo(rect.right, rect.top)
    ..lineTo(rect.right, rect.top + rightEdge.height);
    if (rightEdge.next != null) {
    rightPath.lineTo(
    rect.right + rightEdge.dx,
    rect.top + max(rect.height, rightEdge.dy),
    );
    paintLines(child);
    }
    }

    paintLines(root);
    visit(root);

    canvas.drawPath(
    leftPath,
    Paint()
    ..color = Colors.deepOrange
    ..style = PaintingStyle.stroke
    ..strokeWidth = 2.0
    ..strokeCap = StrokeCap.round,
    );

    canvas.drawPath(
    rightPath,
    Paint()
    ..color = Colors.amber
    ..style = PaintingStyle.stroke
    ..strokeWidth = 2.0
    ..strokeCap = StrokeCap.round,
    );
    }

    @override
  2. pingbird created this gist Feb 14, 2023.
    224 changes: 224 additions & 0 deletions tree_view_boxy.dart
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,224 @@
    import 'dart:math';

    import 'package:boxy/boxy.dart';
    import 'package:flutter/material.dart';

    const darkBlue = Color.fromARGB(255, 18, 32, 47);

    void main() {
    runApp(const MyApp());
    }

    class MyApp extends StatelessWidget {
    const MyApp({Key? key}) : super(key: key);

    @override
    Widget build(BuildContext context) {
    return MaterialApp(
    theme: ThemeData.dark().copyWith(scaffoldBackgroundColor: darkBlue),
    debugShowCheckedModeBanner: false,
    home: const MyHomePage(),
    );
    }
    }

    class MyHomePage extends StatelessWidget {
    const MyHomePage({Key? key}) : super(key: key);

    @override
    Widget build(BuildContext context) {
    return Scaffold(
    body: Center(
    child: Container(
    decoration: BoxDecoration(
    border: Border.all(color: Colors.white),
    ),
    padding: const EdgeInsets.all(64.0),
    child: MyWidget(),
    ),
    ),
    );
    }
    }

    class MyWidget extends StatelessWidget {
    const MyWidget({Key? key}) : super(key: key);

    @override
    Widget build(BuildContext context) {
    return const TreeView(
    root: TreeNode(
    ExampleNode('Object', Colors.blue),
    [
    TreeNode(ExampleNode('String', Colors.pink)),
    TreeNode(
    ExampleNode('num', Colors.pink),
    [
    TreeNode(ExampleNode('int', Colors.purple)),
    TreeNode(ExampleNode('double', Colors.purple)),
    ],
    ),
    TreeNode(ExampleNode('List<T>', Colors.pink)),
    ],
    ),
    horizontalSpacing: 8,
    verticalSpacing: 32,
    );
    }
    }

    class ExampleNode extends StatelessWidget {
    const ExampleNode(this.label, this.color, {Key? key}) : super(key: key);

    final String label;
    final Color color;

    @override
    Widget build(BuildContext context) {
    return Container(
    width: 150,
    height: 100,
    decoration: BoxDecoration(
    color: color,
    borderRadius: BorderRadius.circular(16.0),
    ),
    child: Center(
    child: Text(
    label,
    style: const TextStyle(
    fontSize: 20.0,
    fontWeight: FontWeight.bold,
    color: Colors.white,
    ),
    ),
    ),
    );
    }
    }

    class TreeNode {
    const TreeNode(this.widget, [this.children = const []]);

    final Widget widget;
    final List<TreeNode> children;

    Iterable<Widget> get allWidgets =>
    [widget].followedBy(children.expand((e) => e.allWidgets));
    }

    class TreeView extends StatelessWidget {
    const TreeView({
    required this.root,
    required this.verticalSpacing,
    required this.horizontalSpacing,
    super.key,
    });

    final TreeNode root;
    final double verticalSpacing;
    final double horizontalSpacing;

    @override
    Widget build(BuildContext context) {
    return CustomBoxy(
    delegate: _TreeViewBoxy(
    root: root,
    verticalSpacing: verticalSpacing,
    horizontalSpacing: horizontalSpacing,
    ),
    // Flatten the tree into a single list of widgets
    children: [...root.allWidgets],
    );
    }
    }

    class _TreeViewBoxy extends BoxyDelegate {
    _TreeViewBoxy({
    required this.root,
    required this.verticalSpacing,
    required this.horizontalSpacing,
    });

    final TreeNode root;
    final double verticalSpacing;
    final double horizontalSpacing;

    @override
    Size layout() {
    var index = 0;
    Size visit(TreeNode node, Offset offset) {
    final nodeIndex = index++;
    final child = children[nodeIndex];
    final size = child.layout(const BoxConstraints());
    final Size subtreeSize;

    if (node.children.isEmpty) {
    subtreeSize = size;
    } else {
    var width = 0.0;
    var height = 0.0;
    var x = 0.0;
    final y = offset.dy + child.size.height + verticalSpacing;
    for (final child in node.children) {
    final childSize = visit(child, Offset(offset.dx + x, y));
    height = max(height, childSize.height);
    width += childSize.width;
    x += childSize.width + horizontalSpacing;
    }
    width += (node.children.length - 1) * horizontalSpacing;
    subtreeSize = Size(
    max(width, size.width),
    size.height + height + verticalSpacing,
    );
    }

    child.position(
    offset +
    Offset(
    subtreeSize.width / 2 - child.size.width / 2,
    0,
    ),
    );

    return subtreeSize;
    }

    return visit(root, Offset.zero);
    }

    @override
    void paint() {
    var index = 0;
    void paintLines(TreeNode node) {
    final nodeOffset = children[index++].rect.bottomCenter;
    for (final child in node.children) {
    final childOffset = children[index].rect.topCenter;
    canvas.drawPath(
    Path()
    ..moveTo(nodeOffset.dx, nodeOffset.dy)
    ..cubicTo(
    nodeOffset.dx,
    nodeOffset.dy + verticalSpacing,
    childOffset.dx,
    childOffset.dy - verticalSpacing,
    childOffset.dx,
    childOffset.dy,
    ),
    Paint()
    ..color = Colors.white
    ..style = PaintingStyle.stroke
    ..strokeWidth = 3.0,
    );
    paintLines(child);
    }
    }

    paintLines(root);
    }

    @override
    bool shouldRelayout(_TreeViewBoxy oldDelegate) =>
    root != oldDelegate.root ||
    verticalSpacing != oldDelegate.verticalSpacing ||
    horizontalSpacing != oldDelegate.horizontalSpacing;
    }