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;
020
021/**
022 * A hybrid layout algorithm that applies both the
023 * {@link StripeTreeMapAlgorithm} and (near the leaves) the
024 * {@link SquarifiedTreeMapAlgorithm} to obtain good sorting/locality while
025 * getting rectangles that are "more square". The approach is described in
026 * Vliegen, von Wijk, van der Linden: "Visualizing Business Data with
027 * Generalized Treemaps".
028 * 
029 * @see "http://www.magnaview.nl/documents/Visualizing_Business_Data_with_Generalized_Treemaps.pdf"
030 */
031public class MixedTreeMapAlgorithm implements ITreeMapLayoutAlgorithm {
032
033        /** {@inheritDoc} */
034        @Override
035        public <T> void layout(ITreeMapNode<T> rootNode, Rectangle2D targetArea) {
036                new StripeTreeMapAlgorithm().layout(rootNode, targetArea);
037
038                performLocalSquareLayout(rootNode);
039        }
040
041        /**
042         * Performs the square layout for nodes that are near the leaves.
043         * 
044         * @return the maximum distance to the leaves.
045         */
046        private static <T> int performLocalSquareLayout(ITreeMapNode<T> node) {
047                if (node.getChildren().isEmpty()) {
048                        return 0;
049                }
050
051                int distance = 0;
052                for (ITreeMapNode<T> child : node.getChildren()) {
053                        distance = Math.max(distance, performLocalSquareLayout(child) + 1);
054                }
055
056                // layout last 3 levels
057                if (distance == 3) {
058                        new SquarifiedTreeMapAlgorithm().layout(node, node.getLayoutRectangle());
059                }
060
061                return distance;
062        }
063}