package com.github.davidmoten.rtree;

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

import java.util.Comparator;
import java.util.List;
import java.util.TreeSet;

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) {
		TreeSet<Node<T>> best = new TreeSet<Node<T>>(area);
		Optional<Double> bestMetric = Optional.absent();
		for (Node<T> node : list) {
			double m = node.geometry().mbr().add(r).area()
					- node.geometry().mbr().area();
			if (!bestMetric.isPresent() || m < bestMetric.get()) {
				bestMetric = of(m);
				best = new TreeSet<Node<T>>(area);
				best.add(node);
			} else if (bestMetric.isPresent() && m == bestMetric.get()) {
				best.add(node);
			}
		}
		return best.first();
	}

	private static Comparator<Node<?>> area = new Comparator<Node<?>>() {

		@Override
		public int compare(Node<?> n1, Node<?> n2) {
			return ((Float) n1.geometry().mbr().area()).compareTo(n2.geometry()
					.mbr().area());
		}
	};

}

@@ -82,16 +82,44 @@
 al.of;%0A%0A
+import java.util.ArrayList;%0A
 import j
@@ -139,16 +139,16 @@
 arator;%0A
-
 import j
@@ -646,22 +646,19 @@
 st) %7B%0A%09%09
-TreeSe
+Lis
 t%3CNode%3CT
@@ -663,38 +663,40 @@
 %3CT%3E%3E best = new 
-TreeSe
+ArrayLis
 t%3CNode%3CT%3E%3E(area)
@@ -686,28 +686,24 @@
 st%3CNode%3CT%3E%3E(
-area
 );%0A%09%09Optiona
@@ -958,22 +958,24 @@
 t = new 
-TreeSe
+ArrayLis
 t%3CNode%3CT
@@ -977,20 +977,16 @@
 ode%3CT%3E%3E(
-area
 );%0A%09%09%09%09b
@@ -1098,21 +1098,106 @@
 %09%09%7D%0A
+%0A
 %09%09
+T
 re
-turn best
+eSet%3CNode%3CT%3E%3E ordered = new TreeSet%3CNode%3CT%3E%3E(area);%0A%09%09ordered.addAll(best);%0A%09%09return ordered
 .fir

improve performance