package com.zy.asrs.utils;

import java.util.*;

public class OptimizedLockerPackingUtils {

    public static class Item {
        String name;
        double unitSpace;
        int maxCapacity;
        int stock;
        int remaining;

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

        @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<>();
            this.bindingTags = System.currentTimeMillis();

        }

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

        public void addItem(Item item, int quantity) {
            double spaceUsed = quantity * item.unitSpace;
            remainingSpace -= spaceUsed;
            contents.put(item.name, contents.getOrDefault(item.name, 0) + quantity);
            itemTypes.add(item.name);
            item.remaining -= quantity;
        }

        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();
        }
    }

    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) {
        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;

        // 第一阶段：对每种物品进行集中处理
        for (Item item : itemsToPack) {
            if (item.remaining == 0) continue;

            // 计算这种物品需要多少个完整的储物柜
            int fullLockersNeeded = item.remaining / item.maxCapacity;
            int remainder = item.remaining % item.maxCapacity;

            // 分配完整储物柜
            for (int i = 0; i < fullLockersNeeded; i++) {
                Locker locker = new Locker(lockerId++);
                locker.addItem(item, item.maxCapacity);
                solution.addLocker(locker);
            }

            // 如果有余料，暂时保留（第二阶段处理）
        }

        // 第二阶段：收集所有余料
        List<Item> remainingItems = new ArrayList<>();
        for (Item item : itemsToPack) {
            if (item.remaining > 0) {
                remainingItems.add(item);
            }
        }

        // 如果还有余料，用最佳适应算法处理
        if (!remainingItems.isEmpty()) {
            processRemainingItems(remainingItems, solution, lockerId);
        }

        return solution;
    }

    /**
     * 处理剩余物品（余料）
     */
    private static void processRemainingItems(List<Item> remainingItems, PackingSolution solution, int startLockerId) {
        int lockerId = startLockerId;

        // 按空间占用从大到小排序（优先处理大物品）
        remainingItems.sort((a, b) -> Double.compare(b.unitSpace, a.unitSpace));

        for (Item item : remainingItems) {
            while (item.remaining > 0) {
                // 优先尝试放入已有同种物品的储物柜
                Locker sameTypeLocker = findSameTypeLocker(solution, item);
                if (sameTypeLocker != null) {
                    int maxCanAdd = (int) Math.floor(sameTypeLocker.remainingSpace / item.unitSpace);
                    int actualAdd = Math.min(item.remaining, maxCanAdd);
                    sameTypeLocker.addItem(item, actualAdd);
                    continue;
                }

                // 其次尝试放入现有储物柜（最佳适应）
                Locker bestLocker = findBestLocker(solution, item);
                if (bestLocker != null) {
                    int maxCanAdd = (int) Math.floor(bestLocker.remainingSpace / item.unitSpace);
                    int actualAdd = Math.min(item.remaining, maxCanAdd);
                    bestLocker.addItem(item, actualAdd);
                    continue;
                }

                // 最后创建新储物柜
                Locker newLocker = new Locker(lockerId++);
                int maxCanAdd = (int) Math.floor(1.0 / item.unitSpace);
                int actualAdd = Math.min(item.remaining, maxCanAdd);
                newLocker.addItem(item, actualAdd);
                solution.addLocker(newLocker);
            }
        }
    }

    /**
     * 寻找已有同种物品的储物柜
     */
    private static Locker findSameTypeLocker(PackingSolution solution, Item item) {
        Locker bestLocker = null;
        double bestRemaining = -1;

        for (Locker locker : solution.lockers) {
            if (locker.containsItemType(item.name) && locker.canAdd(item, 1)) {
                if (locker.remainingSpace > bestRemaining) {
                    bestLocker = locker;
                    bestRemaining = locker.remainingSpace;
                }
            }
        }

        return bestLocker;
    }

    /**
     * 寻找最佳适应的储物柜
     */
    private static Locker findBestLocker(PackingSolution solution, Item item) {
        Locker bestLocker = null;
        double bestRemaining = Double.MAX_VALUE;

        for (Locker locker : solution.lockers) {
            if (locker.canAdd(item, 1) && locker.remainingSpace < bestRemaining) {
                bestLocker = locker;
                bestRemaining = locker.remainingSpace;
            }
        }

        return bestLocker;
    }

    /**
     * 高级优化：智能余料分配
     */
    public static PackingSolution advancedOptimizedPacking(List<Item> items) {
        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.remaining == 0) continue;

            int fullLockers = item.remaining / item.maxCapacity;
            int remainder = item.remaining % item.maxCapacity;

            for (int i = 0; i < fullLockers; i++) {
                Locker locker = new Locker(lockerId++);
                locker.addItem(item, item.maxCapacity);
                solution.addLocker(locker);
            }

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

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

        return solution;
    }

    /**
     * 智能余料处理：尝试将余料组合成完整储物柜
     */
    private static void smartRemainderProcessing(Map<String, Integer> remainders,
                                                 List<Item> items,
                                                 PackingSolution solution,
                                                 int startLockerId) {
        int lockerId = startLockerId;

        // 尝试找到可以完美组合的余料
        boolean foundCombination;
        do {
            foundCombination = false;

            // 寻找可以填满一个储物柜的余料组合
            for (Item item1 : items) {
                if (remainders.getOrDefault(item1.name, 0) == 0) continue;

                for (Item item2 : items) {
                    if (item1.name.equals(item2.name) || remainders.getOrDefault(item2.name, 0) == 0) continue;

                    double spaceNeeded = remainders.get(item1.name) * item1.unitSpace +
                            remainders.get(item2.name) * item2.unitSpace;

                    if (spaceNeeded <= 1.0 + 1e-6) { // 考虑浮点误差
                        Locker locker = new Locker(lockerId++);
                        locker.addItem(item1, remainders.get(item1.name));
                        locker.addItem(item2, remainders.get(item2.name));
                        solution.addLocker(locker);

                        remainders.put(item1.name, 0);
                        remainders.put(item2.name, 0);
                        foundCombination = true;
                        break;
                    }
                }
                if (foundCombination) break;
            }
        } while (foundCombination);

        // 处理剩余的零散余料
        for (Item item : items) {
            int remainder = remainders.getOrDefault(item.name, 0);
            if (remainder > 0) {
                Locker bestLocker = findBestLockerForRemainder(solution, item, remainder);
                if (bestLocker != null) {
                    bestLocker.addItem(item, remainder);
                } else {
                    Locker newLocker = new Locker(lockerId++);
                    newLocker.addItem(item, remainder);
                    solution.addLocker(newLocker);
                }
            }
        }
    }

    private static Locker findBestLockerForRemainder(PackingSolution solution, Item item, int quantity) {
        Locker bestLocker = null;
        double bestFit = Double.MAX_VALUE;

        for (Locker locker : solution.lockers) {
            if (locker.canAdd(item, quantity)) {
                double remainingAfterAdd = locker.remainingSpace - quantity * item.unitSpace;
                if (remainingAfterAdd < bestFit) {
                    bestLocker = locker;
                    bestFit = remainingAfterAdd;
                }
            }
        }

        return bestLocker;
    }

    /**
     * 性能测试和比较
     */
    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) + "%");
    }
}