plugins/org.polarsys.chess.multicore/src/org/polarsys/chess/multicore/partitioning/WorstFitBinPacker.java

/*------------------------------------------------------------------------------
  -
  - Copyright (c) 2015-2016 University of Padova, ITALY -  Intecs SpA 
  - All rights reserved. This program and the accompanying materials
  - are made available under the terms of the Eclipse Public License v2.0
  - which accompanies this distribution, and is available at
  - http://www.eclipse.org/legal/epl-v20.html
  -
  - Contributors:
  -
  - Alessandro Zovi azovi@math.unipd.it
  - Stefano Puri stefano.puri@intecs.it
  - Laura Baracchi laura.baracchi@intecs.it
  - Nicholas Pacini nicholas.pacini@intecs.it  
  -
  - Initial API and implementation and/or initial documentation
  ------------------------------------------------------------------------------*/package org.polarsys.chess.multicore.partitioning;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;

/**
 * The Class WorstFitBinPacker.
 */
public class WorstFitBinPacker implements BinPacker {
	
	/** The decreasing ordering. */
	private final boolean DECREASING_ORDERING = true; 

//	@Override
//	public Map<Bin, List<Task>> pack(List<Bin> bins, List<Task> tasks) {		
//		
//		Map<Bin, List<Task>> toReturn = new Hashtable<Bin, List<Task>> ();
//		// init output
//		for(Bin bin : bins)
//			toReturn.put(bin, new ArrayList<Task>());
//		
//		
//		if(tasks.size() <= bins.size()){ // trivial packing
//			int i =0;
//			for(Task task : tasks){
//				Bin bin = bins.get(i);
//				ArrayList<Task> theList = new ArrayList<Task>();
//				theList.add(task);
//				bin.setCapacity(bin.getCapacity()+task.computeU());
//				toReturn.put(bin, theList);
//				i++;
//			}
//		} else {// nominal case
//			
//			// sort the tasks by increasing/decreasing utilisation
//			Object[] allTasks = tasks.toArray();
//			//Arrays.sort(allTasks);
//			Arrays.sort(allTasks, new Comparator<Object>() {
//
//				@Override
//				public int compare(Object o1, Object o2) {
//					if(DECREASING_ORDERING)
//						return -(((Task)o1).computeU()).compareTo(((Task)o2).computeU());
//					else
//						return (((Task)o1).computeU()).compareTo(((Task)o2).computeU());
//				}
//			});
//			
//			int indexEmptiestBin = 0;
//			float emptiestCapacity = 0.0f;
//			Object[] allBins = bins.toArray();
//			
//			
//			for(int taskIndex = 0; taskIndex < allTasks.length; taskIndex++){
//				
//				Task task = (Task)allTasks[taskIndex];
//				boolean found = false;
//				
//				Bin bin = (Bin)allBins[indexEmptiestBin];
//				// try with emptiest bin
//				if(bin.getCapacity() + task.computeU() <= bin.getSize())
//					found = true;
//				else { //try with other bins 
//					for(int indexCurrentBin = 0; indexCurrentBin < allBins.length; indexCurrentBin++){
//						if (indexCurrentBin == indexEmptiestBin) // already visited
//							continue;
//						bin =(Bin)allBins[indexCurrentBin];
//						if(bin.getCapacity() + task.computeU() <= bin.getSize()){
//							found = true;
//							break;
//						}
//					}
//				}
//				
//				if(!found)
//					System.out.println("PACKING FAILED");
//				else {
//					task.setOwner(bin);
//					bin.setCapacity(bin.getCapacity()+task.computeU());
//					// store to output
//					List<Task> theTasks = toReturn.get(bin);
//					theTasks.add(task);
//					toReturn.put(bin, theTasks);
//					found = true;
//					// update info on emptiest bin
//					emptiestCapacity = Float.MAX_VALUE;
//					for(int binIndex = 0; binIndex < allBins.length; binIndex++){
//						float currentCapacity = ((Bin)allBins[binIndex]).getCapacity();
//						if(currentCapacity < emptiestCapacity){
//							emptiestCapacity = currentCapacity;
//							indexEmptiestBin = binIndex;
//						}
//					}
//				}
//			}
//			
//		}
//		return toReturn;
//	}

