android/src/com/android/tools/idea/rendering/multi/BinPacker.java - platform/tools/adt/idea - Git at Google

 /*
  * Copyright (C) 2013 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package com.android.tools.idea.rendering.multi;

 import com.android.annotations.Nullable;
 import com.intellij.util.ui.UIUtil;

 import javax.imageio.ImageIO;
 import java.awt.*;
 import java.awt.image.BufferedImage;
 import java.io.File;
 import java.util.ArrayList;
 import java.util.List;

 /**
  * This class implements 2D bin packing: packing rectangles into a given area as
  * tightly as "possible" (bin packing in general is NP hard, so this class uses
  * heuristics).
  * <p/>
  * The algorithm implemented is to keep a set of (possibly overlapping)
  * available areas for placement. For each newly inserted rectangle, we first
  * pick which available space to occupy, and we then subdivide the
  * current rectangle into all the possible remaining unoccupied sub-rectangles.
  * We also remove any other space rectangles which are no longer eligible if
  * they are intersecting the newly placed rectangle.
  * <p/>
  * This algorithm is not very fast, so should not be used for a large number of
  * rectangles.
  */
 @SuppressWarnings("AssignmentToForLoopParameter")
 class BinPacker {
   /**
    * When enabled, the successive passes are dumped as PNG images showing the
    * various available and occupied rectangles)
    */
   static final boolean DEBUG = false;

   /** Whether new rectangles should be placed on the left side of available rectangles */
   private static final boolean PLACE_LEFT = true;

   /** Whether new rectangles should be placed on the top rather than the bottom */
   private static final boolean PLACE_TOP = true;

   private final List<Rectangle> mySpace = new ArrayList<Rectangle>();
   private final int myMinHeight;
   private final int myMinWidth;

   /**
    * Creates a new {@linkplain BinPacker}. To use it, first add one or more
    * initial available space rectangles with {@link #addSpace(Rectangle)}, and then
    * place the rectangles with {@link #occupy(int, int)}. The returned
    * {@link Rectangle} from {@link #occupy(int, int)} gives the coordinates of the
    * positioned rectangle.
    *
    * @param minWidth  the smallest width of any rectangle placed into this bin
    * @param minHeight the smallest height of any rectangle placed into this bin
    */
   BinPacker(int minWidth, int minHeight) {
     myMinWidth = minWidth;
     myMinHeight = minHeight;

     if (DEBUG) {
       myAllocated = new ArrayList<Rectangle>();
     }
   }

   /**
    * Adds more available space
    */
   void addSpace(Rectangle rect) {
     if (rect.width >= myMinWidth && rect.height >= myMinHeight) {
       mySpace.add(rect);
     }
   }

   /**
    * Attempts to place a rectangle of the given dimensions, if possible
    */
   @Nullable
   Rectangle occupy(int width, int height) {
     int index = findBest(width, height);
     if (index == -1) {
       return null;
     }

     return split(index, width, height);
   }

   /**
    * Finds the best available space rectangle to position a new rectangle of
    * the given size in.
    */
   private int findBest(int width, int height) {
     if (mySpace.isEmpty()) {
       return -1;
     }

     // Try to pack as far up as possible first
     int bestIndex = -1;
     boolean multipleAtSameY = false;
     int minY = Integer.MAX_VALUE;
     for (int i = 0, n = mySpace.size(); i < n; i++) {
       Rectangle rect = mySpace.get(i);
       if (rect.y <= minY) {
         if (rect.width >= width && rect.height >= height) {
           if (rect.y < minY) {
             minY = rect.y;
             multipleAtSameY = false;
             bestIndex = i;
           }
           else if (minY == rect.y) {
             multipleAtSameY = true;
           }
         }
       }
     }

     if (!multipleAtSameY) {
       return bestIndex;
     }

     bestIndex = -1;

     // Pick a rectangle. This currently tries to find the rectangle whose shortest
     // side most closely matches the placed rectangle's size.
     // Attempt to find the best short side fit
     int bestShortDistance = Integer.MAX_VALUE;
     int bestLongDistance = Integer.MAX_VALUE;

     for (int i = 0, n = mySpace.size(); i < n; i++) {
       Rectangle rect = mySpace.get(i);
       if (rect.y != minY) { // Only comparing elements at same y
         continue;
       }
       if (rect.width >= width && rect.height >= height) {
         if (width < height) {
           int distance = rect.width - width;
           if (distance < bestShortDistance || distance == bestShortDistance && (rect.height - height) < bestLongDistance) {
             bestShortDistance = distance;
             bestLongDistance = rect.height - height;
             bestIndex = i;
           }
         }
         else {
           int distance = rect.width - width;
           if (distance < bestShortDistance || distance == bestShortDistance && (rect.height - height) < bestLongDistance) {
             bestShortDistance = distance;
             bestLongDistance = rect.height - height;
             bestIndex = i;
           }
         }
       }
     }

     return bestIndex;
   }

   /**
    * Removes the rectangle at the given index. Since the rectangles are in an
    * {@link ArrayList}, removing a rectangle in the normal way is slow (it
    * would involve shifting all elements), but since we don't care about
    * order, this always swaps the to-be-deleted element to the last position
    * in the array first, <b>then</b> it deletes it (which should be
    * immediate).
    *
    * @param index the index in the {@link #mySpace} list to remove a rectangle
    *              from
    */
   private void removeRect(int index) {
     assert !mySpace.isEmpty();
     int lastIndex = mySpace.size() - 1;
     if (index != lastIndex) {
       // Swap before remove to make deletion faster since we don't
       // care about order
       Rectangle temp = mySpace.get(index);
       mySpace.set(index, mySpace.get(lastIndex));
       mySpace.set(lastIndex, temp);
     }

     mySpace.remove(lastIndex);
   }

   /**
    * Splits the rectangle at the given rectangle index such that it can contain
    * a rectangle of the given width and height.
    */
   private Rectangle split(int index, int width, int height) {
     Rectangle rect = mySpace.get(index);
     assert rect.width >= width && rect.height >= height : rect;

     Rectangle r = new Rectangle();
     if (PLACE_LEFT) {
       r.x = rect.x;
     } else {
       r.x = rect.x + rect.width - width;
     }
     if (PLACE_TOP) {
       r.y = rect.y;
     } else {
       r.y = rect.y + rect.height - height;
     }
     r.width = width;
     r.height = height;

     // Remove all rectangles that intersect my rectangle
     for (int i = 0; i < mySpace.size(); i++) {
       Rectangle other = mySpace.get(i);
       if (other.intersects(r)) {
         removeRect(i);
         i--;
       }
     }


     int remainingHeight = rect.height - height;
     int remainingWidth = rect.width - width;
     if (PLACE_LEFT) {
       if (remainingHeight >= myMinHeight) {
         if (PLACE_TOP) {
           // Split along vertical line x = rect.x + width:
           // (rect.x,rect.y)
           //     +-------------+-------------------------+
           //     |             |                         |
           //     |             |                         |
           //     |             | height                  |
           //     |             |                         |
           //     |             |                         |
           //     +-------------+           B             | rect.h
           //     |   width                               |
           //     |             |                         |
           //     |      A                                |
           //     |             |                         |
           //     |                                       |
           //     +---------------------------------------+
           //                    rect.w
           mySpace.add(new Rectangle(rect.x, rect.y + height, width, remainingHeight)); // Area A
         } else {
           assert PLACE_LEFT;
           assert !PLACE_TOP;
           // Split along vertical line x = rect.x + width:
           // (rect.x,rect.y)
           //     +-------------+-------------------------+
           //     |                                       |
           //     |             |                         |
           //     |      A                                |
           //     |             |                         |
           //     |    width                              |
           //     +-------------+           B             | rect.h
           //     |             |                         |
           //     |             |                         |
           //     |             | height                  |
           //     |             |                         |
           //     |             |                         |
           //     +-------------+-------------------------+
           //                    rect.w
           mySpace.add(new Rectangle(rect.x, rect.y, width, remainingHeight)); // Area A
         }
       }
       if (remainingWidth >= myMinWidth) { // Area B
         mySpace.add(new Rectangle(rect.x + width, rect.y, remainingWidth, rect.height));
       }
     }
     else {
       assert !PLACE_LEFT;
       // Split along vertical line x = rect.x + rect.w - width
       // (rect.x,rect.y)
       //     +---------------------------------------+
       //     |                                       |
       //     |                        |              |
       //     |                               A       |
       //     |                        |              |
       //     |                            width      |
       //     |          B             +--------------| rect.h
       //     |                        |              |
       //     |                        |              |
       //     |                 height |              |
       //     |                        |              |
       //     |                        |              |
       //     +------------------------+--------------+
       //                    rect.w
       if (remainingWidth >= myMinWidth) { // Area B
         mySpace.add(new Rectangle(rect.x, rect.y, remainingWidth, rect.height));
       }
       if (remainingHeight >= myMinHeight) { // Area A
         if (PLACE_TOP) {
           mySpace.add(new Rectangle(rect.x + rect.width - width, rect.y + height, width, remainingHeight));
         } else {
           mySpace.add(new Rectangle(rect.x + rect.width - width, rect.y, width, remainingHeight));
         }
       }
     }

     if (PLACE_LEFT) {
       if (PLACE_TOP) {
         // Split along horizontal line y = rect.y + height:
         //     +-------------+-------------------------+
         //     |             |                         |
         //     |             | height                  |
         //     |             |          A              |
         //     |             |                         |
         //     |             |                         | rect.h
         //     +-------------+ - - - - - - - - - - - - |
         //     |  width                                |
         //     |                                       |
         //     |                B                      |
         //     |                                       |
         //     |                                       |
         //     +---------------------------------------+
         //                   rect.w
         if (remainingHeight >= myMinHeight) { // Area B
           mySpace.add(new Rectangle(rect.x, rect.y + height, rect.width, remainingHeight));
         }
         if (remainingWidth >= myMinWidth) { // Area A
           mySpace.add(new Rectangle(rect.x + width, rect.y, remainingWidth, height));
         }
       } else {
         assert PLACE_LEFT;
         assert !PLACE_TOP;
         //     +---------------------------------------+
         //     |                                       |
         //     |                                       |
         //     |                   B                   |
         //     |                                       |
         //     |                                       | rect.h
         //     +-------------+ - - - - - - - - - - - - |
         //     |  width      |                         |
         //     |             |                         |
         //     |             | height    A             |
         //     |             |                         |
         //     |             |                         |
         //     +-------------+-------------------------+
         //                   rect.w
         if (remainingHeight >= myMinHeight) { // Area B
           mySpace.add(new Rectangle(rect.x, rect.y, rect.width, remainingHeight));
         }
         if (remainingWidth >= myMinWidth) { // Area A
           mySpace.add(new Rectangle(rect.x + width, rect.y + rect.height - height, remainingWidth, height));
         }
       }
     }
     else {
       assert !PLACE_LEFT;
       if (PLACE_TOP) {
         // Split along horizontal line y = rect.y + rect.h - height:
         //     +-------------------------+-------------+
         //     |                         |             |
         //     |                         |             |
         //     |          A       height |             |
         //     |                         |             |
         //     |                         |             | rect.h
         //     | - - - - - - - - - - - - +-------------|
         //     |                              width    |
         //     |                                       |
         //     |                    B                  |
         //     |                                       |
         //     |                                       |
         //     +---------------------------------------+
         //                   rect.w

         if (remainingHeight >= myMinHeight) { // Area B
           mySpace.add(new Rectangle(rect.x, rect.y + height, rect.width, remainingHeight));
         }
         if (remainingWidth >= myMinWidth) { // Area A
           mySpace.add(new Rectangle(rect.x, rect.y, remainingWidth, height));
         }
       } else {
         assert !PLACE_LEFT;
         assert !PLACE_TOP;
         // Split along horizontal line y = rect.y + rect.h - height:
         //     +---------------------------------------+
         //     |                                       |
         //     |                                       |
         //     |                 B                     |
         //     |                                       |
         //     |                              width    | rect.h
         //     | - - - - - - - - - - - - +-------------|
         //     |                         |             |
         //     |                         |             |
         //     |          A       height |             |
         //     |                         |             |
         //     |                         |             |
         //     +-------------------------+-------------+
         //                   rect.w

         if (remainingHeight >= myMinHeight) { // Area B
           mySpace.add(new Rectangle(rect.x, rect.y, rect.width, remainingHeight));
         }
         if (remainingWidth >= myMinWidth) { // Area A
           mySpace.add(new Rectangle(rect.x, rect.y + rect.height - height, remainingWidth, height));
         }
       }
     }

     if (DEBUG) {
       myAllocated.add(r);
     }

     if (DEBUG) {
       dumpDiagnostics();
     }


     // Remove redundant rectangles. This is not very efficient.
     for (int i = 0; i < mySpace.size() - 1; i++) {
       for (int j = i + 1; j < mySpace.size(); j++) {
         Rectangle iRect = mySpace.get(i);
         Rectangle jRect = mySpace.get(j);
         if (jRect.contains(iRect)) {
           removeRect(i);
           i--;
           break;
         }
         if (iRect.contains(jRect)) {
           removeRect(j);
           j--;
         }
       }
     }

     if (DEBUG) {
       dumpDiagnostics();
     }

     return r;
   }

   // DEBUGGING CODE: Enable with DEBUG

   private List<Rectangle> myAllocated;
   private int myIteration;

   @SuppressWarnings("EmptyCatchBlock")
   void dumpDiagnostics() {
     if (DEBUG) {
       myIteration++;
       // Determine size
       Rectangle r = new Rectangle(0, 0, 100, 100);
       for (Rectangle rect : mySpace) {
         r.add(rect);
       }

       BufferedImage image = UIUtil.createImage(r.width, r.height, BufferedImage.TYPE_INT_ARGB);
       Graphics g = image.getGraphics();
       // Fill background
       g.setColor(Color.BLACK);
       g.fillRect(0, 0, r.width, r.height);

       paintDiagnostics((Graphics2D)g);
       g.dispose();

       try {
         File file = new File("/tmp/layout-iteration-" + myIteration + ".png");
         ImageIO.write(image, "PNG", file);
       } catch (Exception e) {
       }
     }
   }

   @SuppressWarnings({"AssignmentToStaticFieldFromInstanceMethod", "CallToPrintStackTrace", "UseOfSystemOutOrSystemErr"})
   void paintDiagnostics(Graphics2D g) {
     if (DEBUG) {
       Composite prevComposite = g.getComposite();
       g.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 0.5f));

       Color[] colors =
         new Color[]{Color.blue, Color.cyan, Color.green, Color.magenta, Color.orange, Color.pink, Color.red, Color.white, Color.yellow,
           Color.darkGray, Color.lightGray, Color.gray,};

       if (myAllocated != null && !myAllocated.isEmpty()) {
         char allocated = 'A';
         for (Rectangle rect : myAllocated) {
           Color color = new Color(0x9FFFFFFF, true);
           g.setColor(color);
           g.setBackground(color);
           g.fillRect(rect.x, rect.y, rect.width, rect.height);
           g.setColor(Color.WHITE);
           g.drawRect(rect.x, rect.y, rect.width, rect.height);
           g.drawString(String.valueOf(allocated++), rect.x + rect.width / 2, rect.y + rect.height / 2);
         }
       }

       int colorIndex = 0;
       for (Rectangle rect : mySpace) {
         Color color = colors[colorIndex];
         colorIndex = (colorIndex + 1) % colors.length;

         color = new Color(color.getRed(), color.getGreen(), color.getBlue(), 128);
         g.setColor(color);

         g.fillRect(rect.x, rect.y, rect.width, rect.height);
         g.setColor(Color.WHITE);
         g.drawString(Integer.toString(colorIndex), rect.x + rect.width / 2, rect.y + rect.height / 2);
       }

       g.setComposite(prevComposite);
     }
   }
 }
	/*
	* Copyright (C) 2013 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	package com.android.tools.idea.rendering.multi;

	import com.android.annotations.Nullable;
	import com.intellij.util.ui.UIUtil;

	import javax.imageio.ImageIO;
	import java.awt.*;
	import java.awt.image.BufferedImage;
	import java.io.File;
	import java.util.ArrayList;
	import java.util.List;

	/**
	* This class implements 2D bin packing: packing rectangles into a given area as
	* tightly as "possible" (bin packing in general is NP hard, so this class uses
	* heuristics).
	* <p/>
	* The algorithm implemented is to keep a set of (possibly overlapping)
	* available areas for placement. For each newly inserted rectangle, we first
	* pick which available space to occupy, and we then subdivide the
	* current rectangle into all the possible remaining unoccupied sub-rectangles.
	* We also remove any other space rectangles which are no longer eligible if
	* they are intersecting the newly placed rectangle.
	* <p/>
	* This algorithm is not very fast, so should not be used for a large number of
	* rectangles.
	*/
	@SuppressWarnings("AssignmentToForLoopParameter")
	class BinPacker {
	/**
	* When enabled, the successive passes are dumped as PNG images showing the
	* various available and occupied rectangles)
	*/
	static final boolean DEBUG = false;

	/** Whether new rectangles should be placed on the left side of available rectangles */
	private static final boolean PLACE_LEFT = true;

	/** Whether new rectangles should be placed on the top rather than the bottom */
	private static final boolean PLACE_TOP = true;

	private final List<Rectangle> mySpace = new ArrayList<Rectangle>();
	private final int myMinHeight;
	private final int myMinWidth;

	/**
	* Creates a new {@linkplain BinPacker}. To use it, first add one or more
	* initial available space rectangles with {@link #addSpace(Rectangle)}, and then
	* place the rectangles with {@link #occupy(int, int)}. The returned
	* {@link Rectangle} from {@link #occupy(int, int)} gives the coordinates of the
	* positioned rectangle.
	*
	* @param minWidth the smallest width of any rectangle placed into this bin
	* @param minHeight the smallest height of any rectangle placed into this bin
	*/
	BinPacker(int minWidth, int minHeight) {
	myMinWidth = minWidth;
	myMinHeight = minHeight;

	if (DEBUG) {
	myAllocated = new ArrayList<Rectangle>();
	}
	}

	/**
	* Adds more available space
	*/
	void addSpace(Rectangle rect) {
	if (rect.width >= myMinWidth && rect.height >= myMinHeight) {
	mySpace.add(rect);
	}
	}

	/**
	* Attempts to place a rectangle of the given dimensions, if possible
	*/
	@Nullable
	Rectangle occupy(int width, int height) {
	int index = findBest(width, height);
	if (index == -1) {
	return null;
	}

	return split(index, width, height);
	}

	/**
	* Finds the best available space rectangle to position a new rectangle of
	* the given size in.
	*/
	private int findBest(int width, int height) {
	if (mySpace.isEmpty()) {
	return -1;
	}

	// Try to pack as far up as possible first
	int bestIndex = -1;
	boolean multipleAtSameY = false;
	int minY = Integer.MAX_VALUE;
	for (int i = 0, n = mySpace.size(); i < n; i++) {
	Rectangle rect = mySpace.get(i);
	if (rect.y <= minY) {
	if (rect.width >= width && rect.height >= height) {
	if (rect.y < minY) {
	minY = rect.y;
	multipleAtSameY = false;
	bestIndex = i;
	}
	else if (minY == rect.y) {
	multipleAtSameY = true;
	}
	}
	}
	}

	if (!multipleAtSameY) {
	return bestIndex;
	}

	bestIndex = -1;

	// Pick a rectangle. This currently tries to find the rectangle whose shortest
	// side most closely matches the placed rectangle's size.
	// Attempt to find the best short side fit
	int bestShortDistance = Integer.MAX_VALUE;
	int bestLongDistance = Integer.MAX_VALUE;

	for (int i = 0, n = mySpace.size(); i < n; i++) {
	Rectangle rect = mySpace.get(i);
	if (rect.y != minY) { // Only comparing elements at same y
	continue;
	}
	if (rect.width >= width && rect.height >= height) {
	if (width < height) {
	int distance = rect.width - width;
	if (distance < bestShortDistance \|\| distance == bestShortDistance && (rect.height - height) < bestLongDistance) {
	bestShortDistance = distance;
	bestLongDistance = rect.height - height;
	bestIndex = i;
	}
	}
	else {
	int distance = rect.width - width;
	if (distance < bestShortDistance \|\| distance == bestShortDistance && (rect.height - height) < bestLongDistance) {
	bestShortDistance = distance;
	bestLongDistance = rect.height - height;
	bestIndex = i;
	}
	}
	}
	}

	return bestIndex;
	}

	/**
	* Removes the rectangle at the given index. Since the rectangles are in an
	* {@link ArrayList}, removing a rectangle in the normal way is slow (it
	* would involve shifting all elements), but since we don't care about
	* order, this always swaps the to-be-deleted element to the last position
	* in the array first, <b>then</b> it deletes it (which should be
	* immediate).
	*
	* @param index the index in the {@link #mySpace} list to remove a rectangle
	* from
	*/
	private void removeRect(int index) {
	assert !mySpace.isEmpty();
	int lastIndex = mySpace.size() - 1;
	if (index != lastIndex) {
	// Swap before remove to make deletion faster since we don't
	// care about order
	Rectangle temp = mySpace.get(index);
	mySpace.set(index, mySpace.get(lastIndex));
	mySpace.set(lastIndex, temp);
	}

	mySpace.remove(lastIndex);
	}

	/**
	* Splits the rectangle at the given rectangle index such that it can contain
	* a rectangle of the given width and height.
	*/
	private Rectangle split(int index, int width, int height) {
	Rectangle rect = mySpace.get(index);
	assert rect.width >= width && rect.height >= height : rect;

	Rectangle r = new Rectangle();
	if (PLACE_LEFT) {
	r.x = rect.x;
	} else {
	r.x = rect.x + rect.width - width;
	}
	if (PLACE_TOP) {
	r.y = rect.y;
	} else {
	r.y = rect.y + rect.height - height;
	}
	r.width = width;
	r.height = height;

	// Remove all rectangles that intersect my rectangle
	for (int i = 0; i < mySpace.size(); i++) {
	Rectangle other = mySpace.get(i);
	if (other.intersects(r)) {
	removeRect(i);
	i--;
	}
	}


	int remainingHeight = rect.height - height;
	int remainingWidth = rect.width - width;
	if (PLACE_LEFT) {
	if (remainingHeight >= myMinHeight) {
	if (PLACE_TOP) {
	// Split along vertical line x = rect.x + width:
	// (rect.x,rect.y)
	// +-------------+-------------------------+
	// \| \| \|
	// \| \| \|
	// \| \| height \|
	// \| \| \|
	// \| \| \|
	// +-------------+ B \| rect.h
	// \| width \|
	// \| \| \|
	// \| A \|
	// \| \| \|
	// \| \|
	// +---------------------------------------+
	// rect.w
	mySpace.add(new Rectangle(rect.x, rect.y + height, width, remainingHeight)); // Area A
	} else {
	assert PLACE_LEFT;
	assert !PLACE_TOP;
	// Split along vertical line x = rect.x + width:
	// (rect.x,rect.y)
	// +-------------+-------------------------+
	// \| \|
	// \| \| \|
	// \| A \|
	// \| \| \|
	// \| width \|
	// +-------------+ B \| rect.h
	// \| \| \|
	// \| \| \|
	// \| \| height \|
	// \| \| \|
	// \| \| \|
	// +-------------+-------------------------+
	// rect.w
	mySpace.add(new Rectangle(rect.x, rect.y, width, remainingHeight)); // Area A
	}
	}
	if (remainingWidth >= myMinWidth) { // Area B
	mySpace.add(new Rectangle(rect.x + width, rect.y, remainingWidth, rect.height));
	}
	}
	else {
	assert !PLACE_LEFT;
	// Split along vertical line x = rect.x + rect.w - width
	// (rect.x,rect.y)
	// +---------------------------------------+
	// \| \|
	// \| \| \|
	// \| A \|
	// \| \| \|
	// \| width \|
	// \| B +--------------\| rect.h
	// \| \| \|
	// \| \| \|
	// \| height \| \|
	// \| \| \|
	// \| \| \|
	// +------------------------+--------------+
	// rect.w
	if (remainingWidth >= myMinWidth) { // Area B
	mySpace.add(new Rectangle(rect.x, rect.y, remainingWidth, rect.height));
	}
	if (remainingHeight >= myMinHeight) { // Area A
	if (PLACE_TOP) {
	mySpace.add(new Rectangle(rect.x + rect.width - width, rect.y + height, width, remainingHeight));
	} else {
	mySpace.add(new Rectangle(rect.x + rect.width - width, rect.y, width, remainingHeight));
	}
	}
	}

	if (PLACE_LEFT) {
	if (PLACE_TOP) {
	// Split along horizontal line y = rect.y + height:
	// +-------------+-------------------------+
	// \| \| \|
	// \| \| height \|
	// \| \| A \|
	// \| \| \|
	// \| \| \| rect.h
	// +-------------+ - - - - - - - - - - - - \|
	// \| width \|
	// \| \|
	// \| B \|
	// \| \|
	// \| \|
	// +---------------------------------------+
	// rect.w
	if (remainingHeight >= myMinHeight) { // Area B
	mySpace.add(new Rectangle(rect.x, rect.y + height, rect.width, remainingHeight));
	}
	if (remainingWidth >= myMinWidth) { // Area A
	mySpace.add(new Rectangle(rect.x + width, rect.y, remainingWidth, height));
	}
	} else {
	assert PLACE_LEFT;
	assert !PLACE_TOP;
	// +---------------------------------------+
	// \| \|
	// \| \|
	// \| B \|
	// \| \|
	// \| \| rect.h
	// +-------------+ - - - - - - - - - - - - \|
	// \| width \| \|
	// \| \| \|
	// \| \| height A \|
	// \| \| \|
	// \| \| \|
	// +-------------+-------------------------+
	// rect.w
	if (remainingHeight >= myMinHeight) { // Area B
	mySpace.add(new Rectangle(rect.x, rect.y, rect.width, remainingHeight));
	}
	if (remainingWidth >= myMinWidth) { // Area A
	mySpace.add(new Rectangle(rect.x + width, rect.y + rect.height - height, remainingWidth, height));
	}
	}
	}
	else {
	assert !PLACE_LEFT;
	if (PLACE_TOP) {
	// Split along horizontal line y = rect.y + rect.h - height:
	// +-------------------------+-------------+
	// \| \| \|
	// \| \| \|
	// \| A height \| \|
	// \| \| \|
	// \| \| \| rect.h
	// \| - - - - - - - - - - - - +-------------\|
	// \| width \|
	// \| \|
	// \| B \|
	// \| \|
	// \| \|
	// +---------------------------------------+
	// rect.w

	if (remainingHeight >= myMinHeight) { // Area B
	mySpace.add(new Rectangle(rect.x, rect.y + height, rect.width, remainingHeight));
	}
	if (remainingWidth >= myMinWidth) { // Area A
	mySpace.add(new Rectangle(rect.x, rect.y, remainingWidth, height));
	}
	} else {
	assert !PLACE_LEFT;
	assert !PLACE_TOP;
	// Split along horizontal line y = rect.y + rect.h - height:
	// +---------------------------------------+
	// \| \|
	// \| \|
	// \| B \|
	// \| \|
	// \| width \| rect.h
	// \| - - - - - - - - - - - - +-------------\|
	// \| \| \|
	// \| \| \|
	// \| A height \| \|
	// \| \| \|
	// \| \| \|
	// +-------------------------+-------------+
	// rect.w

	if (remainingHeight >= myMinHeight) { // Area B
	mySpace.add(new Rectangle(rect.x, rect.y, rect.width, remainingHeight));
	}
	if (remainingWidth >= myMinWidth) { // Area A
	mySpace.add(new Rectangle(rect.x, rect.y + rect.height - height, remainingWidth, height));
	}
	}
	}

	if (DEBUG) {
	myAllocated.add(r);
	}

	if (DEBUG) {
	dumpDiagnostics();
	}


	// Remove redundant rectangles. This is not very efficient.
	for (int i = 0; i < mySpace.size() - 1; i++) {
	for (int j = i + 1; j < mySpace.size(); j++) {
	Rectangle iRect = mySpace.get(i);
	Rectangle jRect = mySpace.get(j);
	if (jRect.contains(iRect)) {
	removeRect(i);
	i--;
	break;
	}
	if (iRect.contains(jRect)) {
	removeRect(j);
	j--;
	}
	}
	}

	if (DEBUG) {
	dumpDiagnostics();
	}

	return r;
	}

	// DEBUGGING CODE: Enable with DEBUG

	private List<Rectangle> myAllocated;
	private int myIteration;

	@SuppressWarnings("EmptyCatchBlock")
	void dumpDiagnostics() {
	if (DEBUG) {
	myIteration++;
	// Determine size
	Rectangle r = new Rectangle(0, 0, 100, 100);
	for (Rectangle rect : mySpace) {
	r.add(rect);
	}

	BufferedImage image = UIUtil.createImage(r.width, r.height, BufferedImage.TYPE_INT_ARGB);
	Graphics g = image.getGraphics();
	// Fill background
	g.setColor(Color.BLACK);
	g.fillRect(0, 0, r.width, r.height);

	paintDiagnostics((Graphics2D)g);
	g.dispose();

	try {
	File file = new File("/tmp/layout-iteration-" + myIteration + ".png");
	ImageIO.write(image, "PNG", file);
	} catch (Exception e) {
	}
	}
	}

	@SuppressWarnings({"AssignmentToStaticFieldFromInstanceMethod", "CallToPrintStackTrace", "UseOfSystemOutOrSystemErr"})
	void paintDiagnostics(Graphics2D g) {
	if (DEBUG) {
	Composite prevComposite = g.getComposite();
	g.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 0.5f));

	Color[] colors =
	new Color[]{Color.blue, Color.cyan, Color.green, Color.magenta, Color.orange, Color.pink, Color.red, Color.white, Color.yellow,
	Color.darkGray, Color.lightGray, Color.gray,};

	if (myAllocated != null && !myAllocated.isEmpty()) {
	char allocated = 'A';
	for (Rectangle rect : myAllocated) {
	Color color = new Color(0x9FFFFFFF, true);
	g.setColor(color);
	g.setBackground(color);
	g.fillRect(rect.x, rect.y, rect.width, rect.height);
	g.setColor(Color.WHITE);
	g.drawRect(rect.x, rect.y, rect.width, rect.height);
	g.drawString(String.valueOf(allocated++), rect.x + rect.width / 2, rect.y + rect.height / 2);
	}
	}

	int colorIndex = 0;
	for (Rectangle rect : mySpace) {
	Color color = colors[colorIndex];
	colorIndex = (colorIndex + 1) % colors.length;

	color = new Color(color.getRed(), color.getGreen(), color.getBlue(), 128);
	g.setColor(color);

	g.fillRect(rect.x, rect.y, rect.width, rect.height);
	g.setColor(Color.WHITE);
	g.drawString(Integer.toString(colorIndex), rect.x + rect.width / 2, rect.y + rect.height / 2);
	}

	g.setComposite(prevComposite);
	}
	}
	}