package com.zy.asrs.utils;

import com.core.common.SnowflakeIdWorker;
import com.core.common.SpringUtils;

import java.util.*;

public class OptimizedLockerPacking3Utils {

    public static class Item {
        String name;
        double unitSpace;
        int maxCapacity;
        int stock;
        int allocated; // 改为已分配数量，避免直接修改remaining导致的混乱

        public Item(String name, int maxCapacity, int stock) {
            this.name = name;
            this.maxCapacity = maxCapacity;
            this.unitSpace = 1.0 / maxCapacity;
            this.stock = stock;
            this.allocated = 0;
        }

        public int getRemaining() {
            return stock - allocated;
        }

        public boolean allocate(int quantity) {
            if (allocated + quantity <= stock) {
                allocated += quantity;
                return true;
            }
            return false;
        }

        @Override
        public String toString() {
            return name + "(单放" + maxCapacity + "个, 库存" + stock + "个)";
        }
    }

    static class Locker {
        int id;
        double remainingSpace;
        long bindingTags;
        Map<String, Integer> contents;
        Set<String> itemTypes;

        public Locker(int id) {
            this.id = id;
            this.remainingSpace = 1.0;
            this.contents = new HashMap<>();
            this.itemTypes = new HashSet<>();
            SnowflakeIdWorker snowflakeIdWorker = SpringUtils.getBean(SnowflakeIdWorker.class);
            this.bindingTags = snowflakeIdWorker.nextId();
        }

        public boolean canAdd(Item item, int quantity) {
            return remainingSpace >= quantity * item.unitSpace;
        }

        public boolean addItem(Item item, int quantity) {
            // 验证分配数量
            if (!item.allocate(quantity)) {
                return false;
            }

            double spaceUsed = quantity * item.unitSpace;
            if (spaceUsed > remainingSpace + 1e-6) {
                // 回滚分配
                item.allocated -= quantity;
                return false;
            }

            remainingSpace -= spaceUsed;
            contents.put(item.name, contents.getOrDefault(item.name, 0) + quantity);
            itemTypes.add(item.name);
            return true;
        }

        public boolean containsItemType(String itemName) {
            return itemTypes.contains(itemName);
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("储物柜").append(id).append(": ");
            sb.append(String.format("剩余空间%.4f", remainingSpace)).append("\n");
            for (Map.Entry<String, Integer> entry : contents.entrySet()) {
                sb.append("  ").append(entry.getKey()).append(": ").append(entry.getValue()).append("个\n");
            }
            return sb.toString();
        }
    }

    static class PackingSolution {
        List<Locker> lockers;
        int totalLockersUsed;
        double overallUtilization;
        int itemTypeChanges;
        int pureLockers;

        public PackingSolution() {
            this.lockers = new ArrayList<>();
        }

        public void addLocker(Locker locker) {
            lockers.add(locker);
            totalLockersUsed = lockers.size();
        }

        public void calculateMetrics() {
            double totalUsedSpace = 0;
            itemTypeChanges = 0;
            pureLockers = 0;
            String lastItemType = null;

            for (Locker locker : lockers) {
                totalUsedSpace += (1.0 - locker.remainingSpace);

                if (locker.itemTypes.size() == 1) {
                    pureLockers++;
                }

                for (String itemType : locker.itemTypes) {
                    if (lastItemType != null && !lastItemType.equals(itemType)) {
                        itemTypeChanges++;
                    }
                    lastItemType = itemType;
                }
            }

            overallUtilization = totalUsedSpace / totalLockersUsed;
        }

        @Override
        public String toString() {
            calculateMetrics();
            StringBuilder sb = new StringBuilder();
            sb.append("=== 优化摆放方案 ===\n");
            sb.append("使用的储物柜数量: ").append(totalLockersUsed).append("个\n");
            sb.append("纯种类储物柜: ").append(pureLockers).append("个\n");
            sb.append("平均空间利用率: ").append(String.format("%.2f", overallUtilization * 100)).append("%\n");
            sb.append("物品种类切换次数: ").append(itemTypeChanges).append("次\n\n");

            List<Locker> pureLockersList = new ArrayList<>();
            List<Locker> mixedLockersList = new ArrayList<>();

            for (Locker locker : lockers) {
                if (locker.itemTypes.size() == 1) {
                    pureLockersList.add(locker);
                } else {
                    mixedLockersList.add(locker);
                }
            }

            sb.append("【纯种类储物柜】:\n");
            for (Locker locker : pureLockersList) {
                sb.append(locker.toString()).append("\n");
            }

            sb.append("【混合储物柜】:\n");
            for (Locker locker : mixedLockersList) {
                sb.append(locker.toString()).append("\n");
            }

            return sb.toString();
        }
    }