	/* (non-Javadoc)
 * @see org.polarsys.chess.multicore.partitioning.BinPacker#pack(java.util.List, java.util.List)
 */
@Override
	public Map<Bin, List<Task>> pack(List<Bin> bins, List<Task> tasks) {		
		
		Map<Bin, List<Task>> toReturn = new Hashtable<Bin, List<Task>> ();
		
		// init output
//		for(Bin bin : bins)
//			toReturn.put(bin, new ArrayList<Task>());
		
		
		if(tasks.size() <= bins.size()){ // trivial packing
			int i =0;
			for(Task task : tasks){
				Bin bin = bins.get(i);
				ArrayList<Task> theList = new ArrayList<Task>();
				theList.add(task);
				bin.setCapacity(bin.getCapacity()+task.getU());
				toReturn.put(bin, theList);
				i++;
			}
		} else {// nominal case
			
			// sort the tasks by increasing/decreasing utilization
			Object[] allTasks = tasks.toArray();
			//Arrays.sort(allTasks);
			Arrays.sort(allTasks, new Comparator<Object>() {

				@Override
				public int compare(Object o1, Object o2) {
					if(DECREASING_ORDERING)
						return -(((Task)o1).getU()).compareTo(((Task)o2).getU());
					else
						return (((Task)o1).getU()).compareTo(((Task)o2).getU());
				}
			});
			
			int indexEmptiestBin = 0;
			float emptiestCapacity = 0.0f;
			Object[] allBins = {new Bin(indexEmptiestBin)}; // ensure there is at least 1 bin even in case an empty list has been passed (this is the case during RUN reduction)
			int indexLastBin = 0;
			if(bins.size() > 0){
				allBins = bins.toArray();
				indexLastBin = bins.size()-1;
			}
				
			
			
			for(int taskIndex = 0; taskIndex < allTasks.length; taskIndex++){
				
				Task task = (Task)allTasks[taskIndex];
				Bin bin = (Bin)allBins[indexEmptiestBin];
				// try with emptiest bin
				if(bin.getCapacity() + task.getU() <= bin.getSize()){
					task.setOwner(bin);
					bin.setCapacity(bin.getCapacity()+task.getU());
					// store to output
					List<Task> theTasks = toReturn.get(bin);
					if(theTasks == null) // needed because we don't initialize toReturn at the beginning, to provide input/output of variable size
						theTasks = new ArrayList<Task>();
					theTasks.add(task);
					toReturn.put(bin, theTasks);
				}
				else {
					//System.out.println("PARTITIONING FAILED, OPENING NEW BIN");
					// open new bin
					Bin newBin = new Bin(new Integer(++indexLastBin));
					task.setOwner(newBin);
					newBin.setCapacity(newBin.getCapacity()+task.getU());
					ArrayList<Task> theList = new ArrayList<Task>();
					theList.add(task);
					toReturn.put(newBin, theList);
					
					// add bin to the common array 
					Object[] tmpBinArray = Arrays.copyOf(allBins, allBins.length + 1);
					assert(tmpBinArray.length -1 == indexLastBin);
					tmpBinArray[indexLastBin] = newBin;
					allBins = tmpBinArray;
				}
				
				// update info on emptiest bin
				emptiestCapacity = Float.MAX_VALUE;
				for(int binIndex = 0; binIndex < allBins.length; binIndex++){
					float currentCapacity = ((Bin)allBins[binIndex]).getCapacity();
					if(currentCapacity < emptiestCapacity){
						emptiestCapacity = currentCapacity;
						indexEmptiestBin = binIndex;
					}
				}
			}
			
		}
		return toReturn;
	}
}