I came across a problem which got me confused. I have a class:

class Order{
   private long customerId;
   private long uniqueId;
}

Now lets say we have total 9 Order objects for 3 customers. Three orders per customer. All these objects are in a list.

I need to sort this list using a Comparator such that the list contains the largest unique id for each customer id first. Then the second largest unique id for each customer id and so on.

Example Final List:

1. order( customerId:1 , uniqueId:87)
2. order( customerId:2 , uniqueId:22)
3. order( customerId:3 , uniqueId:57)
4. order( customerId:1 , uniqueId:66)
5. order( customerId:2 , uniqueId:-4)
6. order( customerId:3 , uniqueId:41)
7. order( customerId:1 , uniqueId:10)
8. order( customerId:2 , uniqueId:-11)
9. order( customerId:3 , uniqueId:10)

How do I implement this in the 'int compare(o1, o2)' method to sort the list as per the requirement?

Is there another better way to achieve this?

CodePudding user response：

A single compare method is probably not the right thing to use here. The information within a single Order is not sufficient to determine its relative ordering. What you'd have to do in compare is:

• get all Orders with the same client ID and sort those in descending order by their Order IDs
• do the same thing for the other Order
• compare the ranks, or if they are the same, the client ID itself

And you'd have to repeat this for each pair of Orders that are compared.

Instead, You should make this a multi-stage process:

• first, split the Orders by client ID, e.g. using Collector.groupingBy
• sort each those batches individually by Order-ID
• use two nested loops to merge those together by taking the first Order for the first customer, the first of the second, etc.; make sure to handle the case of different customers having different numbers of Orders

Alternatively, instead of the final merge step, which is probably the most tricky part of the above, you could combine the first and second approach:

• group orders by customer, sort them, store "rank" of each order in a map
• sort all Orders using compare function, comparing those ranks (and customer ID as tie-breaker)

Here's some Java code for the last (mixed) approach. Not very pretty; haven't done Java in a while and could not find a nice way for the second step.

// group by CustomerId
Map<Long, List<Order>> byCustomer = orders.stream()
        .collect(Collectors.groupingBy(Order::getCustomerId));

// build Map of Ranks per CustomerId
Map<Order, Integer> ranks = new HashMap<>();
for (List<Order> group : byCustomer.values()) {
    group.sort(Comparator.comparing(Order::getUniqueId).reversed());
    for (int i = 0; i < group.size(); i  ) {
        ranks.put(group.get(i), i);
    }
}

// sort by Rank, then by CustomerId
List<Order> orderedOrders = orders.stream()
        .sorted(Comparator.comparing((Order o) -> ranks.get(o))
                .thenComparing(Order::getCustomerId))
        .collect(Collectors.toList());

CodePudding user response：

This will do the work using Guava and its TreeMultimap

    import com.google.common.collect.Ordering;
    import com.google.common.collect.TreeMultimap;

    import java.util.*;
    [...]
    List<Order> orders = new ArrayList<>();
    Order o1 = new Order(1, 87);
    Order o2 = new Order(2, 22);
    Order o3 = new Order(3, 57);
    Order o4 = new Order(1, 66);
    Order o5 = new Order(2, 4);
    Order o6 = new Order(3, 41);
    Order o7 = new Order(1, 10);
    Order o8 = new Order(2, 11);
    Order o9 = new Order(3, 10);
    orders.add(o1);
    orders.add(o2);
    orders.add(o3);
    orders.add(o4);
    orders.add(o5);
    orders.add(o6);
    orders.add(o7);
    orders.add(o8);
    orders.add(o9);

    // Use a treemap to order automatically uniqueId and customer
    // Map[customId => list of uniqueId ordered...]
    TreeMultimap<Long, Long> treeMap = TreeMultimap.create(Ordering.natural(), Ordering.natural());
    orders.forEach(order -> treeMap.put(order.getCustomerId(), order.getUniqueId()));

    System.out.println(treeMap); 
    // output {1=[10, 66, 87], 2=[4, 11, 22], 3=[10, 41, 57]}

    // Will be used to know when all Orders are sorted
    boolean allCleared = false;

    // The result list
    List<Order> ordersOrdered = new ArrayList<>();

    while (!allCleared) {
        for (Long customerId : treeMap.keySet()) {
            SortedSet<Long> uniqueIds = treeMap.get(customerId);
            // We retrieve the Order to sort and we add it to the ordered list
            orders.stream()
                    .filter(order -> order.getCustomerId() == customerId && order.getUniqueId() == uniqueIds.last())
                    .findFirst()
                    .ifPresent(ordersOrdered::add);
        }

        // Once an Order has been sorted, we remove it from the map
        ordersOrdered.forEach(order -> treeMap.remove(order.getCustomerId(), order.getUniqueId()));

        // As long as we have Order to sort, we continue
        allCleared = treeMap.asMap().size() == 0;
    }

    System.out.println(ordersOrdered);
    // [Order{customerId=1, uniqueId=87},
    // Order{customerId=2, uniqueId=22},
    // Order{customerId=3, uniqueId=57},
    // Order{customerId=1, uniqueId=66},
    // Order{customerId=2, uniqueId=11},
    // Order{customerId=3, uniqueId=41},
    // Order{customerId=1, uniqueId=10},
    // Order{customerId=2, uniqueId=4},
    // Order{customerId=3, uniqueId=10}]

