in packages/devtools_app/lib/src/charts/treemap.dart [148:349]
List<PositionedCell> buildTreemaps({
@required List<TreemapNode> children,
@required double x,
@required double y,
@required double width,
@required double height,
}) {
final isHorizontalRectangle = width > height;
final totalByteSize = computeByteSizeForNodes(nodes: children);
if (children.isEmpty) {
return [];
}
// Sort the list of treemap nodes, descending in size.
children.sort((a, b) => b.unsignedByteSize.compareTo(a.unsignedByteSize));
if (children.length <= 2) {
final positionedChildren = <PositionedCell>[];
double offset = 0;
for (final child in children) {
final ratio = child.unsignedByteSize / totalByteSize;
final newWidth = isHorizontalRectangle ? ratio * width : width;
final newHeight = isHorizontalRectangle ? height : ratio * height;
positionedChildren.add(
PositionedCell(
rect: Rect.fromLTWH(
isHorizontalRectangle ? x + offset : x,
isHorizontalRectangle ? y : y + offset,
newWidth,
newHeight,
),
node: child,
child: Treemap.fromRoot(
rootNode: child,
levelsVisible: widget.levelsVisible - 1,
onRootChangedCallback: widget.onRootChangedCallback,
width: newWidth,
height: newHeight,
),
),
);
offset += isHorizontalRectangle ? ratio * width : ratio * height;
}
return positionedChildren;
}
final pivotIndex = computePivot(children);
final pivotNode = children[pivotIndex];
final pivotByteSize = pivotNode.unsignedByteSize;
final list1 = children.sublist(0, pivotIndex);
final list1ByteSize = computeByteSizeForNodes(nodes: list1);
var list2 = <TreemapNode>[];
int list2ByteSize = 0;
var list3 = <TreemapNode>[];
int list3ByteSize = 0;
// The maximum amount of data we can put in [list3].
final l3MaxLength = children.length - pivotIndex - 1;
int bestIndex = 0;
double pivotBestWidth = 0;
double pivotBestHeight = 0;
// We need to be able to put at least 3 elements in [list3] for this algorithm.
if (l3MaxLength >= 3) {
double pivotBestAspectRatio = double.infinity;
// Iterate through different combinations of [list2] and [list3] to find
// the combination where the aspect ratio of pivot is the lowest.
for (int i = pivotIndex + 1; i < children.length; i++) {
final list2Size = computeByteSizeForNodes(
nodes: children,
startIndex: pivotIndex + 1,
endIndex: i,
);
// Calculate the aspect ratio for the pivot treemap node.
final pivotAndList2Ratio = (pivotByteSize + list2Size) / totalByteSize;
final pivotRatio = pivotByteSize / (pivotByteSize + list2Size);
final pivotWidth = isHorizontalRectangle
? pivotAndList2Ratio * width
: pivotRatio * width;
final pivotHeight = isHorizontalRectangle
? pivotRatio * height
: pivotAndList2Ratio * height;
final pivotAspectRatio = pivotWidth / pivotHeight;
// Best aspect ratio that is the closest to 1.
if ((1 - pivotAspectRatio).abs() < (1 - pivotBestAspectRatio).abs()) {
pivotBestAspectRatio = pivotAspectRatio;
bestIndex = i;
// Kept track of width and height to construct the pivot cell.
pivotBestWidth = pivotWidth;
pivotBestHeight = pivotHeight;
}
}
// Split the rest of the data into [list2] and [list3].
list2 = children.sublist(pivotIndex + 1, bestIndex + 1);
list2ByteSize = computeByteSizeForNodes(nodes: list2);
list3 = children.sublist(bestIndex + 1);
list3ByteSize = computeByteSizeForNodes(nodes: list3);
} else {
// Put all data in [list2] and none in [list3].
list2 = children.sublist(pivotIndex + 1);
list2ByteSize = computeByteSizeForNodes(nodes: list2);
final pivotAndList2Ratio =
(pivotByteSize + list2ByteSize) / totalByteSize;
final pivotRatio = pivotByteSize / (pivotByteSize + list2ByteSize);
pivotBestWidth = isHorizontalRectangle
? pivotAndList2Ratio * width
: pivotRatio * width;
pivotBestHeight = isHorizontalRectangle
? pivotRatio * height
: pivotAndList2Ratio * height;
}
final positionedTreemaps = <PositionedCell>[];
// Contruct list 1 sub-treemap.
final list1SizeRatio = list1ByteSize / totalByteSize;
final list1Width = isHorizontalRectangle ? width * list1SizeRatio : width;
final list1Height =
isHorizontalRectangle ? height : height * list1SizeRatio;
if (list1.isNotEmpty) {
positionedTreemaps.addAll(buildTreemaps(
children: list1,
x: x,
y: y,
width: list1Width,
height: list1Height,
));
}
// Construct list 2 sub-treemap.
final list2Width =
isHorizontalRectangle ? pivotBestWidth : width - pivotBestWidth;
final list2Height =
isHorizontalRectangle ? height - pivotBestHeight : pivotBestHeight;
final list2XCoord = isHorizontalRectangle ? list1Width : 0.0;
final list2YCoord = isHorizontalRectangle ? pivotBestHeight : list1Height;
if (list2.isNotEmpty) {
positionedTreemaps.addAll(buildTreemaps(
children: list2,
x: x + list2XCoord,
y: y + list2YCoord,
width: list2Width,
height: list2Height,
));
}
// Construct pivot cell.
final pivotXCoord = isHorizontalRectangle ? list1Width : list2Width;
final pivotYCoord = isHorizontalRectangle ? 0.0 : list1Height;
positionedTreemaps.add(
PositionedCell(
rect: Rect.fromLTWH(
x + pivotXCoord,
y + pivotYCoord,
pivotBestWidth,
pivotBestHeight,
),
node: pivotNode,
child: Treemap.fromRoot(
rootNode: pivotNode,
levelsVisible: widget.levelsVisible - 1,
onRootChangedCallback: widget.onRootChangedCallback,
width: width,
height: height,
),
),
);
// Construct list 3 sub-treemap.
final list3Ratio = list3ByteSize / totalByteSize;
final list3Width = isHorizontalRectangle ? list3Ratio * width : width;
final list3Height = isHorizontalRectangle ? height : list3Ratio * height;
final list3XCoord =
isHorizontalRectangle ? list1Width + pivotBestWidth : 0.0;
final list3YCoord =
isHorizontalRectangle ? 0.0 : list1Height + pivotBestHeight;
if (list3.isNotEmpty) {
positionedTreemaps.addAll(buildTreemaps(
children: list3,
x: x + list3XCoord,
y: y + list3YCoord,
width: list3Width,
height: list3Height,
));
}
return positionedTreemaps;
}