/*
 * Title: CloudSim Toolkit Description: CloudSim (Cloud Simulation) Toolkit for Modeling and
 * Simulation of Clouds Licence: GPL - http://www.gnu.org/copyleft/gpl.html
 * 
 * Copyright (c) 2009-2012, The University of Melbourne, Australia
 */

package org.cloudbus.cloudsim;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import org.cloudbus.cloudsim.lists.PeList;
import org.cloudbus.cloudsim.provisioners.PeProvisioner;

/**
 * VmSchedulerTimeShared is a Virtual Machine Monitor (VMM) allocation policy that allocates one or more PEs 
 * from a PM to a VM, and allows sharing of PEs by multiple VMs. This class also implements 10% performance degradation due
 * to VM migration. This scheduler does not support over-subscription.
 * 
 * Each host has to use is own instance of a VmScheduler
 * that will so schedule the allocation of host's PEs for VMs running on it.
 * 
 * @author Rodrigo N. Calheiros
 * @author Anton Beloglazov
 * @since CloudSim Toolkit 1.0
 */
public class VmSchedulerTimeShared extends VmScheduler {
	/** The map of requested mips, where each key is a VM
	 * and each value is a list of MIPS requested by that VM.
	 */
	private Map<String, List<Double>> mipsMapRequested;

	/** The number of host's PEs in use. */
	private int pesInUse;

	/**
	 * Instantiates a new vm time-shared scheduler.
	 *
	 * @param pelist the list of PEs of the host where the VmScheduler is associated to.
	 */
	public VmSchedulerTimeShared(List<? extends Pe> pelist) {
		super(pelist);
		setMipsMapRequested(new HashMap<String, List<Double>>());
	}

	@Override
	public boolean allocatePesForVm(Vm vm, List<Double> mipsShareRequested) {
		/*
		 * @todo add the same to RAM and BW provisioners
		 */

		if (vm.isInMigration()) {
			if (!getVmsMigratingIn().contains(vm.getUid())) {
				getVmsMigratingIn().add(vm.getUid());
			}
		} else {
			if (getVmsMigratingIn().contains(vm.getUid())) {
				getVmsMigratingIn().remove(vm.getUid());
			}
		}
		boolean result = allocatePesForVm(vm.getUid(), mipsShareRequested);
		updatePeProvisioning();
		return result;
	}

	/**
	 * Allocate PEs for a vm.
	 *
	 * @param //vmUid the vm uid
	 * @param //mipsShareRequested the list of mips share requested by the vm
	 * @return true, if successful
	 */

	protected boolean allocatePesForVm(String vmUid, List<Double> mipsShareRequested) {
		/*getMipsMapRequested().put(vmUid, mipsShareRequested);
		setPesInUse(getPesInUse() + mipsShareRequested.size());

		double totalRequestedMips = 0;
		double peMips = getPeCapacity();
		for (Double mips : mipsShareRequested) {
			if (mips > peMips) { // each virtual PE of a VM must require not more than the capacity of a physical PE
				return false;
			}
			totalRequestedMips += mips;
		}

		List<Double> mipsShareAllocated = new ArrayList<Double>();
		for (Double mipsRequested : mipsShareRequested) {
			if (getVmsMigratingIn().contains(vmUid)) {
				mipsRequested *= 0.9; // performance degradation due to migration = 10% MIPS
			}
			mipsShareAllocated.add(mipsRequested);
		}

		if (getAvailableMips() >= totalRequestedMips) {
			getMipsMap().put(vmUid, mipsShareAllocated);
			setAvailableMips(getAvailableMips() - totalRequestedMips);
		} else {
			int pesSkipped = 0;
			for (List<Double> mipsMap : getMipsMap().values()) {
				for (int i = 0; i < mipsMap.size(); i++) {
					if (mipsMap.get(i) == 0) {
						pesSkipped++;
						continue;
					}
				}
			}

			double shortage = (totalRequestedMips - getAvailableMips()) / (getPesInUse() - pesSkipped);

			getMipsMap().put(vmUid, mipsShareAllocated);
			setAvailableMips(0);

			double additionalShortage = 0;
			do {
				additionalShortage = 0;
				for (List<Double> mipsMap : getMipsMap().values()) {
					for (int i = 0; i < mipsMap.size(); i++) {
						if (mipsMap.get(i) == 0) {
							continue;
						}
						if (mipsMap.get(i) >= shortage) {
							mipsMap.set(i, mipsMap.get(i) - shortage);
						} else {
							additionalShortage += shortage - mipsMap.get(i);
							mipsMap.set(i, 0.0);
						}
						if (mipsMap.get(i) == 0) {
							pesSkipped++;
						}
					}
				}
				shortage = additionalShortage / (getPesInUse() - pesSkipped);
			} while (additionalShortage > 0);
		}*/

		double totalRequestedMips = 0;

		// if the requested mips is bigger than the capacity of a single PE, we cap
		// the request to the PE's capacity
		List<Double> mipsShareRequestedCapped = new ArrayList<Double>();
		double peMips = getPeCapacity();
		for (Double mips : mipsShareRequested) {
			if (mips > peMips) {
				mipsShareRequestedCapped.add(peMips);
				totalRequestedMips += peMips;
			} else {
				mipsShareRequestedCapped.add(mips);
				totalRequestedMips += mips;
			}
		}

		getMipsMapRequested().put(vmUid, mipsShareRequested);
		setPesInUse(getPesInUse() + mipsShareRequested.size());

		if (getVmsMigratingIn().contains(vmUid)) {
			// the destination host only experience 10% of the migrating VM's MIPS
			totalRequestedMips *= 0.1;
		}

		if (getAvailableMips() >= totalRequestedMips) {
			List<Double> mipsShareAllocated = new ArrayList<Double>();
			for (Double mipsRequested : mipsShareRequestedCapped) {
				if (getVmsMigratingOut().contains(vmUid)) {
					// performance degradation due to migration = 10% MIPS
					mipsRequested *= 0.9;
				} else if (getVmsMigratingIn().contains(vmUid)) {
					// the destination host only experience 10% of the migrating VM's MIPS
					mipsRequested *= 0.1;
				}
				mipsShareAllocated.add(mipsRequested);
			}

			getMipsMap().put(vmUid, mipsShareAllocated);
			setAvailableMips(getAvailableMips() - totalRequestedMips);
		} else {
			redistributeMipsDueToOverSubscription();
		}

		return true;
	}