    /**
     * 余料物品辅助类
     */
    private static class RemainderItem {
        Item item;
        int quantity;

        RemainderItem(Item item, int quantity) {
            this.item = item;
            this.quantity = quantity;
        }

        @Override
        public String toString() {
            return item.name + "(" + quantity + "个)";
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            RemainderItem that = (RemainderItem) obj;
            return quantity == that.quantity && item.name.equals(that.item.name);
        }

        @Override
        public int hashCode() {
            return Objects.hash(item.name, quantity);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("请输入物品种类数量:");
        int itemTypes = scanner.nextInt();
        scanner.nextLine();

        List<Item> items = new ArrayList<>();

        for (int i = 0; i < itemTypes; i++) {
            System.out.println("\n请输入第" + (i + 1) + "种物品的信息:");
            System.out.print("物品名称: ");
            String name = scanner.nextLine();

            System.out.print("单种存放最大数量: ");
            int maxCapacity = scanner.nextInt();

            System.out.print("库存数量: ");
            int stock = scanner.nextInt();
            scanner.nextLine();

            items.add(new Item(name, maxCapacity, stock));
        }

        PackingSolution solution = optimizedPacking(items);
        System.out.println("\n" + solution);

        scanner.close();
    }

    /**
     * 优化装箱算法：修复数量管理问题
     */
    public static PackingSolution optimizedPacking(List<Item> items) {
        // 验证输入
        if (items == null || items.isEmpty()) {
            throw new IllegalArgumentException("物品列表不能为空");
        }

        // 创建物品副本用于处理
        List<Item> itemsToPack = new ArrayList<>();
        for (Item item : items) {
            itemsToPack.add(new Item(item.name, item.maxCapacity, item.stock));
        }

        PackingSolution solution = new PackingSolution();
        int lockerId = 1;

        // 第一阶段：对每种物品进行集中处理，分配完整储物柜
        Map<String, Integer> remainders = new HashMap<>();

        for (Item item : itemsToPack) {
            if (item.getRemaining() == 0) continue;

            int fullLockersNeeded = item.getRemaining() / item.maxCapacity;
            int remainder = item.getRemaining() % item.maxCapacity;

            // 分配完整储物柜
            for (int i = 0; i < fullLockersNeeded; i++) {
                Locker locker = new Locker(lockerId++);
                if (locker.addItem(item, item.maxCapacity)) {
                    solution.addLocker(locker);
                } else {
                    System.out.println("警告: 无法分配完整储物柜给物品 " + item.name);
                }
            }

            if (remainder > 0) {
                remainders.put(item.name, remainder);
            }
        }

        // 第二阶段：优化余料分配
        if (!remainders.isEmpty()) {
            uniformRemainderProcessing(remainders, itemsToPack, solution, lockerId);
        }

        // 验证结果
        if (!validateSolution(items, solution)) {
            System.out.println("警告: 数量分配验证失败");
        }

        return solution;
    }

    /**
     * 修复后的均匀余料处理算法
     */
    private static void uniformRemainderProcessing(Map<String, Integer> remainders,
                                                   List<Item> items,
                                                   PackingSolution solution,
                                                   int startLockerId) {
        int lockerId = startLockerId;

        // 将余料转换为可处理的物品列表
        List<RemainderItem> remainderItems = new ArrayList<>();
        for (Item item : items) {
            Integer remainder = remainders.get(item.name);
            if (remainder != null && remainder > 0 && item.getRemaining() > 0) {
                remainderItems.add(new RemainderItem(item, Math.min(remainder, item.getRemaining())));
            }
        }

        // 按物品单位空间从大到小排序
        remainderItems.sort((a, b) -> Double.compare(b.item.unitSpace, a.item.unitSpace));

        // 使用修复后的余料处理算法
        List<Locker> remainderLockers = fixedRemainderArrangement(remainderItems, solution, lockerId);

        // 将最优解添加到解决方案中
        for (Locker locker : remainderLockers) {
            solution.addLocker(locker);
        }
    }

