How to sort items on entry in Java-CodePudding

Let us say we have been given a list of letters B,F,A,G and that they are stacked upon one another and I want to print out the order in which they were stacked in. For example if I was given the information that:

A-G / F-B / A-B / A-F / G-B / G-F

where the symbol - means "is on top of" (so A is on top of G, F is on top of B, A is on top of B...) then I want to output A, G, F, B based on the given data. The problem is that this list is read line by line so after line one is read the expected output is A, G until other lines are read and the expected output is updated. My first instinct was to use stack but then I would require a lot of pop and push operations and would be a hassle because the best data structure would allow me to switch places between letters or move things around freely and trees seem to be the best option but how exactly would this be implemented?

CodePudding user response：

I would use a directed graph. There are no directed graph classes in the JDK, but there are many libraries that implement it (listed

Once your directed graph is created, and you ensure it has no cycles (for example, you did not define A-B, B-C, C-A, which creates a cycle), then sorting is a just a matter of writing a comparator with the following logic:

if o1 == o2 return 0;
if o1 is connected to o2 return -1;
if o1 is not connected to o2 return 1;

CodePudding user response：

You can use the pairs to construct a comparator like this:

Set<List<String>> pairs = Arrays.stream(order.split(" / "))
        .map(p -> p.split("-"))
        .map(Arrays::asList)
        .collect(Collectors.toSet());

Comparator<String> compare = (a, b) ->
        pairs.contains(Arrays.asList(a, b)) ? -1 :
        pairs.contains(Arrays.asList(b, a)) ? 1 :
        0;

Then use that to sort your input in whatever structure you want.

Ideone Demo