Sorting a list of tuplets linked with each other

Question

I want to ask a question about sorting in Java, to be precise i need to sort a list of tuples (that are defined as a custom class) but that are linked like a tree to each other.

Basically this is a list of document ids that express the relation parent-child, and are organized as sets (possibly unordered). The tuples are already filtered to have unique left / right elements, so that the tree has unique links between documents (they are not allowed to have multiple leafs).

Using example data, i have this kind of list: [(1,2), (3,4), (0,1), (2,3)], this represents the following tree:

0
|_ 1
   |_ 2
      |_ 3
         |_ 4

Hence i need the list to be ordered as follow: [(0,1), (1,2), (2,3), (3,4)].

I also add that it's possible that the parent document id is greater than the child one, so a simple sorting based on which id is greater is not possible.

I tried using the .sorted() method of the Stream class, after making the custom class comparable and adding the following code:

    @Override
    public int compareTo(DocumentIdVersionsStack o) {
        if (parentDocumentId == o.getChildDocumentId()) return  1;
        if (childDocumentId == o.getParentDocumentId()) return  -1;
        return 0;
    }

Basically telling it to invert the order if the current one is child of the other tuple and vice versa, but the list is still not what i expect it to be.

Any idea on how to do this using streams? I didn't want to use complex sortings methods that require recursion, just to keep the code cleaner, but if it can't be done otherwise i'll check that.

Thank you!

EDIT: I'll add a couple of informations:

The tuples are already contiguous, there won't be 'holes' of missing ids
The recursion (last id = first id) is again taken care before passing the tuples to the sorting method
There will be a tuple with the left value not found in any of the right values -> this will be the first element after the sort
There will be a tuple with the right value not found in any of the left values -> this will be the last element after sort
All left and right values are unique, they are just linked as explained before (left1 = right2 and so on)

user_7804477 · Answer

You have mentioned that the tuples are unique. So the compareTo method will not work as it deals with "equal" elements as well, which is not applicable to a unique list. In the current compareTo code, the tuples (1,2) and (3,4) would be treated as equals which is why it is not returning expected results. Also since parent id could be greater than child id, you cannot clearly say if (1,2) is greater or less than (3,4). The order could be (1,2), (2,3), (3,4) or (3,4), (4,1), (1,2). Hence without knowing the details of other nodes, it might not be possible to do it using compareTo.

I would suggest an approach to keep a map of these tuples with the parent id as the key, then find the root node and start traversing from root:

Map map = list.stream()//
                .collect(Collectors.toMap(DocumentIdVersionsStack::getParentId,
                                          Function.identity()));

Set child = list.stream()
                         .map(DocumentIdVersionsStack::getChildId)
                         .collect(Collectors.toSet());


// Get the root node
DocumentIdVersionsStack node = list.stream()
                                   .filter(u -> !child.contains(u.getParentId()))
                                   .findFirst()
                                   .orElse(null);
List list2 = new ArrayList<>();
list2.add(node);
// Traverse using the map
while (map.containsKey(node.getChildId())) {
    node = map.get(node.getChildId());
    list2.add(node);
}
System.out.println(list2);

Sorting a list of tuplets linked with each other

1 Answers