    /**
     * 修复后的余料排列方案
     */
    private static List<Locker> fixedRemainderArrangement(List<RemainderItem> remainderItems,
                                                          PackingSolution solution,
                                                          int startLockerId) {
        if (remainderItems.isEmpty()) {
            return new ArrayList<>();
        }

        // 创建副本避免修改原始数据
        List<RemainderItem> remaining = new ArrayList<>();
        for (RemainderItem ri : remainderItems) {
            if (ri.quantity > 0) {
                remaining.add(new RemainderItem(ri.item, ri.quantity));
            }
        }

        List<Locker> lockers = new ArrayList<>();
        int lockerId = startLockerId;

        // 主要策略：创建高利用率储物柜
        while (!remaining.isEmpty()) {
            Locker locker = createOptimizedLocker(remaining, lockerId);
            if (locker != null) {
                lockers.add(locker);
                lockerId++;

                // 移除已处理完的物品
                Iterator<RemainderItem> iterator = remaining.iterator();
                while (iterator.hasNext()) {
                    RemainderItem ri = iterator.next();
                    if (ri.quantity == 0) {
                        iterator.remove();
                    }
                }

                double utilization = (1.0 - locker.remainingSpace) * 100;
                System.out.println("创建储物柜，利用率: " + String.format("%.2f", utilization) + "%");
            } else {
                break;
            }
        }

        // 处理剩余物品（如果有）
        if (!remaining.isEmpty()) {
            System.out.println("使用标准算法处理剩余 " + remaining.size() + " 种物品");
            List<Locker> standardLockers = standardBestFit(remaining, lockerId);
            lockers.addAll(standardLockers);
        }

        return lockers;
    }

    /**
     * 创建优化储物柜（修复数量验证）
     */
    private static Locker createOptimizedLocker(List<RemainderItem> remaining, int lockerId) {
        if (remaining.isEmpty()) {
            return null;
        }

        Locker locker = new Locker(lockerId);
        double targetUtilization = 0.85;
        double minUtilization = 0.3; // 最低利用率阈值

        // 寻找最佳组合
        List<RemainderItem> bestCombination = findValidCombination(remaining, targetUtilization);

        if (bestCombination.isEmpty()) {
            // 尝试达到最低利用率
            bestCombination = findMinUtilizationCombination(remaining, minUtilization);
        }

        if (bestCombination.isEmpty()) {
            return null;
        }

        // 分配组合到储物柜
        boolean success = allocateValidCombination(remaining, locker, bestCombination);

        if (!success || locker.contents.isEmpty()) {
            return null;
        }

        // 检查利用率是否可接受
        double utilization = 1.0 - locker.remainingSpace;
        if (utilization < minUtilization) {
            // 回滚分配
            rollbackAllocation(remaining, locker);
            return null;
        }

        return locker;
    }

    /**
     * 寻找有效组合（修复数量验证）
     */
    private static List<RemainderItem> findValidCombination(List<RemainderItem> items, double targetUtilization) {
        List<RemainderItem> bestCombination = new ArrayList<>();
        double[] bestDiff = {Double.MAX_VALUE};

        // 过滤有效物品
        List<RemainderItem> availableItems = new ArrayList<>();
        for (RemainderItem ri : items) {
            if (ri.quantity > 0 && ri.item.getRemaining() > 0) {
                availableItems.add(ri);
            }
        }

        if (availableItems.isEmpty()) {
            return bestCombination;
        }

        // 使用DFS搜索有效组合
        validDfsCombination(availableItems, 0, 0.0, targetUtilization,
                new ArrayList<>(), bestCombination, bestDiff);

        return bestCombination;
    }

    /**
     * 有效的DFS组合搜索
     */
    private static void validDfsCombination(List<RemainderItem> items, int index, double currentSpace,
                                            double targetUtilization,
                                            List<RemainderItem> current,
                                            List<RemainderItem> bestCombination, double[] bestDiff) {
        // 检查当前组合的有效性
        if (!current.isEmpty()) {
            double diff = Math.abs(currentSpace - targetUtilization);
            if (currentSpace <= 1.0 + 1e-6 && diff < bestDiff[0] && isCombinationValid(current)) {
                bestCombination.clear();
                for (RemainderItem ri : current) {
                    bestCombination.add(new RemainderItem(ri.item, ri.quantity));
                }
                bestDiff[0] = diff;

                if (diff < 0.01) {
                    return;
                }
            }
        }

        if (index >= items.size() || currentSpace > 1.0 + 1e-6) {
            return;
        }

        RemainderItem currentItem = items.get(index);

        // 不选择当前物品
        validDfsCombination(items, index + 1, currentSpace, targetUtilization,
                current, bestCombination, bestDiff);

        // 选择当前物品
        if (currentItem.quantity > 0) {
            int maxCanAdd = Math.min(currentItem.quantity,
                    (int) Math.floor((1.0 - currentSpace) / currentItem.item.unitSpace));
            maxCanAdd = Math.min(maxCanAdd, currentItem.item.getRemaining()); // 重要修复：不超过剩余数量

            for (int qty = 1; qty <= maxCanAdd; qty++) {
                current.add(new RemainderItem(currentItem.item, qty));
                validDfsCombination(items, index + 1, currentSpace + qty * currentItem.item.unitSpace,
                        targetUtilization, current, bestCombination, bestDiff);
                current.remove(current.size() - 1);
            }
        }
    }