	protected void redistributeMipsDueToOverSubscription() {
		// First, we calculate the scaling factor - the MIPS allocation for all VMs will be scaled
		// proportionally
		double totalRequiredMipsByAllVms = 0;

		Map<String, List<Double>> mipsMapCapped = new HashMap<String, List<Double>>();
		for (Map.Entry<String, List<Double>> entry : getMipsMapRequested().entrySet()) {

			double requiredMipsByThisVm = 0.0;
			String vmId = entry.getKey();
			List<Double> mipsShareRequested = entry.getValue();
			List<Double> mipsShareRequestedCapped = new ArrayList<Double>();
			double peMips = getPeCapacity();
			for (Double mips : mipsShareRequested) {
				if (mips > peMips) {
					mipsShareRequestedCapped.add(peMips);
					requiredMipsByThisVm += peMips;
				} else {
					mipsShareRequestedCapped.add(mips);
					requiredMipsByThisVm += mips;
				}
			}

			mipsMapCapped.put(vmId, mipsShareRequestedCapped);

			if (getVmsMigratingIn().contains(entry.getKey())) {
				// the destination host only experience 10% of the migrating VM's MIPS
				requiredMipsByThisVm *= 0.1;
			}
			totalRequiredMipsByAllVms += requiredMipsByThisVm;
		}

		double totalAvailableMips = PeList.getTotalMips(getPeList());
		double scalingFactor = totalAvailableMips / totalRequiredMipsByAllVms;

		// Clear the old MIPS allocation
		getMipsMap().clear();

		// Update the actual MIPS allocated to the VMs
		for (Map.Entry<String, List<Double>> entry : mipsMapCapped.entrySet()) {
			String vmUid = entry.getKey();
			List<Double> requestedMips = entry.getValue();

			List<Double> updatedMipsAllocation = new ArrayList<Double>();
			for (Double mips : requestedMips) {
				if (getVmsMigratingOut().contains(vmUid)) {
					// the original amount is scaled
					mips *= scalingFactor;
					// performance degradation due to migration = 10% MIPS
					mips *= 0.9;
				} else if (getVmsMigratingIn().contains(vmUid)) {
					// the destination host only experiences 10% of the migrating VM's MIPS
					mips *= 0.1;
					// the final 10% of the requested MIPS are scaled
					mips *= scalingFactor;
				} else {
					mips *= scalingFactor;
				}

				updatedMipsAllocation.add(Math.floor(mips));
			}

			// add in the new map
			getMipsMap().put(vmUid, updatedMipsAllocation);

		}

		// As the host is oversubscribed, there no more available MIPS
		setAvailableMips(0);
	}

