Subversion Repositories splitter

Rev

Rev 652 | Blame | Compare with Previous | Last modification | View Log | RSS feed

/*
 * Copyright (c) 2009, Chris Miller
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 3 as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 */


package uk.me.parabola.splitter.solver;

import java.awt.Point;
import java.awt.Rectangle;
import java.time.Duration;
import java.time.Instant;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

import it.unimi.dsi.fastutil.ints.IntArrayList;
import uk.me.parabola.splitter.Area;
import uk.me.parabola.splitter.RoundingUtils;
import uk.me.parabola.splitter.SplitFailedException;
import uk.me.parabola.splitter.Utils;

/**
 * Splits a density map into multiple areas, none of which exceed the desired
 * threshold.
 *
 * @author Chris Miller, Gerd Petermann
 */

public class SplittableDensityArea {
        private static final int MAX_LAT_DEGREES = 85;
        private static final int MAX_LON_DEGREES = 90;
        public static final int MAX_SINGLE_POLYGON_VERTICES = 40;
        private static final int MAX_LOOPS = 100; // number of loops to find better solution for one rectangular area
        static final int AXIS_HOR = 0;
        static final int AXIS_VERT = 1;
        public static final double NICE_MAX_ASPECT_RATIO = 4;
        private static final double VERY_NICE_FILL_RATIO = 0.94;
        private static final long LARGE_MAX_NODES = 10_000_000;
        private static final double MAX_OUTSIDE_RATIO = 0.5;
        private static final int MIN_TILE_AREA_BAD_CACHE = 100;
        private static final int MAX_DEPTH_STATS = 10;
        private boolean enableExtraOpt = true; // option ?
       
        private final int startSearchLimit;
       

        private final DensityMap allDensities;
        private EnhancedDensityMap extraDensityInfo;

        private boolean beQuiet;
        private static final boolean DEBUG = false;
        private long maxNodes;
        private int stopNumber;
        private final int shift;
       
        private final boolean trimShape;
        private boolean trimTiles;
        private boolean allowEmptyPart;
        private int currMapId;
        private boolean hasEmptyPart;
        private int solverId;

        public SplittableDensityArea(DensityMap densities, int startSearchLimit, boolean trim) {
                this.shift = densities.getShift();
                this.startSearchLimit = startSearchLimit;
                this.trimShape = trim;
                allDensities = densities;
        }

        public DensityMap getAllDensities() {
                return allDensities;
        }

        public void setMapId(int mapId) {
                currMapId = mapId;
        }

        public void setMaxNodes(long maxNodes) {
                this.maxNodes = maxNodes;
        }

        public boolean hasData() {
                return allDensities != null && allDensities.getNodeCount() > 0;
        }

        /**
         * @return the area that this splittable area represents
         */

        public Area getBounds() {
                return allDensities.getBounds();
        }

        /**
         * Calculate a solution (list of areas that either matches the given criteria or is empty)
         *
         * @return solution (can be empty if none was found with the given criteria)
         */

        private Solution split() {
                Solution fullSolution = new Solution(maxNodes);
                if (allDensities == null || allDensities.getNodeCount() == 0)
                        return fullSolution;
                prepare(null);
                Tile startTile = new Tile(extraDensityInfo);
                List<Tile> startTiles = new ArrayList<>();
                if (trimShape || allDensities.getBounds().getWidth() >= 0x1000000) {
                        // if trim is wanted or tile spans over planet
                        // we try first to find large empty areas (sea)
                        startTiles.addAll(checkForEmptyClusters(0, startTile, true));
                } else {
                        startTiles.add(startTile);
                }

                int countNoSol;
                while (true) {
                        countNoSol = 0;
                        for (Tile tile : startTiles) {
                                hasEmptyPart = false; // possibly overwritten in solveRectangularArea
                                if (!beQuiet)
                                        System.out.println("Solving partition " + tile.toString());
                                Solution solution = solveRectangularArea(tile);
                                if (solution != null && !solution.isEmpty())
                                        fullSolution.merge(solution);
                                else {
                                        countNoSol++;
                                        if (!beQuiet)
                                                System.out.println("Warning: No solution found for partition " + tile.toString());
                                }
                        }
                        if (countNoSol == 0)
                                break;
                        if (allowEmptyPart || !hasEmptyPart)
                                break;
                        allowEmptyPart = true;
                        fullSolution = new Solution(maxNodes);
                }
                if (countNoSol > 0 && stopNumber == 0)
                        throw new SplitFailedException("Failed to find a correct split");
                if (!beQuiet) {
                        printFinalSplitMsg(fullSolution);
                }
                return fullSolution;
        }

        /**
         * Split with a given polygon and max nodes threshold. If the polygon is not
         * singular, it is divided into singular areas.
         *
         * @param polygonArea
         * @return list of areas
         */

        private List<Area> split(java.awt.geom.Area polygonArea) {
                if (polygonArea == null)
                        return getAreas(split(), null);
                if (polygonArea.isSingular()) {
                        java.awt.geom.Area rasteredArea = allDensities.rasterPolygon(polygonArea);
                        List<List<Point>> shapes = Utils.areaToShapes(rasteredArea);
                        List<Area> areas = new ArrayList<>();
                        for (List<Point> shape : shapes) {
                                java.awt.geom.Area rasteredPart = Utils.shapeToArea(shape);
                                if (rasteredPart.isEmpty()) {
                                        System.err.println("Bounding polygon doesn't intersect with the bounding box of the input file(s)");
                                        return Collections.emptyList();
                                }
                                if (rasteredPart.isSingular()) {
                                        prepare(polygonArea);
                                        Tile tile = new Tile(extraDensityInfo, rasteredPart.getBounds());
                                        Solution solution = findSolutionWithSinglePolygon(0, tile, rasteredPart, new HashSet<>());
                                        if (solution == null && rasteredPart.isRectangular())
                                                solution = split();
                                        if (solution != null) {
                                                areas.addAll(getAreas(solution, polygonArea));
                                        }
                                }
                        }
                        return areas;
                }
                if (polygonArea.intersects(Utils.area2Rectangle(allDensities.getBounds(), 0)))
                        return splitPolygon(polygonArea);
                System.err.println("Bounding polygon doesn't intersect with the bounding box of the input file(s)");
                return Collections.emptyList();
        }

        /**
         * Split a list of named polygons. Overlapping areas of the polygons are
         * extracted and each one is split for itself. A polygon may not be singular.
         *
         * @param namedPolygons list of polygons, if empty the tile bounds are used
         * @return list of areas
         */

