CODEWITHSUNDEEP
javalistalgorithmrecursion
Ayibogan
Ayibogan

Reputation: 95

Recursively iterate through nested list

I want to implement a recursive function, which iterates through a sublist of an object within a list and add all of the elements in the sublists into a grand list.

My object is as follows:

List<Task> tasks with a function called .getDependsOn() which returns a List<Task> of which it depends.

From the beginning of a Task, which depends on Task B, which then again depends on Task C and D, I want to recursively iterate through every Task and add them to a big list, which includes EVERY dependent tasks of Task A.

public List<Task> addDependencies(List<Task> tasks) {
  for (Task task: tasks) {
   if (!task.getDependsOn().isEmpty()) {
    tasks.addAll(addDependencies(task.getDependsOn()));
    return tasks;
   } else {
    return tasks;
   }
  }
  return tasks;
}

This is what I tried, but it doesn't work, as it throws an InvocationTargetException. I am trying to solve my issue, try to debug it in my brain for like 2 hours now already, but can't sort it out.

Upvotes: 1

Views: 1376

Answers (2)

samabcde
samabcde

Reputation: 8114

Some problems in your method:

  1. You just return the tasks when task.getDependsOn() is empty, which ignore remaining task dependencies, you should call continue instead.
  2. You didn't make a copy when you call addDependencies(task.getDependsOn()), which create unexpected side effect(changing task.getDependsOn()).

I prefer using Stream with flatMap for this problem, since it will not create side effect, and we don't need to create many copy of List.

public static Stream<Task> flattenDependencies(List<Task> tasks) {
    return tasks.stream().flatMap(task -> {
        Stream<Task> flattened = flattenDependencies(task.getDependsOn());
        return Stream.concat(Stream.of(task), flattened);
    });
}

Full example
Main class

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class FlattenTask {
    public static void main(String[] args) {
        Task a = new Task("a");
        Task b = new Task("b");
        Task c = new Task("c");
        Task d = new Task("d");
        Task e = new Task("e");
        Task f = new Task("f");
        a.setDependsOn(List.of(b, c));
        b.setDependsOn(List.of(d, e));
        List<Task> tasks = List.of(a, f);
        System.out.println(flattenDependencies(tasks).collect(Collectors.toList()).toString());
    }

    public static Stream<Task> flattenDependencies(List<Task> tasks) {
        return tasks.stream().flatMap(task -> {
            Stream<Task> flattened = flattenDependencies(task.getDependsOn());
            return Stream.concat(Stream.of(task), flattened);
        });
    }
}

Task

import java.util.Collections;
import java.util.List;

public class Task {

    private final String code;
    private List<Task> dependsOn = Collections.emptyList();

    public Task(String code) {
        this.code = code;
    }

    public List<Task> getDependsOn() {
        return dependsOn;
    }

    public void setDependsOn(List<Task> dependsOn) {
        this.dependsOn = dependsOn;
    }

    @Override
    public String toString() {
        return code;
    }
}

Upvotes: 2

David Wright
David Wright

Reputation: 161

I think your exception is happening because you're trying to append the list concurrently whilst iterating over it. If I've understood what you're trying to do, maybe something like this would work

public List<Task> addDependencies(List<Task> tasks) {
  List<Task> subTaskList = new ArrayList<Task>;
  for (Task task: tasks) {
   if (!task.getDependsOn().isEmpty())
    subTaskList.addAll(addDependencies(task.getDependsOn()));
  }
  tasks.addAll(subTaskList);
  return tasks;
}

Upvotes: 1

Related Questions