SortingTraversalStrategy

import com.google.common.collect.HashMultimap;
import com.google.common.collect.SetMultimap;
import com.tinkerpop.gremlin.process.TraversalStrategy;

import java.util.*;

/**
 * @author Matthias Broecheler (me@matthiasb.com)
 */
public interface SortingTraversalStrategy extends TraversalStrategy {


    public default Set<Class<? extends TraversalStrategy>> beforeStrategies() {
        return Collections.EMPTY_SET;
    }

    public default Set<Class<? extends TraversalStrategy>> afterStrategies() {
        return Collections.EMPTY_SET;
    }

    public static void sortStrategies(List<? extends TraversalStrategy> strategies) {
        final SetMultimap<Class<? extends TraversalStrategy>,Class<? extends TraversalStrategy>> dependencyMap = HashMultimap.create();
        Set<Class<? extends TraversalStrategy>> strategyClass = new HashSet<>(strategies.size());
        //Initialize data structure
        strategies.forEach(s -> strategyClass.add(s.getClass()));

        //Initialize all the dependencies
        strategies.forEach( strategy -> {
            if (strategy instanceof SortingTraversalStrategy) {
                SortingTraversalStrategy sts = (SortingTraversalStrategy)strategy;
                sts.beforeStrategies().forEach(s -> { if (strategyClass.contains(s)) dependencyMap.put(sts.getClass(),s); } );
                sts.afterStrategies().forEach(s -> { if (strategyClass.contains(s)) dependencyMap.put(s,sts.getClass()); } );
            }
        });
        //Now, compute transitive closure until convergence
        boolean updated = false;
        do {
            for (Class<? extends TraversalStrategy> sc : strategyClass) {
                List<Class<? extends TraversalStrategy>> toAdd = null;
                for (Class<? extends TraversalStrategy> before : dependencyMap.get(sc)) {
                    Set<Class<? extends TraversalStrategy>> beforeDep = dependencyMap.get(before);
                    if (!beforeDep.isEmpty()) {
                        if (toAdd==null) toAdd = new ArrayList<>(beforeDep.size());
                        toAdd.addAll(beforeDep);
                    }
                }
                if (toAdd!=null && dependencyMap.putAll(sc, toAdd)) updated=true;
            }
        } while (updated);

        Collections.sort(strategies, new Comparator<TraversalStrategy>() {
            @Override
            public int compare(TraversalStrategy s1, TraversalStrategy s2) {
                boolean s1Before = dependencyMap.containsEntry(s1.getClass(),s2.getClass());
                boolean s2Before = dependencyMap.containsEntry(s2.getClass(),s1.getClass());
                if (s1Before && s2Before) throw new IllegalStateException("Cyclic dependency between traversal strategies: ["
                        + s1.getClass().getName() + ", " + s2.getClass().getName() + "]");
                if (s1Before) return -1;
                else if (s2Before) return 1;
                else return 0;
            }
        });
    }

}