        public List<Area> split(List<PolygonDesc> namedPolygons) {
                if (namedPolygons.isEmpty()) {
                        return getAreas(split(), null);
                }
                List<Area> result = new ArrayList<>();
                class ShareInfo {
                        java.awt.geom.Area area;
                        final IntArrayList sharedBy = new IntArrayList();
                }
                List<ShareInfo> sharedParts = new ArrayList<>();
                for (int i = 0; i < namedPolygons.size(); i++) {
                        boolean wasDistinct = true;
                        PolygonDesc namedPart = namedPolygons.get(i);
                        java.awt.geom.Area distinctPart = new java.awt.geom.Area(namedPart.getArea());
                        for (int j = 0; j < namedPolygons.size(); j++) {
                                if (j == i)
                                        continue;
                                java.awt.geom.Area test = new java.awt.geom.Area(namedPart.getArea());
                                test.intersect(namedPolygons.get(j).getArea());
                                if (!test.isEmpty()) {
                                        wasDistinct = false;
                                        distinctPart.subtract(namedPolygons.get(j).getArea());
                                        if (j > i) {
                                                ShareInfo si = new ShareInfo();
                                                si.area = test;
                                                si.sharedBy.add(i);
                                                si.sharedBy.add(j);
                                                sharedParts.add(si);
                                        }
                                }
                        }
                        if (!distinctPart.isEmpty() && distinctPart.intersects(Utils.area2Rectangle(allDensities.getBounds(), 0))) {
//                              KmlWriter.writeKml("e:/ld_sp/distinct_"+namedPart.getName(), "distinct", distinctPart);
                                if (!wasDistinct)
                                        System.out.println("splitting distinct part of " + namedPart.getName());
                                else
                                        System.out.println("splitting " + namedPart.getName());
                                result.addAll(split(distinctPart));
                        }
                }

                for (int i = 0; i < sharedParts.size(); i++) {
                        ShareInfo si = sharedParts.get(i);
                        int last = namedPolygons.size(); // list is extended in the loop
                        for (int j = 0; j < last; j++) {
                                if (si.sharedBy.contains(j))
                                        continue;
                                java.awt.geom.Area test = new java.awt.geom.Area(si.area);
                                test.intersect(namedPolygons.get(j).getArea());
                                if (!test.isEmpty()) {
                                        si.area.subtract(test);
                                        if (j > si.sharedBy.getInt(si.sharedBy.size() - 1)) {
                                                ShareInfo si2 = new ShareInfo();
                                                si2.area = test;
                                                si2.sharedBy.addAll(si.sharedBy);
                                                si2.sharedBy.add(j);
                                                sharedParts.add(si2);
                                        }
                                }
                                if (si.area.isEmpty())
                                        break;
                        }
                        if (!si.area.isEmpty() && si.area.intersects(Utils.area2Rectangle(allDensities.getBounds(), 0))) {
                                String desc = "";
                                for (int pos : si.sharedBy)
                                        desc += namedPolygons.get(pos).getName() + " and ";
                                desc = desc.substring(0, desc.lastIndexOf(" and"));
                                System.out.println("splitting area shared by exactly " + si.sharedBy.size() + " polygons: " + desc);
//                              KmlWriter.writeKml("e:/ld_sp/shared_"+desc.replace(" " , "_"), desc, si.area);
                                result.addAll(split(si.area));
                        }
                }
                return result;
        }

        /**
         * Split into a given number of tiles.
         *
         * @param wantedTiles
         * @return list of areas
         */

        public List<Area> split(int wantedTiles) {
                this.stopNumber = wantedTiles;
                long currMaxNodes = (long) (this.allDensities.getNodeCount() / (wantedTiles * 0.95));
                class Pair {
                        long myMaxNodes;
                        int numTiles;

                        Pair(long maxNodes, int numTiles) {
                                this.myMaxNodes = maxNodes;
                                this.numTiles = numTiles;
                        }
                }
                Pair bestBelow = null;
                Pair bestAbove = null;
                beQuiet = true;
                while (true) {
                        this.setMaxNodes(currMaxNodes);
                        System.out.println("Trying a max-nodes value of " + currMaxNodes + " to split "
                                        + allDensities.getNodeCount() + " nodes into " + wantedTiles + " areas");
                        Solution sol = split();
                       
                        if (sol.isEmpty() || sol.size() == wantedTiles) {
                                beQuiet = false;
                                printFinalSplitMsg(sol);
                                return getAreas(sol, null);
                        }
                       
                        Pair pair = new Pair(currMaxNodes, sol.size());
                        if (sol.size() > wantedTiles) {
                                if (bestAbove == null || bestAbove.numTiles > pair.numTiles
                                                || (bestAbove.numTiles == pair.numTiles && pair.myMaxNodes < bestAbove.myMaxNodes))
                                        bestAbove = pair;
                        } else {
                                if (bestBelow == null || bestBelow.numTiles < pair.numTiles
                                                || (bestBelow.numTiles == pair.numTiles && pair.myMaxNodes > bestBelow.myMaxNodes))
                                        bestBelow = pair;
                        }
                        long testMaxNodes;
                        if (bestBelow == null || bestAbove == null)
                                testMaxNodes = Math.min(Math.round((double) currMaxNodes * sol.size() / wantedTiles),
                                                this.allDensities.getNodeCount() - 1);
                        else
                                testMaxNodes = (bestBelow.myMaxNodes + bestAbove.myMaxNodes) / 2;
                        if (testMaxNodes == currMaxNodes) {
                                System.err.println("Cannot find a good split with exactly " + wantedTiles + " areas");
                                printFinalSplitMsg(sol);
                                return getAreas(sol, null);
                        }
                        currMaxNodes = testMaxNodes;
                }
        }

        /**
         * Filter the density data, calculate once complex trigonometric results
         *
         * @param polygonArea
         */

        private void prepare(java.awt.geom.Area polygonArea) {
                extraDensityInfo = new EnhancedDensityMap(allDensities, polygonArea);
                if (!beQuiet) {
                        System.out.println("Highest node count in a single grid element is "
                                        + Utils.format(extraDensityInfo.getMaxNodesInDensityMapGridElement()));
                        if (polygonArea != null) {
                                System.out.println("Highest node count in a single grid element within the bounding polygon is "
                                                + Utils.format(extraDensityInfo.getMaxNodesInDensityMapGridElementInPoly()));
                        }
                }
                if (polygonArea != null)
                        trimTiles = true;

        }

        /**
         * Try to find empty areas. This will fail if the empty area is enclosed by a
         * non-empty area.
         *
         * @param depth      recursion depth
         * @param tile       the tile that might contain an empty area
         * @param splitHoriz true: search horizontal, else vertical
         * @return a list containing one or more tiles, cut from the original tile, or
         *         just the original tile
         */

