package org.wovagen;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import com.webobjects.eoaccess.EOEntity;
import com.webobjects.eoaccess.EOModel;
import com.webobjects.eoaccess.EOModelGroup;
import com.webobjects.eoaccess.EORelationship;
import com.webobjects.foundation.NSArray;


public final class DependencyAnalizer{
	
	private DependencyAnalizer(){}
	
	
	public static List<EOEntity> sortedEntities() 
		throws CircularDependencyEx{
		
		EOModelGroup mg = EOModelGroup.defaultGroup();
		
		//	get all entities in the model group
		List<EOEntity> entities = new LinkedList<EOEntity>();
		
		NSArray models = mg.models();
		for(int i = 0, c = models.count() ; i < c ; i++){
			NSArray modelEntities = ((EOModel)models.objectAtIndex(i)).entities();
			for(int j = 0, c2 = modelEntities.count() ; j < c2 ; j++)
				entities.add((EOEntity)modelEntities.objectAtIndex(j));
		}
		
		/*
		 * Now that the dependencies are listed, we need to use them to find the
		 * optimal ordering of entities. We need to go through the list of
		 * entities add them to list that sorts them based on their
		 * dependencies.
		 */
		List<EOEntity> sortedEntites = new LinkedList<EOEntity>();
		for(EOEntity entity : entities){
			
			//	index of a dependent entity
			int highIndex = entities.size();
			//	index of an entity this entity is dependent on
			int lowIndex = -1;
			
			//	preferred stuff
			int lowIndexPreferred = -1;
			
			//	iterate through already sorted entities, looking
			//	for the best index for the current entity
			Iterator<EOEntity> it = sortedEntites.iterator();
			for(int i = 0 ; it.hasNext() ; i++){
				
				EOEntity sortedEntity = it.next();
				
				//	iterate though all the dependencies for the entity
				//	being evaluated, update index where necessary
				if(_isDependent(entity, sortedEntity, new LinkedList<EOEntity>(), false))
					lowIndex = Math.max(lowIndex, i);
				
				//	now check out the entity that is already in
				//	the sorted list, if it has a dep on this entity
				if(_isDependent(sortedEntity, entity, new LinkedList<EOEntity>(), false))
					highIndex = Math.min(highIndex, i);
					
				if(lowIndex >= highIndex)
					throw new CircularDependencyEx(entity, sortedEntity);
				
				//	do the same for preferred positions
				if(_isDependent(entity, sortedEntity, new LinkedList<EOEntity>(), true))
					lowIndexPreferred = Math.max(lowIndexPreferred, i);
			}
			
			//	take the preferred positions into account
			if(lowIndexPreferred > lowIndex && lowIndexPreferred <= highIndex)
				lowIndex = lowIndexPreferred;
			
			sortedEntites.add(lowIndex + 1, entity);
		
		}//	end of the iteration over all entities
		
		return sortedEntites;
	}
	
	private static boolean _isDependent(EOEntity e1, EOEntity e2, List<EOEntity> beenThrough, boolean obeyOptional){
		List<Dependency> deps = _dependenciesForEntity(e1);
		
		for(Dependency d : deps)
			if(d.dependence == e2 && (obeyOptional || d.mandatory))
				return true;
		
		beenThrough.add(e1);
		
		/*
		 *	Look for indirect dependencies 
		 */
		for(Dependency d : deps){
			
			if(! (obeyOptional || d.mandatory))
				continue;
			
			if(beenThrough.contains(d.dependence)) continue;
			
			//	recurse!
			if(_isDependent(d.dependence, e2, beenThrough, obeyOptional))
				return true;
		}
		
		return false;
	}

	private static List<Dependency> _dependenciesForEntity(EOEntity e){
		
		List<Dependency> rVal = new LinkedList<Dependency>();
		
		//	get the relationships
		//	and evaluate their dependencies
		NSArray relationships = e.relationships();
		for(int i = 0 , c = relationships.count() ; i < c ; i++){
			EORelationship r = (EORelationship)relationships.objectAtIndex(i);
			rVal.add(new Dependency(r.destinationEntity(), r.isMandatory()));
		}
		
		/*
		 * if this algorithm is used to analyze dependencies based on anything
		 * other then relationships, other kinds of dependencies
		 * (inheritance, prototypes etc) should be evaluated here and added
		 * to the rVal list
		 */
		
		return rVal;
	}
	
	private static class Dependency{
		
		private EOEntity dependence;
		private boolean mandatory;
		
		private Dependency(EOEntity dependence, boolean mandatory){
			this.dependence = dependence;
			this.mandatory = mandatory;
		}
	}
	
	public static class CircularDependencyEx extends Exception{
		
		private EOEntity e1, e2;
		
		private CircularDependencyEx(EOEntity e1, EOEntity e2){
			this.e1 = e1;
			this.e2 = e2;
		}
		
		public EOEntity e1(){ return e1; }
		public EOEntity e2(){ return e2; }
		
		public String getMessage(){
			return "Circular dependency between: "+e1.name()+" and: "+e2.name();
		}
	}
}