CSC352 Homework 2 2013 Solution

--D. Thiebaut (talk) 15:07, 4 October 2013 (EDT)

---

Source Code

Main Applet

/*
 * MainApplet.  
 * D. Thiebaut
 * 
 * Packing rectangles.
 * This applet attempts to pack a collection of rectangles into a large 
 * rectangle of area mainW x mainH.
 * In this very crude implementation, the original collection of rectangles
 * to pack is in rectsToPlace of type RectangleCollection1.  This object simply
 * creates a collection of random rectangles which it sorts by area, the largest
 * first, the smallest last. 
 * When this applet is run in its current form, it first displays it displays a blank window.
 * Every time the user presses Enter, a new rectangle is taken from the collection and
 * positioned (if possible ) on the screen.   It takes a lot of clicking on ENTER to pack
 * the window.
 * A better approach is to call keyPressed() in draw() (which is currently commented out).
 * This way a rectangle is added every time draw() is called: much faster.  But still not
 * as fast as we might want to go.  The solution is to do something like what is in Homework 2!
 */
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Random;
import java.util.concurrent.ConcurrentLinkedQueue;

import processing.core.PApplet;



public class MainAppletThreaded extends PApplet {
	static boolean firstTime = true;
	LineSet lines = null;
	int N	  = 20000; 			// number of rectangles to pack
	int mainW = 1200;
	int mainH = 1000;
	long longMainW = mainW;
	long longMainH = mainH;
	float scaleFactor = 1.0f;
	final int border = 25;
	final int rectColor = 0xFFA069D6;
	final int rectOutline = 0xFF000000;
	final int bigRectColor = 0xFFBFB730;
	long startTime, endTime;
	
	ArrayList<Rectangle> placedRects = null;
	RectangleCollection2 rectsToPlace = null;
	boolean debug = false;
	ConcurrentLinkedQueue<Rectangle> queue = null;  
	
	public void setup() {
		//--- define the geometry of the applet window ---
		size(mainW + 2 * border, mainH + 2 * border);
		smooth();
		
		//--- create the queue for communication with thread ---
		queue = new ConcurrentLinkedQueue<Rectangle>();
		
		//--- create N random rectangles ---
		placedRects = new ArrayList<Rectangle>();
		rectsToPlace = new RectangleCollection2();		
		ArrayList<Integer> geometry = rectsToPlace.initRandomAndSetGeometry( N );
		
		//--- define geometry of the "real" large rectangle to pack.
		longMainW = geometry.get( 0 );
		longMainH = (long) ( geometry.get( 1 ) * 1.03f); // allow for 3% inefficiency
		scaleFactor = Math.min( ( 1.0f / longMainW ) * mainW, ( 1.0f / longMainH ) * mainH );
		scaleFactor = scaleFactor / 1.1f / 1.1f;

		PackingThread2 thread = new PackingThread2( queue, longMainW, longMainH, rectsToPlace );
		//lines = thread.getLines();   // this is just if we are interested in drawing the lines at some point...
		thread.start();
		frameRate(20);
		startTime = System.currentTimeMillis();
	}

	public void draw() {

		if ( queue.isEmpty() )
			return;
		
		//pushMatrix();
		translate(border, border);
		scale( scaleFactor );
		
		//--- display frame the very first time----
		if ( firstTime ) {
			background( 0xffffffff );
			fill( bigRectColor );
			stroke( bigRectColor );
			rect(0, 0, longMainW, longMainH);
			firstTime = false;
		}

		//--- set drawing attributes ---
		fill( rectColor );
		stroke( rectOutline );
		this.strokeWeight(3);

		while ( ! queue.isEmpty() ) {
			Rectangle r = queue.poll();
			placedRects.add( r );
			r.draw( this );
		}
				
		//popMatrix();
		
		//--- display some status information at the top of the frame ---
		stroke( 0xffffffff );		 // all white
		fill( 0xffffffff );
		rect( 0, 0, 400, border-1 ); // erase previous caption
		fill( 0xff000000 );  // black text
		text( String.format( "%d/%d --  %s", 
				placedRects.size(),	N, timeFormat( System.currentTimeMillis()-startTime ) ), 
			  border, border/2 );
	}

