Class NodeSorting

java.lang.Object

net.fabricmc.fabric.impl.base.toposort.NodeSorting

public class NodeSorting
extends Object

Contains a topological sort implementation, with tie breaking using a Comparator.

The final order is always deterministic (i.e. doesn't change with the order of the input elements or the edges), assuming that they are all different according to the comparator. This also holds in the presence of cycles.

The steps are as follows:

1. Compute node SCCs (Strongly Connected Components, i.e. cycles).
2. Sort nodes within SCCs using the comparator.
3. Sort SCCs with respect to each other by respecting constraints, and using the comparator in case of a tie.

Field Summary

Fields

Modifier and Type	Field	Description
static boolean	ENABLE_CYCLE_WARNING

Constructor Summary

Constructors

Constructor	Description
NodeSorting()

Method Summary

Modifier and Type	Method	Description
static <N extends SortableNode<N>> boolean	sort(List<N> sortedNodes, String elementDescription, Comparator<N> comparator)	Sort a list of nodes.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

ENABLE_CYCLE_WARNING

public static boolean ENABLE_CYCLE_WARNING

Constructor Details

NodeSorting

public NodeSorting()

Method Details

sort

public static <N extends SortableNode<N>> boolean sort(List<N> sortedNodes,
 String elementDescription,
 Comparator<N> comparator)

Sort a list of nodes.

Parameters:

sortedNodes - The list of nodes to sort. Will be modified in-place.

elementDescription - A description of the elements, used for logging in the presence of cycles.

comparator - The comparator to break ties and to order elements within a cycle.

Returns:

true if all the constraints were satisfied, false if there was at least one cycle.