        private ArrayList<Tile> checkForEmptyClusters(int depth, final Tile tile, boolean splitHoriz) {
                java.awt.geom.Area area = new java.awt.geom.Area(tile);
                int firstEmpty = -1;
                int countEmpty = 0;
                long countLastPart = 0;
                long countRemaining = tile.getCount();
                int maxEmpty = Utils.toMapUnit(30) / (1 << shift);
                int minEmpty = Utils.toMapUnit(10) / (1 << shift);
                if (splitHoriz) {
                        for (int i = 0; i < tile.width; i++) {
                                long count = tile.getColSum(i);
                                if (count == 0) {
                                        if (firstEmpty < 0)
                                                firstEmpty = i;
                                        countEmpty++;
                                } else {
                                        if (countEmpty > maxEmpty
                                                        || (countEmpty > minEmpty && countLastPart > maxNodes / 3 && countRemaining > maxNodes / 3)) {
                                                java.awt.geom.Area empty = new java.awt.geom.Area(
                                                                new Rectangle(firstEmpty, tile.y, countEmpty, tile.height));
                                                area.subtract(empty);
                                                countLastPart = 0;
                                        }
                                        countRemaining -= count;
                                        firstEmpty = -1;
                                        countEmpty = 0;
                                        countLastPart += count;
                                }
                        }
                } else {
                        for (int i = 0; i < tile.height; i++) {
                                long count = tile.getRowSum(i);
                                if (count == 0) {
                                        if (firstEmpty < 0)
                                                firstEmpty = i;
                                        countEmpty++;
                                } else {
                                        if (countEmpty > maxEmpty
                                                        || (countEmpty > minEmpty && countLastPart > maxNodes / 3 && countRemaining > maxNodes / 3)) {
                                                java.awt.geom.Area empty = new java.awt.geom.Area(
                                                                new Rectangle(tile.x, firstEmpty, tile.width, countEmpty));
                                                area.subtract(empty);
                                                countLastPart = 0;
                                        }
                                        countRemaining -= count;
                                        firstEmpty = -1;
                                        countEmpty = 0;
                                        countLastPart += count;
                                }
                        }
                }
                ArrayList<Tile> clusters = new ArrayList<>();
                if (depth == 0 && area.isSingular()) {
                        // try also the other split axis
                        clusters.addAll(checkForEmptyClusters(depth + 1, tile.trim(), !splitHoriz));
                } else {
                        if (area.isSingular()) {
                                clusters.add(tile.trim());
                        } else {
                                List<List<Point>> shapes = Utils.areaToShapes(area);
                                for (List<Point> shape : shapes) {
                                        java.awt.geom.Area part = Utils.shapeToArea(shape);
                                        Tile t = new Tile(extraDensityInfo, part.getBounds());
                                        if (t.getCount() > 0)
                                                clusters.addAll(checkForEmptyClusters(depth + 1, t.trim(), !splitHoriz));
                                }
                        }
                }
                return clusters;
        }

        /**
         * Split, handling a polygon that may contain multiple distinct areas.
         *
         * @param polygonArea
         * @return a list of areas that cover the polygon
         */

        private List<Area> splitPolygon(final java.awt.geom.Area polygonArea) {
                List<Area> result = new ArrayList<>();
                List<List<Point>> shapes = Utils.areaToShapes(polygonArea);
                for (int i = 0; i < shapes.size(); i++) {
                        List<Point> shape = shapes.get(i);
                        if (!Utils.clockwise(shape))
                                continue;
                        java.awt.geom.Area shapeArea = Utils.shapeToArea(shape);
                        Rectangle rShape = shapeArea.getBounds();
                        if (shape.size() > MAX_SINGLE_POLYGON_VERTICES) {
                                shapeArea = new java.awt.geom.Area(rShape);
                                System.out.println("Warning: shape is too complex, using rectangle " + rShape + " instead");
                        }
                        Area shapeBounds = new Area(rShape.y, rShape.x, (int) rShape.getMaxY(), (int) rShape.getMaxX());
                        int resolution = 24 - allDensities.getShift();
                        shapeBounds = RoundingUtils.round(shapeBounds, resolution);
                        SplittableDensityArea splittableArea = new SplittableDensityArea(allDensities.subset(shapeBounds),
                                        startSearchLimit, trimShape);
                        splittableArea.setMaxNodes(maxNodes);
                        if (!splittableArea.hasData()) {
                                System.out.println(
                                                "Warning: a part of the bounding polygon would be empty and is ignored:" + shapeBounds);
                                // result.add(shapeBounds);
                                continue;
                        }
                        List<Area> partResult = splittableArea.split(shapeArea);
                        if (partResult != null)
                                result.addAll(partResult);
                }
                return result;
        }

        /**
         * Split the given tile using the given (singular) polygon area. The routine
         * splits the polygon into parts and calls itself recursively for each part that
         * is not rectangular.
         *
         * @param depth               recursion depth
         * @param tile                the tile to split
         * @param rasteredPolygonArea an area describing a rectilinear shape
         * @param knownBad collection containing rectangles which are known to be without solution
         * @return a solution (maybe empty), or null if rasteredPolygon is not singular
         */

        private Solution findSolutionWithSinglePolygon(int depth, final Tile tile, java.awt.geom.Area rasteredPolygonArea,
                        Set<Rectangle> knownBad) {
                if (!rasteredPolygonArea.isSingular()) {
                        return null;
                }
                if (rasteredPolygonArea.isRectangular()) {
                        Tile part = new Tile(extraDensityInfo, rasteredPolygonArea.getBounds());
                        return solveRectangularArea(part);
                }
                List<List<Point>> shapes = Utils.areaToShapes(rasteredPolygonArea);
                List<Point> shape = shapes.get(0);

                if (shape.size() > MAX_SINGLE_POLYGON_VERTICES) {
                        Tile part = new Tile(extraDensityInfo, rasteredPolygonArea.getBounds());
                        System.out.println("Warning: rastered shape is too complex, using rectangle " + part + " instead");
                        return solveRectangularArea(part);
                }

                Rectangle pBounds = rasteredPolygonArea.getBounds();
                int lastPoint = shape.size() - 1;
                if (shape.get(0).equals(shape.get(lastPoint)))
                        --lastPoint;
                for (int i = 0; i <= lastPoint; i++) {
                        Point point = shape.get(i);
                        if (i > 0 && point.equals(shape.get(0)))
                                continue;
                        int cutX = point.x;
                        int cutY = point.y;
                        Solution part1Sol = null, part2Sol = null;
                        for (int axis = 0; axis < 2; axis++) {
                                Rectangle r1, r2;
                                if (axis == AXIS_HOR) {
                                        r1 = new Rectangle(pBounds.x, pBounds.y, cutX - pBounds.x, pBounds.height);
                                        r2 = new Rectangle(cutX, pBounds.y, (int) (pBounds.getMaxX() - cutX), pBounds.height);
                                } else {
                                        r1 = new Rectangle(pBounds.x, pBounds.y, pBounds.width, cutY - pBounds.y);
                                        r2 = new Rectangle(pBounds.x, cutY, pBounds.width, (int) (pBounds.getMaxY() - cutY));
                                }
                                if (r1.isEmpty() || r2.isEmpty() || knownBad.contains(r1) || knownBad.contains(r2))
                                        continue;
//                              System.out.println("depth=" + depth + ", trying point " + i + "/" + lastPoint);

                                if (r1.width * r1.height > r2.width * r2.height) {
                                        Rectangle help = r1;
                                        r1 = r2;
                                        r2 = help;
                                }
                                java.awt.geom.Area area = new java.awt.geom.Area(r1);
                                area.intersect(rasteredPolygonArea);
                                part1Sol = findSolutionWithSinglePolygon(depth + 1, tile, area, knownBad);
                               
                                if (part1Sol != null && !part1Sol.isEmpty()) {
                                        area = new java.awt.geom.Area(r2);
                                        area.intersect(rasteredPolygonArea);
                                        part2Sol = findSolutionWithSinglePolygon(depth + 1, tile, area, knownBad);
                                       
                                        if (part2Sol != null && !part2Sol.isEmpty()) {
                                                part1Sol.merge(part2Sol);
                                                return part1Sol;
                                        }
                                        knownBad.add(r2);
                                } else {
                                        knownBad.add(r1);
                                }
                        }
                }
                return new Solution(maxNodes);
        }

