package com.vincent.rsf.server.manager.utils;

import java.util.*;
import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * @param
 * @author Ryan
 * @description 根据对象多个属性合并处理
 * @return
 * @time 2025/4/25 10:55
 */
public class OptimalAlgorithmUtil {

    private static List<Double> bestSolution;
    private static double target;
    private static double minDifference;
    private static final double EPSILON = 1e-10;

    /**
     * 根据多个属性分组合并对象列表
     *
     * @param list       待分组的对象列表
     * @param mergers    合并函数，定义如何合并同一组中的对象
     * @param keyGetters 分组属性的getter方法数组
     * @param <T>        对象类型
     * @param <K>        分组键类型
     * @return 分组合并后的对象列表
     */
    @SafeVarargs
    public static <T, K> List<T> groupAndMerge(
            List<T> list,
            BinaryOperator<T> mergers,
            Function<T, K>... keyGetters) {

        return new ArrayList<>(list.stream()
                .collect(Collectors.toMap(
                        item -> new GroupingKeys<>(Arrays.stream(keyGetters)
                                .map(getter -> getter.apply(item))
                                .toArray()),
                        Function.identity(),
                        mergers))
                .values());
    }

    /**
     * @param
     * @author Ryan
     * @description 用于存储多个分组键的内部类
     * @return
     * @time 2025/4/25 10:56
     */
    private static class GroupingKeys<K> {
        private final Object[] keys;
        private final int hashCode;

        public GroupingKeys(Object[] keys) {
            this.keys = keys;
            this.hashCode = Arrays.deepHashCode(keys);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            GroupingKeys<?> that = (GroupingKeys<?>) o;
            return Arrays.deepEquals(keys, that.keys);
        }

        @Override
        public int hashCode() {
            return hashCode;
        }
    }


    /**
     * @param
     * @return
     * @author Ryan
     * @description 获取全拖或非全拖库位
     * @time 2025/4/28 09:41
     */
    public static List<Integer> findCombination(double[] nums, Double target) {
        // 处理等值情况
        List<Integer> equal = findEqual(nums, target);
        if (equal != null && !equal.isEmpty()) {
            return equal;
        }

        // 处理大于的情况
        List<Integer> greater = findGreater(nums, target);
        if (greater != null && !greater.isEmpty()) {
            return greater;
        }

        // 处理小于的情况
        List<Integer> less = findLess(nums, target);
        return less != null ? less : new ArrayList<>(); // 确保不返回null
    }

    /**
     * @author Ryan
     * @description 使用动态规划寻找和等于目标值的最少元素组合。动态规划数组dp记录达到每个和所需的最少元素数目，prev数组记录路径以便回溯找到具体索引。
     * @param  
     * @return 
     * @time 2025/4/28 12:33
     */
    private static List<Integer> findEqual(double[] nums, double target) {
        int n = nums.length;
        double[] dp = new double[(int) (target * 100 + 1)]; // 放大100倍处理精度问题
        Arrays.fill(dp, Double.MAX_VALUE);
        dp[0] = 0;
        int[] prev = new int[(int) (target * 100 + 1)];
        Arrays.fill(prev, -1);

        for (int j = 0; j < n; j++) {
            int num = (int) (nums[j] * 100); // 放大100倍处理精度问题
            for (int i = (int) (target * 100); i >= num; i--) {
                if (dp[i - num] != Double.MAX_VALUE && dp[i - num] + 1 < dp[i]) {
                    dp[i] = dp[i - num] + 1;
                    prev[i] = j;
                }
            }
        }

        if (dp[(int) (target * 100)] == Double.MAX_VALUE) {
            return null;
        }

        List<Integer> indices = new ArrayList<>();
        int current = (int) (target * 100);
        while (current > 0) {
            int j = prev[current];
            if (j == -1) return null;
            indices.add(j);
            current -= (int) (nums[j] * 100);
        }

        return indices;
    }

    /**
     * @author Ryan
     * @description 将数组降序排序后，贪心地累加元素直到总和超过目标值，返回这些元素的索引
     * @param
     * @return 
     * @time 2025/4/28 12:34
     */
    private static List<Integer> findGreater(double[] nums, double target) {
        List<double[]> sorted = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            sorted.add(new double[]{nums[i], i});
        }
        sorted.sort((a, b) -> Double.compare(b[0], a[0]));

        double sum = 0;
        List<Integer> indices = new ArrayList<>();
        for (double[] pair : sorted) {
            sum += pair[0];
            indices.add((int) pair[1]);
            if (sum > target) {
                return indices;
            }
        }

        return null;
    }

    /**
     * @author Ryan
     * @description 使用回溯法生成所有可能的组合，寻找总和最大但不超过目标值的组合，并记录元素数目最少的组合。
     * @param
     * @return
     * @time 2025/4/28 12:34
     */
    private static List<Integer> findLess(double[] nums, double target) {
        int n = nums.length;
        List<Integer> bestIndices = new ArrayList<>();
        double[] maxSum = {-1.0};
        for (int k = 1; k <= n; k++) {
            List<Integer> currentIndices = new ArrayList<>();
            double[] currentMax = {-1.0};
            backtrack(nums, target, 0, k, 0.0, 0, currentIndices, currentMax, new ArrayList<>());
            if (currentMax[0] != -1.0) {
                if (currentMax[0] > maxSum[0] || (currentMax[0] == maxSum[0] && currentIndices.size() < bestIndices.size())) {
                    maxSum[0] = currentMax[0];
                    bestIndices = new ArrayList<>(currentIndices);
                }
            }
        }

        return bestIndices.isEmpty() ? null : bestIndices;
    }

    private static void backtrack(double[] nums, double target, int start, int k, double currentSum, int count, List<Integer> currentIndices, double[] currentMax, List<Integer> path) {
        if (count == k) {
            if (currentSum <= target && currentSum > currentMax[0]) {
                currentMax[0] = currentSum;
                currentIndices.clear();
                currentIndices.addAll(path);
            }
            return;
        }

        for (int i = start; i < nums.length; i++) {
            if (currentSum + nums[i] > target) continue;
            path.add(i);
            backtrack(nums, target, i + 1, k, currentSum + nums[i], count + 1, currentIndices, currentMax, path);
            path.remove(path.size() - 1);
        }
    }

}