Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java Streams - Get a "symmetric difference list" from two other lists

Im trying to use Java 8 streams to combine lists. How can I get a "symmetric difference list" (all object that only exist in one list) from two existing lists. I know how to get an intersect list and also how to get a union list.

In the code below I want the disjoint Cars from the two lists of cars (bigCarList,smallCarList). I expect the result to be a list with the 2 cars ("Toyota Corolla" and "Ford Focus")

Example code:

public void testDisjointLists() {
    List<Car> bigCarList = get5DefaultCars();
    List<Car> smallCarList = get3DefaultCars();

    //Get cars that exists in both lists
    List<Car> intersect = bigCarList.stream().filter(smallCarList::contains).collect(Collectors.toList());

    //Get all cars in both list as one list
    List<Car> union = Stream.concat(bigCarList.stream(), smallCarList.stream()).distinct().collect(Collectors.toList());

    //Get all cars that only exist in one list
    //List<Car> disjoint = ???

}

public List<Car> get5DefaultCars() {
    List<Car> cars = get3DefaultCars();
    cars.add(new Car("Toyota Corolla", 2008));
    cars.add(new Car("Ford Focus", 2010));
    return cars;
}

public List<Car> get3DefaultCars() {
    List<Car> cars = new ArrayList<>();
    cars.add(new Car("Volvo V70", 1990));
    cars.add(new Car("BMW I3", 1999));
    cars.add(new Car("Audi A3", 2005));
    return cars;
}

class Car {
    private int releaseYear;
    private String name;
    public Car(String name) {
        this.name = name;
    }
    public Car(String name, int releaseYear) {
        this.name = name;
        this.releaseYear = releaseYear;
    }

    //Overridden equals() and hashCode()
}
like image 392
torbjorn_nybro Avatar asked Jun 26 '15 13:06

torbjorn_nybro


2 Answers

Based on your own code, there is a straight-forward solution:

List<Car> disjoint = Stream.concat(
    bigCarList.stream().filter(c->!smallCarList.contains(c)),
    smallCarList.stream().filter(c->!bigCarList.contains(c))
).collect(Collectors.toList());

Just filter one list for all items not contained in the other and vice versa and concatenate both results. That works fairly well for small lists and before consider optimized solutions like hashing or making the result distinct() you should ask yourself why you are using lists if you don’t want neither, duplicates nor a specific order.

It seems like you actually want Sets, not Lists. If you use Sets, Tagir Valeev’s solution is appropriate. But it is not working with the actual semantics of Lists, i.e. doesn’t work if the source lists contain duplicates.


But if you are using Sets, the code can be even simpler:

Set<Car> disjoint = Stream.concat(bigCarSet.stream(), smallCarSet.stream())
  .collect(Collectors.toMap(Function.identity(), t->true, (a,b)->null))
  .keySet();

This uses the toMap collector which creates a Map (the value is irrelevant, we simply map to true here) and uses a merge function to handle duplicates. Since for two sets, duplicates can only occur when an item is contained in both sets, these are the items we want remove.

The documentation of Collectors.toMap says that the merge function is treated “as supplied to Map.merge(Object, Object, BiFunction)” and we can learn from there, that simply mapping the duplicate pair to null will remove the entry.

So afterwards, the keySet() of the map contains the disjoint set.

like image 144
Holger Avatar answered Oct 14 '22 17:10

Holger


Something like this may work:

Stream.concat(bigCarList.stream(), smallCarList.stream())
      .collect(groupingBy(Function.identity(), counting()))
      .entrySet().stream()
      .filter(e -> e.getValue().equals(1L))
      .map(Map.Entry::getKey)
      .collect(toList());

Here we first collect all the cars to the Map<Car, Long> where value is the number of such cars encountered. After that, we filter this Map leaving only cars that are encountered exactly once, drop the counts and collect to the final List.

like image 36
Tagir Valeev Avatar answered Oct 14 '22 18:10

Tagir Valeev