core/org.eclipse.stem.core/src/org/eclipse/stem/core/graph/impl/SimpleGraphPartitionerImpl.java

package org.eclipse.stem.core.graph.impl;

/******************************************************************************* 
 * Copyright (c) 2011 IBM Corporation and others. 
 * All rights reserved. This program and the accompanying materials 
 * are made available under the terms of the Eclipse Public License v1.0 
 * which accompanies this distribution, and is available at 
 * http://www.eclipse.org/legal/epl-v10.html 
 * 
 * Contributors: 
 *     IBM Corporation - initial API and implementation 
 *******************************************************************************/

import java.util.HashMap;
import java.util.Map;
import java.util.NavigableSet;
import java.util.TreeSet;

import org.eclipse.emf.common.util.BasicEList;
import org.eclipse.emf.common.util.EList;
import org.eclipse.emf.ecore.EClass;
import org.eclipse.stem.core.common.Identifiable;
import org.eclipse.stem.core.graph.DynamicLabel;
import org.eclipse.stem.core.graph.GraphPackage;
import org.eclipse.stem.core.graph.SimpleGraphPartitioner;
import org.eclipse.stem.core.model.Decorator;

/**
 * <!-- begin-user-doc -->
 * An implementation of the model object '<em><b>Simple Graph Partitioner</b></em>'.
 * <!-- end-user-doc -->
 * <p>
 * </p>
 *
 * @generated
 */
public class SimpleGraphPartitionerImpl extends GraphPartitionerImpl implements SimpleGraphPartitioner {
	/**
	 * <!-- begin-user-doc -->
	 * <!-- end-user-doc -->
	 * @generated
	 */
	protected SimpleGraphPartitionerImpl() {
		super();
	}

	protected Map<Decorator, Map<Integer, EList<DynamicLabel>>> labelPartitionMap = new HashMap<Decorator, Map<Integer, EList<DynamicLabel>>>();
	
	
	/**
	 * <!-- begin-user-doc -->
	 * <!-- end-user-doc -->
	 * @generated
	 */
	@Override
	protected EClass eStaticClass() {
		return GraphPackage.Literals.SIMPLE_GRAPH_PARTITIONER;
	}
	
	/**
	 * Override to clear map
	 */
	@Override
	public void setNumProcesses(int newNumProcesses) {
		if(getNumProcesses() != newNumProcesses) 
			labelPartitionMap.clear();
		super.setNumProcesses(newNumProcesses);
	}
	
	/**
	 * Simply divide the labels the decorator is updating equally among the 
	 * processes alphabetically by the node URI. The method is synchronized
	 * since the labelPartitionMap is shared among the threads, but most of the times
	 * the method will return right away using the already cached results so performance
	 * is not a concern.
	 */
	@SuppressWarnings("boxing")
	@Override
	public EList<DynamicLabel> partitionDecoratorLabels(Decorator decorator, int processRank) {
		synchronized(labelPartitionMap) {
			if(labelPartitionMap != null && labelPartitionMap.containsKey(decorator)  &&
					labelPartitionMap.get(decorator).containsKey(processRank)) {
				EList<DynamicLabel> res = labelPartitionMap.get(decorator).get(processRank);
				return res;
			}

			EList<DynamicLabel> temp = new BasicEList<DynamicLabel>(); 

			// Find the node and partition the labels according to their node.

			// TreeSet guarantees O(log(n)) add/contains
			TreeSet<String>nodeURIs = new TreeSet<String>();
			for(DynamicLabel lab:decorator.getLabelsToUpdate()) {
				String uri = lab.getIdentifiable().getURI().toString();
				if(!nodeURIs.contains(uri)) nodeURIs.add(uri);
			}

			int size = nodeURIs.size();
			if(processRank == 0 || size > 1) { // If size is 1 and processRank is 0 the single node gets assigned to the first CPU.
				int nodesPerPartition = size / getNumProcesses();
				int start =  processRank*nodesPerPartition;
				int end;
				if(processRank == getNumProcesses() -1) end = size; // The last threads grabs all nodes until the last one
				else end = start + nodesPerPartition;
				String first=nodeURIs.first();
				for(int i=0;i<start;++i) first = nodeURIs.higher(first);
				String last = first;
				for(int i=start;i<end-1;++i)	last = nodeURIs.higher(last);

				NavigableSet<String>processURIs =  nodeURIs.subSet(first, true, last, true);

				for(DynamicLabel dl:decorator.getLabelsToUpdate()) {
					if(processURIs.contains(dl.getIdentifiable().getURI().toString())) {
						temp.add(dl);
					} 
				}
			}

			Map<Integer, EList<DynamicLabel>> partitionMap = null;

			if(labelPartitionMap.containsKey(decorator))
				partitionMap = labelPartitionMap.get(decorator);
			else {
				partitionMap = new HashMap<Integer, EList<DynamicLabel>>();
				labelPartitionMap.put(decorator, partitionMap);
			}

			partitionMap.put(processRank, temp);
			long timeAfter = System.currentTimeMillis();
			return temp;
		}
	}
	
	/**
	 * Same as above but return all labels handled by this decorator
	 */
	@Override
	public EList<DynamicLabel> partitionDecoratorLabels(Decorator decorator) {
		return decorator.getLabelsToUpdate();
	}
	
	/**
	 * Everything is managed by this running STEM instance
	 */
	@Override
	public boolean isManaged(Identifiable identifiable) {
		return true;
	}

} //SimpleGraphPartitionerImpl