CODEWITHSUNDEEP
algorithmlambdajava-8java-stream
Marcelo Glasberg
Marcelo Glasberg

Reputation: 30879

Use Java 8 lambdas to find a pair of objects in a list that meet a certain criteria

Given a List of objects of type A and the method boolean foo(A other); what's the best way to use Java 8 lambdas to find any pair of objects, such as a1.foo(a2) == true?

Note method foo is symmetric, meaning that a1.foo(a2) == a2.foo(a1) (like the equals).

Also, what's the best way if I only need to know any a1, and not the pair (a1, a2)?

For example:

Suppose I have a list of students, and I want to find any student with the same age of some other student in the list.

The method Person.sameAgeAs(Person other) below returns true/false, and is used to compare their age:

for (Person student1 : students) {
    for (Person student2 : students) {
        if (!student1.equals(student2)) { // If not the same student.
            if (student1.sameAgeAs(student2)) { // If they have the same age.
                return student1;
                }
            }
        }
    }

But I want to do it with lambdas:

students.stream()...

EDIT:

If method foo were not symmetric, then @srborlongan 's answer below would be perfect. Encapsulating it in a Pair class and accepting a predicate:

@NotNull
public static <I> Pair<I, I> findPair(@Nullable List<I> list, @NotNull BiPredicate<I, I> predicate) {
    if (list == null) return emptyPair();

    Optional<Pair<I,I>> item = list.parallelStream()
        .flatMap(item1 ->
            list.stream()
            .filter(item2 -> !item1.equals(item2))
            .filter(item2 -> predicate.test(item1, item2))
            .map(item2 -> new Pair<>(item1, item2))).findFirst();

    return item.orElse(emptyPair());
    }

But, as I said, foo is symmetric, and the above code is inefficient because: (i) If an answer exists some symmetric pairs may be searched before all the non-symmetric ones; (ii) and if no answer exists, i.e., student1.sameAgeAs(student2) never returns true this code will search all pairs, including the symmetric ones. To be efficient the code should only check half of the pairs (since student1.sameAgeAs(student2) == student2.sameAgeAs(student1)).

My initial for (Person ... example was not good, since it also searches all pairs. This is really what should be translated to lambdas to be efficient:

@NotNull
public static <I> Pair<I, I> findPair_Symmetric(List<I> list, BiPredicate<I, I> predicate_Symmetric) {
    if (list != null) {
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if ((i != j) && predicate_Symmetric.test(list.get(i), list.get(j))) {
                    return new Pair<>(list.get(i), list.get(j));
                    }
                }
            }
        }

    return emptyPair();
    }

Upvotes: 3

Views: 1826

Answers (1)

srborlongan
srborlongan

Reputation: 4579

//symmetric solution
@NotNull
public static <I> Pair<I, I> findPair_Symmetric(List<I> list, BiPredicate<I, I> predicate_Symmetric) {
  if (list != null) {
    // for (int i = 0; i < list.size(); i++)
    return IntStream.range(0, list.size())
      .mapToObj(
        // for (int j = i + 1; j < list.size(); j++)
        i -> IntStream.range(i + 1, list.size())
          // if (predicate_Symmetric.test(list.get(i), list.get(j))
          .filter(j -> predicate_Symmetric.test(list.get(i), list.get(j)))
          // return new Pair<>(list.get(i), list.get(j));
          .mapToObj(j -> new Pair<>(list.get(i), list.get(j)))
      )
      .flatMap(Function.identity())
      .findFirst()
      .orElseGet(() -> emptyPair())
    ;
  }

  return emptyPair();
}

// to get a1 only

students.stream()
  // Scala-ers (and other functional programming people) usually recommend
  // flatMap to solve life's problems.
  // (Except world peace. World peace is hard.)
  .flatMap(
    // for (Person student1 : students)
    student1 -> students.stream()
      // for (Person student2 : students)
      // if (!student1.equals(student2))
      .filter(student2 -> !student1.equals(student2))
      // if (student1.sameAgeAs(student2))
      .filter(student2 -> student1.sameAgeAs(student2))
      // or .filter(student1::sameAgeAs)
  )
  .findFirst()

// to get a1 and a2 (assuming the method makePair(Student, Student) exists)
// (makePair may return an array, a List, a Set, a Map.Entry, etc.)

students.stream()
  // Scala-ers (and other functional programming people) usually recommend
  // flatMap to solve life's problems.
  // (Except world peace. World peace is hard.)
  .flatMap(
    // for (Person student1 : students)
    student1 -> students.stream()
      // for (Person student2 : students)
      // if (!student1.equals(student2))
      .filter(student2 -> !student1.equals(student2))
      // if (student1.sameAgeAs(student2))
      .filter(student2 -> student1.sameAgeAs(student2))
      // or .filter(student1::sameAgeAs)
      .map(student2 -> makePair(student1, student2))
  )
  .findFirst()

Upvotes: 3

Related Questions