package tum.db;

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

import static java.lang.Math.max;

class Box implements Comparable<Box> {
    public Box(int id, int width, int height, int length) {
        this.id = id;
        this.width = width;
        this.height = height;
        this.length = length;
    }

    protected int id;
    protected int width;
    protected int height;
    protected int length;

    @Override
    public int compareTo(Box o) {
        if (this.width < o.width && this.length < o.length && this.height < o.height) return -1;
        return 1;
    }
}

public class StackedBoxes {
    // Naive solution which descends recursively for all boxes
    static int getMaxHeight(Set<Box> remainingBoxes, Box lastBox) {
        if (remainingBoxes.isEmpty()) return 0;

        // create deep copy of hash set
        Set<Box> remainingBoxesCopy = new HashSet<>();
        remainingBoxesCopy.addAll(remainingBoxes);

        int maximalSubStackHeight = 0;
        for (Box box : remainingBoxes) {
            if (lastBox == null || box.compareTo(lastBox) < 0) {
                remainingBoxesCopy.remove(box);
                maximalSubStackHeight = max(getMaxHeight(remainingBoxesCopy, box), maximalSubStackHeight);
                remainingBoxesCopy.add(box);
            }
        }

        return (lastBox != null ? lastBox.height : 0) + maximalSubStackHeight;
    }

    // Better solution which uses dynamic programming and a memoization table
    static int getMaxHeightDP(Set<Box> remainingBoxes, Box lastBox, HashMap<Box, Integer> memo) {
        if (remainingBoxes.isEmpty())
            return 0;

        // create deep copy of hash set
        Set<Box> remainingBoxesCopy = new HashSet<>(remainingBoxes);

        int maxSubstackHeight = 0;
        for (Box box : remainingBoxes) {
            if (lastBox == null || box.compareTo(lastBox) < 0) {
                if (!memo.containsKey(box)) {// calculate substack height recursively and memoize
                    remainingBoxesCopy.remove(box);
                    int tmpSubstackHeight = getMaxHeightDP(remainingBoxesCopy, box, memo);
                    memo.put(box, tmpSubstackHeight);
                    remainingBoxesCopy.add(box);
                }
                maxSubstackHeight = max(maxSubstackHeight, memo.get(box));
            }
        }
        return maxSubstackHeight + (lastBox == null ? 0 : lastBox.height);
    }

    static int getRandomNumber() {
        return ThreadLocalRandom.current().nextInt(1, 1_000_000);
    }

    public static void main(String[] args) {
        List<Integer> boxNumbers = new ArrayList<>();
        for (int bn = 10; bn < 250; bn += 25) boxNumbers.add(bn);
        for (int numBoxes : boxNumbers) {
            System.out.print(numBoxes);
            Set<Box> boxes = new HashSet<>();

            for (int id = 0; id < numBoxes; id++) // create random boxes with random attributes
                boxes.add(new Box(id, getRandomNumber(), getRandomNumber(), getRandomNumber()));

            // Run dynamic programming approach
            long start = System.nanoTime();
            int maxHeightDP = getMaxHeightDP(boxes, null, new HashMap<>());
            long end = System.nanoTime();
            System.out.print("," + (end - start));

            // Run naive algorithm
            start = System.nanoTime();
            int maxHeight = getMaxHeight(boxes, null);
            end = System.nanoTime();
            if ((maxHeight != maxHeightDP)) throw new AssertionError();
            System.out.println("," + (end - start));
        }
    }
}