	private String timeFormat(long l) {
		if ( l < 1000 ) return String.format( "0.%03d sec", l );
		int s 	= (int) ( l / 1000 );
		int ms 	= ( int ) ( l % 1000 );
		int m 	= (int) ( s / 60 );
		if ( m == 0 )
			return String.format( "%02d.%03d sec", s, ms );
		s 		= (int) ( s % 60 );		
		return String.format( "%02d:%02d.%03d min", m, s, ms );
	}

	public void keyPressed() {
		System.out.println( "Keypressed not implemented..." );
		if ( key=='+' || key =='=' ) 
			scaleFactor = scaleFactor * 1.10f;
		if ( key=='-' || key =='_' ) 
			scaleFactor = scaleFactor / 1.10f;
	}

}

Thread

/**
 * PackingThread2
 * D. Thiebaut
 * This thread uses Packer to packs as fast as it can, in a while loop,
 * all the rectangles in a RectangleCollection. 
 * It enqueues them all in a nonblocking queue that is read by the draw()
 * thread, which draws the rectangles on the applet.
 * 
 */
import java.util.Iterator;
import java.util.concurrent.ConcurrentLinkedQueue;

public class PackingThread2 extends Thread {
	ConcurrentLinkedQueue<Rectangle> queue = new ConcurrentLinkedQueue<Rectangle>();
	RectangleCollection2 rectsToPlace;
	Packer packer = null;
	Iterator<Rectangle> it;
	
	/**
	 * The thread.  When it starts, it is give the queue to communicate with the applet
	 * draw() function
	 * @param queue: the concurrentLinkedQueue
	 * @param mainW: the width of the applet (will be passed to Packer)
	 * @param mainH: the height of the applet
	 * @param rectsToPlace: the collection of rectangles to place
	 */
	PackingThread2( ConcurrentLinkedQueue<Rectangle> queue, int mainW, int mainH,
					RectangleCollection2 rectsToPlace ) {
		this.queue = queue;	
		this.rectsToPlace = rectsToPlace;
		packer =  new Packer(mainW, mainH);
		
	}
	
	/**
	 * The thread.  When it starts, it is give the queue to communicate with the applet
	 * draw() function
	 * @param queue: the concurrentLinkedQueue
	 * @param mainW: the width of the applet (will be passed to Packer)
	 * @param mainH: the height of the applet
	 * @param rectsToPlace: the collection of rectangles to place
	 */
	public PackingThread2(ConcurrentLinkedQueue<Rectangle> queue,
			long longMainW, long longMainH, RectangleCollection2 rectsToPlace ) {
		this.queue = queue;	
		this.rectsToPlace = rectsToPlace;
		packer =  new Packer(longMainW, longMainH);	
	}

	/**
	 * run(): takes all the rectangles one by one, passes them to packer, and if they can be
	 * packed, enqueues them in the queue to pass to draw()
	 */
	public void run() {
		it = rectsToPlace.iterator();
		while ( it.hasNext() ) {
			//--- get a new rectangle from the collection.  The next largest in the collection ---
			Rectangle rectangle = it.next();
			
			//--- if none is returned, we're done packing ---
			if (rectangle == null)
				break;
	
			//--- if packer can pack it, it will set its coordinates to the correct location where   ---
			//--- it should go.  We keep track of it in placedRects.  Otherwise it will return false.---
			if (packer.pack(rectangle) )
				queue.add( rectangle );
		}
	}

	/**
	 * pass the lines back to the applet so that they can be displayed along with the rectangles
	 * @return
	 */
	public LineSet getLines() {
		return packer.lines;
	}
}