001    /*--------------------------------------------------------------------------+
002    $Id: StripeTreeMapAlgorithm.java 26931 2010-03-17 14:53:13Z besenreu $
003    |                                                                          |
004    | Copyright 2005-2010 Technische Universitaet Muenchen                     |
005    |                                                                          |
006    | Licensed under the Apache License, Version 2.0 (the "License");          |
007    | you may not use this file except in compliance with the License.         |
008    | You may obtain a copy of the License at                                  |
009    |                                                                          |
010    |    http://www.apache.org/licenses/LICENSE-2.0                            |
011    |                                                                          |
012    | Unless required by applicable law or agreed to in writing, software      |
013    | distributed under the License is distributed on an "AS IS" BASIS,        |
014    | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
015    | See the License for the specific language governing permissions and      |
016    | limitations under the License.                                           |
017    +--------------------------------------------------------------------------*/
018    package edu.tum.cs.commons.treemap;
019    
020    import java.awt.geom.Rectangle2D;
021    import java.util.ArrayList;
022    import java.util.List;
023    
024    
025    /**
026     * The strip layout algorithm adapted from Bederson, Shneiderman, Wattenberg:
027     * "Ordered and Quantum Treemaps".
028     * <p>
029     * This is useful as it tries to minimize the aspect ratio of the generated
030     * squares while maintaining the original order.
031     * 
032     * @author Benjamin Hummel
033     * @author $Author: besenreu $
034     * @version $Rev: 26931 $
035     * @levd.rating GREEN Hash: 1B6839F786A1CE254964E4259A7B321C
036     */
037    public class StripeTreeMapAlgorithm implements ITreeMapLayoutAlgorithm {
038    
039            /** {@inheritDoc} */
040            public <T> void layout(ITreeMapNode<T> tree, Rectangle2D target) {
041                    tree.setLayoutRectangle(target);
042                    layoutChildren(tree);
043            }
044    
045            /** Layouts the children of the given node (if it has any). */
046            private <T> void layoutChildren(ITreeMapNode<T> node) {
047                    if (node.getChildren().isEmpty()) {
048                            return;
049                    }
050                    Rectangle2D rect = node.getLayoutRectangle();
051                    double scale = rect.getWidth() * rect.getHeight() / node.getArea();
052    
053                    double layoutX = rect.getMinX();
054                    double lastX = 0;
055                    List<ITreeMapNode<T>> l = new ArrayList<ITreeMapNode<T>>();
056                    List<ITreeMapNode<T>> lastList = new ArrayList<ITreeMapNode<T>>();
057                    for (ITreeMapNode<T> child : node.getChildren()) {
058                            double oldAspect = calcAvgAspect(l, rect.getHeight(), scale);
059                            l.add(child);
060                            double newAspect = calcAvgAspect(l, rect.getHeight(), scale);
061    
062                            if (oldAspect < newAspect) {
063                                    l.remove(l.size() - 1);
064                                    lastX = layoutX;
065                                    lastList.clear();
066                                    lastList.addAll(l);
067    
068                                    layoutX += layoutList(l, rect.getHeight(), layoutX, rect
069                                                    .getMinY(), scale);
070                                    l.clear();
071                                    l.add(child);
072                            }
073                    }
074    
075                    // last list might be too small, so potentially merge with previous one
076                    lastList.addAll(l);
077                    if (calcAvgAspect(lastList, rect.getHeight(), scale) < calcAvgAspect(l,
078                                    rect.getHeight(), scale)) {
079                            layoutList(lastList, rect.getHeight(), lastX, rect.getMinY(), scale);
080                    } else {
081                            layoutList(l, rect.getHeight(), layoutX, rect.getMinY(), scale);
082                    }
083            }
084    
085            /**
086             * Calculates the average aspect ratio of the given list of nodes if the
087             * provided height may be used.
088             */
089            private <T> double calcAvgAspect(List<ITreeMapNode<T>> l,
090                            double layoutHeight, double areaScale) {
091                    if (l.isEmpty()) {
092                            return 1e8;
093                    }
094                    double area = 0;
095                    for (ITreeMapNode<T> node : l) {
096                            area += node.getArea();
097                    }
098                    double layoutWidth = area * areaScale / layoutHeight;
099                    double aspectSum = 0;
100                    for (ITreeMapNode<T> node : l) {
101                            double localHeight = node.getArea() * areaScale / layoutWidth;
102                            double localAspect = Math.max(layoutWidth / localHeight,
103                                            localHeight / layoutWidth);
104                            aspectSum += localAspect;
105                    }
106                    return aspectSum / l.size();
107            }
108    
109            /**
110             * Layout the given list of nodes in one column.
111             * 
112             * @param l
113             *            the list of nodes.
114             * @param layoutHeight
115             *            the height of the column.
116             * @param layoutX
117             *            the x start value.
118             * @param layoutY
119             *            the y start value.
120             * @param areaScale
121             *            the scale factor used to convert from node area to layout
122             *            area.
123             * @return the layout width of the column.
124             */
125            private <T> double layoutList(List<ITreeMapNode<T>> l, double layoutHeight,
126                            double layoutX, double layoutY, double areaScale) {
127                    double nodeArea = 0;
128                    for (ITreeMapNode<T> node : l) {
129                            nodeArea += node.getArea();
130                    }
131                    double layoutWidth = nodeArea * areaScale / layoutHeight;
132                    for (ITreeMapNode<T> node : l) {
133                            double nodeHeight = node.getArea() * areaScale / layoutWidth;
134                            node.setLayoutRectangle(new Rectangle2D.Double(layoutX, layoutY,
135                                            layoutWidth, nodeHeight));
136                            layoutY += nodeHeight;
137                            layoutChildren(node);
138                    }
139                    return layoutWidth;
140            }
141    }