WebSVN - splitter - Rev 639 - /branches/solve-parallel/src/uk/me/parabola/splitter/solver/Solution.java

/*
* Copyright (C) 2014, Gerd Petermann
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 3 or
* version 2 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.Rectangle;
import java.util.ArrayList;
import java.util.List;

/**
* Helper class to combine a list of tiles with some
* values that measure the quality.
* @author GerdP
*
*/
public class Solution {
/**
*
*/
private enum sides {TOP,RIGHT,BOTTOM,LEFT}

private final List<Tile> tiles;
private final long maxNodes;
private double worstAspectRatio = -1;
private int numLowCount;
private long worstMinNodes = Long.MAX_VALUE;

public Solution(long maxNodes) {
tiles = new ArrayList<>();
this.maxNodes = maxNodes;
}

public Solution copy() {
Solution s = new Solution(this.maxNodes);
tiles.forEach(s::add);
return s;
}

public boolean add(Tile tile) {
tiles.add(tile);
double aspectRatio = tile.getAspectRatio();
if (aspectRatio < 1.0)
aspectRatio = 1.0 / aspectRatio;
worstAspectRatio = Math.max(aspectRatio, worstAspectRatio);
worstMinNodes = Math.min(tile.getCount(), worstMinNodes);
if (tile.getCount() < maxNodes / 3)
numLowCount++;
return true;
}

/**
* Combine this solution with the other.
* @param other
*/
public void merge(Solution other) {
if (other.tiles.isEmpty())
return;

if (tiles.isEmpty()) {
worstAspectRatio = other.worstAspectRatio;
worstMinNodes = other.worstMinNodes;
} else {
if (other.worstAspectRatio > worstAspectRatio)
worstAspectRatio = other.worstAspectRatio;
if (worstMinNodes > other.worstMinNodes)
worstMinNodes = other.worstMinNodes;
}
numLowCount += other.numLowCount;
tiles.addAll(other.tiles);
}

public List<Tile> getTiles() {
return tiles;
}

public long getWorstMinNodes() {
return worstMinNodes;
}

public double getWorstAspectRatio() {
return worstAspectRatio;
}

public boolean isEmpty() {
return tiles.isEmpty();
}

public int size() {
return tiles.size();
}

/**
* Compare two solutions
* @param other
* @return -1 if this is better, 1 if other is better, 0 if both are equal
*/
public int compareTo(Solution other) {
if (other == null)
return -1;
if (other == this)
return 0;
if (isEmpty() != other.isEmpty())
return isEmpty() ? 1 : -1;
int d = Boolean.compare(isNice(), other.isNice());
if (d != 0)
return -d; // prefer this if nice

if (worstMinNodes != other.worstMinNodes) {
// ignore minNodes when both are bad
if (Math.max(worstMinNodes, other.worstMinNodes) > 1000)
return (worstMinNodes > other.worstMinNodes) ? -1 : 1;
}
// if aspect ratio is very different and tile sizes are almost equal,
// favour better aspect ratio
double tileRatio = (double) tiles.size() / other.tiles.size();
double arRatio = worstAspectRatio / other.worstAspectRatio;
if (tileRatio < 1 && tileRatio > 0.99 && arRatio > 1.5)
return 1;
if (tileRatio < 1.01 && tileRatio > 1 && arRatio < 0.66666)
return -1;

if (tiles.size() != other.tiles.size())
return tiles.size() < other.tiles.size() ? -1 : 1;
if (worstAspectRatio != other.worstAspectRatio)
return worstAspectRatio < other.worstAspectRatio ? -1 : 1;
return 0;
}

/**
* Trim tiles without creating holes or gaps between tiles
*/
public void trimOuterTiles() {
while (true) {
boolean trimmedAny = false;

int minX = Integer.MAX_VALUE;
int maxX = Integer.MIN_VALUE;
int minY = Integer.MAX_VALUE;
int maxY = Integer.MIN_VALUE;

for (Tile tile : tiles) {
if (minX > tile.x) minX = tile.x;
if (minY > tile.y) minY = tile.y;
if (maxX < tile.getMaxX()) maxX = (int) tile.getMaxX();
if (maxY < tile.getMaxY()) maxY = (int) tile.getMaxY();
}
for (sides side:sides.values()) {
for (int direction = -1; direction <= 1; direction += 2) {
int trimToPos = -1;
switch (side) {
case LEFT:
case BOTTOM: trimToPos = Integer.MAX_VALUE;
break;
case TOP:
case RIGHT: trimToPos = -1;
}
while (true) {
Tile candidate = null;
boolean trimmed = false;
for (Tile tile : tiles) {
if (tile.getCount() == 0)
continue;
switch (side) {
case LEFT:
if (minX == tile.x && (candidate == null || (direction < 0 && candidate.y > tile.y)
|| (direction > 0 && candidate.getMaxY() < tile.getMaxY()))) {
candidate = tile;
}
break;
case RIGHT:
if (maxX == tile.getMaxX()
&& (candidate == null || (direction < 0 && candidate.y > tile.y)
|| (direction > 0 && candidate.getMaxY() < tile.getMaxY()))) {
candidate = tile;
}
break;
case BOTTOM:
if (minY == tile.y && (candidate == null || (direction < 0 && candidate.x > tile.x)
|| (direction > 0 && candidate.getMaxX() < tile.getMaxX()))) {
candidate = tile;
}
break;
case TOP:
if (maxY == tile.getMaxY()
&& (candidate == null || (direction < 0 && candidate.x > tile.x)
|| (direction > 0 && candidate.getMaxX() < tile.getMaxX()))) {
candidate = tile;
}
break;
}
}
if (candidate == null)
break;
Rectangle before = new Rectangle(candidate);
switch (side) {
case LEFT:
while (candidate.x < trimToPos && candidate.getColSum(0) == 0) {
candidate.x ++;
candidate.width--;
}
if (candidate.x < trimToPos)
trimToPos = candidate.x;
break;
case RIGHT:
while ((candidate.getMaxX() > trimToPos) && candidate.getColSum(candidate.width-1) == 0) {
candidate.width--;
}
if (candidate.getMaxX() > trimToPos)
trimToPos = (int) candidate.getMaxX();
break;
case BOTTOM:
while (candidate.y < trimToPos && candidate.getRowSum(0) == 0) {
candidate.y ++;
candidate.height--;
}
if (candidate.y < trimToPos)
trimToPos = candidate.y;
break;
case TOP:
while (candidate.getMaxY() > trimToPos && candidate.getRowSum(candidate.height-1) == 0) {
candidate.height--;
}
if (candidate.getMaxX() > trimToPos)
trimToPos = (int) candidate.getMaxY();
break;
}
if (!before.equals(candidate)) {
trimmed = true;
trimmedAny = true;
}
if (!trimmed)
break;
}
}
}
if (!trimmedAny)
return;
}
}

/**
* A solution is considered to be nice when aspect
* ratios are not extreme and every tile is filled
* with at least 33% of the max-nodes value or almost all tiles are filled much better.
* @return
*/
public boolean isNice() {
if (isEmpty() || worstAspectRatio > SplittableDensityArea.NICE_MAX_ASPECT_RATIO)
return false;
final long low = maxNodes / 3;
if (tiles.size() == 1 || worstMinNodes >= low || (numLowCount <= 2 && tiles.size() > 20)
|| (numLowCount == 1 && tiles.size() > 4))
return true;
double lowRatio = 100.0 * numLowCount / tiles.size();
return lowRatio < 3; // less then 3 percent of the tiles are not well filled
}

@Override
public String toString() {
if (isEmpty())
return "is empty";
long percentage = 100 * worstMinNodes / maxNodes;
return tiles.size() + " tile(s). The smallest node count is " + worstMinNodes + " (" + percentage + " %)";

}

/**
* Returns true if this solution is smaller or better than the other.
* @param other the other solution
* @return true if this solution is smaller or better than the other
*/
public boolean isSmallerOrBetter(Solution other) {
if (isEmpty())
return false;
if (other == null || other.isEmpty() && !isEmpty())
return true;
if (other.size() > this.size())
return true;
if (other.size() == this.size())
return compareTo(other) < 0;
return false;
}
}

Subversion Repositories splitter

(root)/branches/solve-parallel/src/uk/me/parabola/splitter/solver/Solution.java - Rev 639