code: /**
   * <copyright>
   * Copyright (c) 2010-2014 Henshin developers. 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
   * </copyright>
   */
  package org.eclipse.emf.henshin.interpreter.impl;
  
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.Collections;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.LinkedHashMap;
  import java.util.LinkedHashSet;
  import java.util.List;
  import java.util.Map;
  import java.util.Set;
  
  import org.eclipse.emf.common.util.EList;
  import org.eclipse.emf.ecore.EClass;
  import org.eclipse.emf.ecore.EClassifier;
  import org.eclipse.emf.ecore.EObject;
  import org.eclipse.emf.ecore.EPackage;
  import org.eclipse.emf.ecore.EReference;
  import org.eclipse.emf.ecore.EcorePackage;
  import org.eclipse.emf.ecore.resource.Resource;
  import org.eclipse.emf.ecore.util.ECrossReferenceAdapter;
  import org.eclipse.emf.ecore.util.EcoreUtil;
  import org.eclipse.emf.ecore.util.EcoreUtil.Copier;
  import org.eclipse.emf.henshin.interpreter.EGraph;
  import org.eclipse.emf.henshin.interpreter.util.EcoreCopier;
  import org.eclipse.emf.henshin.interpreter.util.InterpreterUtil;
  
  /**
   * Default {@link EGraph} implementation. Based on linked hash sets.
   */
  public class EGraphImpl extends LinkedHashSet<EObject> implements EGraph {
  	
  	/**
  	 * Generated serial ID.
  	 */
  	private static final long serialVersionUID = -1917534761444871093L;
  
  	/**
  	 * All involved EPackages.
  	 */
  	protected final Set<EPackage> packages;
  	
  	/**
  	 * Mappings from each type to all its instances.
  	 */
  	protected final Map<EClass, List<EObject>> domainMap;
  	
  	/**
  	 * Mappings from each type to all its extending subtypes.
  	 */
  	protected final Map<EClass, Set<EClass>> inheritanceMap;
  	
  	/**
  	 * Cross reference adapter for determining cross references between registered objects.
  	 */
  	protected final ECrossReferenceAdapter crossReferenceAdapter;
  	
  	/**
  	 * Default constructor.
  	 */
  	public EGraphImpl() {
  		this(32);
  	}
  	
  	/**
  	 * Constructor.
  	 * @param initialCapacity Initial capacity of the graph.
  	 */
  	public EGraphImpl(int initialCapacity) {
  		super(initialCapacity);
  		packages = new LinkedHashSet<EPackage>();
  		domainMap = new LinkedHashMap<EClass, List<EObject>>();
  		inheritanceMap = new LinkedHashMap<EClass, Set<EClass>>();
  		crossReferenceAdapter = new ECrossReferenceAdapter();
  	}
  
  	/**
  	 * Convenience constructor. Adds an object and all reachable objects to this graph. 
  	 * @param object An object.
  	 */
  	public EGraphImpl(EObject object) {
  		this();
  		initializeContents(Collections.singleton(object));
  	}
  
  	/**
  	 * Convenience constructor. Adds a collection of objects and all reachable objects to this graph.
  	 * @param collection A collection of objects.
  	 */
  	public EGraphImpl(Collection<? extends EObject> collection) {
  		this();
  		initializeContents(collection);
  	}
  
  	/**
  	 * Convenience constructor. Adds the contents of a resource and all reachable objects to this graph.
  	 * @param resource A resource.
  	 */
  	public EGraphImpl(Resource resource) {
  		this();
  		initializeContents(resource.getContents());
  	}
  	
  	/**
  	 * Initialize this EGraph.
  	 * @param collection Collection of objects to be added.
  	 */
  	protected void initializeContents(Collection<? extends EObject> collection) {
  		// First add the collection as a normal tree:
  		for (EObject object : collection) {
  			if (!contains(object)) { // omit tree traversal if possible
  				addTree(object);
  			}
  		}
  		// And now again as a graph:
  		addGraph(collection);
  	}
  
  	/*
  	 * (non-Javadoc)
  	 * @see java.util.HashSet#add(java.lang.Object)
  	 */
  	@Override
  	public final boolean add(EObject object) {
  		boolean added = super.add(object);
  		if (added) {
  			didAdd(object);
  		}
  		return added;
  	}
  	
  	/**
  	 * Notify that an object has been added to the graph.
  	 * @param object Added object.
  	 */
  	protected void didAdd(EObject object) {
  		object.eAdapters().add(crossReferenceAdapter);
  		EClass type = object.eClass();
  		getDomain(type).add(object);
  		addEPackage(type.getEPackage());
  	}
  	
  	/*
  	 * (non-Javadoc)
  	 * @see java.util.HashSet#remove(java.lang.Object)
  	 */
  	@Override
  	public final boolean remove(Object object) {
  		boolean removed = super.remove(object);
  		if (removed && object instanceof EObject) {
  			didRemove((EObject) object);
  		}
  		return removed;
  	}
  
  	/**
  	 * Notify that an object has been removed from the graph.
  	 * @param object Removed object.
  	 */
  	protected void didRemove(EObject object) {
  		object.eAdapters().remove(crossReferenceAdapter);
  		domainMap.get(object.eClass()).remove(object);
  	}
  	
  	/*
  	 * (non-Javadoc)
  	 * @see org.eclipse.emf.henshin.interpreter.EGraph#addTree(org.eclipse.emf.ecore.EObject)
  	 */
  	@Override
  	public boolean addTree(EObject root) {
  		boolean changed = add(root);
  		for (Iterator<EObject> it = root.eAllContents(); it.hasNext();) {
  			if (add(it.next())) changed = true;
  		}
  		return changed;
  	}
  	
  	/*
  	 * (non-Javadoc)
  	 * @see org.eclipse.emf.henshin.interpreter.EGraph#removeTree(org.eclipse.emf.ecore.EObject)
  	 */
  	@Override
  	public boolean removeTree(EObject root) {
  		boolean changed = remove(root);
  		for (final Iterator<EObject> it = root.eAllContents(); it.hasNext();) {
  			if (remove(it.next())) changed = true;
  		}
  		return changed;
  	}
  
  	/*
  	 * (non-Javadoc)
  	 * @see org.eclipse.emf.henshin.interpreter.EGraph#addGraph(org.eclipse.emf.ecore.EObject)
  	 */
  	@Override
  	public boolean addGraph(EObject object) {
  		return addAll(computeTransitiveClosure(object));
  	}
  	
  	/*
  	 * (non-Javadoc)
  	 * @see org.eclipse.emf.henshin.interpreter.EGraph#removeGraph(org.eclipse.emf.ecore.EObject)
  	 */
  	@Override
  	public boolean removeGraph(EObject object) {
  		return removeAll(computeTransitiveClosure(object));
  	}
  
  	/*
  	 * Add a graph. Internal helper.
  	 */
  	private void addGraph(Collection<? extends EObject> collection) {
  		Set<EObject> visited = new HashSet<EObject>();
  		for (EObject object : collection) {
  			if (!visited.contains(object)) { // omit computing the transitive closure if possible
  				Set<EObject> closure = computeTransitiveClosure(object);
  				addAll(closure);
  				visited.addAll(closure);
  			}
  		}
  	}
  
  	/**
  	 * Compute the transitive closure of referenced {@link EObject}s.
  	 * It is implemented iteratively to prevent stack overflows.
  	 * @param start The start object.
  	 * @return Set of transitively reachable objects.
  	 */
  	private Set<EObject> computeTransitiveClosure(EObject start) {
  		
  		// Initialize:
  		Set<EObject> result = new LinkedHashSet<EObject>();
  		Set<EObject> newObjects = new LinkedHashSet<EObject>();
  		newObjects.add(start);
  		
  		// Loop:
  		while (!newObjects.isEmpty()) {
  			result.addAll(newObjects);
  			// Compute references:
  			Set<EObject> referencedObjects = new LinkedHashSet<EObject>();
  			for (EObject object : newObjects) {
  				for (EReference ref : object.eClass().getEAllReferences()) {
  					if (ref.isMany()) {
  						@SuppressWarnings("unchecked")
  						EList<EObject> targets = (EList<EObject>) object.eGet(ref);
  						referencedObjects.addAll(targets);
  					} else {
  						EObject target = (EObject) object.eGet(ref);
  						if (target!=null) {
  							referencedObjects.add(target);
  						}
  					}
  				}
  			}
  			
  			// Check which of them are new:
  			newObjects.clear();
  			for (EObject object : referencedObjects) {
  				if (!result.contains(object)) {
  					newObjects.add(object);
  				}
  			}
  		}
  		
  		// Finished.
  		return result;
  		
  	}
  	
  	/*
  	 * (non-Javadoc)
  	 * @see java.util.AbstractCollection#addAll(java.util.Collection)
  	 */
  	@Override
  	public boolean addAll(Collection<? extends EObject> objs) {
  		boolean changed = false;
  		for (EObject object : objs) {
  			if (add(object)) changed = true;
  		}
  		return changed;
  	}
  
  	/*
  	 * (non-Javadoc)
  	 * @see java.util.AbstractSet#removeAll(java.util.Collection)
  	 */
  	@Override
  	public boolean removeAll(Collection<?> objs) {
  		boolean changed = false;
  		for (Object object : objs) {
  			if (remove(object)) changed = true;
  		}
  		return changed;
  	}
  	
  	/*
  	 * (non-Javadoc)
  	 * @see java.util.HashSet#clear()
  	 */
  	@Override
  	public void clear() {
  		for (EObject object : this) {
  			object.eAdapters().remove(crossReferenceAdapter);
  		}
  		super.clear();
  		packages.clear();
  		domainMap.clear();
  		inheritanceMap.clear();
  	}
  	
  	/**
  	 * Add an {@link EPackage}. Update the internal inheritance map.
  	 * @param ePackage {@link EPackage} to be added.
  	 * @return <code>true</code> if it is new.
  	 */
  	protected boolean addEPackage(EPackage ePackage) {
  		boolean added = packages.add(ePackage);
  		if (added) {
  			for (EClassifier classifier : ePackage.getEClassifiers()) {
  				if (classifier instanceof EClass) {
  					EClass type = (EClass) classifier;
  					addChildParentRelation(type, type);
  					for (EClass parent : type.getEAllSuperTypes()) {
  						addChildParentRelation(type, parent);
  					}
  				}
  			}
  		}
  		return added;
  	}
  	
  	/**
  	 * Update the inheritance map. Add a child-parent relationship.
  	 * @param child Child class.
  	 * @param parent Parent class.
  	 */
  	protected void addChildParentRelation(EClass child, EClass parent) {
  		Set<EClass> children = inheritanceMap.get(parent);
  		if (children == null) {
  			children = new LinkedHashSet<EClass>();
  			inheritanceMap.put(parent, children);
  		}
  		children.add(child);
  	}
  
  	/*
  	 * (non-Javadoc)
  	 * @see org.eclipse.emf.henshin.interpreter.EGraph#getDomain(org.eclipse.emf.ecore.EClass, boolean)
  	 */
  	@Override
  	public List<EObject> getDomain(EClass type, boolean strict) {
  		if (strict) {
  			return new ArrayList<EObject>(getDomain(type));
  		}
  		List<EObject> domain = new ArrayList<EObject>();
  		Set<EClass> inhMap = inheritanceMap.get(type);
  		if (inhMap != null) {
  			for (EClass child : inhMap) {
  				domain.addAll(getDomain(child));
  			}
  		}
  		return domain;
  	}
  	
  	/*
  	 * (non-Javadoc)
  	 * @see org.eclipse.emf.henshin.interpreter.EGraph#getDomainSize(org.eclipse.emf.ecore.EClass, boolean)
  	 */
  	@Override
  	public int getDomainSize(EClass type, boolean strict) {
  		if (strict) {
  			return getDomain(type).size();
  		}
  		Set<EClass> inhMap = inheritanceMap.get(type);
  		int size = 0;
  		if (inhMap != null) {
  			for (EClass child : inhMap) {
  				size += getDomain(child).size();
  			}
  		}
  		return size;
  	}
  
  	/*
  	 * Get the domain for a given type.
  	 */
  	protected Collection<EObject> getDomain(EClass type) {
  		List<EObject> domain = domainMap.get(type);
  		if (domain == null) {
  			domain = new ArrayList<EObject>();
  			domainMap.put(type, domain);
  		}
  		return domain;
  	}
  
  	/*
  	 * (non-Javadoc)
  	 * @see org.eclipse.emf.henshin.interpreter.EGraph#getCrossReferenceAdapter()
  	 */
  	@Override
  	public ECrossReferenceAdapter getCrossReferenceAdapter() {
  		return crossReferenceAdapter;
  	}
  
  	/*
  	 * (non-Javadoc)
  	 * @see org.eclipse.emf.henshin.interpreter.EGraph#copy(java.util.Map)
  	 */
  	@Override
  	public EGraph copy(Map<EObject, EObject> copies) {
  		if (copies==null) {
  			Copier copier = null;
  			if (packages.contains(EcorePackage.eINSTANCE)) {
  				copier = new EcoreCopier();
  			} else {
  				copier = new Copier();
  			}
  			copier.copyAll(getRoots());
  			copier.copyReferences();
  			copies = copier;
  		}
  		EGraph copy = new EGraphImpl(size());
  		for (EObject object : this) {
  			copy.add(copies.get(object));
  		}
  		return copy;
  	}
  
  	/*
  	 * (non-Javadoc)
  	 * @see org.eclipse.emf.henshin.interpreter.EGraph#getRoots()
  	 */
  	@Override
  	public List<EObject> getRoots() {
  		Set<EObject> roots = new LinkedHashSet<EObject>();
  		for (EObject object : this) {
  			roots.add(EcoreUtil.getRootContainer(object));
  		}
  		return new ArrayList<EObject>(roots);
  	}
  
  	/*
  	 * (non-Javadoc)
  	 * @see java.util.AbstractCollection#toString()
  	 */
  	@Override
  	public String toString() {
  		return getClass().getSimpleName() + "@" + Integer.toHexString(hashCode()) + 
  				" (nodes: " + size() + ", edges: " + InterpreterUtil.countEdges(this)+")";
  	}
  	
  }