    /**
     * 检查组合是否有效（修复数量验证）
     */
    private static boolean isCombinationValid(List<RemainderItem> combination) {
        Map<String, Integer> totalQuantities = new HashMap<>();

        for (RemainderItem ri : combination) {
            int currentTotal = totalQuantities.getOrDefault(ri.item.name, 0);
            totalQuantities.put(ri.item.name, currentTotal + ri.quantity);

            // 检查是否超过物品剩余数量
            if (currentTotal + ri.quantity > getRemainingQuantity(ri.item)) {
                return false;
            }
        }

        return true;
    }

    /**
     * 获取物品剩余数量
     */
    private static int getRemainingQuantity(Item item) {
        return item.stock - item.allocated;
    }

    /**
     * 寻找达到最低利用率的组合
     */
    private static List<RemainderItem> findMinUtilizationCombination(List<RemainderItem> items, double minUtilization) {
        List<RemainderItem> combination = new ArrayList<>();
        double currentSpace = 0.0;

        // 按单位空间排序
        List<RemainderItem> sortedItems = new ArrayList<>(items);
        sortedItems.sort((a, b) -> Double.compare(b.item.unitSpace, a.item.unitSpace));

        for (RemainderItem ri : sortedItems) {
            if (ri.quantity > 0 && currentSpace < minUtilization) {
                int maxCanAdd = Math.min(ri.quantity,
                        (int) Math.floor((1.0 - currentSpace) / ri.item.unitSpace));
                maxCanAdd = Math.min(maxCanAdd, ri.item.getRemaining()); // 重要修复

                if (maxCanAdd > 0) {
                    combination.add(new RemainderItem(ri.item, maxCanAdd));
                    currentSpace += maxCanAdd * ri.item.unitSpace;
                }
            }
        }

        if (currentSpace >= minUtilization) {
            return combination;
        }

        return new ArrayList<>();
    }

    /**
     * 分配有效组合到储物柜（修复数量验证）
     */
    private static boolean allocateValidCombination(List<RemainderItem> remaining, Locker locker,
                                                    List<RemainderItem> combination) {
        // 验证组合中的所有物品都有足够的数量
        for (RemainderItem combItem : combination) {
            boolean found = false;
            for (RemainderItem remItem : remaining) {
                if (remItem.item.name.equals(combItem.item.name)) {
                    found = true;
                    if (combItem.quantity > remItem.quantity) {
                        return false;
                    }
                    if (combItem.quantity > remItem.item.getRemaining()) {
                        return false;
                    }
                    break;
                }
            }
            if (!found) {
                return false;
            }
        }

        // 实际分配
        for (RemainderItem combItem : combination) {
            for (RemainderItem remItem : remaining) {
                if (remItem.item.name.equals(combItem.item.name)) {
                    if (locker.addItem(combItem.item, combItem.quantity)) {
                        remItem.quantity -= combItem.quantity;
                    } else {
                        return false;
                    }
                    break;
                }
            }
        }

        return true;
    }

    /**
     * 回滚分配
     */
    private static void rollbackAllocation(List<RemainderItem> remaining, Locker locker) {
        for (Map.Entry<String, Integer> entry : locker.contents.entrySet()) {
            String itemName = entry.getKey();
            int quantity = entry.getValue();

            for (RemainderItem ri : remaining) {
                if (ri.item.name.equals(itemName)) {
                    ri.quantity += quantity;
                    ri.item.allocated -= quantity; // 回滚分配数量
                    break;
                }
            }
        }
    }