Note If you can't use Treemultimap, you can replace it with a classic Map<Long, List<Long>> sortedMap = new TreeMap<>(Long::compare) and sort the differents lists with list.sort(Long::compareTo);.

CodePudding user response：

Well, here is what I came up with. I did it in two stages.

• first create a TreeMap<Long,List<Order>> where the lists are sorted in descending order based on the uniqueID.
• Then iterate over the map values and pull out the same location of each List element. First 1, then 2, ...

A record was used to simplify the example.

record Order(long getCustomerId, long getUniqueId) {
    @Override
    public String toString() {
        return String.format("Cid = %s, Uid = %s", getCustomerId,
                getUniqueId);
    }
}

The data and a shuffle to ensure randomization. Additional values were added to create different numbers of orders for each CustomerId

List<Order> orders = new ArrayList<>(List.of(new Order(1, 87),
        new Order(2, 22), new Order(3, 57), new Order(1, 66),
        new Order(2, -11), new Order(3, 98), new Order(2, -4),
        new Order(3, 41), new Order(1, 10), new Order(2, -14),
        new Order(3, 10)));

Collections.shuffle(orders);

Now the map creation

• sort in reversed order, the Unique Id
• as the groupingBy is performed each list will be built in encountered order, preserving the sorted lists. Since this is a TreeMap each list will be in proper order relative to the keys.

Map<Long, List<Order>> map = orders.stream()
        .sorted(Comparator.comparing(Order::getUniqueId)
                .reversed())
        .collect(Collectors.groupingBy(Order::getCustomerId,
                TreeMap::new,
                Collectors.toList()));

Now the final list creation

• first iterate an index starting at 0. This is for each list
• The keys are no longer important so all that is needed are the values(i.e List<Order>)
• As each index is iterated, the Order entry from each list is mapped to a stream and subsequently a new list.
• Since the number of orders for each CustomerId may be different, the size is checked against the index to filter out the shorter lists. Otherwise an IndexOutOfBounds exception would be thrown.
• the new list is then checked for size via takeWhile. If it is empty, then all elements have been processed. All of these lists are then flatMapped to a single returned List<Order> in the required order.

List<Order> result = Stream.iterate(0, i -> i   1)
        .map(i -> map.values().stream()
                .filter(lst -> lst.size() > i)
                .map(lst -> lst.get(i)).toList())
        .takeWhile(lst -> lst.size() > 0)
        .flatMap(List::stream).toList();

result.forEach(System.out::println);

prints

Cid = 1, Uid = 87
Cid = 2, Uid = 22
Cid = 3, Uid = 98
Cid = 1, Uid = 66
Cid = 2, Uid = -4
Cid = 3, Uid = 57
Cid = 1, Uid = 10
Cid = 2, Uid = -11
Cid = 3, Uid = 41
Cid = 2, Uid = -14
Cid = 3, Uid = 10