package com.paveloleynik.shortroute;

import com.google.android.gms.maps.model.LatLng;

import java.util.ArrayList;
import java.util.List;

/**
 * DijkstraAlgorithm
 * Created by MATHAHAKAR (Oleynik Pavel) on 25.02.2017.
 * Project: ShortRoute
 */

public class WarshallAlgorithm {

    private static final WarshallAlgorithm D_A = new WarshallAlgorithm();

    private static List<LatLng> mPoints = new ArrayList<>();
    private static List<LatLng> fPoints  = new ArrayList<>(); // for output

    public static List<LatLng> getRoute (List<LatLng> points) {
        mPoints.clear();
        fPoints.clear();

        addPoints(points);
        findRoute();
        return fPoints;
    }

    private static void addPoints (List<LatLng> points) {
        mPoints = points;
    }

    private static void findRoute () {

        while (mPoints.size() > 0) {

            double dist[] = new double[mPoints.size()];

            for (int j = 0; j < mPoints.size(); j ++) {
                if (j != 0) {
                    dist[j] = getWeight(mPoints.get(0), mPoints.get(j));
                }
            }

            double min = findMinValue(dist);
            int iMin = 0;

            for (int m = 0; m < dist.length; m ++) {
                if (dist[m] == min) iMin = m;
            }

            fPoints.add(mPoints.get(iMin));
            mPoints.remove(0);

            if (mPoints.size() > 0) {

                for (int i = 1; i < mPoints.size(); i ++) {
                    if (mPoints.get(i) != null) {
                        LatLng latLng = mPoints.remove(i);
                        mPoints.add(i - 1, latLng);
                    }
                }

            }

        }

    }

    private static double findMinValue (double[] d) {
        double min = d[0];
        double max = min;
        for (int i = 0; i < d.length; i ++) {
            if (d[i] > max) max = d[i];
            if (d[i] < min) min = d[i];
        }
        return min;
    }

    private static double getWeight (LatLng latLng1, LatLng latLng2) {
        double ax = latLng1.latitude;
        double ay = latLng1.longitude;
        double bx = latLng2.latitude;
        double by = latLng2.longitude;
        return Math.sqrt( (Math.pow((bx - ax), 2)) + (Math.pow((by - ay), 2)) );
    }

}