// Illustration of an algorithm.

public class NaiveBoxAlgorithm implements BoxProblemAlgorithm {

    int width=-1, height=-1;

    public String getName ()
    {
	return "Naive";
    }

    public BoxSolution findSolution (BoxProblem problem)
    {
	// Start by creating an instance of the solution class.
	BoxSolution solution = new BoxSolution ();

	// Key idea: Go left to right assigning along the bottom.

	int currentRight = 0;

	for (int i=0; i<problem.items.size(); i++) {

	    // Try to assign item i.
	    Item item = problem.items.get (i);

	    // Compute the rightmost x and topmost y for this item
	    // in width and height.
	    computeBounds (item);

	    // Will it fit?
	    if ((height <= problem.boxY) && 
		(currentRight + width <= problem.boxX)) {
		// Fits.
		int translateX = currentRight;
		solution.put (i, 0, translateX, 0);
		currentRight += width;
	    }

	} // endfor

	return solution;
    }

    void computeBounds (Item item)
    {
	// Find the rightmost x coordinate and topmost y of this item.
	width = 0;	
	height = 0;
	for (Cell c: item.cells) {
	    if (c.x > width) {
		width = c.x;
	    }
	    if (c.y > height) {
		height = c.y;
	    }
	}

	// Add 1 to get the actual length
	width ++;
	height ++;
    }

}