package de.fhdw.wtf.walker.tasks;
   
   import java.util.Collections;
   import java.util.Iterator;
   import java.util.LinkedList;
   import java.util.List;
   
   import de.fhdw.wtf.common.ast.Attribute;
   import de.fhdw.wtf.common.ast.ConstructorOrOperation;
  import de.fhdw.wtf.common.ast.Group;
  import de.fhdw.wtf.common.ast.Model;
  import de.fhdw.wtf.common.ast.type.ClassType;
  import de.fhdw.wtf.common.ast.type.Type;
  import de.fhdw.wtf.common.exception.walker.TaskException;
  import de.fhdw.wtf.common.task.TaskExecutor;
  import de.fhdw.wtf.walker.walker.SimpleWalkerTask;
  
  /**
   * Analyzes the inheritance trees of the given model. Enriches the model with useful information regarding necessary
   * constructor calls.
   */
  public final class AnalyzeInheritanceTreesTask extends SimpleWalkerTask {
  	
  	/**
  	 * Used to identify the type Anything.
  	 */
  	private static final String ANYTHING = "Anything";
  	
  	/**
  	 * Returns a new instance of {@link AnalyzeInheritanceTreesTask}.
  	 * 
  	 * @param model
  	 *            The model to perform this task on.
  	 * @param taskmanager
  	 *            The executor which performs this task.
  	 * @return a new instance of {@link AnalyzeInheritanceTreesTask}
  	 */
  	public static AnalyzeInheritanceTreesTask create(final Model model, final TaskExecutor taskmanager) {
  		return new AnalyzeInheritanceTreesTask(model, taskmanager);
  	}
  	
  	/**
  	 * Instantiates a new instance of {@link AnalyzeInheritanceTreesTask}.
  	 * 
  	 * @param model
  	 *            The model to perform this task on.
  	 * @param taskmanager
  	 *            The executor which performs this task.
  	 */
  	private AnalyzeInheritanceTreesTask(final Model model, final TaskExecutor taskmanager) {
  		super(model, taskmanager);
  	}
  	
  	/**
  	 * Helper class which represents one path along the inheritance-hierarchy of a root class.
  	 */
  	private class InheritancePath {
  		/**
  		 * Types ordered along this InheritancePath.
  		 */
  		private final List<Type> pathElements;
  		
  		/**
  		 * Constructs an empty InheritancePath.
  		 */
  		private InheritancePath() {
  			this.pathElements = new LinkedList<>();
  		}
  		
  		/**
  		 * Constructs an InheritancePath with first as its root.
  		 * 
  		 * @param first
  		 *            the first element of this path.
  		 */
  		InheritancePath(final Type first) {
  			this();
  			this.addElement(first);
  		}
  		
  		/**
  		 * Constructs an InheritancePath with firsts as its path elements.
  		 * 
  		 * @param firsts
  		 *            the path elements for this.
  		 */
  		InheritancePath(final List<Type> firsts) {
  			this();
  			this.addElements(firsts);
  		}
  		
  		/**
  		 * Constructs an InheritancePath which is identical to firsts.
  		 * 
  		 * @param firsts
  		 *            the path to copy.
  		 */
  		InheritancePath(final InheritancePath firsts) {
  			this(firsts.pathElements);
 		}
 		
 		/**
 		 * Adds element to the end of this path.
 		 * 
 		 * @param element
 		 *            the new end of this path.
 		 */
 		void addElement(final Type element) {
 			this.pathElements.add(element);
 		}
 		
 		/**
 		 * Adds elements to this path so that these elements remain in the order provided in elements.
 		 * 
 		 * @param elements
 		 *            the elements added to this.
 		 */
 		void addElements(final List<Type> elements) {
 			this.pathElements.addAll(elements);
 		}
 		
 		/**
 		 * Returns true if element is also an element of this. False otherwise.
 		 * 
 		 * @param element
 		 *            to check.
 		 * @return true if element is part of this. False otherwise.
 		 */
 		boolean contains(final Type element) {
 			return this.pathElements.contains(element);
 		}
 		
 		/**
 		 * Returns all elements that this and other have in common. The common elements will be provided the order
 		 * provided by this.
 		 * 
 		 * @param other
 		 *            the path to intersect with.
 		 * @return common elements in the order of their existence in this path.
 		 */
 		InheritancePath intersect(final InheritancePath other) {
 			final InheritancePath result = new InheritancePath();
 			final Iterator<Type> myElements = this.pathElements.iterator();
 			while (myElements.hasNext()) {
 				final Type myElement = myElements.next();
 				if (other.contains(myElement)) {
 					result.addElement(myElement);
 				}
 			}
 			return result;
 		}
 		
 		/**
 		 * Makes one step in the inheritance-tree. Alternative paths will be returned.
 		 * 
 		 * @return alternative paths if any exist. An empty llist otherwise.
 		 */
 		List<InheritancePath> step() {
 			final List<InheritancePath> alternativePaths = new LinkedList<>();
 			final Type lastElement = this.pathElements.get(this.pathElements.size() - 1);
 			final Iterator<Type> followers = lastElement.getSuperTypes().iterator();
 			if (followers.hasNext()) {
 				final Type firstFollower = followers.next();
 				while (followers.hasNext()) {
 					final Type follower = followers.next();
 					if (!follower.toString().equals(ANYTHING)) {
 						final InheritancePath alternativePath = new InheritancePath(this);
 						alternativePath.addElement(follower);
 						alternativePaths.add(alternativePath);
 					}
 				}
 				if (!firstFollower.toString().equals(ANYTHING)) {
 					this.addElement(firstFollower);
 				}
 			}
 			return alternativePaths;
 		}
 		
 		/**
 		 * Calculates all inheritance paths reachable from the end of this path and returns them.
 		 * 
 		 * @return a list with all paths reachable from the last element of this.
 		 */
 		List<InheritancePath> run() {
 			final List<InheritancePath> result = new LinkedList<>();
 			final List<InheritancePath> preResult = new LinkedList<>();
 			int oldSize = this.pathElements.size();
 			List<InheritancePath> alternativePaths = this.step();
 			while (this.pathElements.size() != oldSize || !alternativePaths.isEmpty()) {
 				preResult.addAll(alternativePaths);
 				oldSize = this.pathElements.size();
 				alternativePaths = this.step();
 			}
 			final Iterator<InheritancePath> paths = preResult.iterator();
 			result.add(this);
 			while (paths.hasNext()) {
 				result.addAll(paths.next().run());
 			}
 			return result;
 		}
 		
 		@Override
 		public String toString() {
 			return this.pathElements.toString();
 		}
 		
 		@Override
 		public boolean equals(final Object o) {
 			if (o instanceof InheritancePath) {
 				final InheritancePath oAsInheritancePath = (InheritancePath) o;
 				return this.pathElements.equals(oAsInheritancePath.pathElements);
 			}
 			return false;
 		}
 		
 		@Override
 		public int hashCode() {
 			return this.pathElements.hashCode();
 		}
 		
 		/**
 		 * 
 		 * @return true if this path is empty.
 		 */
 		boolean isEmpty() {
 			return this.pathElements.isEmpty();
 		}
 		
 		/**
 		 * removes top from this path if top is the top of this path.
 		 * 
 		 * @param top
 		 *            the top to remove.
 		 * 
 		 */
 		void removeTop(final Type top) {
 			final int highestIndex = this.pathElements.size() - 1;
 			if (highestIndex >= 0 && this.pathElements.get(highestIndex).equals(top)) {
 				this.pathElements.remove(highestIndex);
 			}
 		}
 		
 	}
 	
 	@Override
 	public void handleClass(final ClassType c) throws TaskException {
 		final List<InheritancePath> allPaths = new LinkedList<>();
 		final Iterator<Type> superTypes = c.getSuperTypes().iterator();
 		while (superTypes.hasNext()) {
 			final Type currentSuperType = superTypes.next();
 			if (!currentSuperType.toString().equals(ANYTHING)) {
 				allPaths.addAll(new InheritancePath(currentSuperType).run());
 			}
 		}
 		final List<Type> definitiveResponsibilities = new LinkedList<>();
 		final List<InheritancePath> allIntersections =
 				this.gatherAllRelevantIntersections(allPaths, definitiveResponsibilities);
 		this.mapCalls(c, allIntersections, definitiveResponsibilities);
 	}
 	
 	/**
 	 * First step to get all call responsibilities. Fills definitiveResponsibilities with the value found in the first
 	 * intersection of none open ended paths where the intersection is of length 1.
 	 * 
 	 * @param allPaths
 	 *            all inheritance paths.
 	 * @param definitiveResponsibilities
 	 *            a collection with all definitive call responsibilities.
 	 * @return a list with resulting intersection.
 	 */
 	private List<InheritancePath> gatherAllRelevantIntersections(final List<InheritancePath> allPaths,
 			final List<Type> definitiveResponsibilities) {
 		if (allPaths.size() <= 1) {
 			return allPaths;
 		}
 		final List<InheritancePath> allIntersections = new LinkedList<>();
 		final List<InheritancePath> copy = new LinkedList<>();
 		copy.addAll(allPaths);
 		Collections.reverse(copy);
 		boolean firstSingleOne = true;
 		boolean firstRound = true;
 		boolean firstAllLooseEnds = true;
 		final Iterator<InheritancePath> paths = allPaths.iterator();
 		while (paths.hasNext()) {
 			final InheritancePath currentPath = paths.next();
 			final Type pathEnd = currentPath.pathElements.get(currentPath.pathElements.size() - 1);
 			final List<InheritancePath> currentIntersections = new LinkedList<>();
 			boolean commonEnd = false;
 			final Iterator<InheritancePath> copyPaths = copy.iterator();
 			while (copyPaths.hasNext()) {
 				final InheritancePath currentCopy = copyPaths.next();
 				final InheritancePath intersection = currentPath.intersect(currentCopy);
 				if (!intersection.isEmpty()) {
 					currentIntersections.add(intersection);
 				}
 				if (!currentPath.equals(currentCopy)) {
 					commonEnd =
 							commonEnd
 									|| pathEnd
 											.equals(currentCopy.pathElements.get(currentCopy.pathElements.size() - 1));
 					firstAllLooseEnds = firstAllLooseEnds && firstRound && !commonEnd;
 				}
 			}
 			if (commonEnd) {
 				if (firstSingleOne) {
 					firstSingleOne =
 							this.gatherSingleOnes(currentPath, currentIntersections, definitiveResponsibilities);
 				}
 				allIntersections.addAll(currentIntersections);
 			} else {
 				if (firstAllLooseEnds && currentPath.pathElements.size() == 1) {
 					final Type type = currentPath.pathElements.get(0);
 					if (!definitiveResponsibilities.contains(type)) {
 						definitiveResponsibilities.add(type);
 					}
 				} else {
 					allIntersections.addAll(currentIntersections);
 				}
 			}
 			firstRound = firstAllLooseEnds;
 		}
 		
 		return allIntersections;
 	}
 	
 	/**
 	 * Fills definitiveResponsibilities with the value found in the first intersection of none open ended paths where
 	 * the intersection is of length 1.
 	 * 
 	 * @param currentPath
 	 *            the current path.
 	 * @param currentIntersections
 	 *            the current intersections.
 	 * @param definitiveResponsibilities
 	 *            a list with definitive responsibilities.
 	 * @return true if definitiveResponsibilities has been changed.
 	 */
 	private boolean gatherSingleOnes(final InheritancePath currentPath,
 			final List<InheritancePath> currentIntersections,
 			final List<Type> definitiveResponsibilities) {
 		final Iterator<InheritancePath> intersections = currentIntersections.iterator();
 		final Type first = currentPath.pathElements.get(0);
 		boolean firstOne = false;
 		while (intersections.hasNext()) {
 			final InheritancePath current = intersections.next();
 			if (current.pathElements.size() == 1) {
 				final Type type = current.pathElements.get(0);
 				firstOne = !type.equals(first) && !definitiveResponsibilities.contains(type);
 				if (firstOne) {
 					definitiveResponsibilities.add(type);
 				}
 			}
 		}
 		return firstOne;
 	}
 	
 	/**
 	 * Maps c to all types it has to instantiate during runtime. Uses the map "constructorCalldependencies" in Model for
 	 * this purpose. Maps to an empty list if c has no responsibilities in the regard of instantiating super types.
 	 * 
 	 * @param c
 	 *            the root of the inheritance tree to map types from.
 	 * @param allIntersections
 	 *            The inheritance tree with c as root in form of all paths that have the direct super types of c as root
 	 *            after running gatherAllRelevantIntersections.
 	 * @param definitiveResponsibilities
 	 *            a list with definitive responsibilities.
 	 */
 	private void mapCalls(final ClassType c,
 			final List<InheritancePath> allIntersections,
 			final List<Type> definitiveResponsibilities) {
 		List<InheritancePath> copyNewIntersections = new LinkedList<>();
 		copyNewIntersections.addAll(allIntersections);
 		while (!copyNewIntersections.isEmpty()) {
 			final List<InheritancePath> newIntersections = new LinkedList<>();
 			final Iterator<InheritancePath> intersections = copyNewIntersections.iterator();
 			while (intersections.hasNext()) {
 				final InheritancePath path = intersections.next();
 				if (path.isEmpty()) {
 					intersections.remove();
 				} else if (path.pathElements.size() == 1) {
 					final Type type = path.pathElements.get(0);
 					if (!definitiveResponsibilities.contains(type)) {
 						definitiveResponsibilities.add(type);
 					}
 					final List<InheritancePath> copyList = new LinkedList<>();
 					copyList.addAll(copyNewIntersections);
 					final Iterator<InheritancePath> copy = copyList.iterator();
 					while (copy.hasNext()) {
 						copy.next().removeTop(type);
 					}
 					// intersections.remove();
 				} else {
 					final Type top = path.pathElements.get(path.pathElements.size() - 1);
 					final List<InheritancePath> copyList = new LinkedList<>();
 					copyList.addAll(copyNewIntersections);
 					final Iterator<InheritancePath> copies = copyList.iterator();
 					while (copies.hasNext()) {
 						final InheritancePath copy = copies.next();
 						final InheritancePath intersection = path.intersect(copy);
 						copy.removeTop(top);
 						if (!intersection.isEmpty()) {
 							if (intersection.pathElements.size() == 1) {
 								final Type type = path.pathElements.get(0);
 								if (!definitiveResponsibilities.contains(type)) {
 									definitiveResponsibilities.add(type);
 								}
 							} else {
 								intersection.removeTop(top);
 								newIntersections.add(intersection);
 							}
 						}
 					}
 				}
 			}
 			copyNewIntersections = new LinkedList<>();
 			copyNewIntersections.addAll(newIntersections);
 		}
 		this.getModel().putConstructorCallDependency(c, definitiveResponsibilities);
 	}
 	
 	@Override
 	public void handleGroup(final Group g) throws TaskException {
 		// Nothing to do.
 	}
 	
 	@Override
 	public void handleAttribute(final Attribute a, final ClassType owner) throws TaskException {
 		// Nothing to do.
 	}
 	
 	@Override
 	public void handleConstructorOrOperation(final ConstructorOrOperation coo, final ClassType owner)
 			throws TaskException {
 		// Nothing to do.
 	}
 	
 	@Override
 	public void finalizeTask() throws TaskException {
 		// Nothing to do.
 	}
 	
 	@Override
 	public void beginTask() throws TaskException {
 		// Nothing to do.
 	}
 	
 }