/*******************************************************************************
* Copyright (c)                                                                *
*           2005   Tristan Allwood,                                            *
*           2005   Daniel Burke,                                               *
*           2005   Marc Hull,                                                  *
*           2005   Ekaterina Itskova,                                          *
*           2005   Steve Zymler                                                *
*                                                                              *
* Permission is hereby granted, free of charge, to any person obtaining a      *
* copy of this software and associated documentation files (the                *
* "Software"), to deal in the Software without restriction, including          *
* without limitation the rights to use, copy, modify, merge, publish,          *
* distribute, sublicense, and/or sell copies of the Software, and to           *
* permit persons to whom the Software is furnished to do so, subject to        *
* the following conditions:                                                    *
*                                                                              *
* The above copyright notice and this permission notice shall be included      *
* in all copies or substantial portions of the Software.                       *
*                                                                              *
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS      *
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF                   *
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.       *
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY         *
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,         *
* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE            *
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                       *
*******************************************************************************/
/*
 * Created on 19-Oct-2004
 *
 * Created by Steve Zymler
 */
package uk.ac.ic.doc.kevlar.core.framework.internal.typecheck;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import uk.ac.ic.doc.kevlar.core.framework.typecheck.IInterfaceClass;
import uk.ac.ic.doc.kevlar.core.framework.typecheck.ITypeTree;
import uk.ac.ic.doc.kevlar.core.framework.typecheck.ITypeTreeNode;

/**
 * @author Steve Zymler
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class TypeTree implements ITypeTree 
{
	private ITypeTreeNode rootNode;
	
	/*
	public TypeTree(IInterfaceClass rootType)
	{
		rootNode = new TypeTreeNode( rootType );
	}*/
	
	public TypeTree( ITypeTreeNode rootNode )
	{
		this.rootNode = rootNode ;  
	}
	
    public synchronized boolean isInTree(IInterfaceClass alpha) 
    {
    	return isInTree(alpha, rootNode);
    }
    
    private synchronized boolean isInTree(IInterfaceClass alpha, ITypeTreeNode node)
    {
    	if( node.getInterfaceClass().equals(alpha) )
    	{
    		return true;
    	}
    	else
    	{
    		for( ITypeTreeNode typeNode : node.getSubNodes() )
    		{
    			if( isInTree( alpha, typeNode ) )
    			{
    				return true ;
				}    				
			}
			return false ;
		}
    }

    public synchronized IInterfaceClass getLeastUpperBound(Set<IInterfaceClass> subTypes) 
    {
        if(subTypes.size() == 0)
        {
            return null;
        }
        
        if(subTypes.size() == 1)
        {
            for(IInterfaceClass subType : subTypes)
            {
                return subType;
            }
        }
        
    	// check if all subTypes are actually in tree
        for( IInterfaceClass typeClass : subTypes )
        {
        	if( false == isInTree(typeClass) )
        	{
        		throw new IllegalArgumentException("One of subtypes is not in type tree");
        	}
        }
        
        List< Set<IInterfaceClass> >  paths = new ArrayList< Set<IInterfaceClass> >();
        for( IInterfaceClass typeClass : subTypes )
        {
        	paths.add( buildPath( typeClass ) );
        }
        
        Set<IInterfaceClass> pathIntersection = paths.get(0) ;
        for( Set path : paths )
        {
        	pathIntersection.retainAll( path );
        }
        
        IInterfaceClass leastUpperBound = rootNode.getInterfaceClass() ;
        for( IInterfaceClass typeClass : pathIntersection )
        {
        	if( isDerivedFrom(typeClass, leastUpperBound) )
        	{
        		leastUpperBound = typeClass ;
        	}
        	else
        	{
        		continue;
        	}        	
        }
        
        return leastUpperBound ;                                        
    }
    
    private synchronized Set<IInterfaceClass> buildPath( IInterfaceClass subType )
	{
    	Set<IInterfaceClass> superTypes = new HashSet<IInterfaceClass>();
    	ITypeTree subTree = getSubTree(subType);
		ITypeTreeNode subNode = subTree.getRootNode();
    	
    	// start with subtype and walk up the tree
    	ITypeTreeNode superNode = subNode ; 
    	
    	while( null != superNode )
    	{
    		superTypes.add( superNode.getInterfaceClass() );
    		superNode = superNode.getSuperNode() ;
    	}
    	
    	return superTypes ;
	}
   
	public synchronized ITypeTree getSubTree(IInterfaceClass rootType) 
	{
		if( false == isInTree(rootType) ) 
		{
			throw new IllegalArgumentException();
		}
		else
		{
			return getSubTree( rootType, rootNode );
		}		
	}
	
	private synchronized ITypeTree getSubTree( IInterfaceClass root, ITypeTreeNode node )
	{
    	if( node.getInterfaceClass().equals(root) )
    	{
    		return new TypeTree( node );
    	}
    	else
    	{
    		for( ITypeTreeNode typeNode : node.getSubNodes() )
    		{
    			ITypeTree subTree ;
    			if( null != ( subTree = getSubTree( root, typeNode )))
    			{
    				return subTree ;
				}    				
			}
			return null ;
		}		
	}

	public synchronized ITypeTreeNode getRootNode() 
	{
		return rootNode;
	}
	
	public synchronized boolean isDerivedFrom(IInterfaceClass typeClassA, 
								   IInterfaceClass typeClassB) 
	{
		ITypeTree subTree = getSubTree( typeClassB );
		return subTree.isInTree( typeClassA );		
	}		
}
