package com.github.davidmoten.rtree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.github.davidmoten.guavamini.Preconditions;
import com.github.davidmoten.guavamini.annotations.VisibleForTesting;
import com.github.davidmoten.rtree.geometry.HasGeometry;
import com.github.davidmoten.rtree.geometry.ListPair;
import com.github.davidmoten.rtree.internal.Comparators;

import rx.functions.Func1;

public final class SplitterRStar implements Splitter {

    private final Comparator<ListPair<?>> comparator;

    @SuppressWarnings("unchecked")
    public SplitterRStar() {
        this.comparator = Comparators.compose(Comparators.overlapListPairComparator,
                Comparators.areaPairComparator);
    }

    @Override
    public <T extends HasGeometry> ListPair<T> split(List<T> items, int minSize) {
        Preconditions.checkArgument(!items.isEmpty());
        // sort nodes into increasing x, calculate min overlap where both groups
        // have more than minChildren

        Map<SortType, List<ListPair<T>>> map = new HashMap<SortType, List<ListPair<T>>>(5, 1.0f);
        map.put(SortType.X_LOWER, getPairs(minSize, sort(items, INCREASING_X_LOWER)));
        map.put(SortType.X_UPPER, getPairs(minSize, sort(items, INCREASING_X_UPPER)));
        map.put(SortType.Y_LOWER, getPairs(minSize, sort(items, INCREASING_Y_LOWER)));
        map.put(SortType.Y_UPPER, getPairs(minSize, sort(items, INCREASING_Y_UPPER)));

        // compute S the sum of all margin-values of the lists above
        // the list with the least S is then used to find minimum overlap

        SortType leastMarginSumSortType = Collections.min(sortTypes, marginSumComparator(map));
        List<ListPair<T>> pairs = map.get(leastMarginSumSortType);

        return Collections.min(pairs, comparator);
    }

    private static enum SortType {
        X_LOWER, X_UPPER, Y_LOWER, Y_UPPER;
    }

    private static final List<SortType> sortTypes = Collections
            .unmodifiableList(Arrays.asList(SortType.values()));

    private static <T extends HasGeometry> Comparator<SortType> marginSumComparator(
            final Map<SortType, List<ListPair<T>>> map) {
        return Comparators.toComparator(new Func1<SortType, Double>() {
            @Override
            public Double call(SortType sortType) {
                return (double) marginValueSum(map.get(sortType));
            }
        });
    }

    private static <T extends HasGeometry> float marginValueSum(List<ListPair<T>> list) {
        float sum = 0;
        for (ListPair<T> p : list)
            sum += p.marginSum();
        return sum;
    }

    @VisibleForTesting
    static <T extends HasGeometry> List<ListPair<T>> getPairs(int minSize, List<T> list) {
        List<ListPair<T>> pairs = new ArrayList<ListPair<T>>(list.size() - 2 * minSize + 1);
        for (int i = minSize; i < list.size() - minSize + 1; i++) {
            List<T> list1 = list.subList(0, i);
            List<T> list2 = list.subList(i, list.size());
            ListPair<T> pair = new ListPair<T>(list1, list2);
            pairs.add(pair);
        }
        return pairs;
    }

    private static <T extends HasGeometry> List<T> sort(List<T> items,
            Comparator<HasGeometry> comparator) {
        ArrayList<T> list = new ArrayList<T>(items);
        Collections.sort(list, comparator);
        return list;
    }

    private static Comparator<HasGeometry> INCREASING_X_LOWER = new Comparator<HasGeometry>() {

        @Override
        public int compare(HasGeometry n1, HasGeometry n2) {
            return Float.compare(n1.geometry().mbr().x1(), n2.geometry().mbr().x1());
        }
    };

    private static Comparator<HasGeometry> INCREASING_X_UPPER = new Comparator<HasGeometry>() {

        @Override
        public int compare(HasGeometry n1, HasGeometry n2) {
            return Float.compare(n1.geometry().mbr().x2(), n2.geometry().mbr().x2());
        }
    };

    private static Comparator<HasGeometry> INCREASING_Y_LOWER = new Comparator<HasGeometry>() {

        @Override
        public int compare(HasGeometry n1, HasGeometry n2) {
            return Float.compare(n1.geometry().mbr().y1(), n2.geometry().mbr().y1());
        }
    };

    private static Comparator<HasGeometry> INCREASING_Y_UPPER = new Comparator<HasGeometry>() {

        @Override
        public int compare(HasGeometry n1, HasGeometry n2) {
            return Float.compare(n1.geometry().mbr().y2(), n2.geometry().mbr().y2());
        }
    };

}

@@ -3519,32 +3519,38 @@
  private static 
+final 
 Comparator%3CHasGe
@@ -3602,32 +3602,32 @@
 asGeometry%3E() %7B%0A
-
 %0A        @Overri
@@ -3805,32 +3805,38 @@
  private static 
+final 
 Comparator%3CHasGe
@@ -4091,32 +4091,38 @@
  private static 
+final 
 Comparator%3CHasGe
@@ -4358,32 +4358,32 @@
       %7D%0A    %7D;%0A%0A
-
     private stat
@@ -4385,16 +4385,22 @@
  static 
+final 
 Comparat

add final to static comparators in SplitterRStar