tree_view_boxy.dart

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);

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.white12),
          ),
          padding: const EdgeInsets.all(8.0),
          child: const 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('num', Colors.pink), [
            TreeNode(ExampleNode('int', Colors.purple)),
            TreeNode(ExampleNode('double', Colors.purple)),
          ]),
          TreeNode(ExampleNode('String', Colors.pink)),
          TreeNode(ExampleNode(
            'List<T>',
            Colors.pink,
            size: Size(300, 200),
          )),
        ],
      ),
      horizontalSpacing: 8,
      verticalSpacing: 32,
    );
  }
}

class ExampleNode extends StatelessWidget {
  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: size.width,
      height: size.height,
      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,
          ),
        ),
      ),
    );
  }
}

/// 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;

  // 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 {
  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.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,
    required this.verticalSpacing,
    required this.horizontalSpacing,
  });

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

  @override
  Size layout() {
    var index = 0;

    // 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) {
        // 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,
          );
        }

        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];
        }
      }

      // 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,
      );

      // 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,
        ),
      );
    }

    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;

    final path = Path();

    void addLines(TreeNode node) {
      final nodeOffset = children[index++].rect.bottomCenter;
      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 + 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),
        );
      }
    }

    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
  bool shouldRelayout(_TreeViewBoxy oldDelegate) =>
      root != oldDelegate.root ||
      verticalSpacing != oldDelegate.verticalSpacing ||
      horizontalSpacing != oldDelegate.horizontalSpacing;
}