Dart: How to sort the lists into the object tree-CodePudding

I have an array with a bunch of objects, where there are parentId and id parameters, how do I make a tree of nested objects, sort so that the first object is an object without parentId, and the rest are nested in it in the children field.

For example:

{
"id": 1,
"parentId": null,
"children": [
    {
      "id": 2,
      "parentId": 1,
      "children": [
        "id": 3,
        "parentId": 2,
        "children": [...]
      ] ...
    }
  ]
}

https://dartpad.dev/?id=799b87806e56d036ba0dac7c9bebcbb2

CodePudding user response：

I came up with an idea, I can't really check if it works right now, but if it doesn't please let me know so we can sort out why together, recursion problems tend to be hard to think about:


void main() {
  Object obj = getObjectChildren(objects).first;
}

List<Object> getObjectChildren(List<Object1> items, [int? currentId]) {
  // get current objects
  List<Object> objects = items
      .where((obj) => obj.parentId == currentId)
      .map((v) => Object.fromObject1(v))
      .toList();

  for (int i = 0; i < objects.length; i  ) {
    // get object's children, recursively
    var children = getObjectChildren(items, objects[i].id);

    // set parent
    for (int j = 0; j < children.length; j  ) {
      children[j].parent = objects[i];
    }

    // set children
    objects[i].children = children;
  }
  return objects;
}

I also added a constructor to your Object class, it looks like this:

  Object.fromObject1(Object1 obj)
      : id = obj.id,
        parent = null,
        parentId = obj.parentId,
        children = [];

CodePudding user response：

I worked on your dartpad, I couldn't find any issues, but if you do, please let me know! The resulting code looks like this:

List<Object1> objects = [
  Object1(id: 1, parentId: null),
  Object1(id: 2, parentId: 1),
  Object1(id: 3, parentId: 2),
  Object1(id: 4, parentId: 2),
  Object1(id: 5, parentId: 2),
  Object1(id: 6, parentId: 1),
  Object1(id: 7, parentId: 6),
  Object1(id: 8, parentId: 6),
  Object1(id: 9, parentId: 7),
  Object1(id: 10, parentId: 9),
  Object1(id: 11, parentId: 9),
  Object1(id: 12, parentId: 10),
];

class Object1 {
  Object1({
    required this.id,
    this.parent,
    this.parentId,
  });

  Object1? parent;
  final List<Object1> children = [];

  int id;
  int? parentId;
  
  void addChildren(List<Object1> list) {
    final newList = getChildren(list, id);
    for (final object in newList) {
      object.parent = this;
      object.addChildren(list);
      children.add(object);
    }
  }
  
  @override
  String toString() {
    return 'Object1('
      'id: $id,\n'
      'parentId: $parentId,\n'
      'children: ${children.toString()}'
      ')';
  }
}

void main() {
  Object1? main;
  for (final object in objects) {
    if (object.parentId == null) {
      main = object;
      break;
    }
  }
  if (main != null) {
    main.addChildren(objects);
    print(main.toString());
  }
}

List<Object1> getChildren(List<Object1> list, int id) {
  final List<Object1> newList = [];
  for (final object in list) {
    if (object.parentId == id) {
      newList.add(object);
    }
  }
  return newList;
}