Class TopologicalSort<T>

  • Type Parameters:
    T - The type to be sorted. It must be able to be added to a HashSet

    public class TopologicalSort<T>
    extends java.lang.Object
    Topological sort a list or array.

    A Topological sort is used when you have a partial ordering expressed as dependencies between elements (also often represented as edges in a directed acyclic graph). A Topological sort should not be used when you have a total ordering expressed as a Comparator over the items. The algorithm has the additional characteristic that dependency sets are sorted by the original list order so that order is preserved when possible.

    The sort algorithm works by recursively visiting every item, once and only once. On each visit, the items dependencies are first visited and then the item is added to the sorted list. Thus the algorithm ensures that dependency items are always added before dependent items.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.Map<T,​java.util.Set<T>> _dependencies  
    • Constructor Summary

      Constructors 
      Constructor Description
      TopologicalSort()  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void addDependency​(T dependent, T dependency)
      Add a dependency to be considered in the sort.
      void sort​(java.util.Collection<T> list)
      Sort the passed list according to dependencies previously set with addDependency(Object, Object).
      void sort​(T[] array)
      Sort the passed array according to dependencies previously set with addDependency(Object, Object).
      java.lang.String toString()  
      private void visit​(T item, java.util.Set<T> visited, java.util.List<T> sorted, java.util.Comparator<T> comparator)
      Visit an item to be sorted.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Field Detail

      • _dependencies

        private final java.util.Map<T,​java.util.Set<T>> _dependencies
    • Constructor Detail

      • TopologicalSort

        public TopologicalSort()
    • Method Detail

      • addDependency

        public void addDependency​(T dependent,
                                  T dependency)
        Add a dependency to be considered in the sort.
        Parameters:
        dependent - The dependent item will be sorted after all its dependencies
        dependency - The dependency item, will be sorted before its dependent item
      • sort

        public void sort​(T[] array)
        Sort the passed array according to dependencies previously set with addDependency(Object, Object). Where possible, ordering will be preserved if no dependency
        Parameters:
        array - The array to be sorted.
      • sort

        public void sort​(java.util.Collection<T> list)
        Sort the passed list according to dependencies previously set with addDependency(Object, Object). Where possible, ordering will be preserved if no dependency
        Parameters:
        list - The list to be sorted.
      • visit

        private void visit​(T item,
                           java.util.Set<T> visited,
                           java.util.List<T> sorted,
                           java.util.Comparator<T> comparator)
        Visit an item to be sorted.
        Parameters:
        item - The item to be visited
        visited - The Set of items already visited
        sorted - The list to sort items into
        comparator - A comparator used to sort dependencies.
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object