	/**
	 * Update allocation of VMs on PEs.
	 * @too The method is too long and may be refactored to make clearer its
	 * responsibility.
	 */
	protected void updatePeProvisioning() {
		/*getPeMap().clear();
		for (Pe pe : getPeList()) {
			pe.getPeProvisioner().deallocateMipsForAllVms();
		}
		Iterator<Pe> peIterator = getPeList().iterator();
		Pe pe = peIterator.next();
		PeProvisioner peProvisioner = pe.getPeProvisioner();
		double availableMips = peProvisioner.getAvailableMips();

		for (Map.Entry<String, List<Double>> entry : getMipsMap().entrySet()) {
			String vmUid = entry.getKey();
			getPeMap().put(vmUid, new LinkedList<Pe>());

			for (double mips : entry.getValue()) {
				while (mips >= 0.1) {
					if (availableMips >= mips) {
						peProvisioner.allocateMipsForVm(vmUid, mips);
						getPeMap().get(vmUid).add(pe);
						availableMips -= mips;
						break;
					} else {
						peProvisioner.allocateMipsForVm(vmUid, availableMips);
						getPeMap().get(vmUid).add(pe);
						mips -= availableMips;
						if (mips <= 0.1) {
							break;
						}
						if (!peIterator.hasNext()) {
							//break;
							Log.printConcatLine("There is no enough MIPS (", mips, ") to accommodate VM ", vmUid);
							//System.exit(0);

						}
						pe = peIterator.next();
						peProvisioner = pe.getPeProvisioner();
						availableMips = peProvisioner.getAvailableMips();
					}
				}
			}
		}*/

		Iterator<Pe> peIterator  = getPeList().iterator();
		Pe pe = peIterator.next();
		PeProvisioner peProvisioner = pe.getPeProvisioner();
		peProvisioner.deallocateMipsForAllVms();
		double availableMips = peProvisioner.getAvailableMips();
		for (Map.Entry<String, List<Double>> entry : getMipsMap().entrySet()) {
			String vmUid = entry.getKey();
			for (double mips : entry.getValue()) {
				if (availableMips >= mips) {
					peProvisioner.allocateMipsForVm(vmUid, mips);
					availableMips -= mips;
				} else {
					while (mips >= 0) {
						peProvisioner.allocateMipsForVm(vmUid, availableMips);
						mips -= availableMips;
						if (mips <= 0.1) {
							mips = 0;
							break;
						}
						if (!peIterator.hasNext()) {
							Log.printLine("There is no enough MIPS (" + mips + ") to accommodate VM " + vmUid);
						}
						pe = peIterator.next();
						peProvisioner = pe.getPeProvisioner();
						peProvisioner.deallocateMipsForAllVms();
						availableMips = peProvisioner.getAvailableMips();
					}
				}
			}
		}
	}




	@Override
	public void deallocatePesForVm(Vm vm) {
		getMipsMapRequested().remove(vm.getUid());
		setPesInUse(0);
		getMipsMap().clear();
		setAvailableMips(PeList.getTotalMips(getPeList()));

		for (Pe pe : getPeList()) {
			pe.getPeProvisioner().deallocateMipsForVm(vm);
		}

		for (Map.Entry<String, List<Double>> entry : getMipsMapRequested().entrySet()) {
			allocatePesForVm(entry.getKey(), entry.getValue());
		}
		updatePeProvisioning();
	}

	/**
	 * Releases PEs allocated to all the VMs.
	 *
	 * @pre $none
	 * @post $none
	 */
	@Override
	public void deallocatePesForAllVms() {
		super.deallocatePesForAllVms();
		getMipsMapRequested().clear();
		setPesInUse(0);
	}

	/**
	 * Returns maximum available MIPS among all the PEs. For the time shared policy it is just all
	 * the avaiable MIPS.
	 *
	 * @return max mips
	 */
	@Override
	public double getMaxAvailableMips() {
		return getAvailableMips();
	}

	/**
	 * Sets the number of PEs in use.
	 *
	 * @param pesInUse the new pes in use
	 */
	protected void setPesInUse(int pesInUse) {
		this.pesInUse = pesInUse;
	}

	/**
	 * Gets the number of PEs in use.
	 *
	 * @return the pes in use
	 */
	protected int getPesInUse() {
		return pesInUse;
	}

	/**
	 * Gets the mips map requested.
	 *
	 * @return the mips map requested
	 */
	protected Map<String, List<Double>> getMipsMapRequested() {
		return mipsMapRequested;
	}

	/**
	 * Sets the mips map requested.
	 *
	 * @param mipsMapRequested the mips map requested
	 */
	protected void setMipsMapRequested(Map<String, List<Double>> mipsMapRequested) {
		this.mipsMapRequested = mipsMapRequested;
	}
}