        private Solution solveRectangularArea(Tile startTile) {
                if (startTile.getCount() <= 1)
                        return new Solution(maxNodes);
                int bestPossible = stopNumber > 0 ? stopNumber : startTile.getMinParts(maxNodes);
                System.out.println("Splitting tile " + startTile + ", goal is to get near " + bestPossible + " tiles");
                return solveRectangularAreaParallel(startTile, 0);
        }
       
        /**
         * Split large tile into smaller parts with a simple split and solve the small parts using parallel stream.
         * @param startTile the tile to split
         * @param depth recursion depth
         * @return solution
         */

        private Solution solveRectangularAreaParallel(Tile startTile, int depth) {
                if (depth == 0 && (stopNumber > 0 || startTile.getCount() < 256 * maxNodes))
                        return solveRectangularAreaOne(startTile);

                Solution res = new Solution(maxNodes);
                long partSize = 64 * maxNodes;
                if (depth > 0) {
                        partSize = Math.max(1, startTile.getCount() - 1);
                }
                List<Tile> todo = startTile.divide(partSize);
                System.out.println("Initial simple split returned " + todo.size() + " tile(s)");
                List<Solver> solvers = new ArrayList<>();
                List<Area> initialAreas = new ArrayList<>();

                for (Tile t : todo) {
                        if (t.outsidePolygon())
                                continue;
                        if (trimTiles)
                                t = t.trim();
                        int areaSize = t.width * t.height;
                        boolean useSearchAll = areaSize < 32_000 || t.getCount() < 16 * maxNodes;
                        boolean anyOutside = t.countElemsOutside() > 0;
                        Solver solver = new Solver(++solverId, useSearchAll, maxNodes, t, shift, 0, trimTiles, startSearchLimit, allowEmptyPart);
                        solver.maxAspectRatio = getStartRatio(startTile);
                       
                        System.out.println("Using " + solver.toString() + " on " + Utils.format(areaSize) + " grid elements"
                                        + (trimTiles && anyOutside ? ", trim needed" : ", trim not needed"));
                       
                        Rectangle r = t.getRealBBox();
                        Area area = new Area(r.y, r.x, (int) r.getMaxY(), (int) r.getMaxX());
                        area.setMapId(solverId);
                        initialAreas.add(area);
//                      if (depth > 0 ||solver.name.startsWith("S19 "))
                        solvers.add(solver);
                }

                solvers.parallelStream().forEach(Solver::solve);
                List<Solver> solvers2 = new ArrayList<>();
                if (enableExtraOpt) {
                        for (int i = 0; i < solvers.size(); i++) {
                                Solver solver = solvers.get(i);
                                Solution s = solver.bestSolution;
                                int goal = solver.startTile.getMinParts(maxNodes);
                                int areaSize = solver.startTile.width * solver.startTile.height;
                                if (areaSize > 200_000)
                                        continue;
                                if (s.size() > 1 && (!s.isNice() || s.size() >= goal + 3)) {
                                        System.out.println("trying to improve poor solution from " + solver);
                                        Solver sv2 = new Solver(++solverId, !solver.searchAll, maxNodes, solver.startTile, shift, stopNumber, solver.trimTiles, startSearchLimit, allowEmptyPart);
                                        System.out.println("Starting " + sv2.toString());
                                        sv2.maxAspectRatio = getStartRatio(startTile);
                                        solvers2.add(sv2);
                                }
                        }
                       
                        solvers2.parallelStream().forEach(Solver::solve);
                }
                for (Solver sv : solvers) {
                        Solution sol = sv.bestSolution;
                        Optional<Solver> opt = solvers2.stream().filter(s2 -> sv.startTile.equals(s2.startTile)).findAny();
                        if (opt.isPresent()) {
                                Solution sol2 = opt.get().bestSolution;
                                if (sol2.isNice() && sol2.isSmallerOrBetter(sol)) {
                                        System.out.println(opt.get().name + ": replaced solution from " + sv.name);
                                        sol = sol2;
                                }
                        }
                        if (sol.isEmpty())
                                sol = solveRectangularAreaParallel(sv.startTile, depth + 1);
                        res.merge(sol);
                }
                return res;
        }

        /**
         * Get a first solution and search for better ones until either a nice solution
         * is found or no improvement was found.
         *
         * @param startTile the tile to split
         * @return a solution (maybe be empty)
         */

