package com.demo.navtogether.utils;

import android.graphics.Point;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * My father is Object, ites purpose of  迪杰斯特拉算法
 *
 * @purpose Created by Runt (qingingrunt2010@qq.com) on 2020-12-23.
 */

public class DijkstraUtils {

    HashMap<PathPlan.Place, PathPlan.Distance> distances;//每个点的信息集合

    public DijkstraUtils(HashMap<PathPlan.Place, PathPlan.Distance> distances) {
        this.distances = distances;
    }


    public ArrayList<PathPlan.Place> excute(PathPlan.Place start ){
       return excute(start,null);
    }

    /**
     * 执行算法
     * @param start  起点
     * @param end
     */
    public ArrayList<PathPlan.Place> excute(PathPlan.Place start, PathPlan.Place end){

        PathPlan.Distance startDis = distances.get(start);
        PathPlan.Distance endDis = end == null ? null:distances.get(end);
        deletePlace(start);
        if(end != null){//如果有终点则去除
            deletePlace(end);
        }
        ArrayList<PathPlan.Place> places = new ArrayList<>();
        places.add(start);
        while (distances.size()>0){//循环遍历
            PathPlan.Place nearWay = findNearWay(startDis);//获取与其他点的最短个那一个
            startDis = distances.get(nearWay);//距离信息
            deletePlace(nearWay);//从集合中删除，避免下次循环再次出现该地点
            places.add(nearWay);//添加到线路集合记录中
        }
        if(end != null){//如果有终点则最后追加
            end.distance = endDis.distanceMap.get(places.get(places.size()-1));
            places.add(end);
        }
        return places;//返回规划的路线集合

    }

    /**
     * 清除位置
     * @param place
     */
    private void deletePlace(PathPlan.Place place){
        distances.remove(place);
        for(PathPlan.Place p : distances.keySet()){//将与之相关的距离也清除
            distances.get(p).distanceMap.remove(place);
        }
    }

    /**
     * 寻找最近的位置
     * @return
     */
    public PathPlan.Place findNearWay(PathPlan.Distance distance){
        PathPlan.Place place = null;
        double dist = -1;
        for(PathPlan.Place temp : distance.distanceMap.keySet()){//循环遍历
            double placeDist =  distance.distanceMap.get(temp);//对应位置距离；
            placeDist = placeDist - placeDist*temp.priority/100;//计算权重
            if(dist == -1){
                dist = placeDist;
                temp.distance = dist;
                place = temp;
            }else if( dist > placeDist){//若小于之前对比的数据
                dist = placeDist;
                temp.distance = dist;
                place = temp;
            }
        }
        return place;
    }


    public static void main(String[] args) {

        ArrayList<PathPlan.Place> places = new ArrayList<>();
        places.add(new PathPlan.Place("A",random(),0));
        places.add(new PathPlan.Place("B",random(),0));
        places.add(new PathPlan.Place("C",random(),0));
        places.add(new PathPlan.Place("D",random(),0));
        places.add(new PathPlan.Place("E",random(),0));
        places.add(new PathPlan.Place("F",random(),0));
        Map map = new HashMap();
        map.put(places.get(2),"hehe");
        System.out.println("2"+map.get(places.get(2)));
        ArrayList<PathPlan.Place> excute = new DijkstraUtils(PathPlan.intPoints(places)).excute(places.get(2));
        for(int i = 0 ; i < excute.size() ; i ++){
            System.out.println(excute.get(i)+" 距离："+(i == excute.size() -1?"":TriangleUtils.getLengthOfSide(excute.get(i).point,excute.get(i+1).point)) +" "+excute.get(i).distance);
        }


    }

    ArrayList<ArrayList<PathPlan.Place>> arrayLists = new ArrayList<>();//路线记录
    /**
     * 自定义规划路线算法
     * @param start 起始地点
     * @param end   末尾地点
     */
    public  ArrayList<ArrayList<PathPlan.Place>> initCustomPathPlan(  PathPlan.Place start,PathPlan.Place end){
        arrayLists.clear();//清空记录
        ArrayList<PathPlan.Place > places = new ArrayList<>(distances.keySet());//所有地点集合
        for(int i=1;i<=places.size();i++){
            sortPlace(places,new ArrayList<PathPlan.Place>(),i,start,end);
        }
        return arrayLists;

    }
    //最短距离
    double dist = -1;

    /**
     * 组合
     * @param datas  地点数据
     * @param target 整理的新路线
     * @param num   循环的下标位置，即路线规划的地点数量
     * @param start 起始地点
     * @param end   末尾地点
     */
    private void sortPlace(ArrayList<PathPlan.Place>  datas, ArrayList<PathPlan.Place>  target,int num,PathPlan.Place start,PathPlan.Place end) {
        if (target.size() == num) {
            ArrayList newDatas = new ArrayList( );
            ArrayList<PathPlan.Place > places = new ArrayList<>(distances.keySet());//所有地点集合
            //数量不够，起始和末尾不对应，则不再执行
            if(places.size()> num || start!=null && !target.get(0).equals(start) || end!=null && !target.get(target.size()-1).equals(end)){
                return;
            }
            double tempDist = 0 ;
            for (PathPlan.Place obj : target) {
                //复制对象
                PathPlan.Place place = new PathPlan.Place(obj);
                //距离
                place.distance = newDatas.size() == 0 ?0: distances.get(obj).distanceMap.get(newDatas.get(newDatas.size() - 1));
                tempDist+=place.distance;
                newDatas.add(place);
            }
            //记录最短距离
            if(dist == -1 || dist >= tempDist){
                if(dist > tempDist){
                    arrayLists.clear();//清除之前的数据
                }
                dist = tempDist;
                arrayLists.add(newDatas);
            }else if(dist < tempDist){ //当前距离不是最短
                return;
            }
            return;
        }
        for (int i = 0; i < datas.size(); i++) {
            ArrayList newDatas = new ArrayList(datas);
            ArrayList newTarget = new ArrayList(target);
            newTarget.add(newDatas.get(i));
            newDatas.remove(i);
            sortPlace(newDatas, newTarget,num,start,end);
        }
    }

    /**
     * 创建一个随机位置  坐标在0-100内
     * @return
     */
    public static Point random(){
        Point point = new Point();

        point.x  = (int) (Math.random()*100);
        point.y  = (int) (Math.random()*100);

        return point;
    }

}