I have data like this:

List<Item> data = [
  Item(id: 'aaa', childIds: ['ccc']),
  Item(id: 'bbb', childIds: ['ccc', 'ddd']),
  Item(id: 'ccc', childIds: ['ggg']),
  Item(id: 'ddd', childIds: ['fff','hhh']),
  Item(id: 'eee', childIds: ['xxx']),
  Item(id: 'fff', childIds: ['ggg']),
  Item(id: 'ggg', childIds: null),
  Item(id: 'hhh', childIds: null),
];

I want to create a field <List>String "parentIds" for each element that uses the recursion function to find it, Ex: Item(id: 'aaa', childIds: ['ccc']) => Item(id: 'ccc', parentIds: ['aaa'])

About recursion function: it will take a list<String> ids and will return a list<String> ids of the final parent

Base condition:

• in each id will look in the data to see if any element has childIds containing it, otherwise keep it and end the loop for that id

A recursive function repeats itself:

• The remaining ids will find the parent of the parent until the item has no parent

Ex: id 'ggg' => ['fff', 'ccc'] => ['ddd', 'aaa', 'bbb'] => ['aaa', 'bbb'] (parentIds: ['aaa', 'bbb']: last parent)

The result that I want to achieve will be like this

List<Item> data = [
  Item(id: 'aaa', childIds: ['ccc'], parentIds: []),
  Item(id: 'bbb', childIds: ['ccc', 'ddd'], parentIds: []),
  Item(id: 'ccc', childIds: ['ggg'], parentIds: ['aaa','bbb']),
  Item(id: 'ddd', childIds: ['fff','hhh'], parentIds: ['bbb']),
  Item(id: 'eee', childIds: ['hhh'], parentIds: []),
  Item(id: 'fff', childIds: ['ggg'], parentIds: ['bbb']),
  Item(id: 'ggg', childIds: null, parentIds: ['aaa','bbb']),
  Item(id: 'hhh', childIds: null, parentIds: ['bbb','eee']),
];

So pls help me, this is my code so far:

class Item {
  Item({this.id, this.childIds, this.parentIds});

  final String id;
  final List<String> childIds;
  List<String> parentIds;

  @override
  String toString() {
    return 'Item{id: $id, childIds: $childIds, parentIds: $parentIds}';
  }
}

List<Item> data = [
  Item(id: 'aaa', childIds: ['ccc']),
  Item(id: 'bbb', childIds: ['ccc', 'ddd']),
  Item(id: 'ccc', childIds: ['ggg']),
  Item(id: 'ddd', childIds: ['fff','hhh']),
  Item(id: 'eee', childIds: ['hhh']),
  Item(id: 'fff', childIds: ['ggg']),
  Item(id: 'ggg', childIds: null),
  Item(id: 'hhh', childIds: null),
];

void main() {
  data.map((e) => e.parentIds = idFindParent(e.id)).toList();
  data.forEach((e) => print(e));
}

List<String> idFindParent(String id) {
  List<Item> itemsHasChild = data.where((e) => e.childIds != null).toList();
  List<Item> parents = itemsHasChild.where((parent) => parent.childIds.contains(id)).toList();
  List<String> parentIds = parents.map((e) => e.id).toSet().toList();

  return findParent1(parentIds);
}


// need to replace with recursive method
List<String> findParent1(List<String> ids) {
  List<String> _ids = [];
  ids.map((id) {
    List<Item> itemsHasChild = data.where((e) => e.childIds != null).toList();
    List<Item> parents =
        itemsHasChild.where((e) => e.childIds.any((childIds) => childIds.contains(id))).toList();
    if (parents.isEmpty) {
      _ids.add(id);
    } else if (parents.isNotEmpty) {
      parents.map((e) => _ids.add(e.id)).toSet().toList();
    }
  }).toList();

  return findParent2(_ids.toSet().toList());
}

List<String> findParent2(List<String> ids) {
  List<String> _ids = [];
  ids.map((id) {
    List<Item> hasSlot = data.where((e) => e.childIds != null).toList();
    List<Item> parents =
    hasSlot.where((e) => e.childIds.any((childIds) => childIds.contains(id))).toList();
    if (parents.isEmpty) {
      _ids.add(id);
    } else if (parents.isNotEmpty) {
      parents.map((e) => _ids.add(e.id)).toSet().toList();
    }
  }).toList();

  return _ids.toSet().toList();
}

CodePudding user response：

It here!!!

class Item {
  Item({required this.id, this.childIds, this.parentIds});

  final String id;
  final List<String>? childIds;
  List<String>? parentIds;

  @override
  String toString() {
    return 'Item{id: $id, childIds: $childIds, parentIds: $parentIds}';
  }
}

List<Item> data = [
  Item(id: 'aaa', childIds: ['ccc']),
  Item(id: 'bbb', childIds: ['ccc', 'ddd']),
  Item(id: 'ccc', childIds: ['ggg']),
  Item(id: 'ddd', childIds: ['fff','hhh']),
  Item(id: 'eee', childIds: ['hhh']),
  Item(id: 'fff', childIds: ['ggg']),
  Item(id: 'ggg', childIds: null),
  Item(id: 'hhh', childIds: null),
];

void main() {
  data.map((e) => e.parentIds = idFindParent(e.id)).toList();
  data.forEach((e) => print(e));
}

List<String> idFindParent(String id) {
  List<Item> itemsHasChild = data.where((e) => e.childIds != null).toList();
  List<Item> parents = itemsHasChild.where((parent) => parent.childIds!.contains(id)).toList();
  List<String> parentIds = parents.map((e) => e.id).toSet().toList();
  return findParent(parentIds,parentIds.length);
}


// need to replace with recursive method
List<String> findParent(List<String> ids,int level) {
  print(ids);
  if(ids.isEmpty || level == 0) return ids;
  List<String> _ids = [];
  ids.map((id) {
    List<Item> itemsHasChild = data.where((e) => e.childIds != null).toList();
    List<Item> parents =
        itemsHasChild.where((e) => e.childIds!.any((childIds) => childIds.contains(id))).toList();
    if (parents.isEmpty) {
      _ids.add(id);
    } else if (parents.isNotEmpty) {
      parents.map((e) => _ids.add(e.id)).toSet().toList();
    }
  }).toList();
  
  return findParent(_ids.toSet().toList(),level-1);
}