        private Solution solveRectangularAreaOne(Tile startTile) {
                // start values for optimization process: we make little steps towards a good
                // solution
                if (startTile.getCount() == 0)
                        return new Solution(maxNodes);
               
                List<Solver> solvers = new ArrayList<>();
                int numAlgos = 2;
               
                for (int i = 0; i < numAlgos; i++) {
                        Solver solver = new Solver(++solverId, i == 1, maxNodes, startTile, shift, stopNumber, trimTiles, startSearchLimit, allowEmptyPart);
                        if (solver.searchAll && startTile.getCount() > 300 * maxNodes)
                                continue; // too complex for FULL
                        if (!solver.searchAll && stopNumber == 0 && startTile.getCount() < 10 * maxNodes)
                                continue; // too simple for SOME
                        solver.maxAspectRatio = getStartRatio(startTile);
                        solvers.add(solver);
                }
                if (solvers.size() == 1) {
                        solvers.get(0).solve();
                } else {
                        ExecutorService threadPool = Executors.newFixedThreadPool(solvers.size());
                        List<Future<?>> futures = new ArrayList<>();
                        for (Solver solver : solvers) {
                                futures.add(threadPool.submit(solver::solve));
                        }
                        threadPool.shutdown();


                        Instant t1 = null;
                        final double n75 = 0.75 * maxNodes;
                        final double n85 = 0.85 * maxNodes;
                        while (!threadPool.isTerminated()) {
                                for (int i = 0; i < solvers.size(); i++) {
                                        Future<?> future = futures.get(i);
                                        if (future.isDone()) {
                                                try {
                                                        future.get();
                                                } catch (InterruptedException | ExecutionException e) {
                                                        throw new SplitFailedException("parallel solver crashed", e.getCause());
                                                }
                                                Solution sol = solvers.get(i).bestSolution;
                                                if (sol.isNice()) {
                                                        if (t1 == null)
                                                                t1 = Instant.now();
                                                        long dt = Duration.between(t1, Instant.now()).getSeconds();
                                                        boolean stop = false;
                                                        if (sol.getWorstMinNodes() >= n85 && dt > 10) {
                                                                stop = true; // all tiles have at least 85% of max-nodes
                                                        } else {
                                                                int num75 = 0;
                                                                for (Tile tile : sol.getTiles()) {
                                                                        if (tile.getCount() < n75)
                                                                                num75++;
                                                                }
                                                                double below75 = 100.0 * num75 / sol.size();
                                                                if (below75 > 5 && dt > 30) {
                                                                        // +5 percent of tiles are less the 75 percent but we waited +30 seconds
                                                                        stop = true;
                                                                }
                                                        }
                                                        if (stop) {
                                                                // stop the other solver
                                                                solvers.forEach(Solver::stop);
                                                        }
                                                }
                                        }
                                }
                                try {
                                        Thread.sleep(500);
                                } catch (InterruptedException e) {
                                        e.printStackTrace();
                                }
                        }
                        // call get() on each future to recognise possible exceptions
                        futures.forEach(f -> {
                                try {
                                        f.get();
                                } catch (InterruptedException | ExecutionException e) {
                                        Thread.currentThread().interrupt();
                                        throw new SplitFailedException("parallel solver crashed", e.getCause());
                                }
                        });
                        // sort by number of tiles so that the smaller number comes first
                        // can't use compareTo here as it prefers the higher worstMinNodes value
                        solvers.sort((o1, o2) -> {
                                int d = Boolean.compare(o1.bestSolution.isNice(), o2.bestSolution.isNice());
                                if (d != 0)
                                        return -d; // prefer nice
                                d = Integer.compare(o1.bestSolution.size(), o2.bestSolution.size());
                                if (d != 0)
                                        return d;
                                // prefer higher min-nodes
                                return Long.compare(o2.bestSolution.getWorstMinNodes(), o1.bestSolution.getWorstMinNodes());
                        });
                }
                Solver best = solvers.get(0);
                if (best.bestSolution.isEmpty()) {
                        int highestCount = extraDensityInfo.getMaxNodesInDensityMapGridElement();
                        // inform user about possible better options?
                        double ratio = (double) highestCount / maxNodes;
                        if (ratio > 4)
                                System.err.printf(
                                                "max-nodes value %d is far below highest node count %d in single grid element, consider using a higher resolution.%n",
                                                maxNodes, highestCount);
                        else if (ratio > 1)
                                System.err.printf(
                                                "max-nodes value %d is below highest node count %d in single grid element, consider using a higher resolution.%n",
                                                maxNodes, highestCount);
                        else if (ratio < 0.25)
                                System.err.printf(
                                                "max-nodes value %d is far above highest node count %d in single grid element, consider using a lower resolution.%n",
                                                maxNodes, highestCount);


                }
                hasEmptyPart = best.hasEmptyPart;
                printFinishMsg(best.bestSolution, best.searchLimit);
                return best.bestSolution;
        }

        private double getStartRatio(Tile startTile) {
                if (extraDensityInfo.getNodeCount() / maxNodes < 4) {
                        return 32;
                }
                double startMaxAspectRatio = startTile.getAspectRatio();
                if (startMaxAspectRatio < 1)
                        startMaxAspectRatio = 1 / startMaxAspectRatio ;
                if (startMaxAspectRatio < NICE_MAX_ASPECT_RATIO)
                        startMaxAspectRatio = NICE_MAX_ASPECT_RATIO;
                return startMaxAspectRatio;
        }

        private void printFinishMsg(Solution solution, int searchLimit) {
                if (!beQuiet) {
                        if (!solution.isEmpty()) {
                                if (solution.getWorstMinNodes() > VERY_NICE_FILL_RATIO * maxNodes && solution.isNice())
                                        System.out.println(
                                                        "Solution is very nice. No need to search for a better solution: " + solution.toString());
                                else
                                        System.out.println("Solution is " + (solution.isNice() ? "" : "not ")
                                                        + "nice. Can't find a better solution with search-limit " + searchLimit + ": "
                                                        + solution.toString());
                        }
                }
        }

        private static void printFinalSplitMsg(Solution solution) {
                System.out.println("Final solution: " + solution.toString());
                if (solution.isNice())
                        System.out.println("This seems to be nice.");
        }

        /**
         * Convert the list of Tile instances of a solution to Area instances, report
         * some statistics.
         *
         * @param sol         the solution
         * @param polygonArea the split polygon
         *
         * @return list of areas
         */

        private List<Area> getAreas(Solution sol, java.awt.geom.Area polygonArea) {
                List<Area> result = new ArrayList<>();
                int minLat = allDensities.getBounds().getMinLat();
                int minLon = allDensities.getBounds().getMinLong();

                if (polygonArea != null) {
                        System.out.println("Trying to cut the areas so that they fit into the polygon ...");
                } else {
                        if (trimShape)
                                sol.trimOuterTiles();
                }

                boolean fits = true;
                for (Tile tile : sol.getTiles()) {
                        if (tile.getCount() == 0)
                                continue;
                        if (!tile.verify())
                                throw new SplitFailedException("found invalid tile");
                        Rectangle r = new Rectangle(minLon + (tile.x << shift), minLat + (tile.y << shift), tile.width << shift,
                                        tile.height << shift);

                        if (polygonArea != null) {
                                java.awt.geom.Area cutArea = new java.awt.geom.Area(r);
                                cutArea.intersect(polygonArea);
                                if (!cutArea.isEmpty() && cutArea.isRectangular()) {
                                        r = cutArea.getBounds();
                                } else {
                                        fits = false;
                                }
                        }
                        Area area = new Area(r.y, r.x, (int) r.getMaxY(), (int) r.getMaxX());
                        if (!beQuiet) {
                                String note;
                                if (tile.getCount() > maxNodes)
                                        note = " but is already at the minimum size so can't be split further";
                                else
                                        note = "";
                                long percentage = 100 * tile.getCount() / maxNodes;
                                System.out.println("Area " + currMapId++ + " covers " + area + " and contains " + tile.getCount()
                                                + " nodes (" + percentage + " %)" + note);
                        }
                        result.add(area);
                }
                if (!fits) {
                        System.out.println("One or more areas do not exactly fit into the bounding polygon");
                }
                return result;

        }

