package com.yami.shop.utils;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Function;

// 自己实现简单的装箱算法
public class BinPackingUtil {

    /**
     * 首次适配递减算法
     */
    public static <T> List<List<T>> firstFitDecreasing(
            List<T> items,
            Function<T, Double> weightExtractor,
            double capacity) {

        // 按重量从大到小排序
        List<T> sortedItems = new ArrayList<>(items);
        sortedItems.sort((a, b) ->
                Double.compare(weightExtractor.apply(b), weightExtractor.apply(a)));

        List<List<T>> bins = new ArrayList<>();
        List<Double> binWeights = new ArrayList<>();

        for (T item : sortedItems) {
            double weight = weightExtractor.apply(item);
            boolean placed = false;

            // 尝试放入现有箱子
            for (int i = 0; i < bins.size(); i++) {
                if (binWeights.get(i) + weight <= capacity) {
                    bins.get(i).add(item);
                    binWeights.set(i, binWeights.get(i) + weight);
                    placed = true;
                    break;
                }
            }

            // 创建新箱子
            if (!placed) {
                List<T> newBin = new ArrayList<>();
                newBin.add(item);
                bins.add(newBin);
                binWeights.add(weight);
            }
        }

        return bins;
    }

    /**
     * 最佳适配递减算法
     */
    public static <T> List<List<T>> bestFitDecreasing(
            List<T> items,
            Function<T, Double> weightExtractor,
            double capacity) {

        List<T> sortedItems = new ArrayList<>(items);
        sortedItems.sort((a, b) ->
                Double.compare(weightExtractor.apply(b), weightExtractor.apply(a)));

        List<List<T>> bins = new ArrayList<>();
        List<Double> binWeights = new ArrayList<>();

        for (T item : sortedItems) {
            double weight = weightExtractor.apply(item);
            int bestBinIndex = -1;
            double minRemaining = Double.MAX_VALUE;

            // 寻找最佳箱子
            for (int i = 0; i < bins.size(); i++) {
                double remaining = capacity - binWeights.get(i);
                if (remaining >= weight && remaining < minRemaining) {
                    minRemaining = remaining;
                    bestBinIndex = i;
                }
            }

            if (bestBinIndex != -1) {
                bins.get(bestBinIndex).add(item);
                binWeights.set(bestBinIndex, binWeights.get(bestBinIndex) + weight);
            } else {
                List<T> newBin = new ArrayList<>();
                newBin.add(item);
                bins.add(newBin);
                binWeights.add(weight);
            }
        }

        return bins;
    }
}