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;

/**
 * @author Ryan
 * @description 根据对象多个属性合并处理
 * @param
 * @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());
    }

    /**
     * @author Ryan
     * @description 用于存储多个分组键的内部类
     * @param
     * @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;
        }
    }


    public static List<Double> findBestCombination(Double[] candidates, double targetSum) {
        bestSolution = null;
        target = targetSum;
        minDifference = Double.MAX_VALUE;
        Arrays.sort(candidates);
        backtrack(candidates, 0, new ArrayList<>(), 0.0);

        // 如果没有精确解，返回最接近的近似解
        return bestSolution != null ? bestSolution : new ArrayList<>();
    }

    private static void backtrack(Double[] candidates, int start,
                                  List<Double> current, double currentSum) {
        // 计算当前和与目标的差值
        double difference = Math.abs(currentSum - target);

        // 如果找到更优解（差值更小或差值相同但组合更短）
        if (difference < minDifference - EPSILON ||
                (Math.abs(difference - minDifference) < EPSILON &&
                        (bestSolution == null || current.size() < bestSolution.size()))) {
            minDifference = difference;
            bestSolution = new ArrayList<>(current);
        }

        // 如果已经找到精确解，不需要继续搜索更长的组合
        if (minDifference < EPSILON) {
            return;
        }

        // 遍历候选数字
        for (int i = start; i < candidates.length; i++) {
            double num = candidates[i];

            // 剪枝：如果当前和已经远大于目标值，跳过
            if (currentSum + num > target + minDifference + EPSILON) {
                continue;
            }

            // 跳过重复数字
            if (i > start && Math.abs(candidates[i] - candidates[i - 1]) < EPSILON) {
                continue;
            }

            current.add(num);
            backtrack(candidates, i + 1, current, currentSum + num);
            current.remove(current.size() - 1);
        }
    }

}