        private static class Solver {
                private final long myMaxNodes;
                private boolean hasEmptyPart;
                private double maxAspectRatio;
                private int countBad;
                private Long minNodes;
                private int searchLimit;
                private LinkedHashMap<Tile, Integer> incomplete;
                private Map<Tile, Long> knownBad = new HashMap<>(50_000);
                static final  int MAX_SEARCH_LIMIT = 5_000_000;
                final String name;
                private boolean searchAll;
                private Solution bestSolution;
                private Solution smallestSolution;
                private boolean stopped;
                private long localOptMinNodes;
                private final Tile startTile;
                private int bestPossible;
                private long largestOptTileCount;
                private int largestOptSize;
                private long optLoops;
                private int[] lastGoodCounts;
                private final int maxTileHeight;
                private final int maxTileWidth;
                private final int stopNumber;
                private final boolean trimTiles;
                private final int startSearchLimit;
                private final boolean allowEmptyPart;
               

                public Solver(int id, boolean searchAll, long maxNodes, Tile startTile, int shift, int stopNumber,
                                boolean trimTiles, int startSearchLimit, boolean allowEmptyPart) {
                        this.searchAll = searchAll;
                        this.myMaxNodes = maxNodes;
                        this.startTile = startTile;
                        this.stopNumber = stopNumber;
                        this.trimTiles = trimTiles;
                        this.startSearchLimit = startSearchLimit;
                        this.allowEmptyPart = allowEmptyPart;
                        incomplete = new LinkedHashMap<>();
                        bestSolution = new Solution(myMaxNodes);
                        name = "S" + id + " " + (searchAll ? "FULL" : "SOME");
                        maxTileHeight = Utils.toMapUnit(MAX_LAT_DEGREES) / (1 << shift);
                        maxTileWidth = Utils.toMapUnit(MAX_LON_DEGREES) / (1 << shift);
                }

                /**
                 * Try to split the tile into nice parts recursively.
                 *
                 * @param depth the recursion depth
                 * @param tile  the tile to be split
                 * @param smiParent meta info for parent tile
                 * @return a solution instance or null
                 */

                private Solution findSolution(int depth, final Tile tile, Tile parent, TileMetaInfo smiParent) {
                        if (stopped)
                                return null;
                        boolean addAndReturn = false;
                        if (tile.getCount() == 0) {
                                if (!allowEmptyPart) {
                                        hasEmptyPart = true;
                                        return null;
                                }
                                if (tile.width * tile.height <= 4)
                                        return null;
                                return new Solution(myMaxNodes); // allow empty part of the world
                        } else if (tile.getCount() > myMaxNodes && tile.width == 1 && tile.height == 1) {
                                addAndReturn = true; // can't split further
                        } else if (tile.getCount() < minNodes && depth == 0) {
                                addAndReturn = true; // nothing to do
                        } else if (tile.getCount() < minNodes) {
                                return null;
                        } else if (tile.getCount() <= myMaxNodes) {
                                double ratio = tile.getAspectRatio();
                                if (ratio < 1.0)
                                        ratio = 1.0 / ratio;
                                if (ratio <= maxAspectRatio) {
                                        if (stopNumber > 0 || myMaxNodes >= LARGE_MAX_NODES || checkSize(tile))
                                                addAndReturn = true;
                                } else {
                                        return null;
                                }
                        } else if (tile.width < 2 && tile.height < 2) {
                                return null;
                        }
                        if (addAndReturn) {
                                if (depth > 0 && smiParent.getNumOutside() > MAX_OUTSIDE_RATIO * tile.width * tile.height
                                                && !tile.outsideRatioIsOK(MAX_OUTSIDE_RATIO)) {                                
                                        return null;
                                }
                                Solution solution = new Solution(myMaxNodes);
                                solution.add(tile); // can't split further
                                return solution;
                        }
                        if (tile.getCount() < minNodes * 2) {
                                return null;
                        }
                        if (!trimTiles && tile.getMinParts(myMaxNodes) * minNodes > tile.getCount()) {
                                return null;
                        }
                       
                        // we have to split the tile
                        Integer alreadyDone = null;
                        if (countBad == 0 && !incomplete.isEmpty()) {
                                alreadyDone = incomplete.remove(tile);
                                if (alreadyDone == null)
                                        incomplete.clear(); // rest is not useful
                        }
                        final boolean isCacheCandidate = depth > 0 && tile.width * tile.height > MIN_TILE_AREA_BAD_CACHE;
                        if (alreadyDone == null && isCacheCandidate) {
                                Long x = knownBad.get(tile);
                                if (x != null && x <= minNodes) {
                                        return null;
                                }
                        }

                        // copy the existing density info from parent
                        // typically, at least one half can be re-used
                        TileMetaInfo smi = new TileMetaInfo(tile, parent, smiParent);
                        smi.setMinNodes(minNodes);

                        // we have to split the tile
                        TestGenerator generator = new TestGenerator(searchAll, tile, smi);
                        int countDone = 0;
                        Solution bestSol = null;

                        while (generator.hasNext()) {
                                int splitPos = generator.next();
                                countDone++;
                                if (alreadyDone != null && countDone <= alreadyDone.intValue()) {
                                        continue;
                                }
                                // create the two parts of the tile
                                int axis = generator.getAxis();
                                boolean ok = axis == AXIS_HOR ? tile.splitHoriz(splitPos, smi) : tile.splitVert(splitPos, smi);
                                if (!ok)
                                        continue;

                                Tile[] parts = smi.getParts();
                                if (parts[0].getCount() > parts[1].getCount()) {
                                        // first try the less populated part
                                        Tile help = parts[0];
                                        parts[0] = parts[1];
                                        parts[1] = help;
                                }
                                Solution[] sols = new Solution[2];
                                int countOK = 0;
                                for (int i = 0; i < 2; i++) {
                                        if (trimTiles && smi.getNumOutside() > 0) {
                                                parts[i] = parts[i].trim();
                                        }
                                        // depth first recursive search
                                        if (incomplete.isEmpty() || incomplete.containsKey(parts[i])) {
                                                sols[i] = findSolution(depth + 1, parts[i], tile, smi);
                                                if (sols[i] == null) {
                                                        countBad++;
                                                        break;
                                                }
                                                countOK++;
                                        }
                                }
                                if (countOK == 2) {
                                        Solution sol = sols[0];
                                        sol.merge(sols[1]);
                                        if (bestSol == null || bestSol.compareTo(sol) > 0)
                                                bestSol = sol;
                                        if (depth > 0 || tile.getCount() > 2 * myMaxNodes)
                                                break; // we found a valid split
                                } else if (countBad >= searchLimit) {
                                        if (DEBUG)
                                                System.out.println(name + ": limit reached " + depth + " min-nodes " + minNodes);
                                        if (depth < MAX_DEPTH_STATS)
                                                lastGoodCounts[depth] = -1;
                                        incomplete.put(tile, countDone - 1);
                                        break;
                                }
                        }

                        if (depth < MAX_DEPTH_STATS && countBad < searchLimit) {
                                lastGoodCounts[depth] = countDone;
                        }

                        smi.propagateToParent(smiParent, tile, parent);

                        if (bestSol == null && countBad < searchLimit && isCacheCandidate) {
                                Long x = knownBad.get(tile);
                                if (x == null || x > minNodes)
                                        knownBad.put(tile, minNodes);
                        }
                       
                        // check if we should perform a local optimisation
                        if (bestSol != null && localOptMinNodes > 0 && bestSol.size() > 2 && bestSol.size() <= 32) {
                                long backupMinNodes = minNodes;
                                boolean backupSearchAll = searchAll;
                                int backupCountBad = countBad;
                                int min = tile.getMinParts(myMaxNodes);
                                int oldSize = bestSol.size();
                                while (bestSol.size() > min) {
                                        localOptMinNodes = Math.max(tile.getCount() / bestSol.size(), bestSol.getWorstMinNodes() + 1);
                                        minNodes = localOptMinNodes;
                                        searchAll = false;
                                        countBad = 0;
                                        Solution sol2 = findSolution(depth, tile, parent, smiParent);
                                        if(DEBUG) {
                                                if (countBad > 200_000) {
                                                        System.out.println(name + ": bad opt? tile " + tile + " required " + countBad + " bad tests for " + sol2);
                                                }
                                        }
                                        optLoops++;
                                        minNodes = backupMinNodes;
                                        searchAll = backupSearchAll;
                                        if (sol2 != null && sol2.isSmallerOrBetter(bestSol)) {
                                                if (tile.getCount() > largestOptTileCount)
                                                        largestOptTileCount = tile.getCount();
                                                if (oldSize > largestOptSize)
                                                        largestOptSize = oldSize;
                                                bestSol = sol2; // we found a better split
                                        } else
                                                break;
                                }
                                countBad = backupCountBad;
                        }
                        return bestSol;
                }

