# UsageGraph.java

    /*
     * Copyright 2008 Niclas Hedhman. All rights Reserved.
     *
     * Licensed  under the  Apache License,  Version 2.0  (the "License");
     * you may not use  this file  except in  compliance with the License.
     * You may obtain a copy of the License at
     *
     *   http://www.apache.org/licenses/LICENSE-2.0
     *
     * Unless required by applicable law or agreed to in writing, software
     * distributed  under the  License is distributed on an "AS IS" BASIS,
     * WITHOUT  WARRANTIES OR CONDITIONS  OF ANY KIND, either  express  or
     * implied.
     *
     * See the License for the specific language governing permissions and
     * limitations under the License.
     */
    package org.qi4j.runtime.composite;

    import java.util.Collection;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import org.qi4j.bootstrap.BindingException;

    /**
     * This class is NOT thread-safe.
     * //TODO: Algorithm need to be optimized.
     */
    public final class UsageGraph<K>
    {
        private final Collection<K> data;
        private final Use<K> use;
        private final boolean allowCyclic;
        private List<K> resolved;
        private HashMap<K, List<K>> transitive;

        public UsageGraph( Collection<K> data, Use<K> use, boolean allowCyclic )
        {
            this.data = data;
            this.use = use;
            this.allowCyclic = allowCyclic;
        }

        public boolean transitiveUse( K source, K other )
            throws BindingException
        {
            if( transitive == null )
            {
                buildUsageGraph();
            }
            return transitive.containsKey( source ) && transitive.get( source ).contains( other );
        }

        private void checkCyclic( List<K> visited, K sourceItem, K used )
            throws BindingException
        {
            Collection<K> nextLevel = use.uses( used );
            for( K next : nextLevel )
            {
                if( next == sourceItem )
                {
                    if( !allowCyclic )
                    {
                        visited.add( next );
                        throw new BindingException( "Cyclic usage detected: " + sourceItem + " -> " + visited );
                    }
                }
                if( !visited.contains( next ) )
                {
                    visited.add( next );
                    checkCyclic( visited, sourceItem, next );
                }
            }
        }

        /**
         * Must be called if the data set has been modified.
         */
        public void invalidate()
        {
            resolved = null;
            transitive = null;
        }

        public List<K> resolveOrder()
            throws BindingException
        {
            if( resolved == null )
            {
                buildUsageGraph();
                resolved = new LinkedList<K>();
                for( K item : data )
                {
                    int pos = resolved.size();
                    for( K entry : resolved )
                    {
                        if( transitiveUse( entry, item ) )
                        {
                            pos = resolved.indexOf( entry );
                            break;
                        }
                    }
                    resolved.add( pos, item );
                }
            }
            return resolved;
        }

        private void buildUsageGraph()
            throws BindingException
        {
            transitive = new HashMap<K, List<K>>();
            for( K sourceItem : data )
            {
                LinkedList<K> visited = new LinkedList<K>();
                checkCyclic( visited, sourceItem, sourceItem );
                transitive.put( sourceItem, visited );
            }
        }

        public interface Use<K>
        {

            /**
             * @param source The item to be queried.
             *
             * @return A list of items it uses.
             */
            Collection<K> uses( K source );
        }
    }