Is it possible to join two Java 8 streams?

Question

I was wondering if I can join two pre-sorted streams (in a single pass). For example, if I have the following Java classes:

public class Person { // constructor & getters ommitted
  private String name;
  private int salary;
  private List<Car> cars;
  public void addCar(Car c) { cars.add(c); }
}

public class Car { // constructor & getters ommitted
  private String owner;
  private String brand;
}

And I have pre-sorted streams, as in:

Stream<Person> clients = Arrays.asList(
  new Person("Anne", 500), 
  new Person("Johnny", 340)
  ).stream();

Stream<Car> cars = Arrays.asList(
  new Car("Johnny", "Mazda"), 
  new Car("Johnny", "Fiat"), 
  new Car("Mary", "Volvo")
  ).stream();

I wanted to apply addCar() to Johnny with the "Mazda" and "Fiat". There's no car for Anne, and Mary is not a client.

Is it possible to join both streams with a single pass on the streams?

I've seen solutions where one stream is walked multiple times, but since they are pre-ordered, I guess there could be a chance of doing it in one pass.

EDIT: The expected result of the operation would be to call addCar() twice for "Johnny": once with the "Mazda", once with the "Fiat".

@Naman The expected result is to call `addCar()` on each client, according to the existing data. I edited the question to clarify this. Thanks. — Joe DiNottra, Mar 19 '20 at 18:26
Related: https://stackoverflow.com/questions/17640754/zipping-streams-using-jdk8-with-lambda-java-util-stream-streams-zip — Kayaman, Mar 19 '20 at 18:30
streams are not appropriate data structures for this task. Arrange clients as HashMap. — Alexei Kaigorodov, Mar 19 '20 at 18:49
@AlexeiKaigorodov I was wondering about that. I was hoping to make good use of the pre-sorted characteristic of both streams, but maybe it's not possible. Thanks. — Joe DiNottra, Mar 19 '20 at 18:55
Note: you can write `Stream.of(...)` instead of `Arrays.asList(...).stream()`. — IlyaMuravjov, Mar 19 '20 at 19:08

score 3 · Answer 1 · answered Mar 19 '20 at 19:03

3

I am afraid it's not possible to efficiently solve this task using Stream API. But you can still do it using iterators.

public static void addCars(Stream<Person> clients, Stream<Car> cars) {
    Iterator<Person> clientsIt = clients.iterator();
    Iterator<Car> carsIt = cars.iterator();
    Person client = null;
    while (carsIt.hasNext()) {
        Car car = carsIt.next();
        while (client == null || !client.getName().equals(car.getOwner())) {
            if(!clientsIt.hasNext()) return;
            client = clientsIt.next();
        }
        client.addCar(car);
    }
}

answered Mar 19 '20 at 19:03

IlyaMuravjov

2,352
1
9
27

I was afraid it wasn't possible. Thanks. +1 – Joe DiNottra Mar 19 '20 at 19:59
@Naman The complexity is `O(cars + clients)`. The outer loop is executed at most `cars.size()` times since `carsIt.next()` is called on each iteration. The inner loop is executed at most `clients.size()` times **in total** since `clientsIt.next()` is called on each iteration, and the same `clientsIt` is used every time. This is the fastest solution because it only iterates once over `cars` and once over `clients`, and no overhead is caused by using containers like `HashMap`. – IlyaMuravjov Mar 20 '20 at 16:13

Naman · Answer 2 · 2020-03-20T04:04:41.203

1

A precompute can help. Something like

Map<String, List<Car>> cars = Stream.of(
        new Car("Johnny", "Mazda"),
        new Car("Johnny", "Fiat"),
        new Car("Mary", "Volvo"))
        .collect(Collectors.groupingBy(Car::getOwner));

Stream.of(new Person("Anne", 500),
        new Person("Johnny", 340))
        .forEachOrdered(p -> cars.getOrDefault(p.getName(), 
                Collections.emptyList()).forEach(p::addCar));

edited Mar 20 '20 at 04:04

answered Mar 19 '20 at 18:31

Naman

27,789
26
218
353

2

what is the complexity of your solution? O(n^2)? – Alexei Kaigorodov Mar 19 '20 at 18:49
This solution discounts the fact that both streams are already ordered. It does work, though. – Joe DiNottra Mar 19 '20 at 18:58
1

@AlexeiKaigorodov the complexity is _O(cars + clients)_ since `HashMap` performs operations in constant time. – IlyaMuravjov Mar 19 '20 at 19:00
@JoeDiNottra You can specifically mark the `Stream`s to be processed in an ordered manner if that's required. In the existing code change `forEach` to `forEachOrdered`. Made an update in the answer. – Naman Mar 20 '20 at 04:03

Is it possible to join two Java 8 streams?

2 Answers2