How to sort a list when certain values must appear later than others, potentially ignoring sort order












7















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.










share|improve this question

























  • Possible duplicate of Sample Directed Graph and Topological Sort Code

    – kfx
    38 mins ago











  • @kfx While the solution to the linked question does provide example code that provides a solution to this question, I do not believe my question to be a duplicate. People searching for that question already know they want a topological sort. People who encounter this question in the future (and indeed, myself when I wrote it) do not know what they need is a topological sort.

    – Scott Dennison
    17 mins ago
















7















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.










share|improve this question

























  • Possible duplicate of Sample Directed Graph and Topological Sort Code

    – kfx
    38 mins ago











  • @kfx While the solution to the linked question does provide example code that provides a solution to this question, I do not believe my question to be a duplicate. People searching for that question already know they want a topological sort. People who encounter this question in the future (and indeed, myself when I wrote it) do not know what they need is a topological sort.

    – Scott Dennison
    17 mins ago














7












7








7








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.










share|improve this 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.







java algorithm sorting






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited 41 mins ago







Scott Dennison

















asked 45 mins ago









Scott DennisonScott Dennison

6526




6526













  • Possible duplicate of Sample Directed Graph and Topological Sort Code

    – kfx
    38 mins ago











  • @kfx While the solution to the linked question does provide example code that provides a solution to this question, I do not believe my question to be a duplicate. People searching for that question already know they want a topological sort. People who encounter this question in the future (and indeed, myself when I wrote it) do not know what they need is a topological sort.

    – Scott Dennison
    17 mins ago



















  • Possible duplicate of Sample Directed Graph and Topological Sort Code

    – kfx
    38 mins ago











  • @kfx While the solution to the linked question does provide example code that provides a solution to this question, I do not believe my question to be a duplicate. People searching for that question already know they want a topological sort. People who encounter this question in the future (and indeed, myself when I wrote it) do not know what they need is a topological sort.

    – Scott Dennison
    17 mins ago

















Possible duplicate of Sample Directed Graph and Topological Sort Code

– kfx
38 mins ago





Possible duplicate of Sample Directed Graph and Topological Sort Code

– kfx
38 mins ago













@kfx While the solution to the linked question does provide example code that provides a solution to this question, I do not believe my question to be a duplicate. People searching for that question already know they want a topological sort. People who encounter this question in the future (and indeed, myself when I wrote it) do not know what they need is a topological sort.

– Scott Dennison
17 mins ago





@kfx While the solution to the linked question does provide example code that provides a solution to this question, I do not believe my question to be a duplicate. People searching for that question already know they want a topological sort. People who encounter this question in the future (and indeed, myself when I wrote it) do not know what they need is a topological sort.

– Scott Dennison
17 mins ago












1 Answer
1






active

oldest

votes


















9














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






share|improve this answer
























  • I will look into topological sorting (something I had never heard of before today) and associated algorithms, as this sounds like exactly what I need, albeit with the caveat that I am not currently representing my items as a directed graph. In addition, I can confirm that in my use case, circular/recursive blockings are invalid. I will leave this question open for a day or so in-case there are further answers. If not, I will mark this answer as accepted.

    – Scott Dennison
    36 mins ago













Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54307968%2fhow-to-sort-a-list-when-certain-values-must-appear-later-than-others-potentiall%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









9














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






share|improve this answer
























  • I will look into topological sorting (something I had never heard of before today) and associated algorithms, as this sounds like exactly what I need, albeit with the caveat that I am not currently representing my items as a directed graph. In addition, I can confirm that in my use case, circular/recursive blockings are invalid. I will leave this question open for a day or so in-case there are further answers. If not, I will mark this answer as accepted.

    – Scott Dennison
    36 mins ago


















9














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






share|improve this answer
























  • I will look into topological sorting (something I had never heard of before today) and associated algorithms, as this sounds like exactly what I need, albeit with the caveat that I am not currently representing my items as a directed graph. In addition, I can confirm that in my use case, circular/recursive blockings are invalid. I will leave this question open for a day or so in-case there are further answers. If not, I will mark this answer as accepted.

    – Scott Dennison
    36 mins ago
















9












9








9







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






share|improve this answer













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







share|improve this answer












share|improve this answer



share|improve this answer










answered 42 mins ago









Pratik DeogharePratik Deoghare

17.6k2583135




17.6k2583135













  • I will look into topological sorting (something I had never heard of before today) and associated algorithms, as this sounds like exactly what I need, albeit with the caveat that I am not currently representing my items as a directed graph. In addition, I can confirm that in my use case, circular/recursive blockings are invalid. I will leave this question open for a day or so in-case there are further answers. If not, I will mark this answer as accepted.

    – Scott Dennison
    36 mins ago





















  • I will look into topological sorting (something I had never heard of before today) and associated algorithms, as this sounds like exactly what I need, albeit with the caveat that I am not currently representing my items as a directed graph. In addition, I can confirm that in my use case, circular/recursive blockings are invalid. I will leave this question open for a day or so in-case there are further answers. If not, I will mark this answer as accepted.

    – Scott Dennison
    36 mins ago



















I will look into topological sorting (something I had never heard of before today) and associated algorithms, as this sounds like exactly what I need, albeit with the caveat that I am not currently representing my items as a directed graph. In addition, I can confirm that in my use case, circular/recursive blockings are invalid. I will leave this question open for a day or so in-case there are further answers. If not, I will mark this answer as accepted.

– Scott Dennison
36 mins ago







I will look into topological sorting (something I had never heard of before today) and associated algorithms, as this sounds like exactly what I need, albeit with the caveat that I am not currently representing my items as a directed graph. In addition, I can confirm that in my use case, circular/recursive blockings are invalid. I will leave this question open for a day or so in-case there are further answers. If not, I will mark this answer as accepted.

– Scott Dennison
36 mins ago




















draft saved

draft discarded




















































Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54307968%2fhow-to-sort-a-list-when-certain-values-must-appear-later-than-others-potentiall%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

How to label and detect the document text images

Vallis Paradisi

Tabula Rosettana