                private boolean checkSize(Tile tile) {
                        return tile.height <= maxTileHeight && tile.width <= maxTileWidth;
                }

                @Override
                public String toString() {
                        return name + " for tile " +startTile;
                }
               
                public void solve() {
                        bestPossible = stopNumber > 0 ? stopNumber : startTile.getMinParts(myMaxNodes);
                        solve0();
                        if (smallestSolution.isSmallerOrBetter(bestSolution))
                                bestSolution = smallestSolution;
                        System.out.println(name + " goal was " + bestPossible + " tiles, solver "
                                        + (stopped ? "was stopped" : "finished") + " with : " + bestSolution.toString());
                        knownBad.clear();
                        incomplete.clear();
                }
               
                private void solve0() {
                        knownBad.clear();
                        lastGoodCounts = new int[MAX_DEPTH_STATS];
                        bestSolution = new Solution(myMaxNodes);
                        smallestSolution = new Solution(myMaxNodes);
                        minNodes = Math.max(Math.min((long) (0.05 * myMaxNodes), startTile.getLargestInfo()), 1);
                                       
                        searchLimit = startSearchLimit;
                        TileMetaInfo smiStart = new TileMetaInfo(startTile, null, null);
                        final long veryNiceMinNodes = (long) (VERY_NICE_FILL_RATIO * myMaxNodes);
                       
                        boolean clearIncomplete = false;
                        for (int numLoops = 1; numLoops < MAX_LOOPS && !stopped; numLoops++) {
                                if (clearIncomplete) {
                                        incomplete.clear();
                                }
                                // store values to be able to detect progress
                                double saveMaxAspectRatio = maxAspectRatio;
                                long saveMinNodes = minNodes;
                               
                                countBad = 0;
                                final String dbgPrefix = name + ": step " + numLoops;
                                if (DEBUG) {
                                        System.out.println(dbgPrefix + " searching for split with min-nodes " + minNodes + ", cache size " + Utils.format(knownBad.size()));
                                }
                                smiStart.setMinNodes(minNodes);
                                int oldCacheSize = knownBad.size();
                                largestOptTileCount = 0;
                                largestOptSize = 0;
                                Solution solution = findSolution(0, startTile, startTile, smiStart);
                                if (stopped)
                                        return;
                                if (DEBUG) {
                                        System.out.println(dbgPrefix + " positions " + Arrays.toString(lastGoodCounts));
                                        if (optLoops > 0) {
                                                System.out.println(dbgPrefix + " local opt. runs: " + optLoops
                                                                + ", worked up to count " + Utils.format(largestOptTileCount)
                                                                + ", worked up to old size " + largestOptSize
                                                                );
                                        }
                                }
                                if (solution != null) {
                                        if (solution.isSmallerOrBetter(smallestSolution)) {
                                                smallestSolution = solution;
                                        }
                                        if (solution.size() < stopNumber) {
                                                minNodes = (bestSolution.getWorstMinNodes() + solution.getWorstMinNodes()) / 2;
                                                if(minNodes != saveMinNodes)
                                                        continue;
                                                solution = null;
                                        }
                                        boolean foundBetter = bestSolution.compareTo(solution) > 0;
                                        if (solution != null) {
                                                if (foundBetter ) {
                                                        Solution prevBest = bestSolution;
                                                        bestSolution = solution;
                                                        System.out.println(dbgPrefix+ " goal: " + bestPossible + " tiles, now: "
                                                                        + bestSolution + ", cache size " + Utils.format(knownBad.size()));
                                                        // change criteria to find a better(nicer) result
                                                        double factor = 1.10;
                                                        if (!prevBest.isEmpty() && prevBest.isNice())
                                                                factor = Math.min(1.30, (double) bestSolution.getWorstMinNodes() / prevBest.getWorstMinNodes());
                                                        minNodes = Math.max(myMaxNodes / 3, (long) (bestSolution.getWorstMinNodes() * factor));
                                                        if (localOptMinNodes == 0) {
                                                                // enable local optimisation
                                                                minNodes = bestSolution.getWorstMinNodes() + 1;
                                                                localOptMinNodes = minNodes;
                                                        }

                                                } else {
                                                        minNodes = solution.getWorstMinNodes() + 1;
                                                }
                                        }
                                } else if (!bestSolution.isEmpty() && minNodes > bestSolution.getWorstMinNodes() + 1) {
                                        // reduce minNodes
                                        minNodes = (bestSolution.getWorstMinNodes() + minNodes) / 2;
                                        if (minNodes < bestSolution.getWorstMinNodes() * 1.001)
                                                minNodes = bestSolution.getWorstMinNodes() + 1;
                                } else if (!searchAll && oldCacheSize < knownBad.size()) {
                                        if (bestSolution.isEmpty()) {
                                                clearIncomplete = false;
                                                continue;
                                        }
                                }
                                if (!bestSolution.isEmpty() ) {
                                        if (stopNumber * 0.95 > bestSolution.getTiles().size())
                                                return;
                                        if (bestSolution.size() == 1)
                                                return;
                                        if (bestSolution.size() == bestPossible && numLoops > 6) {
                                                return;
                                        }
                                }
                                if (stopNumber == 0 && minNodes > veryNiceMinNodes)
                                        minNodes = veryNiceMinNodes;
                                clearIncomplete = true;
                                maxAspectRatio = Math.min(32, Math.max(bestSolution.getWorstAspectRatio() / 2, NICE_MAX_ASPECT_RATIO));
                                if (saveMaxAspectRatio == maxAspectRatio && saveMinNodes == minNodes) {
                                        // no improvement found
                                        boolean tryAgain = false;
                                        if (bestSolution.isEmpty() || bestSolution.getWorstMinNodes() < 0.5 * myMaxNodes) {
                                                // try to improve by adjusting threshold values
                                                if (countBad > searchLimit && searchLimit < MAX_SEARCH_LIMIT) {
                                                        searchLimit *= 2;
                                                        knownBad.clear();
                                                        clearIncomplete = false;
                                                        System.out.println(name + ": No good solution found, duplicated search-limit to " + searchLimit);
                                                        tryAgain = true;
                                                } else if (bestSolution.isEmpty() && minNodes > 1) {
                                                        minNodes = 1L;
                                                        searchLimit = searchAll? startSearchLimit : Math.max(MAX_SEARCH_LIMIT, startSearchLimit);
                                                        // sanity check
                                                        System.out.println(name + ": No good solution found, trying to find one accepting anything");
                                                        tryAgain = true;
                                                } else if (!bestSolution.isEmpty() && smallestSolution.size() < bestSolution.size()
                                                                && minNodes != smallestSolution.getWorstMinNodes() + 1) {
                                                        minNodes = smallestSolution.getWorstMinNodes() + 1;
                                                        if (DEBUG) {
                                                                System.out.println(name + ": Trying to improve smallest solution");
                                                        }
                                                        tryAgain = true;
                                                }
                                        }
                                        if (!tryAgain) {
                                                return;
                                        }
                                }
                        }
                }

