eclipse/plugins/com.android.ide.eclipse.adt/src/com/android/ide/eclipse/adt/internal/editors/layout/gle2/BinPacker.java - platform/sdk - Git at Google

 /*
  * Copyright (C) 2012 The Android Open Source Project
  *
  * Licensed under the Eclipse Public License, Version 1.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.eclipse.org/org/documents/epl-v10.php
  *
  * 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.ide.eclipse.adt.internal.editors.layout.gle2;

 import com.android.annotations.Nullable;
 import com.android.ide.common.api.Rect;

 import java.awt.Color;
 import java.awt.Graphics2D;
 import java.awt.image.BufferedImage;
 import java.io.File;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.List;

 import javax.imageio.ImageIO;

 /**
  * 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.
  */
 class BinPacker {
     /**
      * When enabled, the successive passes are dumped as PNG images showing the
      * various available and occupied rectangles)
      */
     private static final boolean DEBUG = false;

     private final List<Rect> mSpace = new ArrayList<Rect>();
     private final int mMinHeight;
     private final int mMinWidth;

     /**
      * Creates a new {@linkplain BinPacker}. To use it, first add one or more
      * initial available space rectangles with {@link #addSpace(Rect)}, and then
      * place the rectangles with {@link #occupy(int, int)}. The returned
      * {@link Rect} 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) {
         mMinWidth = minWidth;
         mMinHeight = minHeight;

         if (DEBUG) {
             mAllocated = new ArrayList<Rect>();
             sLayoutId++;
             sRectId = 1;
         }
     }

     /** Adds more available space */
     void addSpace(Rect rect) {
         if (rect.w >= mMinWidth && rect.h >= mMinHeight) {
             mSpace.add(rect);
         }
     }

     /** Attempts to place a rectangle of the given dimensions, if possible */
     @Nullable
     Rect 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 (mSpace.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 = mSpace.size(); i < n; i++) {
             Rect rect = mSpace.get(i);
             if (rect.y <= minY) {
                 if (rect.w >= width && rect.h >= 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 = mSpace.size(); i < n; i++) {
             Rect rect = mSpace.get(i);
             if (rect.y != minY) { // Only comparing elements at same y
                 continue;
             }
             if (rect.w >= width && rect.h >= height) {
                 if (width < height) {
                     int distance = rect.w - width;
                     if (distance < bestShortDistance ||
                             distance == bestShortDistance &&
                             (rect.h - height) < bestLongDistance) {
                         bestShortDistance = distance;
                         bestLongDistance = rect.h - height;
                         bestIndex = i;
                     }
                 } else {
                     int distance = rect.w - width;
                     if (distance < bestShortDistance ||
                             distance == bestShortDistance &&
                             (rect.h - height) < bestLongDistance) {
                         bestShortDistance = distance;
                         bestLongDistance = rect.h - 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 #mSpace} list to remove a rectangle
      *            from
      */
     private void removeRect(int index) {
         assert !mSpace.isEmpty();
         int lastIndex = mSpace.size() - 1;
         if (index != lastIndex) {
             // Swap before remove to make deletion faster since we don't
             // care about order
             Rect temp = mSpace.get(index);
             mSpace.set(index, mSpace.get(lastIndex));
             mSpace.set(lastIndex, temp);
         }

         mSpace.remove(lastIndex);
     }

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

         Rect r = new Rect(rect);
         r.w = width;
         r.h = height;

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


         // Split along vertical line x = rect.x + width:
         // (rect.x,rect.y)
         //     +-------------+-------------------------+
         //     |             |                         |
         //     |             |                         |
         //     |             | height                  |
         //     |             |                         |
         //     |             |                         |
         //     +-------------+           B             | rect.h
         //     |   width                               |
         //     |             |                         |
         //     |      A                                |
         //     |             |                         |
         //     |                                       |
         //     +---------------------------------------+
         //                    rect.w
         int remainingHeight = rect.h - height;
         int remainingWidth = rect.w - width;
         if (remainingHeight >= mMinHeight) {
             mSpace.add(new Rect(rect.x, rect.y + height, width, remainingHeight));
         }
         if (remainingWidth >= mMinWidth) {
             mSpace.add(new Rect(rect.x + width, rect.y, remainingWidth, rect.h));
         }

         // Split along horizontal line y = rect.y + height:
         //     +-------------+-------------------------+
         //     |             |                         |
         //     |             | height                  |
         //     |             |          A              |
         //     |             |                         |
         //     |             |                         | rect.h
         //     +-------------+ - - - - - - - - - - - - |
         //     |  width                                |
         //     |                                       |
         //     |                B                      |
         //     |                                       |
         //     |                                       |
         //     +---------------------------------------+
         //                   rect.w
         if (remainingHeight >= mMinHeight) {
             mSpace.add(new Rect(rect.x, rect.y + height, rect.w, remainingHeight));
         }
         if (remainingWidth >= mMinWidth) {
             mSpace.add(new Rect(rect.x + width, rect.y, remainingWidth, height));
         }

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

         if (DEBUG) {
             mAllocated.add(r);
             dumpImage();
         }

         return r;
     }

     // DEBUGGING CODE: Enable with DEBUG

     private List<Rect> mAllocated;
     private static int sLayoutId;
     private static int sRectId;
     private void dumpImage() {
         if (DEBUG) {
             int width = 100;
             int height = 100;
             for (Rect rect : mSpace) {
                 width = Math.max(width, rect.w);
                 height = Math.max(height, rect.h);
             }
             width += 10;
             height += 10;

             BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);
             Graphics2D g = image.createGraphics();
             g.setColor(Color.BLACK);
             g.fillRect(0, 0, image.getWidth(), image.getHeight());

             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,
             };

             char allocated = 'A';
             for (Rect rect : mAllocated) {
                 Color color = new Color(0x9FFFFFFF, true);
                 g.setColor(color);
                 g.setBackground(color);
                 g.fillRect(rect.x, rect.y, rect.w, rect.h);
                 g.setColor(Color.WHITE);
                 g.drawRect(rect.x, rect.y, rect.w, rect.h);
                 g.drawString("" + (allocated++),
                         rect.x + rect.w / 2, rect.y + rect.h / 2);
             }

             int colorIndex = 0;
             for (Rect rect : mSpace) {
                 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.w, rect.h);
                 g.setColor(Color.WHITE);
                 g.drawString(Integer.toString(colorIndex),
                         rect.x + rect.w / 2, rect.y + rect.h / 2);
             }


             g.dispose();

             File file = new File("/tmp/layout" + sLayoutId + "_pass" + sRectId + ".png");
             try {
                 ImageIO.write(image, "PNG", file);
                 System.out.println("Wrote diagnostics image " + file);
             } catch (IOException e) {
                 e.printStackTrace();
             }
             sRectId++;
         }
     }
 }
	/*
	* Copyright (C) 2012 The Android Open Source Project
	*
	* Licensed under the Eclipse Public License, Version 1.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.eclipse.org/org/documents/epl-v10.php
	*
	* 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.ide.eclipse.adt.internal.editors.layout.gle2;

	import com.android.annotations.Nullable;
	import com.android.ide.common.api.Rect;

	import java.awt.Color;
	import java.awt.Graphics2D;
	import java.awt.image.BufferedImage;
	import java.io.File;
	import java.io.IOException;
	import java.util.ArrayList;
	import java.util.List;

	import javax.imageio.ImageIO;

	/**
	* 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.
	*/
	class BinPacker {
	/**
	* When enabled, the successive passes are dumped as PNG images showing the
	* various available and occupied rectangles)
	*/
	private static final boolean DEBUG = false;

	private final List<Rect> mSpace = new ArrayList<Rect>();
	private final int mMinHeight;
	private final int mMinWidth;

	/**
	* Creates a new {@linkplain BinPacker}. To use it, first add one or more
	* initial available space rectangles with {@link #addSpace(Rect)}, and then
	* place the rectangles with {@link #occupy(int, int)}. The returned
	* {@link Rect} 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) {
	mMinWidth = minWidth;
	mMinHeight = minHeight;

	if (DEBUG) {
	mAllocated = new ArrayList<Rect>();
	sLayoutId++;
	sRectId = 1;
	}
	}

	/** Adds more available space */
	void addSpace(Rect rect) {
	if (rect.w >= mMinWidth && rect.h >= mMinHeight) {
	mSpace.add(rect);
	}
	}

	/** Attempts to place a rectangle of the given dimensions, if possible */
	@Nullable
	Rect 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 (mSpace.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 = mSpace.size(); i < n; i++) {
	Rect rect = mSpace.get(i);
	if (rect.y <= minY) {
	if (rect.w >= width && rect.h >= 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 = mSpace.size(); i < n; i++) {
	Rect rect = mSpace.get(i);
	if (rect.y != minY) { // Only comparing elements at same y
	continue;
	}
	if (rect.w >= width && rect.h >= height) {
	if (width < height) {
	int distance = rect.w - width;
	if (distance < bestShortDistance \|\|
	distance == bestShortDistance &&
	(rect.h - height) < bestLongDistance) {
	bestShortDistance = distance;
	bestLongDistance = rect.h - height;
	bestIndex = i;
	}
	} else {
	int distance = rect.w - width;
	if (distance < bestShortDistance \|\|
	distance == bestShortDistance &&
	(rect.h - height) < bestLongDistance) {
	bestShortDistance = distance;
	bestLongDistance = rect.h - 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 #mSpace} list to remove a rectangle
	* from
	*/
	private void removeRect(int index) {
	assert !mSpace.isEmpty();
	int lastIndex = mSpace.size() - 1;
	if (index != lastIndex) {
	// Swap before remove to make deletion faster since we don't
	// care about order
	Rect temp = mSpace.get(index);
	mSpace.set(index, mSpace.get(lastIndex));
	mSpace.set(lastIndex, temp);
	}

	mSpace.remove(lastIndex);
	}

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

	Rect r = new Rect(rect);
	r.w = width;
	r.h = height;

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


	// Split along vertical line x = rect.x + width:
	// (rect.x,rect.y)
	// +-------------+-------------------------+
	// \| \| \|
	// \| \| \|
	// \| \| height \|
	// \| \| \|
	// \| \| \|
	// +-------------+ B \| rect.h
	// \| width \|
	// \| \| \|
	// \| A \|
	// \| \| \|
	// \| \|
	// +---------------------------------------+
	// rect.w
	int remainingHeight = rect.h - height;
	int remainingWidth = rect.w - width;
	if (remainingHeight >= mMinHeight) {
	mSpace.add(new Rect(rect.x, rect.y + height, width, remainingHeight));
	}
	if (remainingWidth >= mMinWidth) {
	mSpace.add(new Rect(rect.x + width, rect.y, remainingWidth, rect.h));
	}

	// Split along horizontal line y = rect.y + height:
	// +-------------+-------------------------+
	// \| \| \|
	// \| \| height \|
	// \| \| A \|
	// \| \| \|
	// \| \| \| rect.h
	// +-------------+ - - - - - - - - - - - - \|
	// \| width \|
	// \| \|
	// \| B \|
	// \| \|
	// \| \|
	// +---------------------------------------+
	// rect.w
	if (remainingHeight >= mMinHeight) {
	mSpace.add(new Rect(rect.x, rect.y + height, rect.w, remainingHeight));
	}
	if (remainingWidth >= mMinWidth) {
	mSpace.add(new Rect(rect.x + width, rect.y, remainingWidth, height));
	}

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

	if (DEBUG) {
	mAllocated.add(r);
	dumpImage();
	}

	return r;
	}

	// DEBUGGING CODE: Enable with DEBUG

	private List<Rect> mAllocated;
	private static int sLayoutId;
	private static int sRectId;
	private void dumpImage() {
	if (DEBUG) {
	int width = 100;
	int height = 100;
	for (Rect rect : mSpace) {
	width = Math.max(width, rect.w);
	height = Math.max(height, rect.h);
	}
	width += 10;
	height += 10;

	BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);
	Graphics2D g = image.createGraphics();
	g.setColor(Color.BLACK);
	g.fillRect(0, 0, image.getWidth(), image.getHeight());

	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,
	};

	char allocated = 'A';
	for (Rect rect : mAllocated) {
	Color color = new Color(0x9FFFFFFF, true);
	g.setColor(color);
	g.setBackground(color);
	g.fillRect(rect.x, rect.y, rect.w, rect.h);
	g.setColor(Color.WHITE);
	g.drawRect(rect.x, rect.y, rect.w, rect.h);
	g.drawString("" + (allocated++),
	rect.x + rect.w / 2, rect.y + rect.h / 2);
	}

	int colorIndex = 0;
	for (Rect rect : mSpace) {
	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.w, rect.h);
	g.setColor(Color.WHITE);
	g.drawString(Integer.toString(colorIndex),
	rect.x + rect.w / 2, rect.y + rect.h / 2);
	}


	g.dispose();

	File file = new File("/tmp/layout" + sLayoutId + "_pass" + sRectId + ".png");
	try {
	ImageIO.write(image, "PNG", file);
	System.out.println("Wrote diagnostics image " + file);
	} catch (IOException e) {
	e.printStackTrace();
	}
	sRectId++;
	}
	}
	}