package org.fusesource.fabric.agent.sort;


import org.apache.felix.bundlerepository.Capability;
import org.apache.felix.bundlerepository.Requirement;
import org.apache.felix.bundlerepository.Resource;

import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class RequirementSort  {

	/**
	 * Sorts {@link Resource} based on their {@link Requirement}s and {@link Capability}s.
	 * @param resources
	 * @return
	 */
	public Collection<Resource> sort(Collection<Resource> resources) {
		Set<Resource> sorted = new LinkedHashSet<Resource>();
		Set<Resource> visited = new LinkedHashSet<Resource>();
		for (Resource r : resources) {
			visit(r, resources, visited, sorted);
		}
		return sorted;
	}

    public TreeMap<Integer, Collection<Resource>> classify(Collection<Resource> resources) {
        TreeMap<Integer, Collection<Resource>> result = new TreeMap<Integer, Collection<Resource>>();
        Collection<Resource> sorted = sort(resources);

        for (Resource r : sorted) {
            int level = findLevel(result, r);
            if (!result.containsKey(level)) {
                List<Resource> list = new LinkedList<Resource>();
                list.add(r);
                result.put(level, list);
            } else {
                result.get(level).add(r);
            }
        }
        return result;
    }

    private int findLevel(Map<Integer, Collection<Resource>> resourceLevels, Resource resource) {
        int result = 0;
        for (Map.Entry<Integer, Collection<Resource>> entry : resourceLevels.entrySet()) {
            int level = entry.getKey();
            Collection<Resource> resources = entry.getValue();
            //Find the dependencies of the resource on the current level.
            Collection<Resource> dependencies = collectDependencies(resource, resources);
            if (!dependencies.isEmpty() && result <= level) {
                result = level + 1;
            }
        }
        return result;
    }

	private void visit(Resource resource, Collection<Resource> resources, Set<Resource> visited, Set<Resource> sorted) {
		if (visited.contains(resource)) {
			return;
		}
		visited.add(resource);
		for (Resource r : collectDependencies(resource, resources)) {
			visit(r, resources, visited, sorted);
		}
		sorted.add(resource);
	}

	/**
	 * Finds the dependencies of the current resource.
	 * @param resource
	 * @param allResources
	 * @return
	 */
	private Set<Resource> collectDependencies(Resource resource, Collection<Resource> allResources) {
		Set<Resource> result = new LinkedHashSet<Resource>();
		Requirement[] requirements = resource.getRequirements();
		for (Requirement requirement : requirements) {
			boolean isSatisfied = false;
			for (Resource r : result) {
				for (Capability capability : r.getCapabilities()) {
					if (requirement.isSatisfied(capability)) {
						isSatisfied = true;
						break;
					}
				}
			}

			for (Resource r : allResources) {
				if (!isSatisfied) {
					for (Capability capability : r.getCapabilities()) {
						if (requirement.isSatisfied(capability)) {
							result.add(r);
							break;
						}
					}
				}
			}
		}
		return result;
	}
}