Career cup 9.10

Box.java

package Chapter9;

import java.util.ArrayList;
import java.util.HashMap;

public class Box {
    public int w;
    public int h;
    public int d;

    public Box(int w, int h, int d) {
	this.w = w;
	this.h = h;
	this.d = d;
    }

    public static ArrayList<Box> getMaxHeightStack(ArrayList<Box> boxes,
	    Box bottom, HashMap<Box, ArrayList<Box>> stackCache) {
	//check cache
	if (stackCache.containsKey(bottom))
	    return stackCache.get(bottom);
	
	int maxHeight = 0;
	ArrayList<Box> maxHeightStack = new ArrayList<>();
	for (Box box : boxes) {
	    if(box.canPutOn(bottom)) {
		ArrayList<Box> s = getMaxHeightStack(boxes, box, stackCache);
		int height = getStackHeight(s);
		if(maxHeight < height) {
		    maxHeight = height;
		    maxHeightStack = s;
		}
	    }
	}
	
	maxHeightStack.add(0, bottom);
	stackCache.put(bottom, maxHeightStack);
	
	return maxHeightStack;

    }

    private static int getStackHeight(ArrayList<Box> s) {
	int height = 0;
	for (Box box : s) {
	    height += box.h;
	}
	return height;
    }

    private boolean canPutOn(Box bottom) {
	return bottom.h > h && bottom.w > w && bottom.d > d;
    }
}