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.List;
022
023/**
024 * The strip layout algorithm adapted from Bederson, Shneiderman, Wattenberg:
025 * "Ordered and Quantum Treemaps".
026 * <p>
027 * This is useful as it tries to minimize the aspect ratio of the generated
028 * squares while maintaining the original order.
029 * 
030 * @author Benjamin Hummel
031 */
032public class StripeTreeMapAlgorithm implements ITreeMapLayoutAlgorithm {
033
034        /** {@inheritDoc} */
035        @Override
036        public <T> void layout(ITreeMapNode<T> tree, Rectangle2D target) {
037                tree.setLayoutRectangle(target);
038                layoutChildren(tree);
039        }
040
041        /** Layouts the children of the given node (if it has any). */
042        private <T> void layoutChildren(ITreeMapNode<T> node) {
043                if (node.getChildren().isEmpty()) {
044                        return;
045                }
046                Rectangle2D rect = node.getLayoutRectangle();
047                double scale = rect.getWidth() * rect.getHeight() / node.getArea();
048
049                double layoutX = rect.getMinX();
050                double lastX = 0;
051                List<ITreeMapNode<T>> l = new ArrayList<ITreeMapNode<T>>();
052                List<ITreeMapNode<T>> lastList = new ArrayList<ITreeMapNode<T>>();
053                for (ITreeMapNode<T> child : node.getChildren()) {
054                        double oldAspect = calcAvgAspect(l, rect.getHeight(), scale);
055                        l.add(child);
056                        double newAspect = calcAvgAspect(l, rect.getHeight(), scale);
057
058                        if (oldAspect < newAspect) {
059                                l.remove(l.size() - 1);
060                                lastX = layoutX;
061                                lastList.clear();
062                                lastList.addAll(l);
063
064                                layoutX += layoutList(l, rect.getHeight(), layoutX, rect.getMinY(), scale);
065                                l.clear();
066                                l.add(child);
067                        }
068                }
069
070                // last list might be too small, so potentially merge with previous one
071                lastList.addAll(l);
072                if (calcAvgAspect(lastList, rect.getHeight(), scale) < calcAvgAspect(l, rect.getHeight(), scale)) {
073                        layoutList(lastList, rect.getHeight(), lastX, rect.getMinY(), scale);
074                } else {
075                        layoutList(l, rect.getHeight(), layoutX, rect.getMinY(), scale);
076                }
077        }
078
079        /**
080         * Calculates the average aspect ratio of the given list of nodes if the
081         * provided height may be used.
082         */
083        private static <T> double calcAvgAspect(List<ITreeMapNode<T>> l, double layoutHeight, double areaScale) {
084                if (l.isEmpty()) {
085                        return 1e8;
086                }
087                double area = 0;
088                for (ITreeMapNode<T> node : l) {
089                        area += node.getArea();
090                }
091                double layoutWidth = area * areaScale / layoutHeight;
092                double aspectSum = 0;
093                for (ITreeMapNode<T> node : l) {
094                        double localHeight = node.getArea() * areaScale / layoutWidth;
095                        double localAspect = Math.max(layoutWidth / localHeight, localHeight / layoutWidth);
096                        aspectSum += localAspect;
097                }
098                return aspectSum / l.size();
099        }
100
101        /**
102         * Layout the given list of nodes in one column.
103         * 
104         * @param l
105         *            the list of nodes.
106         * @param layoutHeight
107         *            the height of the column.
108         * @param layoutX
109         *            the x start value.
110         * @param layoutY
111         *            the y start value.
112         * @param areaScale
113         *            the scale factor used to convert from node area to layout area.
114         * @return the layout width of the column.
115         */
116        private <T> double layoutList(List<ITreeMapNode<T>> l, double layoutHeight, double layoutX, double layoutY,
117                        double areaScale) {
118                double nodeArea = 0;
119                for (ITreeMapNode<T> node : l) {
120                        nodeArea += node.getArea();
121                }
122                double layoutWidth = nodeArea * areaScale / layoutHeight;
123                for (ITreeMapNode<T> node : l) {
124                        double nodeHeight = node.getArea() * areaScale / layoutWidth;
125                        node.setLayoutRectangle(new Rectangle2D.Double(layoutX, layoutY, layoutWidth, nodeHeight));
126                        layoutY += nodeHeight;
127                        layoutChildren(node);
128                }
129                return layoutWidth;
130        }
131}