How to sort a list when certain values must appear later than others, potentially ignoring sort order for such items that need 'delaying' [duplicate]

Question

Problem

I have the requirement to sort a list by a certain property of each object in that list. This is a standard action supported in most languages.

However, there is additional requirement that certain items may depend on others, and as such, must not appear in the sorted list until items they depend on have appeared first, even if this requires going against the normal sort order. Any such item that is 'blocked', should appear in the list the moment the items 'blocking' it have been added to the output list.

An Example

If I have items:

[{'a',6},{'b',1},{'c',5},{'d',15},{'e',12},{'f',20},{'g',14},{'h',7}]

Sorting these normally by the numeric value will get:

[{'b',1},{'c',5},{'a',6},{'h',7},{'e',12},{'g',14},{'d',15},{'f',20}]

However, if the following constraints are enforced:

• a depends on e
• g depends on d
• c depends on b

Then this result is invalid. Instead, the result should be:

[{'b',1},{'c',5},{'h',7},{'e',12},{'a',6},{'d',15},{'g',14},{'f',20}]

Where b, c, d, e, f and h have been sorted in correct order b, c, h, e, d and f; both a and g got delayed until e and d respectively had been output; and c did not need delaying, as the value it depended on, b, had already been output.

What I have already tried

Initially I investigated if this was possible using basic Java comparators, where the comparator implementation was something like:

private Map<MyObject,Set<MyObject>> dependencies; // parent to set of children

public int compare(MyObj x, MyObj y) {
   if (dependencies.get(x).contains(y)) {
      return 1;
   } else if (dependencies.get(y).contains(x)) {
      return -1;
   } else if (x.getValue() < y.getValue()) {
     return -1;
   } else if (x.getValue() > y.getValue()) {
     return 1;
   } else {
     return 0;
   }
}

However this breaks the requirement of Java comparators of being transitive. Taken from the java documentation:

((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

However, in the above example

• a(6) < h(7) : true
• h(7) < e(12) : true
• a(6) < e(12) : false

Instead, I have come up with the below code, which while works, seems massively over-sized and over-complex for what seems like a simple problem. (Note: This is a slightly cut down version of the class. It can also be viewed and run at https://ideone.com/XrhSeA)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public final class ListManager<ValueType extends Comparable<ValueType>> {
    private static final class ParentChildrenWrapper<ValueType> {
        private final ValueType parent;
        private final Set<ValueType> childrenByReference;

        public ParentChildrenWrapper(ValueType parent, Set<ValueType> childrenByReference) {
            this.parent = parent;
            this.childrenByReference = childrenByReference;
        }

        public ValueType getParent() {
            return this.parent;
        }

        public Set<ValueType> getChildrenByReference() {
            return this.childrenByReference;
        }
    }

    private static final class QueuedItem<ValueType> implements Comparable<QueuedItem<ValueType>> {
        private final ValueType item;
        private final int index;

        public QueuedItem(ValueType item, int index) {
            this.item = item;
            this.index = index;
        }

        public ValueType getItem() {
            return this.item;
        }

        public int getIndex() {
            return this.index;
        }

        @Override
        public int compareTo(QueuedItem<ValueType> other) {
            if (this.index < other.index) {
                return -1;
            } else if (this.index > other.index) {
                return 1;
            } else {
                return 0;
            }
        }
    }

    private final Set<ValueType> unsortedItems;
    private final Map<ValueType, Set<ValueType>> dependentsOfParents;

    public ListManager() {
        this.unsortedItems = new HashSet<>();
        this.dependentsOfParents = new HashMap<>();
    }

    public void addItem(ValueType value) {
        this.unsortedItems.add(value);
    }

    public final void registerDependency(ValueType parent, ValueType child) {
        if (!this.unsortedItems.contains(parent)) {
            throw new IllegalArgumentException("Unrecognized parent");
        } else if (!this.unsortedItems.contains(child)) {
            throw new IllegalArgumentException("Unrecognized child");
        } else if (Objects.equals(parent,child)) {
            throw new IllegalArgumentException("Parent and child are the same");
        } else {
            this.dependentsOfParents.computeIfAbsent(parent, __ -> new HashSet<>()).add(child);
        }
    }

    public List<ValueType> createSortedList() {
        // Create a copy of dependentsOfParents where the sets of children can be modified without impacting the original.
        // These sets will representing the set of children for each parent that are yet to be dealt with, and such sets will shrink as more items are processed.
        Map<ValueType, Set<ValueType>> blockingDependentsOfParents = new HashMap<>(this.dependentsOfParents.size());
        for (Map.Entry<ValueType, Set<ValueType>> parentEntry : this.dependentsOfParents.entrySet()) {
            Set<ValueType> childrenOfParent = parentEntry.getValue();
            if (childrenOfParent != null && !childrenOfParent.isEmpty()) {
                blockingDependentsOfParents.put(parentEntry.getKey(), new HashSet<>(childrenOfParent));
            }
        }

        // Compute a list of which children impact which parents, alongside the set of children belonging to each parent.
        // This will allow a child to remove itself from all of it's parents' lists of blocking children.
        Map<ValueType,List<ParentChildrenWrapper<ValueType>>> childImpacts = new HashMap<>();
        for (Map.Entry<ValueType, Set<ValueType>> entry : blockingDependentsOfParents.entrySet()) {
            ValueType parent = entry.getKey();
            Set<ValueType> childrenForParent = entry.getValue();
            ParentChildrenWrapper<ValueType> childrenForParentWrapped = new ParentChildrenWrapper<>(parent,childrenForParent);
            for (ValueType child : childrenForParent) {
                childImpacts.computeIfAbsent(child, __ -> new LinkedList<>()).add(childrenForParentWrapped);
            }
        }

        // If there are no relationships, the remaining code can be massively optimised.
        boolean hasNoRelationships = blockingDependentsOfParents.isEmpty();

        // Create a pre-sorted stream of items.
        Stream<ValueType> rankedItemStream = this.unsortedItems.stream().sorted();
        List<ValueType> outputList;
        if (hasNoRelationships) {
            // There are no relationships, and as such, the stream is already in a perfectly fine order.
            outputList = rankedItemStream.collect(Collectors.toList());
        } else {
            Iterator<ValueType> rankedIterator = rankedItemStream.iterator();

            int queueIndex = 0;
            outputList = new ArrayList<>(this.unsortedItems.size());

            // A collection of items that have been visited but are blocked by children, stored in map form for easy deletion.
            Map<ValueType,QueuedItem<ValueType>> lockedItems = new HashMap<>();
            // A list of items that have been freed from their blocking children, but have yet to be processed, ordered by order originally encountered.
            PriorityQueue<QueuedItem<ValueType>> freedItems = new PriorityQueue<>();

            while (true) {
                // Grab the earliest-seen item which was once locked but has now been freed. Otherwise, grab the next unseen item.
                ValueType item;
                boolean mustBeUnblocked;
                QueuedItem<ValueType> queuedItem = freedItems.poll();
                if (queuedItem == null) {
                    if (rankedIterator.hasNext()) {
                        item = rankedIterator.next();
                        mustBeUnblocked = false;
                    } else {
                        break;
                    }
                } else {
                    item = queuedItem.getItem();
                    mustBeUnblocked = true;
                }

                // See if this item has any children that are blocking it from being added to the output list.
                Set<ValueType> childrenWaitingUpon = blockingDependentsOfParents.get(item);
                if (childrenWaitingUpon == null || childrenWaitingUpon.isEmpty()) {
                    // There are no children blocking this item, so start removing it from all blocking lists.

                    // Get a list of all parents that is item was blocking, if there are any.
                    List<ParentChildrenWrapper<ValueType>> childImpact = childImpacts.get(item);
                    if (childImpact != null) {
                        // Iterate over all those parents
                        ListIterator<ParentChildrenWrapper<ValueType>> childImpactIterator = childImpact.listIterator();
                        while (childImpactIterator.hasNext()) {
                            // Remove this item from that parent's blocking children.
                            ParentChildrenWrapper<ValueType> wrappedParentImpactedByChild = childImpactIterator.next();
                            Set<ValueType> childrenOfParentImpactedByChild = wrappedParentImpactedByChild.getChildrenByReference();
                            childrenOfParentImpactedByChild.remove(item);

                            // Does this parent no longer have any children blocking it?
                            if (childrenOfParentImpactedByChild.isEmpty()) {
                                // Remove it from the children impacts map, to prevent unnecessary processing of a now empty set in future iterations.
                                childImpactIterator.remove();

                                // If this parent was locked, mark it as now freed.
                                QueuedItem<ValueType> freedQueuedItem = lockedItems.remove(wrappedParentImpactedByChild.getParent());
                                if (freedQueuedItem != null) {
                                    freedItems.add(freedQueuedItem);
                                }
                            }
                        }
                        // If there are no longer any parents at all being blocked by this child, remove it from the map.
                        if (childImpact.isEmpty()) {
                            childImpacts.remove(item);
                        }
                    }
                    outputList.add(item);
                } else if (mustBeUnblocked) {
                    throw new IllegalStateException("Freed item is still blocked. This should not happen.");
                } else {
                    // Mark the item as locked.
                    lockedItems.put(item,new QueuedItem<>(item,queueIndex++));
                }
            }

            // Check that all items were processed successfully. Given there is only one path that will add an item to to the output list without an exception, we can just compare sizes.
            if (outputList.size() != this.unsortedItems.size()) {
                throw new IllegalStateException("Could not complete ordering. Are there recursive chains of items?");
            }
        }
        return outputList;
    }
}

My question

Is there an already existing algorithm, or an algorithm significantly shorter than the above, that will allow this to be done?

While the language I am developing in is Java, and the code above is in Java, language-independent answers that I could implement in Java are also fine.

Answer 1

This is called topological sorting. You can model "blocking" as edges of a directed graph. This should work if there are no circular "blockings".

Answer 2

I've done this in <100 lines of c# code (with comments). This implementation seems a little complicated.

Here is the outline of the algorithm

1. Create a priority queue that is keyed by value that you want to sort by
2. Insert all the items that do not have any "blocking" connections incoming
3. While there are elements in the queue:
   1. Take an element of the queue. Put it in your resulting list.
   2. If there are any elements that were being directly blocked by this element and were not visited previously, put them into the queue (an element can have more than one blocking element, so you check for that)

A list of unprocessed elements should be empty at the end, or you had a cycle in your dependencies.

This is essentialy Topological sort with built in priority for nodes. Keep in mind that the result can be quite suprising depending on the number of connections in your graph (ex. it's possible to actually get elements that are in reverse order).