Flatten a nested N-Level nested object in java

Question

I have a java class

class Example{
   String field1;
   String field2;
   List<Example> subExamples;    
}

In the above scenario, Example is having subExamples which is again a list of Examples. This nesting can be n-levels. What I want to achieve is to have a list of Examples, i.e to flatten the above object and collect all the Examples into a final list (collecting all n-level examples). One obvious way is recursion. is there any way in Java I can achieve it more efficiently. I tried some java 8 concepts but they're not fitting into the requirement.

`flatMap` with recursion. see also [this](https://stackoverflow.com/questions/32656888/recursive-use-of-stream-flatmap) — Eugene, Mar 18 '19 at 10:40
@Flown interesting, but I fail to see how without recursion that would be possible. may be provide an answer? — Eugene, Mar 18 '19 at 10:52
@Eugene see my answer it is an implementation of breadth-first search (can also be done in a depth-first search manner). — Flown, Mar 18 '19 at 12:38

score 2 · Answer 1 · answered Mar 18 '19 at 10:51

2

For example:

private static Stream<Example> flat(Example example) {
    return Stream.concat(Stream.of(example),
                         example.getSubExamples().stream().flatMap(Sandbox::flat));
}

where Sandbox is the class where flat method is defined.

answered Mar 18 '19 at 10:51

Eugene

117,005
15
201
306

Hi @Eugene using parallelStream() can improve efficiency here, right? – codeluv Mar 18 '19 at 11:12
1

@codeluv if you have *lots and lots* of elements, _may be_, but I doubt it. – Eugene Mar 18 '19 at 11:13

score 2 · Answer 2 · answered Mar 18 '19 at 10:54

2

An simple method you could use:

static Stream<Example> flatten(Example ex) {
    if (ex.getSubExamples() == null || ex.getSubExamples().isEmpty()) {
        return Stream.of(ex);
    }

    return Stream.concat(Stream.of(ex), 
                ex.getSubExamples().stream().flatMap(Main::flatten));
}

Which you can the use as

List<Example> flattened = examples.stream()
        .flatMap(Main::flatten) //change class name
        .collect(Collectors.toList());

answered Mar 18 '19 at 10:54

ernest_k

44,416
5
53
99

2

Since developers should never let `List` properties become `null` and empty lists are handled correctly by the stream anyway, the `if` statement is obsolete. – Holger Mar 18 '19 at 12:31

score 1 · Accepted Answer · answered Mar 18 '19 at 12:37

This could be done in a non-recursive manner:

private Collection<Example> flatten(Example example) {
  Queue<Example> work = new ArrayDeque<>();
  if (example != null) {
    work.offer(example);
  }
  Collection<Example> flattened = new ArrayList<>();
  while(!work.isEmpty()) {
    Example cur = work.poll();
    flattened.add(cur);
    cur.subExamples.forEach(work::offer);
  }
  return flattened;
}

Flatten a nested N-Level nested object in java

3 Answers3