001/*-------------------------------------------------------------------------+
002|                                                                          |
003| Copyright 2005-2011 the ConQAT Project                                   |
004|                                                                          |
005| Licensed under the Apache License, Version 2.0 (the "License");          |
006| you may not use this file except in compliance with the License.         |
007| You may obtain a copy of the License at                                  |
008|                                                                          |
009|    http://www.apache.org/licenses/LICENSE-2.0                            |
010|                                                                          |
011| Unless required by applicable law or agreed to in writing, software      |
012| distributed under the License is distributed on an "AS IS" BASIS,        |
013| WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
014| See the License for the specific language governing permissions and      |
015| limitations under the License.                                           |
016+-------------------------------------------------------------------------*/
017package org.conqat.lib.commons.treemap;
018
019import java.awt.geom.Rectangle2D;
020import java.util.ArrayList;
021import java.util.Collections;
022import java.util.Comparator;
023import java.util.List;
024
025import org.conqat.lib.commons.collections.CollectionUtils;
026
027/**
028 * A layout algorithm using the squarified layout approach described in Mark
029 * Bruls, Kees Huizing, and Jarke J. van Wijk: "Squarified Treemaps". This
030 * algorithm will maintain nearly perfect squares but does not preserve order.
031 * 
032 * @see "http://www.win.tue.nl/~vanwijk/stm.pdf"
033 */
034public class SquarifiedTreeMapAlgorithm implements ITreeMapLayoutAlgorithm {
035
036        /** {@inheritDoc} */
037        @Override
038        public <T> void layout(ITreeMapNode<T> rootNode, Rectangle2D targetArea) {
039                rootNode.setLayoutRectangle(targetArea);
040                layoutChildren(rootNode);
041        }
042
043        /** Layouts the children of the given node (if it has any). */
044        private <T> void layoutChildren(ITreeMapNode<T> node) {
045                if (node.getChildren().isEmpty()) {
046                        return;
047                }
048
049                Rectangle2D rect = node.getLayoutRectangle();
050                double areaScale = rect.getWidth() * rect.getHeight() / node.getArea();
051
052                // sort larger nodes to the front
053                List<ITreeMapNode<T>> sortedNodes = new ArrayList<ITreeMapNode<T>>(node.getChildren());
054                Collections.sort(sortedNodes, new Comparator<ITreeMapNode<T>>() {
055                        @Override
056                        public int compare(ITreeMapNode<T> node1, ITreeMapNode<T> node2) {
057                                return Double.compare(node2.getArea(), node1.getArea());
058                        }
059                });
060
061                while (!sortedNodes.isEmpty() && CollectionUtils.getLast(sortedNodes).getArea() <= 0) {
062                        sortedNodes.remove(sortedNodes.size() - 1);
063                }
064
065                int start = 0;
066                double shorterSide = Math.min(rect.getWidth(), rect.getHeight());
067                for (int end = 1; end <= sortedNodes.size();) {
068                        if (end < sortedNodes.size() && worstAspectRatio(sortedNodes.subList(start, end), shorterSide,
069                                        areaScale) > worstAspectRatio(sortedNodes.subList(start, end + 1), shorterSide, areaScale)) {
070                                end += 1;
071                        } else {
072                                rect = layoutRow(sortedNodes.subList(start, end), rect, areaScale);
073                                shorterSide = Math.min(rect.getWidth(), rect.getHeight());
074                                start = end;
075                                end = start + 1;
076                        }
077                }
078
079                for (ITreeMapNode<T> child : sortedNodes) {
080                        layoutChildren(child);
081                }
082        }
083
084        /**
085         * Layouts the given nodes as a row along the shorter side of the rectangle.
086         */
087        private static <T> Rectangle2D layoutRow(List<ITreeMapNode<T>> nodes, Rectangle2D rect, double areaScale) {
088                double overallArea = getArea(nodes);
089                if (rect.getWidth() < rect.getHeight()) {
090                        double height = overallArea * areaScale / rect.getWidth();
091                        double x = rect.getX();
092                        for (ITreeMapNode<T> node : nodes) {
093                                double nodeWidth = node.getArea() * areaScale / height;
094                                node.setLayoutRectangle(new Rectangle2D.Double(x, rect.getY(), nodeWidth, height));
095                                x += nodeWidth;
096                        }
097                        return new Rectangle2D.Double(rect.getX(), rect.getY() + height, rect.getWidth(),
098                                        rect.getHeight() - height);
099                }
100
101                double width = overallArea * areaScale / rect.getHeight();
102                double y = rect.getY();
103                for (ITreeMapNode<T> node : nodes) {
104                        double nodeHeight = node.getArea() * areaScale / width;
105                        node.setLayoutRectangle(new Rectangle2D.Double(rect.getX(), y, width, nodeHeight));
106                        y += nodeHeight;
107                }
108                return new Rectangle2D.Double(rect.getX() + width, rect.getY(), rect.getWidth() - width, rect.getHeight());
109        }
110
111        /**
112         * Returns the worst aspect ratio is the given nodes were layouted in a
113         * rectangle with this side length.
114         */
115        private static <T> double worstAspectRatio(List<ITreeMapNode<T>> nodes, double minSide, double areaScale) {
116                double overallArea = getArea(nodes) * areaScale;
117                double side = overallArea / minSide;
118                double worst = 1;
119                for (ITreeMapNode<T> node : nodes) {
120                        double aspect = node.getArea() * areaScale / side / side;
121                        worst = Math.max(worst, Math.max(aspect, 1 / aspect));
122                }
123                return worst;
124        }
125
126        /** Returns the accumulated area for a list of nodes. */
127        private static <T> double getArea(List<ITreeMapNode<T>> nodes) {
128                double area = 0;
129                for (ITreeMapNode<T> node : nodes) {
130                        area += node.getArea();
131                }
132                return area;
133        }
134}