package com.github.davidmoten.rtree;

import static com.google.common.base.Optional.of;

import java.util.List;

import com.github.davidmoten.rtree.geometry.Geometry;
import com.github.davidmoten.rtree.geometry.Rectangle;
import com.google.common.base.Optional;

public final class SelectorMinimalAreaIncrease implements Selector {

	@Override
	public <T> Node<T> select(Geometry g, List<? extends Node<T>> nodes) {
		return findLeastIncreaseInMbrArea(g.mbr(), nodes);
	}

	static <T> Node<T> findLeastIncreaseInMbrArea(Rectangle r,
			List<? extends Node<T>> list) {
		Optional<Double> minDifference = Optional.absent();
		Optional<Node<T>> minDiffItem = Optional.absent();
		for (Node<T> m : list) {
			double diff = m.geometry().mbr().add(r).area()
					- m.geometry().mbr().area();
			if (!minDifference.isPresent() || diff < minDifference.get()) {
				minDifference = of(diff);
				minDiffItem = of(m);
			}
		}
		return minDiffItem.get();
	}

}

@@ -99,19 +99,74 @@
 va.util.
-Lis
+Comparator;%0Aimport java.util.List;%0Aimport java.util.TreeSe
 t;%0A%0Aimpo
@@ -622,91 +622,89 @@
 %7B%0A%09%09
-Optional%3CDouble%3E minDifference = Optional.absent();%0A%09%09Optional%3CNode%3CT%3E%3E minDiffItem
+TreeSet%3CNode%3CT%3E%3E best = new TreeSet%3CNode%3CT%3E%3E(area);%0A%09%09Optional%3CDouble%3E bestMetric
  = O
@@ -736,17 +736,20 @@
 Node%3CT%3E 
-m
+node
  : list)
@@ -765,16 +765,16 @@
 ble 
-diff = m
+m = node
 .geo
@@ -808,17 +808,20 @@
 %0A%09%09%09%09%09- 
-m
+node
 .geometr
@@ -846,29 +846,26 @@
 %09%09%09if (!
-minDifference
+bestMetric
 .isPrese
@@ -876,132 +876,466 @@
  %7C%7C 
-diff %3C minDifference.get()) %7B%0A%09%09%09%09minDifference = of(diff);%0A%09%09%09%09minDiffItem = of(m);%0A%09%09%09%7D%0A%09%09%7D%0A%09%09return minDiffItem.get(
+m %3C bestMetric.get()) %7B%0A%09%09%09%09bestMetric = of(m);%0A%09%09%09%09best = new TreeSet%3CNode%3CT%3E%3E(area);%0A%09%09%09%09best.add(node);%0A%09%09%09%7D else if (bestMetric.isPresent() && m == bestMetric.get()) %7B%0A%09%09%09%09best.add(node);%0A%09%09%09%7D%0A%09%09%7D%0A%09%09return best.first();%0A%09%7D%0A%0A%09private static Comparator%3CNode%3C?%3E%3E area = new Comparator%3CNode%3C?%3E%3E() %7B%0A%0A%09%09@Override%0A%09%09public int compare(Node%3C?%3E n1, Node%3C?%3E n2) %7B%0A%09%09%09return ((Float) n1.geometry().mbr().area()).compareTo(n2.geometry()%0A%09%09%09%09%09.mbr().area()
 );%0A
+%09
 %09%7D
+%0A%09%7D;
 %0A%0A%7D%0A

add R*-tree heuristics