    /**
     * 标准最佳适应算法
     */
    private static List<Locker> standardBestFit(List<RemainderItem> remainderItems, int startLockerId) {
        List<Locker> lockers = new ArrayList<>();
        int lockerId = startLockerId;

        // 创建副本
        List<RemainderItem> remaining = new ArrayList<>();
        for (RemainderItem ri : remainderItems) {
            if (ri.quantity > 0) {
                remaining.add(new RemainderItem(ri.item, ri.quantity));
            }
        }

        // 按单位空间排序
        remaining.sort((a, b) -> Double.compare(b.item.unitSpace, a.item.unitSpace));

        for (RemainderItem ri : remaining) {
            while (ri.quantity > 0 && ri.item.getRemaining() > 0) {
                Locker bestLocker = null;
                double bestRemainingSpace = Double.MAX_VALUE;

                // 寻找最佳储物柜
                for (Locker locker : lockers) {
                    if (locker.canAdd(ri.item, 1) && locker.remainingSpace < bestRemainingSpace) {
                        bestLocker = locker;
                        bestRemainingSpace = locker.remainingSpace;
                    }
                }

                if (bestLocker != null) {
                    int maxCanAdd = (int) Math.floor(bestLocker.remainingSpace / ri.item.unitSpace);
                    int actualAdd = Math.min(ri.quantity, maxCanAdd);
                    actualAdd = Math.min(actualAdd, ri.item.getRemaining()); // 重要修复

                    if (actualAdd > 0 && bestLocker.addItem(ri.item, actualAdd)) {
                        ri.quantity -= actualAdd;
                    } else {
                        break;
                    }
                } else {
                    // 创建新储物柜
                    Locker newLocker = new Locker(lockerId++);
                    int maxCanAdd = (int) Math.floor(1.0 / ri.item.unitSpace);
                    int actualAdd = Math.min(ri.quantity, maxCanAdd);
                    actualAdd = Math.min(actualAdd, ri.item.getRemaining()); // 重要修复

                    if (actualAdd > 0 && newLocker.addItem(ri.item, actualAdd)) {
                        lockers.add(newLocker);
                        ri.quantity -= actualAdd;
                    } else {
                        break;
                    }
                }
            }
        }

        return lockers;
    }

    /**
     * 验证解决方案（修复验证逻辑）
     */
    private static boolean validateSolution(List<Item> originalItems, PackingSolution solution) {
        Map<String, Integer> allocatedQuantities = new HashMap<>();
        Map<String, Integer> originalQuantities = new HashMap<>();

        // 记录原始数量
        for (Item item : originalItems) {
            originalQuantities.put(item.name, item.stock);
        }

        // 计算分配数量
        for (Locker locker : solution.lockers) {
            for (Map.Entry<String, Integer> entry : locker.contents.entrySet()) {
                String itemName = entry.getKey();
                int quantity = entry.getValue();
                allocatedQuantities.put(itemName, allocatedQuantities.getOrDefault(itemName, 0) + quantity);
            }
        }

        boolean valid = true;
        for (Map.Entry<String, Integer> entry : originalQuantities.entrySet()) {
            String itemName = entry.getKey();
            int originalQty = entry.getValue();
            int allocatedQty = allocatedQuantities.getOrDefault(itemName, 0);

            if (originalQty != allocatedQty) {
                System.out.println("验证失败: " + itemName + " 原始数量=" + originalQty +
                        ", 分配数量=" + allocatedQty);
                valid = false;
            }
        }

        if (valid) {
            System.out.println("数量验证通过");
        }

        return valid;
    }

    /**
     * 性能测试和比较
     */
    public static void performanceTest() {
        System.out.println("=== 性能测试 ===");

        // 测试数据
        List<Item> testItems = Arrays.asList(
                new Item("X", 20, 87),
                new Item("Y", 15, 63),
                new Item("Z", 34, 125),
                new Item("T", 25, 48),
                new Item("U", 40, 92)
        );

        System.out.println("测试物品数量: " + testItems.size());
        int totalItems = testItems.stream().mapToInt(item -> item.stock).sum();
        System.out.println("总物品数量: " + totalItems);

        long startTime = System.currentTimeMillis();
        PackingSolution solution = optimizedPacking(testItems);
        long endTime = System.currentTimeMillis();

        System.out.println("\n优化算法结果:");
        System.out.println("处理时间: " + (endTime - startTime) + "ms");
        System.out.println("储物柜数量: " + solution.totalLockersUsed);
        System.out.println("纯种类储物柜: " + solution.pureLockers);
        System.out.println("空间利用率: " + String.format("%.2f", solution.overallUtilization * 100) + "%");
    }
}