                void stop() {
                        stopped = true;
                }
       
                private class TestGenerator {
                        final boolean searchAll;
                        int axis;
                        final Tile tile;
                        final TileMetaInfo smi;
                        int countAxis;
                        int usedTestPos;
                        private IntArrayList todoList;

                        public TestGenerator(boolean searchAll, Tile tile, TileMetaInfo smi) {
                                this.searchAll = searchAll;
                                this.tile = tile;
                                this.smi = smi;

                                axis = (tile.getAspectRatio() >= 1.0) ? AXIS_HOR : AXIS_VERT;
                                todoList = generateTestCases();
                        }

                        boolean hasNext() {
                                if (usedTestPos >= todoList.size()) {
                                        countAxis++;
                                        if (countAxis > 1)
                                                return false;
                                        axis = axis == AXIS_HOR ? AXIS_VERT : AXIS_HOR;
                                        todoList = generateTestCases();
                                        usedTestPos = 0;
                                }
                                return usedTestPos < todoList.size();
                        }

                        int next() {
                                return todoList.get(usedTestPos++);
                        }

                        public int getAxis() {
                                return axis;
                        }

                        IntArrayList generateTestCases() {
                                final int start = (axis == AXIS_HOR) ? tile.findValidStartX(smi) : tile.findValidStartY(smi);
                                final int end = (axis == AXIS_HOR) ? tile.findValidEndX(smi) : tile.findValidEndY(smi);
                                final int mid = (start + end) / 2;
                                final int range = end - start;
                                if (searchAll || range < 4) {
                                        return Tile.genTests(start, end);
                                }
                                double ratio = tile.getAspectRatio();
                                IntArrayList tests = new IntArrayList();
                                if (range < 0 || ratio < 1.0 / 32 || ratio > 32 || ratio < 1.0 / 16 && axis == AXIS_HOR || ratio > 16 && axis == AXIS_VERT) {
                                        return tests;
                                } else if (range == 0) {
                                        tests.add(start);
                                        return tests;
                                }

                                if (range > 1024 && (axis == AXIS_HOR && tile.width >= maxTileWidth
                                                || axis == AXIS_VERT && tile.height >= maxTileHeight)) {
                                        // large tile, just split at a few valid positions
                                        for (int i = 5; i > 1; --i)
                                                tests.add(start + range / i);

                                } else if (tile.getCount() < myMaxNodes * 4 && range > 256) {
                                        // large tile with rather few nodes, allow more tests
                                        int step = (range) / 20;
                                        for (int pos = start; pos <= end; pos += step)
                                                tests.add(pos);
                                        if (tests.get(tests.size() - 1) != end)
                                                tests.add(end);
                                } else if (tile.getCount() > myMaxNodes * 4) {
                                        int step = range / 7; // 7 turned out to be a good value here
                                        if (step < 1)
                                                step = 1;
                                        for (int pos = start; pos <= end; pos += step)
                                                tests.add(pos);
                                } else {
                                        // count <= 4 * max, this will be one of the last splits
                                        long minCount = smi.getNumOutside() > 0 ? tile.countInside() : tile.getCount();
                                        int nMin = (int) (minCount / myMaxNodes);
                                        if (nMin * myMaxNodes < minCount)
                                                nMin++;
                                        if (nMin == 0) {
                                                nMin++;
                                        }
                                        long limit = nMin == 0? 1 : minCount / nMin;
                                        double dMin = (double) minCount / myMaxNodes;
                                        final int around;
                                        if ((dMin > 1.8 && dMin < 2.0 && ratio > 0.125 && ratio < 8) || (dMin > 2.8 && dMin < 3.0)) {
                                                around = tile.findFirstHigher(axis, smi, limit);
                                        } else if (dMin > 3.8) {
                                                around = tile.findFirstHigher(axis, smi, 2 * limit);
                                        } else {
                                                around = -1;
                                        }
                                        if (around >= 0) {
                                                // this is likely to be a good split, generate more cases
                                                final int numAround = 20;
                                                final int p1 = Math.max(start, around - numAround / 2);
                                                final int p2 = Math.min(end, around + numAround / 2);
                                                final int toAdd = p2 - p1;
                                                if (toAdd > 16)
                                                        tests = new IntArrayList(toAdd);
                                                for (int i = p1; i <= p2; i++) {
                                                        tests.add(i);
                                                }
                                                tests.sort((o1, o2) -> Integer.compare(Math.abs(o1 - around), Math.abs(o2 - around)));
                                                return tests;
                                        }
                                        if (nMin == 4)
                                                tests.add(tile.findFirstHigher(axis, smi, 2 * limit));
                                        tests.add(tile.findFirstHigher(axis, smi, limit));
                                       
                                }
                                if (tests.size() > 4) {
                                        tests.sort((o1, o2) -> Integer.compare(Math.abs(o1 - mid), Math.abs(o2 - mid)));
                                        if (tests.getInt(0) != mid) {
                                                tests.add(0, mid);
                                        }
                                }

                                return tests;
                        }
                }
        }
       
}